Bitcoin block propagation with IBLT
This is a crosspost from Popeller
Late 2014 I started looking into IBLT (Invertible Bloom Lookup Tables) applied to Bitcoin block propagation, after reading a github gist written by Gavin Andresen. Most of my findings can be read on my Bitcoin IBLT wiki page. On this blog I will give a series of digestible posts. Part I will describe the data structure and how it can be applied it to Bitcoin blocks.
A miner solving a Bitcoin block want to get that block out to all the other miners as fast as possible. If some other miner, B, solves a block roughly at the same time, a race starts. The block that reaches a majority of the network’s hashing power first will probably be the winning block.
This means that there’s incentive for the miner to keep the block small so that it propagates the network faster. Smaller blocks means fewer transactions. Fewer transactions means higher fees for end users. Higher fees means less adoption. End of the world.
What if we could exploit the fact that all transactions in the block probably already have propagated the network. Why do we have to send all the transactions in the block again? We don’t. We have a few things to consider:
- Order of transactions within the block matters
- There are probably differences between mempools on different nodes
- We don’t know the differences
Let’s ignore 1 for now. (We can fix that either by canonical ordering of transactions within blocks, or by attaching ordering information with the message.)
This is how we deal with 2 and 3. Buckle up!
Voila! We have extracted the same block as Node A solved!
Next post will cover some basic statistical analysis on the number of hash functions, k, and value size. (Spoiler: k = 3 and value size = 64 bytes.)