What are the benefits of Invertible Bloom Lookup Tables for Bitcoin? Gavin Andresen announced a few days ago, that he started working on Invertible Bloom Lookup Tables.

His repository's README refers to two papers, What's the difference?: efficient set reconciliation without prior context by Eppstein, Goorich, Uyeda, and Varghese, and Invertible Bloom Lookup Tables by Goodrich and Mitzenmacher, whose abstracts seem to be hinting at a special datastructure that could significantly improve lookup times, and might be expedient for consolidating information in a peer-to-peer network, e.g. block propagation.

Has someone already wrapped his head around the whole thing and would kindly explain:


What do Invertible Bloom Lookup Tables do?
How would they be used in the Bitcoin project?
What improvements compared to the status quo can we expect?
Invertible Bloom lookup tables can be used in many different ways, but the first paper you linked to explicitly proposes to use them to find differences between two data sets stored on different hosts without transferring the entire data set from one of the hosts to the other.

In context of Bitcoin, suppose that two nodes have just established a connection. Now they need to synchronize their transaction pools to make sure that each node knows about every transaction the other node knows about. A trivial solution is to send the list of transaction IDs for all transactions in the pool from one node to the other, but this list can be large. At the same time, each node will probably have most of the transactions that the other node has, so the number of transactions that have to be transferred is small.

The problem is to find which transactions should be transferred, and this is the problem that invertible Bloom lookup tables can solve. Rather than sending the list of all transactions IDs, a node only sends an invertible Bloom table, which is smaller, but it is only usable if the number of differences (transactions which are present on one of the nodes but not on the other) is small. The table can be made of different sizes, and the larger the table, the greater is the number of differences that it can resolve.

For Bitcoin, this means that the amount of unnecessary communication will be reduced, and that nodes will be able to synchronize their transaction pools more quickly. Bitcoin nodes need to synchronize the block chain as well, but because of its linear, append-only structure, there are simpler and more efficient algorithms for this, and such algorithms are used in Bitcoin from the beginning.