The Blockchain Consensus Layer and BFT.

Details

At the core of Bitcoin is a method for reaching agreement on a shared chain of blocks where each block contains a sequence of transactions. This core is called the Blockchain. In many ways, the Blockchain is the most intriguing and innovative aspect of Bitcoin.

Blockchain uses idea of `computational puzzles' as proof-of-work (PoW) in order to obtain several goals at once. It is a way to mint currency but more importantly it is a key ingredient in the Bitcoin Blockchain protocol that reaches agreement and prevents double spending. Newly minted blocks are spread among the miners over a peer-to-peer network, and each miner keeps the longest chain as the winning chain, even if it means overturning earlier segments of the chain. Since winning the longest chain means solving cryptographic puzzles in each block, overturning a long tail segment is hard. For this reason, blocks ``buried'' deep in a miner's chain are typically considered committed with high probability.

From a foundational standpoint, this layer builds a chain of consensus blocks, a problem that has received tremendous attention in the distributed systems arena. Yet the Blockchain consensus engine, which achieves agreement among distrusting parties in a scalable settings with unknown participants, seems very different from the classical methods for Byzantine fault tolerance (BFT).

In this tutorial, invited by the bulletin of the EATCS (BEATCS link), we analyze Blockchain through the lens of the theory of distributed computing.

The tutorial covers the following three topics. First, it studies the algorithmic foundation of Nakamoto Consensus (NC), explaining how it solves (with high probability) the state-machine replication (SMR) problem. Second, it relates NC to the classical literature on Byzantine fault tolerant SMR (BFT). Finally, it overviews several approaches for bringing the two paradigms together.