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
|
Return-Path: <bfd@cock.lu>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 3407D959
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 3 Jan 2017 20:24:39 +0000 (UTC)
X-Greylist: delayed 00:05:35 by SQLgrey-1.7.6
Received: from cock.li (cock.li [185.100.85.212])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 5BBC3209
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 3 Jan 2017 20:24:38 +0000 (UTC)
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
X-Spam-Level:
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID,DKIM_VALID_AU autolearn=ham version=3.3.1
MIME-Version: 1.0
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cock.lu; s=mail;
t=1483475075; bh=hG4jym2u7IDlqqcTUxDGQUyobe8afcg6YpXPUhCL8OU=;
h=Date:From:To:Cc:Subject:In-Reply-To:References:From;
b=lekT5vTM2TGqgkCQgrEiutqh3jPcTqo4fZevZiisqVJN4NhBPI7C5rgJqlcZ/9ODY
RnnhTFbLTFr7BRDFexcvBa/A5LM4TPRlcGcvq/2vpNk7qorBRiLKvETAs53+jhYI09
B/N/R3TbBGlSWQVgJMXAEfCWEe99M3rJ9icItfdDqwhk2VneMiuoWU6W9jSI5AoqA5
mkj7ZN0jQWix+a6cDXsME7spl6dfO+Br9vmFgr5gmyRWjCZgDzvjZgZ5gHGWgWnTUb
3a4Sl1gu1Y2ItfPv9L0WNKLHH2YgCWHRaB3nek4eaFGNHP5qiJd5unBq0LBqJtXJRN
DwwOUkeRaeSGA==
Content-Type: text/plain; charset=US-ASCII;
format=flowed
Content-Transfer-Encoding: 7bit
Date: Tue, 03 Jan 2017 12:24:35 -0800
From: bfd@cock.lu
To: Bob McElrath <bob_bitcoin@mcelrath.org>
In-Reply-To: <20160511202933.GR20063@mcelrath.org>
References: <71d822e413ac457a530e1c367811cc24@cock.lu>
<20160511200648.GQ20063@mcelrath.org>
<20160511202933.GR20063@mcelrath.org>
Message-ID: <019588aaf210830f55742bbc5db43ea3@cock.lu>
X-Sender: bfd@cock.lu
User-Agent: Roundcube Webmail/1.2.3
X-Mailman-Approved-At: Tue, 03 Jan 2017 20:40:07 +0000
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.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: Tue, 03 Jan 2017 20:24:39 -0000
I believe the filter can be more compact than this, but even if not an
order of magnitude saving of disk space is still significant.
On 2016-05-11 13:29, Bob McElrath 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
> 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
|
