Countermeasures to information leakage of Bloom Filters in Bitcoin lightweight clients

by Albert Szmigielski

Keep the state about the seed.

When a device restarts and uses a different seed (as well as other filter information) to create a new bloom filter, the probability of having the same false positives is very low. Therefore an adversary with access to two bloom filters from the same client, created with different seeds can easily check if addresses appear in both filters. If so, they are addresses of the SPV client, otherwise they are false positives. Keeping the state about the seed would not give that advantage to the adversary. When an SPV client restarts it will create the exact same filter.

Disadvantages

  • The need to store a seed and some other information about the Bloom filter in non-volatile storage may be an issue for some devices, although the overhead is small (less than half a KB)
  • Keeping the information saved opens up security concerns about that information.

Do not include both addresses and public keys.

The original intuition about including both the addresses and associated public keys was so that clients can get information about transactions related to both the addresses and the public keys. However including that information in Bloom filters allows an adversary to find the false positives. If an address included in the filter does not have a corresponding public key then it is a false positive. By not including the public keys, it takes away the adversaries ability to guess with high probability which addresses are false positives.

Disadvantages

  • Perhaps the SPV client will not hear about transactions sent to the public key, but such transactions are rare nowadays.

Do not keep re-sizing the Bloom filter.

Filters are designed to hold at first 50 addresses and matching public keys. When users accumulate more addresses than the filter can hold, the filter is re-sized. As a result of this, the new filter will have completely different false positives than the original filter. Therefore an adversary looking at the two filters could easily identify the addresses belonging to the SPV client. By pre-generating lots of addresses and therefore avoiding resizing, we take away the adversary’s ability to determine the addresses belonging to the SPV client.

Disadvantages

  • creating a large number of addresses maybe difficult or not feasible for resource constrained SPV clients, but this only adds additional overhead at start-up.
  • creating a large bloom filter also adds to network traffic when sending the filter to full nodes. However, once again, that overhead seems negligible.

Leave a Reply

Your email address will not be published. Required fields are marked *