Part I: Bloom Filters

Introduction

As bitcoin adoption grows, so has the growth of light clients, i.e. nodes on the network incapable of independent transaction verification. To ensure that these clients can verify transactions related to them, the concept of bloom filters was proposed for usage in what is known as simple payment verification.

Light Client Transaction Verification

Not all devices have the “luxury” of performing independent verification of transactions, which can only be done with access to the entire bitcoin ledger. This is primarily because of device-specific constraints on space, bandwidth, and processing power. These constrained devices are, in truth, only interested in the transactions related to the addresses in their wallets and should not be downloading multiple GBs of unrelated data. Also, with the growth of bitcoin, it has become increasingly more expensive to run a full node. Beyond just downloading the blockchain, nodes must remain connected to different peers on the network all the time. The memory, processing, and bandwidth requirements are quite “steep” and unreasonable for all nodes on the network to have.

Figure 1: A block of transactions with a transaction of interest for a light client

Bloom Filters:

Light clients cannot share their addresses/script_pubkeys to full nodes. Well, they can, but should not because of the loss of privacy in doing so. What they can do is create a superset of transactions they might be interested in. This is done using bloom filters — a probabilistic search filter. These filters are n-sized bit field created by passing transactions through a set number of hash functions, noting the output number q (between 1 and n) of each hash function, and flicking the bit at position q on (0 to 1).

Figure 2: Creating list of transaction objects
Figure 3: Adding transaction objects to bloom filter
  • verify transaction: With the Merkle block, the light client checks for matched transactions, and updates its view of the UTXO set, wallet balance, and the bloom filter to match future transactions that will reference the found UTXO.
  1. Trust: Light clients need to connect with at least one honest peer that would neither deny them service by hiding transactions nor send them double-spent transactions. The new way should encourage bitcoin’s philosophy of trustlessness. Light clients should request and get filter information for transactions they want to verify without having to trust any one honest peer.
  2. Work: Full nodes are in a state of perpetual work, scanning and re-scanning bloom filters for every incoming transaction they receive. Apart from providing a service that keeps the bitcoin network active for growing light clients, there is no reward for server-side transaction filtering. The risks of DOS attacks also need consideration. If a new solution to the transaction verification problem for light clients reduces the work of scanning to one-time computation and eliminates the attack vector, then that should be explored.
  3. Size: The size of the new filter should be lightweight. Small enough to compute and save to disk, and to relay along the network.

Conclusion

As bitcoin adoption grows, so has the growth of light clients. These clients, without access to the full ledger, have particular requirements concerning transaction verification for addresses in their wallets. They rely on a payment verification method that creates and sends bloom filters to full node peers. These filters are tune-able, giving light clients privacy control, but makes them vulnerable to Sybil attacks. These filters also place a disproportionate amount of work on full nodes. To counter the disadvantages, a new kind of filtering system called compact block filters was proposed and will be the topic of discussion in my article.

Contact me

I would deeply appreciate any feedback you can provide. If you found this article helpful/useful or found factual misrepresentation, please do not hesitate to comment or contact me here or on Twitter @engb_os.

References

  1. Antonopoulos, A. (2017). Mastering Bitcoin: Programming the open blockchain
  2. Song, J. (2019). Programming bitcoin: Learn how to program bitcoin from scratch
  3. Rosenbaum, K. (2019). Grokking Bitcoin
  4. Mouton, E (2021): Compact Block Filters Deep Dive (BIP 158). https://bitcoin-dev.blog/blog/bip158-deep-dive/. Accessed 2 May 2022.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
ochekliye enigbe

Mechanical engineer. Software Developer. Exploring bitcoin software development at Qala.