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
|
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 9AACE98C
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 9 Jun 2017 03:43:14 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-yw0-f172.google.com (mail-yw0-f172.google.com
[209.85.161.172])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id C1F4CFD
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 9 Jun 2017 03:43:10 +0000 (UTC)
Received: by mail-yw0-f172.google.com with SMTP id e142so9946064ywa.1
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 08 Jun 2017 20:43:10 -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=74umXgYXMAGH5ztwaUB6yNo0TXfvEPPIaMW0UpAScRc=;
b=IiyKNQF4s0q05bupPPyQ0nIR3fDETim+3HRV0/HU6bW4ZYnPxaD0OfYeP2BiXd6UYd
9RKSSgTOr7MzjEiKwspjNacXpxgXXo4eJhu0B8mW7Rtg8pMaZctWc/bFtxviR8od5nyT
UYMABMrdCb/RA0Lb0+moQ9l7daFYlisV2FyhaQhNU3C2SAig7TEWS6REfAJflty9SQtq
T3FGgiTkvWw4nSrqs/cPYkWoOFWrjVO2/jnf2UF4cxc2xinrZMc9NKeh2CUEQH851K3i
qds8WBsqcAHHchEy3+HMUplmtKSCqnqqMyKkrhzPEwVs37t7eB/X01P9akji9PNmhhX6
fxog==
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=74umXgYXMAGH5ztwaUB6yNo0TXfvEPPIaMW0UpAScRc=;
b=un4TtlsMH8Nh9p3W5JaCtHm+jsAodt3FZvxQ+dE3QE8KISHdoxnp4I45x5Ot0BbHsD
lm/pWanrKm4p00tFCpKxQK1V8Sy+Nly56yfzgjallaZFkgQKoL0gKhYWdvEX1saUO2Y3
LKSm9scYyJQldTZtWR220hunP5i+Jv3SGiP3CQWpbw10Lv/lIz6YCkT6egsKF/YZ4V6D
NRAVFqsPSocmOt6Jxl4UizD6wRMup6A/qNRrMC+ftSHLTY2uK6JoC/CF2Dj+69aDifvZ
yU4w/zC6BobmFYRS8qP2QTZfRRYCvpsXuunkDH4nnJgDPqafu+2em4d6uxZ+/f8SGkk8
a86A==
X-Gm-Message-State: AODbwcBLtVqVaO7GE2N+UaHq/Ociiz9QWBSYWdzfX5N4LWyIS7Pf0/Be
66r8mEZoPROTtdUVLbFvyGpx+xioVkrn
X-Received: by 10.129.155.137 with SMTP id s131mr521837ywg.124.1496979789894;
Thu, 08 Jun 2017 20:43:09 -0700 (PDT)
MIME-Version: 1.0
References: <CAO3Pvs8ccTkgrecJG6KFbBW+9moHF-FTU+4qNfayeE3hM9uRrg@mail.gmail.com>
<CAAS2fgRVTfsfXAyHBoBaCqAXpK+=QCFy-Lx3zH=d3tPteu7GcA@mail.gmail.com>
In-Reply-To: <CAAS2fgRVTfsfXAyHBoBaCqAXpK+=QCFy-Lx3zH=d3tPteu7GcA@mail.gmail.com>
From: Olaoluwa Osuntokun <laolu32@gmail.com>
Date: Fri, 09 Jun 2017 03:42:58 +0000
Message-ID: <CAO3Pvs-_0scKqFnT-fE7aDd7gkw+epJkTcQ-jAYZwENsWt8b=A@mail.gmail.com>
To: Gregory Maxwell <greg@xiph.org>
Content-Type: multipart/alternative; boundary="94eb2c0b927c9cdc6b05517ec449"
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 03:43:14 -0000
--94eb2c0b927c9cdc6b05517ec449
Content-Type: text/plain; charset="UTF-8"
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.
>
--94eb2c0b927c9cdc6b05517ec449
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div>Gregory wrote:</div><div>> I see the inner loop of=
construction and lookup are free of</div><div>> non-constant divmod. Th=
is will result in implementations being</div><div>> needlessly slow=C2=
=A0</div><div><br></div><div>Ahh, sipa brought this up other day, but I tho=
ught he was referring to the</div><div>coding loop (which uses a power of 2=
divisor/modulus), not the</div><div>siphash-then-reduce loop.</div><div><b=
r></div><div>> I believe this can be fixed by using this approach</div><=
div>> <a href=3D"http://lemire.me/blog/2016/06/27/a-fast-alternative-to-=
the-modulo-reduction/">http://lemire.me/blog/2016/06/27/a-fast-alternative-=
to-the-modulo-reduction/</a></div><div>> which has the same non-uniformi=
ty as mod but needs only a multiply and</div><div>> shift.</div><div><br=
></div><div>Very cool, I wasn't aware of the existence of such a mappin=
g.</div><div><br></div><div>Correct me if I'm wrong, but from my interp=
retation 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</div><div>we could encode to b=
e ~4096 to ensure that we don't overflow with fp</div><div>values such =
as 20 (which we currently use in our code).</div><div><br></div><div>If fil=
ter commitment are to be considered for a soft-fork in the future,</div><di=
v>then we should definitely optimize the construction of the filters as muc=
h</div><div>as possible! I'll look into that paper you referenced to ge=
t a feel for</div><div>just how complex the optimization would be.</div><di=
v><br></div><div>> Shouldn't all cases in your spec where you have N=
=3Dtransactions be</div><div>> n=3Dindexed-outputs? Otherwise, I think y=
our golomb parameter and false</div><div>> positive rate are wrong.</div=
><div><br></div><div>Yep! Nice catch. Our code is correct, but mistake in t=
he spec was an</div><div>oversight on my part. I've pushed a commit[1] =
to 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 adva=
ntage 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 hr=
ef=3D"https://github.com/Roasbeef/bips/commit/bc5c6d6797f3df1c4a44213963ba1=
2e72122163d">https://github.com/Roasbeef/bips/commit/bc5c6d6797f3df1c4a4421=
3963ba12e72122163d</a></div><div>[2]: <a href=3D"https://github.com/Roasbee=
f/bips/commit/578a4e3aa8ec04524c83bfc5d14be1b2660e7f7a">https://github.com/=
Roasbeef/bips/commit/578a4e3aa8ec04524c83bfc5d14be1b2660e7f7a</a></div><div=
><br></div><br><div class=3D"gmail_quote"><div dir=3D"ltr">On Wed, Jun 7, 2=
017 at 2:41 PM Gregory Maxwell <<a href=3D"mailto:greg@xiph.org">greg@xi=
ph.org</a>> wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"m=
argin: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>
--94eb2c0b927c9cdc6b05517ec449--
|
