On Relay: How Different Bitcoin Developers Are Speeding Up the Network (Part 1)
Bitcoin is designed as a peer-to-peer network, where nodes randomly connect to other nodes. Transactions and blocks are transmitted over this network by these nodes, until each has received all. This works quite well, as the distributed model makes Bitcoin relatively censorship-resistant; there is no central point of control to shut down or pressure into compliance.
But it also has a significant downside: The peer-to-peer network is relatively slow. As such, miners (and pools) sometimes waste hash power mining on top of an old block while a newer block is finding its way through the network. Transmission delay, therefore, benefits pooled mining as well as geographic clustering of miners, incentivizing a more centralized mining topology. This is generally considered one of the bottlenecks for scalability, as larger blocks (which can include more transactions) propagate even more slowly.
Over the past years, therefore, several projects have been in development to increase the speed of block propagation. These projects focus on roughly two main issues: block compression to limit the amount of data that needs to be propagated over the network, and relay speed to cut the time it takes for blocks to propagate.
This two-part series provides an overview of these projects. Part 1 will cover block compression.
Head First Mining
Each Bitcoin block has a block header, which refers to all data in that block. A hash of this block header must be included in the subsequent block in order for that next block to be valid. That's how all blocks on the blockchain are chained.
When a miner finds a block, it sends out the block header first — quickly followed by the rest of the block. This header, as well as the rest of the block, is checked for validity by receiving nodes. If valid, miners will mine “on top of” that block using the block header. The block (including the header) is also forwarded to other nodes.
Head First Mining is a trick proposed by former Bitcoin Core lead developer Gavin Andresen. With Head First Mining, miners don’t wait for the complete block to arrive before they start mining a subsequent block. Instead, they immediately mine on top of the block header as soon as they receive it, and also forward the header to other nodes. This obviously saves time.
Head First Mining does, however, have two disadvantages. First, miners don’t know for sure whether the block they are mining on top of is really valid. While the block header may appear valid (due to sufficient proof of work), the block may, for example, include invalid transactions. As such, there is a bit of risk involved in this solution. “Attacking” fellow-miners with fake blockheaders to have them waste resources is expensive, but not impossible.
Second, as a perhaps bigger disadvantage, miners have no idea which transactions are included in the block they are mining on top of. As such, the only way to ensure their subsequent block is valid, and doesn’t double-spend a transaction, is by including no transactions at all. Only after miners receive the complete block will they work on a block that does include transactions.
Of course, this means that some blocks will be empty, which isn’t great for network throughput. (But if the block size can be increased as a result, it might compensate.)
As seen, Bitcoin nodes typically forward each other blocks over the peer-to-peer network. Unfortunately, this can cause significant outbound bandwidth spikes each time a new block is found, which can slow down block propagation in between nodes.
Compact Blocks, developed by Bitcoin Core developer Matt Corallo, is a trick designed to decrease data-transmission. When a new block is found, nodes initially communicate only very compact hashes of transaction data. Because nodes already received the full transaction data when it was originally sent over the network, they can use these hashes to figure out which transactions are included in the block, and reconstruct the full block themselves.
But this trick does not always work out perfectly. If a node has not yet received the initial transaction before receiving the hashes, it cannot select the corresponding transaction. Additionally, in rare cases a wrong transaction may hash into a right hash, fooling a node into believing it received the right transaction — until it tries to reconstruct the block and finds it doesn't add up.
In both these cases of failure, the node simply requests the specific transaction data after all. Even with some full transactions in them, Compact Blocks will transmit over the network much faster and require significantly less bandwidth.
Xtreme Thinblocks, an option included in Bitcoin Unlimited, is similar to Compact Blocks in many ways; for example, rather than sending all transaction data, Xtreme Thinblocks transmit more compact hashes.
As the main difference, Xtreme Thinblocks use an extra mathematical trick to communicate transaction hashes: Bloom Filters. Without going into too much detail of exactly how this trick works, Bloom Filters are compact data structures that sort of turn the Compact Blocks trick upside down. Nodes can use Bloom Filters to figure out which transactions in a block a node is missing, and request only these.
Thus, the validity of Bitcoin blocks is, in part, determined by the block header. More specifically, the hash of this block header must start with at least a specific amount of zeroes, partly resulting from a random number (“nonce”) also included in the block header. Having the sufficient amount of zeroes “proves” that the required proof of work was done.
The specific amount of zeroes required is determined by the difficulty. So, as an example that doesn't actually translate into reality, let's say the difficulty is eight. That would mean the hash of a blockheader would need to start with eight zeroes; a hashed block header that starts with six or seven zeroes would not be valid. It would perhaps be “almost valid,” but not quite.
Weak Blocks, a relatively old idea, are essentially “almost valid” blocks. They are normal blocks in every way: They include transactions and all the rest — except that the hash of its header doesn't start with enough zeroes.
Weak Blocks can be useful. By transmitting Weak Blocks over the network, miners can indicate on what block they're working, and which transactions it includes.
Then, when a miner does find some way to hash the block correctly, he has a valid block. And since all other miners now already know on which block that miner was working, he really needs only to transmit a minimal amount of data: a confirmation and the correct nonce. So while the total amount of data sent over the network is actually increased (as weak blocks are transmitted all the time), the relevant data to mine on top of is limited.
Tomorrow: On Relay: How Different Bitcoin Developers are Speeding Up the Network (Part 2)