In this section, we discuss the privacy provisions of existing lightweight Bitcoin clients as reported in [4]. We start by overviewing the operation of Bloom filters that are used in the SPV mode to filter transactions that are not relevant for SPV clients.

Bloom Filters

As mentioned earlier, SPV clients do not receive all the transactions that are broadcast within the Bitcoin P2P network, but instead receive a subset of transactions filtered for them by the full nodes to which they are connected. To reduce bandwidth consumption, SPV clients make use of Bloom filters [5,6]. These filters basically consist of space-efficient probabilistic data structures that are used to test membership of an element. An SPV client constructs a Bloom filter by embedding all the Bitcoin addresses and public keys that appear in its wallets. The SPV client then outsources the constructed Bloom filter to a full Bitcoin node, as shown in Figure 6.1. Whenever the full node receives a transaction, it first checks to see if its input and/or output match the SPV client’s Bloom filter. If so, the full node forwards the received transaction to the SPV client.

A Bloom filter B of an SPV client is typically specified by the maximum number of elements that it can fit, denoted by M, and a target false-positive rate Pt.

Sketch of the basic operation of Bloom filters

Figure 6.2 Sketch of the basic operation of Bloom filters.

As shown in Figure 6.2, a Bloom filter B basically consists of an array B [.] of n bits accessed by k independent hash functions Hi(.),..., Hk(.), each of which maps an input string x e {0,1}* to one of the n bits of the array; all bits of B[.] are initialized to zero. To insert an element s, one has to set the bits at position hi(x),... ,hk (x) in B[.] to 1. Similarly, to test whether an element is a member of B [.], one has to check the bits at positions hi (x),... ,hk (x); if any of those bits are not 1, then the element is not a member of B[.].

Bloom filters can generate a number of false positives, but cannot result in false negatives. In this book, we compute the false positive rate of a filter B(M, Pt) which has m elements, Pf (m), as follows [7]:

Here, note that Pf (M) « Pt. That is, the target false positive rate of a Bloom filter is only reached when the number of elements contained in the filter matches M [4].

< Prev   CONTENTS   Source   Next >