From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id BD8E688A for ; Fri, 9 Jun 2017 04:47:34 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-yw0-f182.google.com (mail-yw0-f182.google.com [209.85.161.182]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 1E89EEB for ; Fri, 9 Jun 2017 04:47:31 +0000 (UTC) Received: by mail-yw0-f182.google.com with SMTP id v7so1439327ywc.2 for ; Thu, 08 Jun 2017 21:47:31 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=KwrardISVVybESKTG5MYWJIWyoP+R3MxQyyDlKAK2tE=; b=YIrc/Om91QV2YwFR5xQuP/g4mdNvj789Q/hchygBY7YGokPlZxx1GwXAb6trDHdIeJ 1ea+q3/ek1pY8e47Pt1oHjXpQcvT+YDMnnR9b2J3W32f6CZCDinJEUvSOUjlFSLQMU/M rVBOGpVSWefdghPFvWuH4xPm7V++a6ybuzUzF/NzeZvvngMCMybwxUYTiffWobRo3aIr YitSqbRPYC8mEnXiokLkJeEdHsuYII+B58FHAjXKsWD0tdwjGyKVLb+t339ZltzEwfuE OzO6evnrXpOq2l6GDbEm74uLvLI6zJ1xChtlH+/a6u6sq3MaC6BomOo4PpbUX3PFYnc1 h+4g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=KwrardISVVybESKTG5MYWJIWyoP+R3MxQyyDlKAK2tE=; b=VAyLU23I83xqeZK49UxZAWAqphoNA4HAsk6YmcGoPZVTQuVcI119a7zQpaer8sDVuR OMb3eR5Dq4NkB8lZ+gxBErtam3mwNGCQ7w8oMi1LBGqxNWTKQdg3XP3J8Sulifke8ekx BVb56cM5GGJ6If4FVQbud6MnuzWBN+YEgTvEf3iLNbHl4vKGta0a26z0V/jQU7wCOoVT I2QvJr6tWFjA89z5rVKr5mPmQT3d6IQ5SJ3Bsk3r+oyCRiHi18Kb6rUK+NsYpk6XsjMN q+mdqbbH/G3GFTwvux0Qz+aG/ewMyiH53JOiin+E7n7wMkdkpjXgqWz62VhyBzWAXX6L sx7g== X-Gm-Message-State: AODbwcBdx05ABiHhC+HNiRet6aixBYCURulqXaseUsOFoNgWi9C5RBXe KyjNMnMf4pycPqV9Afc5CKKUXjd28g== X-Received: by 10.129.155.137 with SMTP id s131mr629930ywg.124.1496983650343; Thu, 08 Jun 2017 21:47:30 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Olaoluwa Osuntokun Date: Fri, 09 Jun 2017 04:47:19 +0000 Message-ID: To: Gregory Maxwell Content-Type: multipart/alternative; boundary="94eb2c0b927cb69e8405517faa23" X-Spam-Status: No, score=-1.7 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_ENVFROM_END_DIGIT,FREEMAIL_FROM, HTML_MESSAGE,RCVD_IN_DNSWL_NONE autolearn=no version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Cc: Arnoud Kouwenhoven - Pukaki Corp via bitcoin-dev Subject: Re: [bitcoin-dev] BIP Proposal: Compact Client Side Filtering for Light Clients X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 09 Jun 2017 04:47:34 -0000 --94eb2c0b927cb69e8405517faa23 Content-Type: text/plain; charset="UTF-8" > 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 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 wrote: > >> On Thu, Jun 1, 2017 at 7:01 PM, Olaoluwa Osuntokun via bitcoin-dev >> 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. >> > --94eb2c0b927cb69e8405517faa23 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
> Correct me if I'm wrong, but from my interpr= etation we can't use that
> method as described as we need= to output 64-bit integers rather than
> 32-bit integers.=C2= =A0

Had a chat with gmax off-list and came to the = realization that the method
_should_ indeed generalize to our cas= e of outputting 64-bit integers.
We'll need to do a bit of bi= t twiddling to make it work properly. I'll
modify our impleme= ntation 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-c= onstant divmod. This will result in implementations being
> ne= edlessly slow=C2=A0

Ahh, si= pa 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
> which has the same non-uni= formity as mod but needs only a multiply and
> shift.

Very cool, I wasn't aware of th= e 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 wi= th 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 constr= uction of the filters as much
as possible! I'll look into tha= t paper you referenced to get a feel for
just how complex the opt= imization would be.

> Sh= ouldn't all cases in your spec where you have N=3Dtransactions be
=
> n=3Dindexed-outputs? Otherwise, I think your golomb parameter and= false
> positive rate are wrong.

Yep! Nice catch. Our code is correct, but mistake in th= e spec was an
oversight on my part. I've pushed a commit[1] t= o the bip repo referenced
in the OP to fix this error.
=
I've also pushed another commit to explicitly take advan= tage of the fact
that P is a power-of-two within the coding loop = [2].

-- Laolu



On Wed, Jun 7, 2017 at 2:41 PM Gr= egory Maxwell <greg@x= iph.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:
>=C2=A0 =C2=A0 * https://g= ithub.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/20= 16/06/27/a-fast-alternative-to-the-modulo-reduction/
=C2=A0 =C2=A0which has the same non-uniformity as mod but needs only a mult= iply
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=3Dtransactions be
n=3Dindexed-outputs? Otherwise, I think your golomb parameter and false
positive rate are wrong.
--94eb2c0b927cb69e8405517faa23--