public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Olaoluwa Osuntokun <laolu32@gmail.com>
To: Gregory Maxwell <greg@xiph.org>
Cc: Arnoud Kouwenhoven - Pukaki Corp via bitcoin-dev
	<bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] BIP Proposal: Compact Client Side Filtering for Light Clients
Date: Fri, 09 Jun 2017 04:47:19 +0000	[thread overview]
Message-ID: <CAO3Pvs-P2WcNRKGfH_FA7DFNRZOi5H+szO58wBLKA8gVh7mxZQ@mail.gmail.com> (raw)
In-Reply-To: <CAO3Pvs-_0scKqFnT-fE7aDd7gkw+epJkTcQ-jAYZwENsWt8b=A@mail.gmail.com>

[-- Attachment #1: Type: text/plain, Size: 3776 bytes --]

> Correct me if I'm wrong, but from my interpretation we can't use that
> method as described as we need to output 64-bit integers rather than
> 32-bit integers.

Had a chat with gmax off-list and came to the realization that the method
_should_ indeed generalize to our case of outputting 64-bit integers.
We'll need to do a bit of bit twiddling to make it work properly. I'll
modify our implementation and report back with some basic benchmarks.

-- Laolu


On Thu, Jun 8, 2017 at 8:42 PM Olaoluwa Osuntokun <laolu32@gmail.com> wrote:

> Gregory wrote:
> > I see the inner loop of construction and lookup are free of
> > non-constant divmod. This will result in implementations being
> > needlessly slow
>
> Ahh, sipa brought this up other day, but I thought he was referring to the
> coding loop (which uses a power of 2 divisor/modulus), not the
> siphash-then-reduce loop.
>
> > I believe this can be fixed by using this approach
> >
> http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
> > which has the same non-uniformity as mod but needs only a multiply and
> > shift.
>
> Very cool, I wasn't aware of the existence of such a mapping.
>
> Correct me if I'm wrong, but from my interpretation we can't use that
> method as described as we need to output 64-bit integers rather than
> 32-bit integers. A range of 32-bits would be constrain the number of items
> we could encode to be ~4096 to ensure that we don't overflow with fp
> values such as 20 (which we currently use in our code).
>
> If filter commitment are to be considered for a soft-fork in the future,
> then we should definitely optimize the construction of the filters as much
> as possible! I'll look into that paper you referenced to get a feel for
> just how complex the optimization would be.
>
> > Shouldn't all cases in your spec where you have N=transactions be
> > n=indexed-outputs? Otherwise, I think your golomb parameter and false
> > positive rate are wrong.
>
> Yep! Nice catch. Our code is correct, but mistake in the spec was an
> oversight on my part. I've pushed a commit[1] to the bip repo referenced
> in the OP to fix this error.
>
> I've also pushed another commit to explicitly take advantage of the fact
> that P is a power-of-two within the coding loop [2].
>
> -- Laolu
>
> [1]:
> https://github.com/Roasbeef/bips/commit/bc5c6d6797f3df1c4a44213963ba12e72122163d
> [2]:
> https://github.com/Roasbeef/bips/commit/578a4e3aa8ec04524c83bfc5d14be1b2660e7f7a
>
>
> On Wed, Jun 7, 2017 at 2:41 PM Gregory Maxwell <greg@xiph.org> wrote:
>
>> On Thu, Jun 1, 2017 at 7:01 PM, Olaoluwa Osuntokun via bitcoin-dev
>> <bitcoin-dev@lists.linuxfoundation.org> wrote:
>> > Hi y'all,
>> >
>> > Alex Akselrod and I would like to propose a new light client BIP for
>> > consideration:
>> >    *
>> https://github.com/Roasbeef/bips/blob/master/gcs_light_client.mediawiki
>>
>> I see the inner loop of construction and lookup are free of
>> non-constant divmod. This will result in implementations being
>> needlessly slow (especially on arm, but even on modern x86_64 a
>> division is a 90 cycle-ish affair.)
>>
>> I believe this can be fixed by using this approach
>>
>> http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
>>    which has the same non-uniformity as mod but needs only a multiply
>> and shift.
>>
>> Otherwise fast implementations will have to implement the code to
>> compute bit twiddling hack exact division code, which is kind of
>> complicated. (e.g. via the technique in "{N}-bit Unsigned Division via
>> {N}-bit Multiply-Add" by Arch D. Robison).
>>
>> Shouldn't all cases in your spec where you have N=transactions be
>> n=indexed-outputs? Otherwise, I think your golomb parameter and false
>> positive rate are wrong.
>>
>

[-- Attachment #2: Type: text/html, Size: 5729 bytes --]

  reply	other threads:[~2017-06-09  4:47 UTC|newest]

Thread overview: 39+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2017-06-01 19:01 [bitcoin-dev] BIP Proposal: Compact Client Side Filtering for Light Clients Olaoluwa Osuntokun
2017-06-01 21:00 ` Eric Lombrozo
2017-06-01 21:33 ` Matt Corallo
2017-06-01 22:10   ` Olaoluwa Osuntokun
2017-06-02  2:15     ` Chris
2017-06-02  2:28       ` Gregory Maxwell
2017-06-02  3:35         ` Alex Akselrod
2017-06-02 16:07         ` Chris Pacia
2017-06-02  4:49 ` Olaoluwa Osuntokun
2017-06-09  3:59   ` Olaoluwa Osuntokun
2017-11-09 23:44     ` Olaoluwa Osuntokun
2017-06-02  6:00 ` Karl Johan Alm
     [not found]   ` <CAE0pnx+RRAP269VeWAcxKbrcS9qX4LS8_6nY_js8X5NtQ22t_A@mail.gmail.com>
     [not found]     ` <CAE0pnxLKYnwHnktTqW949s1AA9uK=6WnVYWmRoau8B1SszzYEg@mail.gmail.com>
     [not found]       ` <CAE0pnxJxHYQ4+2pt3tt=1WZ0-K0vDxGB4KBXY+R=WfktMmATwA@mail.gmail.com>
2017-06-02 17:55         ` Alex Akselrod
2017-06-05  2:06           ` Karl Johan Alm
2017-06-09  3:03             ` Olaoluwa Osuntokun
2017-06-07 21:41 ` Gregory Maxwell
2017-06-09  3:42   ` Olaoluwa Osuntokun
2017-06-09  4:47     ` Olaoluwa Osuntokun [this message]
2017-06-08  9:50 ` Tomas
2017-06-09  3:50   ` Olaoluwa Osuntokun
2017-06-09  8:26     ` Tomas
2017-06-19 11:58 ` Andreas Schildbach
2017-06-19 12:26   ` bfd
2017-06-19 15:15     ` Tom Zander
2017-06-19 15:49       ` Jonas Schnelli
2017-06-19 15:59         ` Andreas Schildbach
2017-06-19 16:22           ` Jonas Schnelli
2017-06-19 16:36             ` adiabat
2017-06-19 20:49               ` Andreas Schildbach
2017-06-20  7:03             ` Eric Voskuil
2017-06-19 16:07         ` Tom Zander
2017-06-19 16:30           ` Jonas Schnelli
2017-06-19 16:38             ` Tom Zander
2017-06-19 15:43     ` Andreas Schildbach
2017-06-19 16:10       ` Jonas Schnelli
2017-06-19 22:41     ` Gregory Maxwell
2017-06-20  9:52       ` Tom Zander
2017-06-20 13:08         ` bfd
2017-06-20 17:20           ` Adam Back

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=CAO3Pvs-P2WcNRKGfH_FA7DFNRZOi5H+szO58wBLKA8gVh7mxZQ@mail.gmail.com \
    --to=laolu32@gmail.com \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    --cc=greg@xiph.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox