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
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
|
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 45FA2E4D
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 19 May 2018 02:51:19 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm0-f65.google.com (mail-wm0-f65.google.com [74.125.82.65])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 176A5B0
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 19 May 2018 02:51:18 +0000 (UTC)
Received: by mail-wm0-f65.google.com with SMTP id f8-v6so18229741wmc.4
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 18 May 2018 19:51:17 -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;
bh=EP/poyr6jJxFayL3QKvwckUEb1mAVzJksnXmgtdUly0=;
b=rgUWRl0LRhssyIG/hd6WuDkGEuAoXS3YcTUm5kgLESKm3hFf9yNa11onnvgvclIkdA
YvuI5h6zQBPhfoZvvLpEo5J/8ZIgt/2DfSed8YzBwDLMqxMQTmaAeRljoQsykV1yX7XA
S+pXA/jdP8Xnbj78zNd4elo/LsVb+4XBtO7ik8KAKbCtJn0MZy3D8ODN5EXj50KzmYIU
mnuOT/J/+SqwTauztVgyzx/POw3jmJt3lz9kly3ogjnVtmAkbrlIz5BD+zUDRh0IMnEm
iRoJX/8e2I+/tMIY2AXl5+yNszq1bSeCpl3Ncj3ukXXtGdJ4NA7yOe1tZ1xnC4cRaLJ6
UFgQ==
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;
bh=EP/poyr6jJxFayL3QKvwckUEb1mAVzJksnXmgtdUly0=;
b=IzniSCW8bwdsb8jIsdT+yyM2JXMZun7KlzFVdj1My05yRqEJAn4yq8bCA65eEVT39T
rdvXoLVKsvnyHceQBwjAcYWs16kNIUPVIoYE3GKofp0SM0H117bfsTOdMhh36FjRtdhS
1G+AR+AGnZ8DDMXrjK7RPrwJR5Ixct1h1hA6iUvyMRsU1cNO5Ww8bUrDebW4ses3U5QG
umfemiyhMAAmfgBf+8wKG1HhWkUMw11Xo2ruHmxJMFEa/uPBrCXrRX5RvJy9JxKiy4Q7
aYBeaU8f+ZANHKs/w/rK1Dg/N43vIjtVwbeifPfAoW8mUt/FI4tkPlbO/T49l3DNUZdZ
wnWQ==
X-Gm-Message-State: ALKqPwdNELMkFdAbEKXWQQZU7lDb4A56ZIVhun0r3mgsatS9Z+rjyMEm
lbijx8gAcI5/ozR45EMeYKZ65O8d1bin+gFX0o7w9g==
X-Google-Smtp-Source: AB8JxZporD0M7ei6tH8kJI4JJH66mWSzGcrLA1bxTEFCQj4a+4BoPY/rCGQfGcuzIUcjksm/7DijYK1nntEjP5Jl2qY=
X-Received: by 2002:aa7:c2d0:: with SMTP id
m16-v6mr14427761edp.171.1526698276507;
Fri, 18 May 2018 19:51:16 -0700 (PDT)
MIME-Version: 1.0
References: <d43c6082-1b2c-c95b-5144-99ad0021ea6c@mattcorallo.com>
In-Reply-To: <d43c6082-1b2c-c95b-5144-99ad0021ea6c@mattcorallo.com>
From: Olaoluwa Osuntokun <laolu32@gmail.com>
Date: Fri, 18 May 2018 19:51:02 -0700
Message-ID: <CAO3Pvs8t6rNBkdCNBfqH+cyxLftBPCUMB9ZjDuHq--SXGmCvnA@mail.gmail.com>
To: Matt Corallo <lf-lists@mattcorallo.com>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="00000000000073544d056c862419"
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
Subject: Re: [bitcoin-dev] BIP 158 Flexibility and Filter Size
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: Sat, 19 May 2018 02:51:19 -0000
--00000000000073544d056c862419
Content-Type: text/plain; charset="UTF-8"
Matt wrote:
> I believe (1) could be skipped entirely - there is almost no reason why
> you'd not be able to filter for, eg, the set of output scripts in a
> transaction you know about
Depending on the use-case, the txid is more precise than searching for the
output script as it doesn't need to deal with duplicated output scripts. To
my knowledge, lnd is the only major project that currently utilizes BIP
157+158. At this point, we use the txid in the regular filter for
confirmations (channel confirmed, sweep tx confirmed, cltv confirmed, etc).
Switching to use output scripts instead wouldn't be _too_ invasive w.r.t
changes required in the codebase, only the need to deal with output script
duplication could be annoying.
> (2) and (3) may want to be split out - many wallets may wish to just find
> transactions paying to them, as transactions spending from their outputs
> should generally be things they've created.
FWIW, in the "rescan after importing by seed phrase" both are needed in
order to ensure the wallet ends up with the proper output set after the
scan. In lnd we actively use both (2) to detect deposits to the internal
wallet, and (3) to be notified when our channel outputs are spent on-chain
(and also generally when any of our special scripts are spent).
> In general, I'm concerned about the size of the filters making existing
SPV
> clients less willing to adopt BIP 158 instead of the existing bloom filter
> garbage and would like to see a further exploration of ways to split out
> filters to make them less bandwidth intensive.
Agreed that the current filter size may prevent adoption amongst wallets.
However, the other factor that will likely prevent adoption amongst current
BIP-37 mobile wallets is the lack of support for notifying _unconfirmed_
transactions. When we drafted up the protocol last year and asked around,
this was one of the major points of contention amongst existing mobile
wallets that utilize BIP 37.
On the other hand, the two "popular" BIP 37 wallets I'm aware of
(Breadwallet, and Andreas Schildbach's Bitcoin Wallet) have lagged massively
behind the existing set of wallet related protocol upgrades. For example,
neither of them have released versions of their applications that take
advantage of segwit in any manner. Breadwallet has more or less "pivoted"
(they did an ICO and have a token) and instead is prioritizing things like
adding random ICO tokens over catching up with the latest protocol updates.
Based on this behavior, even if the filter sizes were even _more_ bandwidth
efficient that BIP 37, I don't think they'd adopt the protocol.
> Some further ideas we should probably play with before finalizing moving
> forward is providing filters for certain script templates, eg being able
to
> only get outputs that are segwit version X or other similar ideas.
Why should this block active deployment of BIP 157+158 as is now? As
defined, the protocol already allows future updates to add additional filter
types. Before the filters are committed, each filter type requires a new
filter header. We could move to a single filter header that commits to the
hashes of _all_ filters, but that would mean that a node couldn't serve the
headers unless they had all currently defined features, defeating the
optionality offered.
Additionally, more filters entails more disk utilization for nodes serving
these filters. Nodes have the option to instead create the filters at "query
time", but then this counters the benefit of simply slinging the filters
from disk (or a memory map or w/e). IMO, it's a desirable feature that
serving light clients no longer requires active CPU+I/O and instead just
passive I/O (nodes could even write the filters to disk in protocol msg
format).
To get a feel for the current filter sizes, a txid-only filter size, and a
regular filter w/o txid's, I ran some stats on the last 10k blocks:
regular size: 217107653 bytes
regular avg: 21710.7653 bytes
regular median: 22332 bytes
regular max: 61901 bytes
txid-only size: 34518463 bytes
txid-only avg: 3451.8463 bytes
txid-only median: 3258 bytes
txid-only max: 10193 bytes
reg-no-txid size: 182663961 bytes
reg-no-txid avg: 18266.3961 bytes
reg-no-txid median: 19198 bytes
reg-no-txid max: 60172 bytes
So the median regular filter size over the past 10k blocks is 20KB. If we
extract the txid from the regular filter and add a txid-only filter, the
median size of that is 3.2KB. Finally, the median size of a modified regular
filter (no txid) is 19KB.
-- Laolu
On Thu, May 17, 2018 at 8:33 AM Matt Corallo via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:
> BIP 158 currently includes the following in the "basic" filter: 1)
> txids, 2) output scripts, 3) input prevouts.
>
> I believe (1) could be skipped entirely - there is almost no reason why
> you'd not be able to filter for, eg, the set of output scripts in a
> transaction you know about and (2) and (3) may want to be split out -
> many wallets may wish to just find transactions paying to them, as
> transactions spending from their outputs should generally be things
> they've created.
>
> In general, I'm concerned about the size of the filters making existing
> SPV clients less willing to adopt BIP 158 instead of the existing bloom
> filter garbage and would like to see a further exploration of ways to
> split out filters to make them less bandwidth intensive. Some further
> ideas we should probably play with before finalizing moving forward is
> providing filters for certain script templates, eg being able to only
> get outputs that are segwit version X or other similar ideas.
>
> Matt
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
--00000000000073544d056c862419
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div>Matt wrote:</div><div>> I believe (1) could be ski=
pped entirely - there is almost no reason why</div><div>> you'd not =
be able to filter for, eg, the set of output scripts in a</div><div>> tr=
ansaction you know about</div><div><br></div><div>Depending on the use-case=
, the txid is more precise than searching for the</div><div>output script a=
s it doesn't need to deal with duplicated output scripts. To</div><div>=
my knowledge, lnd is the only major project that currently utilizes BIP</di=
v><div>157+158. At this point, we use the txid in the regular filter for</d=
iv><div>confirmations (channel confirmed, sweep tx confirmed, cltv confirme=
d, etc).</div><div>Switching to use output scripts instead wouldn't be =
_too_ invasive w.r.t</div><div>changes required in the codebase, only the n=
eed to deal with output script</div><div>duplication could be annoying.</di=
v><div><br></div><div>> (2) and (3) may want to be split out - many wall=
ets may wish to just find</div><div>> transactions paying to them, as tr=
ansactions spending from their outputs</div><div>> should generally be t=
hings they've created.</div><div><br></div><div>FWIW, in the "resc=
an after importing by seed phrase" both are needed in</div><div>order =
to ensure the wallet ends up with the proper output set after the</div><div=
>scan. In lnd we actively use both (2) to detect deposits to the internal</=
div><div>wallet, and (3) to be notified when our channel outputs are spent =
on-chain</div><div>(and also generally when any of our special scripts are =
spent).</div><div><br></div><div>> In general, I'm concerned about t=
he size of the filters making existing SPV</div><div>> clients less will=
ing to adopt BIP 158 instead of the existing bloom filter</div><div>> ga=
rbage and would like to see a further exploration of ways to split out</div=
><div>> filters to make them less bandwidth intensive.</div><div><br></d=
iv><div>Agreed that the current filter size may prevent adoption amongst wa=
llets.</div><div>However, the other factor that will likely prevent adoptio=
n amongst current</div><div>BIP-37 mobile wallets is the lack of support fo=
r notifying _unconfirmed_</div><div>transactions. When we drafted up the pr=
otocol last year and asked around,</div><div>this was one of the major poin=
ts of contention amongst existing mobile</div><div>wallets that utilize BIP=
37.</div><div><br></div><div>On the other hand, the two "popular"=
; BIP 37 wallets I'm aware of</div><div>(Breadwallet, and Andreas Schil=
dbach's Bitcoin Wallet) have lagged massively</div><div>behind the exis=
ting set of wallet related protocol upgrades. For example,</div><div>neithe=
r of them have released versions of their applications that take</div><div>=
advantage of segwit in any manner. Breadwallet has more or less "pivot=
ed"</div><div>(they did an ICO and have a token) and instead is priori=
tizing things like</div><div>adding random ICO tokens over catching up with=
the latest protocol updates.</div><div>Based on this behavior, even if the=
filter sizes were even _more_ bandwidth</div><div>efficient that BIP 37, I=
don't think they'd adopt the protocol.</div><div><br></div><div>&g=
t; Some further ideas we should probably play with before finalizing moving=
</div><div>> forward is providing filters for certain script templates, =
eg being able to</div><div>> only get outputs that are segwit version X =
or other similar ideas.</div><div><br></div><div>Why should this block acti=
ve deployment of BIP 157+158 as is now? As</div><div>defined, the protocol =
already allows future updates to add additional filter</div><div>types. Bef=
ore the filters are committed, each filter type requires a new</div><div>fi=
lter header. We could move to a single filter header that commits to the</d=
iv><div>hashes of _all_ filters, but that would mean that a node couldn'=
;t serve the</div><div>headers unless they had all currently defined featur=
es, defeating the</div><div>optionality offered.</div><div><br></div><div>A=
dditionally, more filters entails more disk utilization for nodes serving</=
div><div>these filters. Nodes have the option to instead create the filters=
at "query</div><div>time", but then this counters the benefit of=
simply slinging the filters</div><div>from disk (or a memory map or w/e). =
IMO, it's a desirable feature that</div><div>serving light clients no l=
onger requires active CPU+I/O and instead just</div><div>passive I/O (nodes=
could even write the filters to disk in protocol msg</div><div>format).</d=
iv><div><br></div><div>To get a feel for the current filter sizes, a txid-o=
nly filter size, and a</div><div>regular filter w/o txid's, I ran some =
stats on the last 10k blocks:</div><div><br></div><div>regular size:=C2=A0 =
=C2=A0 217107653=C2=A0 bytes</div><div>regular avg:=C2=A0 =C2=A0 =C2=A02171=
0.7653 bytes</div><div>regular median:=C2=A0 22332=C2=A0 =C2=A0 =C2=A0 byte=
s</div><div>regular max:=C2=A0 =C2=A0 =C2=A061901=C2=A0 =C2=A0 =C2=A0 bytes=
</div><div><br></div><div>txid-only size:=C2=A0 =C2=A0 34518463=C2=A0 bytes=
</div><div>txid-only avg:=C2=A0 =C2=A0 =C2=A03451.8463 bytes</div><div>txid=
-only median:=C2=A0 3258=C2=A0 =C2=A0 =C2=A0 bytes</div><div>txid-only max:=
=C2=A0 =C2=A0 =C2=A010193=C2=A0 =C2=A0 =C2=A0bytes</div><div><br></div><div=
>reg-no-txid size:=C2=A0 =C2=A0 182663961=C2=A0 bytes</div><div>reg-no-txid=
avg:=C2=A0 =C2=A0 =C2=A018266.3961 bytes</div><div>reg-no-txid median:=C2=
=A0 19198=C2=A0 =C2=A0 =C2=A0 bytes</div><div>reg-no-txid max:=C2=A0 =C2=A0=
=C2=A060172=C2=A0 =C2=A0 =C2=A0 bytes</div><div><br></div><div>So the medi=
an regular filter size over the past 10k blocks is 20KB. If we</div><div>ex=
tract the txid from the regular filter and add a txid-only filter, the</div=
><div>median size of that is 3.2KB. Finally, the median size of a modified =
regular</div><div>filter (no txid) is 19KB.</div><div><br></div><div>-- Lao=
lu</div><div><br></div><br><div class=3D"gmail_quote"><div dir=3D"ltr">On T=
hu, May 17, 2018 at 8:33 AM Matt Corallo via bitcoin-dev <<a href=3D"mai=
lto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.linuxfoundatio=
n.org</a>> wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"ma=
rgin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">BIP 158 curren=
tly includes the following in the "basic" filter: 1)<br>
txids, 2) output scripts, 3) input prevouts.<br>
<br>
I believe (1) could be skipped entirely - there is almost no reason why<br>
you'd not be able to filter for, eg, the set of output scripts in a<br>
transaction you know about and (2) and (3) may want to be split out -<br>
many wallets may wish to just find transactions paying to them, as<br>
transactions spending from their outputs should generally be things<br>
they've created.<br>
<br>
In general, I'm concerned about the size of the filters making existing=
<br>
SPV clients less willing to adopt BIP 158 instead of the existing bloom<br>
filter garbage and would like to see a further exploration of ways to<br>
split out filters to make them less bandwidth intensive. Some further<br>
ideas we should probably play with before finalizing moving forward is<br>
providing filters for certain script templates, eg being able to only<br>
get outputs that are segwit version X or other similar ideas.<br>
<br>
Matt<br>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div></div>
--00000000000073544d056c862419--
|