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
|
Return-Path: <bob_bitcoin@mcelrath.org>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 1BF86267
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 11 May 2016 20:29:38 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from mcelrath.org (moya.mcelrath.org [50.31.3.130])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 753AD11D
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 11 May 2016 20:29:37 +0000 (UTC)
Received: from mcelrath.org (localhost [127.0.0.1])
by mcelrath.org (8.14.3/8.14.3/Debian-9.4) with ESMTP id u4BKTXLw020974
(version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT);
Wed, 11 May 2016 20:29:33 GMT
Received: (from mcelrath@localhost)
by mcelrath.org (8.14.3/8.14.3/Submit) id u4BKTXwN020973;
Wed, 11 May 2016 20:29:33 GMT
X-Authentication-Warning: mcelrath.org: mcelrath set sender to
bob_bitcoin@mcelrath.org using -f
Date: Wed, 11 May 2016 20:29:33 +0000
From: Bob McElrath <bob_bitcoin@mcelrath.org>
To: Bob McElrath <bob_bitcoin@mcelrath.org>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <20160511202933.GR20063@mcelrath.org>
References: <71d822e413ac457a530e1c367811cc24@cock.lu>
<20160511200648.GQ20063@mcelrath.org>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha1;
protocol="application/pgp-signature"; boundary="S1BNGpv0yoYahz37"
Content-Disposition: inline
In-Reply-To: <20160511200648.GQ20063@mcelrath.org>
User-Agent: Mutt/1.5.20 (2009-06-14)
X-Spam-Status: No, score=-3.3 required=5.0 tests=BAYES_00,RP_MATCHES_RCVD
autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
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: Wed, 11 May 2016 20:29:38 -0000
--S1BNGpv0yoYahz37
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
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 block
headers only which are about 33 MB today. So this proposal is not really
compatible with such a wallet being "light"...
Damn units...
Bob McElrath via bitcoin-dev [bitcoin-dev@lists.linuxfoundation.org] wrote:
> 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 of elements
> it contains for fixed false-positive rate, and logarithmic in the false-positive
> rate. (This comment applies to a RLL encoded Bloom filter Greg mentioned, but
> that's not the only way) That is for N elements and false positive rate
> \epsilon:
>
> filter size = - 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, choosing a
> fixed false-positive rate, given expected wallet sizes. For Bloom filters,
> 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 filter, for a
> 3% increase in block size, if blocks commit to the filter. Thus the required
> size of the filter commitment is roughly:
>
> filter size = N \log_2 H
>
> where H is the block height. If bitcoin had these filters from the beginning, a
> light client today would have to download about 12MB of data in filters. 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
>
>
>
> !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, and wrong."
-- H. L. Mencken
--S1BNGpv0yoYahz37
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
Content-Disposition: inline
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
iEYEARECAAYFAlczli0ACgkQjwioWRGe9K2mkgCg5JpqONxSmKBgaRefTYokV4jG
824An0COOkTo10pIPptsi18bjRKbH6U6
=602b
-----END PGP SIGNATURE-----
--S1BNGpv0yoYahz37--
|
