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
|
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 8770C256
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 9 May 2016 08:34:18 +0000 (UTC)
X-Greylist: delayed 00:08:08 by SQLgrey-1.7.6
Received: from cock.li (cock.li [185.100.85.212])
by smtp1.linuxfoundation.org (Postfix) with ESMTP id 8A33515A
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 9 May 2016 08:34:16 +0000 (UTC)
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII;
format=flowed
Content-Transfer-Encoding: 7bit
Date: Mon, 09 May 2016 09:26:06 +0100
From: bfd@cock.lu
To: bitcoin-dev@lists.linuxfoundation.org
Message-ID: <71d822e413ac457a530e1c367811cc24@cock.lu>
X-Sender: bfd@cock.lu
User-Agent: Roundcube Webmail/1.1.4
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: Mon, 09 May 2016 08:35:34 +0000
Subject: [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 Development 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: Mon, 09 May 2016 08:34:18 -0000
We introduce several concepts that rework the lightweight Bitcoin
client model in a manner which is secure, efficient and privacy
compatible.
Thea properties of BIP37 SPV [0] are unfortunately not as strong as
originally thought:
* The expected privacy of the probabilistic nature of bloom
filters does not exist [1][2], any user with a BIP37 SPV wallet
should be operating under no expectation of privacy.
Implementation flaws make this effect significantly worse, the
behavior meaning that no matter how high the false positive
rate (up to simply downloading the whole blocks verbatim) the
intent of the client connection is recoverable.
* Significant processing load is placed on nodes in the Bitcoin
network by lightweight clients, a single syncing wallet causes
(at the time of writing) 80GB of disk reads and a large amount
of CPU time to be consumed processing this data. This carries
significant denial of service risk [3], non-distinguishable
clients can repeatedly request taxing blocks causing
reprocessing on every request. Processed data is unique to every
client, and can not be cached or made more efficient while
staying within specification.
* Wallet clients can not have strong consistency or security
expectations, BIP37 merkle paths allow for a wallet to validate
that an output was spendable at some point in time but does not
prove that this output is not spent today.
* Nodes in the network can denial of service attack all BIP37 SPV
wallet clients by simply returning null filter results for
requests, the wallet has no way of discerning if it has been
lied to and may be made simply unaware that any payment has been
made to them. Many nodes can be queried in a probabilistic manor
but this increases the already heavy network load with little
benefit.
We propose a new concept which can work towards addressing these
shortcomings.
A Bloom Filter Digest is deterministically created of every block
encompassing the inputs and outputs of the containing transactions,
the filter parameters being tuned such that the filter is a small
portion of the size of the total block data. To determine if a block
has contents which may be interesting a second bloom filter of all
relevant key material is created. A binary comparison between the two
filters returns true if there is probably matching transactions, and
false if there is certainly no matching transactions. Any matched
blocks can be downloaded in full and processed for transactions which
may be relevant.
The BFD can be used verbatim in replacement of BIP37, where the filter
can be cached between clients without needing to be recomputed. It can
also be used by normal pruned nodes to do re-scans locally of their
wallet without needing to have the block data available to scan, or
without reading the entire block chain from disk.
-
For improved probabilistic security the bloom filters can be presented
to lightweight clients by semi-trusted oracles. A client wallet makes
an assumption that they trust a set, or subset of remote parties
(wallet vendors, services) which all all sign the BFD for each block.
The BFD can be downloaded from a single remote source, and the hash of
the filters compared against others in the trust set. Agreement is a
weak suggestion that the filter has not been tampered with, assuming
that these parties are not conspiring to defraud the client.
The oracles do not learn any additional information about the client
wallet, the client can download the block data from either nodes on
the network, HTTP services, NTTP, or any other out of band
communication method that provides the privacy desired by the client.
-
The security model of the oracle bloom filter can be vastly improved
by instead committing a hash of the BFD inside every block as a soft-
fork consensus rule change. After this, every node in the network would
build the filter and validate that the hash in the block is correct,
then make a conscious choice discard it for space savings or cache the
data to disk.
With a commitment to the filter it becomes impossible to lie to
lightweight clients by omission. Lightweight clients are provided with
a block header, merkle path, and the BFD. Altering the BFD invalidates
the merkle proof, it's validity is a strong indicator that the client
has an unadulterated picture of the UTXO condition without needing to
build one itself. A strong assurance that the hash of the BFD means
that the filters can be downloaded out of band along with the block
data at the leisure of the client, allowing for significantly greater
privacy and taking load away from the P2P Bitcoin network.
Committing the BFD is not a hard forking change, and does not require
alterations to mining software so long as the coinbase transaction
scriptSig is not included in the bloom filter.
[0] https://github.com/bitcoin/bips/blob/master/bip-0037.mediawiki
[1] https://eprint.iacr.org/2014/763.pdf
[2] https://jonasnick.github.io/blog/2015/02/12/privacy-in-bitcoinj/
[3] https://github.com/petertodd/bloom-io-attack
|
