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
|
Return-Path: <leo@LeoWandersleb.de>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 9E57171
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 28 Jul 2016 21:16:34 +0000 (UTC)
X-Greylist: delayed 00:09:01 by SQLgrey-1.7.6
Received: from geekbox.info (geekbox.info [5.9.151.241])
by smtp1.linuxfoundation.org (Postfix) with ESMTP id 8561D193
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 28 Jul 2016 21:16:33 +0000 (UTC)
Received: from [192.168.178.57] (ppp-83-171-168-238.dynamic.mnet-online.de
[83.171.168.238]) (Authenticated sender: leo)
by geekbox.info (Postfix) with ESMTPSA id C4BC8DE03C9
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 28 Jul 2016 23:07:30 +0200 (CEST)
To: bitcoin-dev@lists.linuxfoundation.org
References: <71d822e413ac457a530e1c367811cc24@cock.lu>
<20160511200648.GQ20063@mcelrath.org>
<20160511202933.GR20063@mcelrath.org>
From: Leo Wandersleb <leo@LeoWandersleb.de>
Openpgp: id=FAE4D5168E9EF9F104AA1B2D6B9A1F0CB7C20812
X-Enigmail-Draft-Status: N1110
Message-ID: <307a1ca0-5554-a14e-fd3b-aace7d7c2233@LeoWandersleb.de>
Date: Thu, 28 Jul 2016 23:07:29 +0200
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101
Icedove/45.1.0
MIME-Version: 1.0
In-Reply-To: <20160511202933.GR20063@mcelrath.org>
Content-Type: multipart/signed; micalg=pgp-sha256;
protocol="application/pgp-signature";
boundary="rG9Xq5TKBKPiPVai09PRBRfpIl6eWTV11"
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 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: Sat, 30 Jul 2016 14:20:44 +0000
Subject: Re: [bitcoin-dev] Committed bloom filters for improved wallet
performance and SPV security
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: Thu, 28 Jul 2016 21:16:34 -0000
This is an OpenPGP/MIME signed message (RFC 4880 and 3156)
--rG9Xq5TKBKPiPVai09PRBRfpIl6eWTV11
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: quoted-printable
gmaxwell just made me aware of this mail thread [0]. Some days ago I had
independently and naively started implementing "something similar" [1].
My version totally ignored the commitment and signing part but I'm pretty=
sure
that 12GB is overkill. My code is currently broken and I have no time to =
work on
it much but I thought it might be helpful to chime in.
At this point in time the difference between 80GB and 3GB (as my current =
1.5GB
of only outputs would suggest if I had covered the inputs) or even 12GB m=
akes
the difference of being able to store it on a phone, vs. not being able t=
o. 80GB
"compressed" to 3GB is not that bad at all. Unfortunately, with segWit th=
is will
be worse, with the higher transaction count per MB.
Regards,
Leo
[0]
https://www.reddit.com/r/Bitcoin/comments/4v28jl/how_have_fungiblity_prob=
lems_affected_you_in/d5ux6aq
[1] https://github.com/Giszmo/TransactionFinder
On 05/11/2016 10:29 PM, Bob McElrath via bitcoin-dev wrote:
> Eerrrr....let me revise that last paragraph. That's 12 *GB* of filters=
at
> today's block height (at fixed false-positive rate 1e-6. Compared to b=
lock
> headers only which are about 33 MB today. So this proposal is not real=
ly
> compatible with such a wallet being "light"...
>
> Damn units...
>
> Bob McElrath via bitcoin-dev [bitcoin-dev@lists.linuxfoundation.org] wr=
ote:
>> I like this idea, but let's run some numbers...
>>
>> bfd--- via bitcoin-dev [bitcoin-dev@lists.linuxfoundation.org] wrote:
>>> A Bloom Filter Digest is deterministically created of every block
>> Bloom filters completely obfuscate the required size of the filter for=
a desired
>> false-positive rate. But, an optimal filter is linear in the number o=
f elements
>> it contains for fixed false-positive rate, and logarithmic in the fals=
e-positive
>> rate. (This comment applies to a RLL encoded Bloom filter Greg mentio=
ned, but
>> that's not the only way) That is for N elements and false positive ra=
te
>> \epsilon:
>>
>> filter size =3D - N \log_2 \epsilon
>>
>> Given that the data that would be put into this particular filter is *=
already*
>> hashed, it makes more sense and is faster to use a Cuckoo[1] filter, c=
hoosing a
>> fixed false-positive rate, given expected wallet sizes. For Bloom fil=
ters,
>> multiply the above formula by 1.44.
>>
>> To prevent light clients from downloading more blocks than necessary, =
the
>> false-positive rate should be roughly less than 1/(block height). If =
we take
>> the false positive rate to be 1e-6 for today's block height ~ 410000, =
this is
>> about 20 bits per element. So for todays block's, this is a 30kb filt=
er, for a
>> 3% increase in block size, if blocks commit to the filter. Thus the r=
equired
>> size of the filter commitment is roughly:
>>
>> filter size =3D N \log_2 H
>>
>> where H is the block height. If bitcoin had these filters from the be=
ginning, a
>> light client today would have to download about 12MB of data in filter=
s. My
>> personal SPV wallet is using 31MB currently. It's not clear this is a=
bandwidth
>> win, though it's definitely a win for computing load on full nodes.
>>
>>
>> [1] https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
>>
>> --
>> Cheers, Bob McElrath
>>
>> "For every complex problem, there is a solution that is simple, neat, =
and wrong."
>> -- H. L. Mencken=20
>>
>>
>>
>> !DSPAM:5733934b206851108912031!
>
>
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>>
>> !DSPAM:5733934b206851108912031!
> --
> Cheers, Bob McElrath
>
> "For every complex problem, there is a solution that is simple, neat, a=
nd wrong."
> -- H. L. Mencken=20
>
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
--rG9Xq5TKBKPiPVai09PRBRfpIl6eWTV11
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: OpenPGP digital signature
Content-Disposition: attachment; filename="signature.asc"
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2
iQEcBAEBCAAGBQJXmnQRAAoJEGuaHwy3wggS/JkH+QH6dL+fy4iPVpc51vXI9DDO
1jwZXw5wYC8I5Vrkz/CRFdVtej0mod9mh6iDrvGGpvEhEK4wkJ2b+9H21l0d221P
xKYNNu6gXH8hwCDzi+ybHLcJQEYX5LqsJOZQswSP41Ylhg3oThkhr8y13Hngyppf
do5gJCdr7aoORXcSwoMdUUrFSh/wN2bED+8jEaKg/AkwFB2W6/EjS1FZCwtyqOOn
/cmaBs3WzWqkGgua7nZta943Mrwn4jsN119GV7VuK5cGVAJVy4kB5FXDddeALZMV
5XQhdzDQYVak51YmwaQEOIt/7lV+fBy623oQ/6zKTo0OK/q7hU7aqDNUaRI7/Fk=
=MNzI
-----END PGP SIGNATURE-----
--rG9Xq5TKBKPiPVai09PRBRfpIl6eWTV11--
|