How the Invertible Bloom Lookup Table (IBLT) promotes the decentralization of Bitcoin

The Bitcoin system requires the decentralization of miners (or mining pools) and full nodes to achieve what some people consider to be the core attribute of Bitcoin: censorship resistance resistance. Therefore, the block size dispute also means a trade-off. Larger blocks allow the Bitcoin network to carry more transactions, but it also brings problems. It takes more time to propagate transactions, which will benefit large miners and mining pools. At the same time, the increased data transmission is also a blow to users running full nodes.

Fortunately, there are proposals to increase the efficiency of the Bitcoin network and reduce the risks of larger blocks. One of the most promising innovations is Invertible Bloom Lookup Table , or IBLT. The concept was first proposed by Bitcoin Core and Bitcoin XT developer Gavin Andresen, and has been used by people such as Blockstream’s Lightning Network Network developer Paul “Rusty” Russell, who is using the idea of ​​IBLT.

“If we can get this done, it means less bandwidth demand on the bitcoin network, fewer blocks, which will be good for the health of the network,” Russell said.

redundancy

So what problem does this reversible Bloom lookup table solve?

Normally, all Bitcoin transactions are done peer-to-peer, from node to node, and then stored in the memory pool (mempool) of individual nodes (recording unconfirmed transactions). When a miner finds a block, it includes (part of) the transactions in the block and then broadcasts the block in the same peer-to-peer network. Of course, this means that all transactions in the block are effectively sent twice on the network: once as a transaction, and once as part of the block.

Russell explained:

“There’s already redundancy in the blocks. Most nodes already know some of what the block contains because they’ve already seen it, and if we can optimize that, we can propagate blocks faster. It also reduces centralization pressure because miners can get their blocks out faster and the network can run better… that’s pretty cool.”

The magic of reversible Bloom lookup tables

The problem we need reversible bloom lookup tables to solve is that the set of transactions in a block is usually not exactly the same because they are stored in the memory pools of all individual nodes. The biggest difference is the last transaction that passed through the network before the block was discovered. In addition, the memory pools of all individual nodes are usually slightly different from each other. This makes it difficult to know what transactions a miner has made in a new block without seeing the entire block.

This is the problem that IBLs solve, IBLs combine a variety of mathematical tricks to bring sets of transactions into a consistent state. Therefore, they can allow two different memory pools to be compared and reconciled.

The basic principles are as follows:

First, all transactions contained in a block are written into a table, with each transaction starting at a different point on the table. However, there are far more transactions than there is room in the table, so it results in hopeless overlap. This makes IBLT appear very dense, but it is unreadable and undecipherable to those who do not have access to any transaction data.

Those who have transaction data can use similar logic to fill their own transactions into an IBLT, and then compare the overlapping transaction data on the IBLT. If the two IBLTs end up looking exactly the same, it means that all transactions are an exact match.

Even if the two IBLTs do not end up looking identical, this may still be useful as long as the transaction sets are very similar. In this case, the two IBLTs can be compared in such a way that all identical transactions cancel out one side. The "leftover" transactions in the IBLT can often be used to reconstruct the missing transactions.

So instead of broadcasting full blocks on the peer-to-peer network, nodes can broadcast smaller IBLTs. This requires less data and is faster.

efficiency

And this idea has been improved. In Russell's design, it is not even necessary to fill all the transactions in the new block into the IBLT. Instead, the nodes connected to each other on the Bitcoin peer-to-peer network let the good nodes broadcast to the peer nodes. This may increase the time of broadcasting, but it will further reduce the use of data.

“Gavin’s original idea was that miners would generate IBLTs and send the same IBLT to every node on the network,” Russell said. “But as we started playing with the concept, it turned out that generating IBLTs is very fast. So why not try to make it possible for every node to generate IBLTs? Let every peer node generate IBLTs because every node has the best understanding of its memory pool and how close it is to a peer node.”

In addition, interconnected nodes can continuously learn to understand each other's behavior. Once a node receives an IBLT from the network and constructs a valid block, the node will know how many transactions it has missed. In addition, the node will learn over time how many transactions its peers have that differ from it. This difference will be reflected in the IBLT, which the node will then send to its peers.

In this way, the IBLT system can improve itself over time, limiting the transmission of data over the network to a minimum.

"Ideally, if we could stuff this thing into two IP packets," he said, "we'd be lightning fast."

Details about IBLT and Bitcoin can be found in Russell’s blog and Andresen’s contributions on GitHub.

Original article: https://bitcoinmagazine.com/articles/how-the-magic-of-iblts-could-boost-bitcoin-s-decentralization-1448382673
By Aaron van Wirdum
Compiled by: Satuoxi
Editor: Satuoxi
Source (translation): 8btc Information (http://www.8btc.com/iblts-bitcoin-decentralization)