Home Business & Finance Bitcoin and Blockchain Security

# Multiple Bloom Filters

In the previous paragraphs, we discussed the case where the adversary is equipped with only two Bloom filters. Note that our analysis equally applies to the case where the adversary possesses any number b > 2 of Bloom filters pertaining to the same entity.

As mentioned earlier, by computing the intersection between each pair of filters, the adversary can find common elements to different filters; this also enables the adversary to guess with high confidence whether different filters have been generated by the same client. Given b filters that belong to the same SPV client, the adversary can compute the number of elements inserted within each filter using (6.4). In the sequel, we assume that filters B1,..., Bb are sorted by increasing number of elements (i.e., Bb contains the largest number of elements), and that filters are constructed using different seeds. Let Kj = Bj n • • • П B(b-1), Vj g [1,b - 1].

Note that K1 < |K2| • • • < |K(b-1)|. Here, the larger the number of Bloom filters at the disposal of the adversary, the smaller is the error of the adversary in correctly classifying the genuine addresses of the SPV client, and the larger is Ph(}. That is, the larger is b, the smaller are the number of common false positives that are exhibited by the different filters, and the higher is the confidence of the adversary in identifying the false positives of Bj.

Moreover, as j increases, Kj will contain more false positives, and Ph(j) will decrease.

In what follows, we analytically validate this analysis and investigate the impact of having b > 2 Bloom filters pertaining to the same SPV client. For that purpose, we use 5 Bloom filters B1,B2,... ,B5 generated using different seeds with N = {3070,3120, 3170,3220, 3270}. We then compute Kj = B1 n • • • n

B(j+1), Vj g [1, b — 1], and the corresponding Ph() as follows:

The results (depicted in Table 6.1) validate the aforementioned analysis3 and show that the larger the number b of acquired Bloom filters of the same SPV client, the larger is Ph() and the smaller is the privacy of the user’s addresses. For instance, if the adversary is able to collect b > 2 different Bloom filters pertaining to the same wallet, then the adversary will be able to recover 100% of the true positives of the smallest Bloom filter.

Found a mistake? Please highlight the word and press Shift + Enter

Subjects