Introduction

In this tutorial paper, we analyze Blockchain consensus protocols in the lens of the foundations of distributed computing.

Abstract

In the early 2000’s, a group of activists advocating the wide-spread 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. 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. In this paper, we study Blockchain through the lens of the theory of distributed computing. Our goal is to present analogies and connections between Blockchain protocols and Byzantine fault tolerant (BFT) protocols. We also discuss opportunities to consider hybrid solutions.

Details

The story of the evolution of the BitCoin technology is fascinating, and harnesses deep 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 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.

Files

Date

October, 2017

Authors

Related Projects

Type

Incollection

Booktitle

Bulletin of the EATCS