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
|
Return-Path: <riccardo.casatta@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id D956715
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 18 May 2018 08:46:50 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-it0-f42.google.com (mail-it0-f42.google.com
[209.85.214.42])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 381066D3
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 18 May 2018 08:46:50 +0000 (UTC)
Received: by mail-it0-f42.google.com with SMTP id c3-v6so12212725itj.4
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 18 May 2018 01:46:50 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:in-reply-to:references:from:date:message-id:subject:to
:cc; bh=5wGYCg8+mxyHOBG2rSM6M8JSWexBkE6Krnt5eccEs90=;
b=VhVc5jYomOGxJGJR2BScaZuRkes0eEqbI5VGkKnsYyaakDxWspn2WlP75zdPTuRyQ1
1bcEhpHWtMz/6eoWfLMko5PbdoX4KN9NqcO7VXL5gFSNKtRf5XHXKuD7A8HE4FE+hcXt
O/qtuviToyz0y8qidkKI6vmVZoCZekeB6UvjClntH9Xwlpw9yyX2OJ+srIt88xEm7BpJ
32uA+fDO7DX7sKIMrCL/2tZIAZlJ1s2gXmys5fa7TncY5y0rylsglbTPxXcRBIBNXXX9
IIuuuYIlm+ufhGXXjvcS0G++JaOo5lEViRH2j0IIloJk/lJFBDRcK2sxkoAysO+7BdD+
HH1Q==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:in-reply-to:references:from:date
:message-id:subject:to:cc;
bh=5wGYCg8+mxyHOBG2rSM6M8JSWexBkE6Krnt5eccEs90=;
b=AUA8Lq6CIXi1rJ3sXkXyldBsLHoDos38InaapUdWWc0eLCh8Ms11kpYaG3XpLF8W+S
0407m+GOkuaICUZ/cKkYIPZKevWtWZkbuU5l6sUZeH6I/xylEW9CDGPoIFYmfGgZF8fG
IBUfXTXtyf4jGSMkG0qTvlgSO0BHO/SE4GbUUqtHMgT0VxIVsbo1pjMw/q1S0DMXDz5S
pTBu3qV0X7nPz2K8pByArP2thX7bgwVb6H6+czydGKfF4Tq1MEsE9aMADMeW3GtNfJjn
sZmPKtbSfzjgdg2l/tRbcdPFsKfZ2UXsJGTUC2ySbmEbLqA8leyx3bl8eJTANZgJ8gj/
kjVg==
X-Gm-Message-State: ALKqPwcfc+Rg4p+zGRGaR0ulSA6wWE2FoZFRr13plf7Q+A1cWzwPB0aW
FvGriqwqCdRv6vk9FRrmAt3O3DJo4Whj5kbhk/E=
X-Google-Smtp-Source: AB8JxZrX/O76TAz/3ZTlUJ1TIyy5LLUO5BA8kh5lZNhdAK7gFOH3BP7YRu1zqVOUECopflv9gE9BjXGx0h428glTu74=
X-Received: by 2002:a24:51d5:: with SMTP id
s204-v6mr6009453ita.151.1526633209431;
Fri, 18 May 2018 01:46:49 -0700 (PDT)
MIME-Version: 1.0
Received: by 2002:a02:d87:0:0:0:0:0 with HTTP;
Fri, 18 May 2018 01:46:29 -0700 (PDT)
In-Reply-To: <CAAS2fgRF-MhOvpFY6c_qAPzNMo3GQ28RExdSbOV6Q6Oy2iWn1A@mail.gmail.com>
References: <d43c6082-1b2c-c95b-5144-99ad0021ea6c@mattcorallo.com>
<CAAS2fgRF-MhOvpFY6c_qAPzNMo3GQ28RExdSbOV6Q6Oy2iWn1A@mail.gmail.com>
From: Riccardo Casatta <riccardo.casatta@gmail.com>
Date: Fri, 18 May 2018 10:46:29 +0200
Message-ID: <CADabwBCKe6DaiBf_sjz9zyirkw8BdsDZnWSLEiAABEZvVDwj-Q@mail.gmail.com>
To: Gregory Maxwell <greg@xiph.org>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000002697b0056c76fea8"
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE,
RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
X-Mailman-Approved-At: Fri, 18 May 2018 12:34:42 +0000
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: Fri, 18 May 2018 08:46:50 -0000
--0000000000002697b0056c76fea8
Content-Type: text/plain; charset="UTF-8"
Another parameter which heavily affects filter size is the false positive
rate which is empirically set
<https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki#construction>
to 2^-20
The BIP recall some go code
<https://github.com/Roasbeef/bips/blob/83b83c78e189be898573e0bfe936dd0c9b99ecb9/gcs_light_client/gentestvectors.go>
for how the parameter has been selected which I can hardly understand and
run, it's totally my fault but if possible I would really like more details
on the process, like charts and explanations (for example, which is the
number of elements to search for which the filter has been optimized for?)
Instinctively I feel 2^-20 is super low and choosing a lot higher alpha
will shrink the total filter size by gigabytes at the cost of having to
wastefully download just some megabytes of blocks.
2018-05-17 18:36 GMT+02:00 Gregory Maxwell via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org>:
> On Thu, May 17, 2018 at 3:25 PM, Matt Corallo via bitcoin-dev
> <bitcoin-dev@lists.linuxfoundation.org> 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
>
> I think this is convincing for the txids themselves.
>
> What about also making input prevouts filter based on the scriptpubkey
> being _spent_? Layering wise in the processing it's a bit ugly, but
> if you validated the block you have the data needed.
>
> This would eliminate the multiple data type mixing entirely.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
--
Riccardo Casatta - @RCasatta <https://twitter.com/RCasatta>
--0000000000002697b0056c76fea8
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">Another parameter which heavily affects filter size is the=
false positive rate which is <a href=3D"https://github.com/bitcoin/bips/bl=
ob/master/bip-0158.mediawiki#construction">empirically set</a> to 2^-20=C2=
=A0<div>The BIP recall some <a href=3D"https://github.com/Roasbeef/bips/blo=
b/83b83c78e189be898573e0bfe936dd0c9b99ecb9/gcs_light_client/gentestvectors.=
go">go code</a> for how the parameter has been selected which I can hardly =
understand and run, it's totally my fault but if possible I would reall=
y like more details on the process, like charts and explanations (for examp=
le, which is the number of elements to search for which the filter has been=
optimized for?)</div><div><br></div><div>Instinctively I feel 2^-20 is sup=
er low and choosing a lot higher alpha will shrink the total filter size by=
gigabytes at the cost of having to wastefully download just some megabytes=
of blocks.</div><div><br></div></div><div class=3D"gmail_extra"><br><div c=
lass=3D"gmail_quote">2018-05-17 18:36 GMT+02:00 Gregory Maxwell via bitcoin=
-dev <span dir=3D"ltr"><<a href=3D"mailto:bitcoin-dev@lists.linuxfoundat=
ion.org" target=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>></s=
pan>:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;borde=
r-left:1px #ccc solid;padding-left:1ex"><span class=3D"">On Thu, May 17, 20=
18 at 3:25 PM, Matt Corallo via bitcoin-dev<br>
<<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@li=
sts.<wbr>linuxfoundation.org</a>> wrote:<br>
> I believe (1) could be skipped entirely - there is almost no reason wh=
y<br>
> you'd not be able to filter for, eg, the set of output scripts in =
a<br>
> transaction you know about<br>
<br>
</span>I think this is convincing for the txids themselves.<br>
<br>
What about also making input prevouts filter based on the scriptpubkey<br>
being _spent_?=C2=A0 Layering wise in the processing it's a bit ugly, b=
ut<br>
if you validated the block you have the data needed.<br>
<br>
This would eliminate the multiple data type mixing entirely.<br>
<div class=3D"HOEnZb"><div class=3D"h5">______________________________<wbr>=
_________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.=
<wbr>linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.<wbr>org=
/mailman/listinfo/bitcoin-<wbr>dev</a><br>
</div></div></blockquote></div><br><br clear=3D"all"><div><br></div>-- <br>=
<div class=3D"gmail_signature" data-smartmail=3D"gmail_signature"><div dir=
=3D"ltr">Riccardo Casatta - <a href=3D"https://twitter.com/RCasatta" target=
=3D"_blank">@RCasatta</a></div></div>
</div>
--0000000000002697b0056c76fea8--
|
