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
|
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 6A85EC07
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 29 May 2018 04:01:50 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm0-f46.google.com (mail-wm0-f46.google.com [74.125.82.46])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 94380224
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 29 May 2018 04:01:49 +0000 (UTC)
Received: by mail-wm0-f46.google.com with SMTP id a8-v6so36465311wmg.5
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 28 May 2018 21:01:49 -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=OtpS/RQVVgn9H6EeP48cFeET4eNFRHbWrCIgWYRgOnc=;
b=BzwHUrM+ZRHE2SB+0cUBfIbgkVLbDezhynf12xiU1bLNYW6jZbr3FiQ7fdUPXl0Uf5
BfJTQnrZqbO9Q/sP7FHex6na02FQdWt9rl6o7nrtUnUbs11hRifsQ6NzxuBzDHJrrITa
bLVIDJ7C39px5ou+9QqeyFNPJ7U4oUcIn5ZcUa414KaK+Y/I+I84T+MU+OKFFNHt2oyD
wtGyYm36iDmS+7R9xSRdo+ZUMjvozwtde+A7eyM/QmFAVHyK0+F4tCVwe5sic5+Sn2Uf
AFWxojkBDfMC4ypz+pAOxEsCfslvZxsjLy8OYOPOkwn5VsAwhR3V3khcKdz8fmIaxL6q
BAZg==
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=OtpS/RQVVgn9H6EeP48cFeET4eNFRHbWrCIgWYRgOnc=;
b=t+VVSCCvE/fllHKjvVOjvOy/CL3Sb/g62wHLUogIZKTBz5zzmY+J/PvoYDCWpXg7GX
mASMlalMbZnFMMhkCcaOeYoQaYp/KIRvQ97rp1Xbc+shg+Z43IQLvXyhIZFlCkWOqB6+
CQ88VVanjvw07N2z3CaPVtUGkRm5qsBwXyshLEtmQU+/f45A0//T/EhU4HMuDyKD7r5q
3inBfPBMrxWiMkSKhpDgP7iWYwYhbxsj578p9D1JwLdjXkN5HsLnUgyCaWImaZsCl6Eh
/mIarXEE8AdCh1C/h7CXJe/l7qyMGdkcoc9J1hY+mKQvOUwnlNmLuDwZcD0x0qMTNNdt
cbow==
X-Gm-Message-State: ALKqPwcvrI/QMuQSZYc1BbckAmCbKt6lYbzmSWeAypPOookEOg4WAhfh
IPmmi8tUITPhLUZN2g0MzUuaq5mq/UC5u7hM64k=
X-Google-Smtp-Source: AB8JxZr8sjcaqiJthlwr1VfKwVb6vGnjrnuyMlykj4lI8obxRByqbFRZOgCOYBwFm+a2XcZXK+sJrZK4sQ8g3aBzFrM=
X-Received: by 2002:a50:a227:: with SMTP id
36-v6mr17310142edl.151.1527566508039;
Mon, 28 May 2018 21:01:48 -0700 (PDT)
MIME-Version: 1.0
References: <d43c6082-1b2c-c95b-5144-99ad0021ea6c@mattcorallo.com>
<CAAS2fgRF-MhOvpFY6c_qAPzNMo3GQ28RExdSbOV6Q6Oy2iWn1A@mail.gmail.com>
<22d375c7-a032-8691-98dc-0e6ee87a4b08@mattcorallo.com>
<CAAS2fgR3QRHeHEjjOS1ckEkL-h7=Na56G12hYW9Bmy9WEMduvg@mail.gmail.com>
<CADZtCShLmH_k-UssNWahUNHgHvWQQ1y638LwaOfnJEipwjbiYg@mail.gmail.com>
<CAAS2fgQLCN_cuZ-3QPjCLfYOtHfEk=SenTn5=y9LfGzJxLPR3Q@mail.gmail.com>
<CADZtCSjYr6VMBVQ=rx44SgRWcFSXhVXUZJB=rHMh4X78Z2eY1A@mail.gmail.com>
<CAO3Pvs9K3n=OzVQ06XGQvzNC+Aqp9S60kWM9VRPA8hWTJ3u9BQ@mail.gmail.com>
<c23a5346-9f99-44f0-abbf-d7e7979bf1d8@gmail.com>
<CAO3Pvs_MA4TtgCCu1NgCBjK2bZRN+rKnGQJN6m4yTrViBXRiPA@mail.gmail.com>
<CAD3i26BibcaMdbQv-j+Egz_1y0GuhzepBp5ATNpj=Qv8hi1TVA@mail.gmail.com>
<CADZtCShAYpbN=4qNoX5c8yd1j08+mEZzG8gZwcHrj2suY0mb9w@mail.gmail.com>
<CADZtCShYnM3A949H18V2+BArA-K9J+cDkd=rX8xRn0+0js5CwA@mail.gmail.com>
<CAAS2fgTXS5Tains7dfe_Rc9JxR6M=NuFW9UtieRELm+6N2uNog@mail.gmail.com>
<CAFfwr8F+ghYb2HYEgC7Lh7Z-ytNE7EABr6cxiVXYhWLk-TPO7A@mail.gmail.com>
<CADZtCShDzPK_jqeOrK4XBoB2uriU9c9T8Dm7By-8ew3XOoAeQg@mail.gmail.com>
<7E4FA664-BBAF-421F-8C37-D7CE3AA5310A@gmail.com>
<F87D7069-0FDC-4572-B02B-398A2A455935@gmail.com>
<CAAS2fgT716PiP0ucoASxryM9y+s9H2z06Z0ToaP1xT3BozAtNw@mail.gmail.com>
<CADZtCSguto2z6Z9CykymxnCokqo1G=sW0Ov0ht+KcD+KMnYyow@mail.gmail.com>
In-Reply-To: <CADZtCSguto2z6Z9CykymxnCokqo1G=sW0Ov0ht+KcD+KMnYyow@mail.gmail.com>
From: Olaoluwa Osuntokun <laolu32@gmail.com>
Date: Mon, 28 May 2018 21:01:35 -0700
Message-ID: <CAO3Pvs-YDzfRqmyJ85wTH0ciccjCvkm5stGyP_tVGGna=PMv3A@mail.gmail.com>
To: Jim Posen <jim.posen@gmail.com>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="00000000000015246c056d504b19"
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: Tue, 29 May 2018 04:01:50 -0000
--00000000000015246c056d504b19
Content-Type: text/plain; charset="UTF-8"
> The additional benefit of the input script/outpoint filter is to watch for
> unexpected spends (coins getting stolen or spent from another wallet) or
> transactions without a unique change or output address. I think this is a
> reasonable implementation, and it would be nice to be able to download
that
> filter without any input elements.
As someone who's implemented a complete integration of the filtering
technique into an existing wallet, and a higher application I disagree.
There's not much gain to be had in splitting up the filters: it'll result in
additional round trips (to fetch these distinct filter) during normal
operation, complicate routine seed rescanning logic, and also is detrimental
to privacy if one is fetching blocks from the same peer as they've
downloaded the filters from.
However, I'm now convinced that the savings had by including the prev output
script (addr re-use and outputs spent in the same block as they're created)
outweigh the additional booking keeping required in an implementation (when
extracting the precise tx that matched) compared to using regular outpoint
as we do currently. Combined with the recently proposed re-parametrization
of the gcs parameters[1], the filter size should shrink by quite a bit!
I'm very happy with the review the BIPs has been receiving as of late. It
would've been nice to have this 1+ year ago when the draft was initially
proposed, but better late that never!
Based on this thread, [1], and discussions on various IRC channels, I plan
to make the following modifications to the BIP:
1. use P=2^19 and M=784931 as gcs parameters, and also bind these to the
filter instance, so future filter types may use distinct parameters
2. use the prev output script rather than the prev input script in the
regular filter
3. remove the txid from the regular filter(as with some extra book-keeping
the output script is enough)
4. do away with the extended filter all together, as our original use case
for it has been nerfed as the filter size grew too large when doing
recursive parsing. instead we watch for the outpoint being spent and
extract the pre-image from it if it matches now
The resulting changes should slash the size of the filters, yet still ensure
that they're useful enough for our target use case.
[1]:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-May/016029.html
-- Laolu
--00000000000015246c056d504b19
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div>> The additional benefit of the input script/outpo=
int filter is to watch for<br></div><div><div>> unexpected spends (coins=
getting stolen or spent from another wallet) or</div><div>> transaction=
s without a unique change or output address. I think this is a</div><div>&g=
t; reasonable implementation, and it would be nice to be able to download t=
hat</div><div>> filter without any input elements.=C2=A0</div><div><br><=
/div><div>As someone who's implemented a complete integration of the fi=
ltering</div><div>technique into an existing wallet, and a higher applicati=
on I disagree.</div><div>There's not much gain to be had in splitting u=
p the filters: it'll result in</div><div>additional round trips (to fet=
ch these distinct filter) during normal</div><div>operation, complicate rou=
tine seed rescanning logic, and also is detrimental</div><div>to privacy if=
one is fetching blocks from the same peer as they've</div><div>downloa=
ded the filters from.</div><div><br></div><div>However, I'm now convinc=
ed that the savings had by including the prev output</div><div>script (addr=
re-use and outputs spent in the same block as they're created)</div><d=
iv>outweigh the additional booking keeping required in an implementation (w=
hen</div><div>extracting the precise tx that matched) compared to using reg=
ular outpoint</div><div>as we do currently. Combined with the recently prop=
osed re-parametrization</div><div>of the gcs parameters[1], the filter size=
should shrink by quite a bit!</div><div><br></div><div>I'm very happy =
with the review the BIPs has been receiving as of late. It</div><div>would&=
#39;ve been nice to have this 1+ year ago when the draft was initially</div=
><div>proposed, but better late that never!</div><div><br></div><div>Based =
on this thread, [1], and discussions on various IRC channels, I plan</div><=
div>to make the following modifications to the BIP:</div><div><br></div><di=
v>=C2=A0 1. use P=3D2^19 and M=3D784931 as gcs parameters, and also bind th=
ese to the</div><div>=C2=A0 =C2=A0 =C2=A0filter instance, so future filter =
types may use distinct parameters</div><div>=C2=A0 2. use the prev output s=
cript rather than the prev input script in the</div><div>=C2=A0 =C2=A0 =C2=
=A0regular filter</div><div>=C2=A0 3. remove the txid from the regular filt=
er(as with some extra book-keeping</div><div>=C2=A0 =C2=A0 =C2=A0the output=
script is enough)=C2=A0</div><div>=C2=A0 4. do away with the extended filt=
er all together, as our original use case</div><div>=C2=A0 =C2=A0 =C2=A0for=
it has been nerfed as the filter size grew too large when doing</div><div>=
=C2=A0 =C2=A0 =C2=A0recursive parsing. instead we watch for the outpoint be=
ing spent and</div><div>=C2=A0 =C2=A0 =C2=A0extract the pre-image from it i=
f it matches now</div><div><br></div><div>The resulting changes should slas=
h the size of the filters, yet still ensure</div><div>that they're usef=
ul enough for our target use case.</div><div><br></div><div>[1]: <a href=3D=
"https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-May/016029.ht=
ml">https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-May/016029=
.html</a></div><div><br></div><div>-- Laolu</div></div></div>
--00000000000015246c056d504b19--
|
