This is Part I of a multi-part series on Bitcoin block propagation with IBLT. | Part II >>
Skip boring text and go straight to infographic!
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.
The problem
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.
Solution
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!
Part II of this series will cover some basic statistical analysis on the number of hash functions, k, and value size. (Spoiler: k = 3 and value size = 64 bytes.)
