The following is an excerpt from the European Association for Theoretical Computer Science’s (EATSC) just released October Bulletin. VMware Research Group members Ittai Abraham and Dahlia Malkhi, experts in distributed computing, were asked to present their perspective on Blockchain consensus protocols, through the lens of distributed computing, and discuss the relationship to Byzantine Fault Tolerant (BFT) protocols.
In the early 2000’s, a group of activists advocating the widespread use of cryptography and privacy-enhancing technologies were engaging over the cypherpunks mailing-list in an effort to create an anonymous, monitor-free digital cash. Step by step, they jointly built the ingredients that eventually led to the emergence of Bitcoin in 2009. In recent years, more crypto-currency variants have emerged. As of late 2017, the market cap associated with Bitcoin is over 70 billion dollars, and the total crypto-currency market cap is about twice that.
The story of the evolution of the Bitcoin technology is fascinating and harnesses profound ideas and methods from published academic works. Its incredible market cap reflects the public trust in the robustness and soundness of the technology, without any company or institution backing it.
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 the idea of computational puzzles as proof-of-work (PoW) 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 an 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 setting with unknown participants, seems very different from the classical methods for Byzantine fault tolerance (BFT).
This paper extensively covers 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 exciting approaches for bringing the two paradigms together.
It is essential to understand the theory of Blockchain technology and its potential to revolutionize the financial technology arena.
To learn more about VMware Research Group, visit https://research.vmware.com/.
