1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
|
Return-Path: <laolu32@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id BD8E688A
for <bitcoin-dev@lists.linuxfoundation.org>;
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 <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 9 Jun 2017 04:47:31 +0000 (UTC)
Received: by mail-yw0-f182.google.com with SMTP id v7so1439327ywc.2
for <bitcoin-dev@lists.linuxfoundation.org>;
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: <CAO3Pvs8ccTkgrecJG6KFbBW+9moHF-FTU+4qNfayeE3hM9uRrg@mail.gmail.com>
<CAAS2fgRVTfsfXAyHBoBaCqAXpK+=QCFy-Lx3zH=d3tPteu7GcA@mail.gmail.com>
<CAO3Pvs-_0scKqFnT-fE7aDd7gkw+epJkTcQ-jAYZwENsWt8b=A@mail.gmail.com>
In-Reply-To: <CAO3Pvs-_0scKqFnT-fE7aDd7gkw+epJkTcQ-jAYZwENsWt8b=A@mail.gmail.com>
From: Olaoluwa Osuntokun <laolu32@gmail.com>
Date: Fri, 09 Jun 2017 04:47:19 +0000
Message-ID: <CAO3Pvs-P2WcNRKGfH_FA7DFNRZOi5H+szO58wBLKA8gVh7mxZQ@mail.gmail.com>
To: Gregory Maxwell <greg@xiph.org>
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
<bitcoin-dev@lists.linuxfoundation.org>
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 <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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 <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.
>>
>
--94eb2c0b927cb69e8405517faa23
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div>> Correct me if I'm wrong, but from my interpr=
etation we can't use that</div><div>> method as described as we need=
to output 64-bit integers rather than</div><div>> 32-bit integers.=C2=
=A0</div><div><br></div><div>Had a chat with gmax off-list and came to the =
realization that the method</div><div>_should_ indeed generalize to our cas=
e of outputting 64-bit integers.</div><div>We'll need to do a bit of bi=
t twiddling to make it work properly. I'll</div><div>modify our impleme=
ntation and report back with some basic benchmarks.</div><div><br></div><di=
v>-- Laolu</div><div><br></div><br><div class=3D"gmail_quote"><div dir=3D"l=
tr">On Thu, Jun 8, 2017 at 8:42 PM Olaoluwa Osuntokun <<a href=3D"mailto=
:laolu32@gmail.com">laolu32@gmail.com</a>> wrote:<br></div><blockquote c=
lass=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;=
padding-left:1ex"><div dir=3D"ltr"><div>Gregory wrote:</div><div>> I see=
the inner loop of construction and lookup are free of</div><div>> non-c=
onstant divmod. This will result in implementations being</div><div>> ne=
edlessly slow=C2=A0</div><div><br></div></div><div dir=3D"ltr"><div>Ahh, si=
pa brought this up other day, but I thought he was referring to the</div><d=
iv>coding loop (which uses a power of 2 divisor/modulus), not the</div><div=
>siphash-then-reduce loop.</div></div><div dir=3D"ltr"><div><br></div><div>=
> I believe this can be fixed by using this approach</div><div>> <a h=
ref=3D"http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-re=
duction/" target=3D"_blank">http://lemire.me/blog/2016/06/27/a-fast-alterna=
tive-to-the-modulo-reduction/</a></div><div>> which has the same non-uni=
formity as mod but needs only a multiply and</div><div>> shift.</div><di=
v><br></div></div><div dir=3D"ltr"><div>Very cool, I wasn't aware of th=
e existence of such a mapping.</div><div><br></div><div>Correct me if I'=
;m wrong, but from my interpretation we can't use that</div><div>method=
as described as we need to output 64-bit integers rather than</div><div>32=
-bit integers. A range of 32-bits would be constrain the number of items</d=
iv><div>we could encode to be ~4096 to ensure that we don't overflow wi=
th fp</div><div>values such as 20 (which we currently use in our code).</di=
v><div><br></div><div>If filter commitment are to be considered for a soft-=
fork in the future,</div><div>then we should definitely optimize the constr=
uction of the filters as much</div><div>as possible! I'll look into tha=
t paper you referenced to get a feel for</div><div>just how complex the opt=
imization would be.</div></div><div dir=3D"ltr"><div><br></div><div>> Sh=
ouldn't all cases in your spec where you have N=3Dtransactions be</div>=
<div>> n=3Dindexed-outputs? Otherwise, I think your golomb parameter and=
false</div><div>> positive rate are wrong.</div><div><br></div></div><d=
iv dir=3D"ltr"><div>Yep! Nice catch. Our code is correct, but mistake in th=
e spec was an</div><div>oversight on my part. I've pushed a commit[1] t=
o the bip repo referenced</div><div>in the OP to fix this error.</div><div>=
<br></div><div>I've also pushed another commit to explicitly take advan=
tage of the fact</div><div>that P is a power-of-two within the coding loop =
[2].</div><div><br></div><div>-- Laolu</div><div><br></div><div>[1]: <a hre=
f=3D"https://github.com/Roasbeef/bips/commit/bc5c6d6797f3df1c4a44213963ba12=
e72122163d" target=3D"_blank">https://github.com/Roasbeef/bips/commit/bc5c6=
d6797f3df1c4a44213963ba12e72122163d</a></div><div>[2]: <a href=3D"https://g=
ithub.com/Roasbeef/bips/commit/578a4e3aa8ec04524c83bfc5d14be1b2660e7f7a" ta=
rget=3D"_blank">https://github.com/Roasbeef/bips/commit/578a4e3aa8ec04524c8=
3bfc5d14be1b2660e7f7a</a></div></div><div dir=3D"ltr"><div><br></div><br><d=
iv class=3D"gmail_quote"><div dir=3D"ltr">On Wed, Jun 7, 2017 at 2:41 PM Gr=
egory Maxwell <<a href=3D"mailto:greg@xiph.org" target=3D"_blank">greg@x=
iph.org</a>> wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"=
margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On Thu, Jun =
1, 2017 at 7:01 PM, Olaoluwa Osuntokun via bitcoin-dev<br>
<<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_bla=
nk">bitcoin-dev@lists.linuxfoundation.org</a>> wrote:<br>
> Hi y'all,<br>
><br>
> Alex Akselrod and I would like to propose a new light client BIP for<b=
r>
> consideration:<br>
>=C2=A0 =C2=A0 * <a href=3D"https://github.com/Roasbeef/bips/blob/master=
/gcs_light_client.mediawiki" rel=3D"noreferrer" target=3D"_blank">https://g=
ithub.com/Roasbeef/bips/blob/master/gcs_light_client.mediawiki</a><br>
<br>
I see the inner loop of construction and lookup are free of<br>
non-constant divmod. This will result in implementations being<br>
needlessly slow (especially on arm, but even on modern x86_64 a<br>
division is a 90 cycle-ish affair.)<br>
<br>
I believe this can be fixed by using this approach<br>
<a href=3D"http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modul=
o-reduction/" rel=3D"noreferrer" target=3D"_blank">http://lemire.me/blog/20=
16/06/27/a-fast-alternative-to-the-modulo-reduction/</a><br>
=C2=A0 =C2=A0which has the same non-uniformity as mod but needs only a mult=
iply<br>
and shift.<br>
<br>
Otherwise fast implementations will have to implement the code to<br>
compute bit twiddling hack exact division code, which is kind of<br>
complicated. (e.g. via the technique in "{N}-bit Unsigned Division via=
<br>
{N}-bit Multiply-Add" by Arch D. Robison).<br>
<br>
Shouldn't all cases in your spec where you have N=3Dtransactions be<br>
n=3Dindexed-outputs? Otherwise, I think your golomb parameter and false<br>
positive rate are wrong.<br>
</blockquote></div></div></blockquote></div></div>
--94eb2c0b927cb69e8405517faa23--
|
