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 --]
next prev parent 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 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$(echo .)com \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=greg@xiph$(echo .)org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
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