Blockchain-Based Consensus (Keynote)

Distributed consensus (aka Byzantine agreement [Pease, Shostak & Lamport, 1980]) is one of the fundamental problems in fault-tolerant distributed computing and cryptographic protocols. It requires correct participants (parties) to reach agreement on initially held values despite the arbitrary behavior of some of them, with the additional requirement (known as Validity) that if all the correct participants start off with the same value, then that must be the decision value. The problem has been studied extensively in both the unconditional setting (where no assumptions are made about the computational power of the adversary) and the cryptographic setting, and efficient (i.e., polynomial-time) solutions exist tolerating the optimal number of misbehaving parties and running in the optimal number of rounds, on networks with pairwise authenticated channels. In many interesting scenarios, however, such as "peer-to-peer" networks, where parties come and go as they please and there are no prior relations among them, such infrastructure (pairwise authenticated channels, public-key infrastructure) is unavailable, thus raising the question whether anything "interesting" can be achieved. In this talk we answer this question in the affirmative, presenting two new probabilistic consensus protocols based on "proofs of work" (POWs, aka "moderately hard functions," "cryptographic puzzles" [Dwork & Naor, 1992]), the technology underlying Bitcoin, the first and most popular decentralized cryptocurrency to date. (In Bitcoin, POWs are implemented using the SHA-256 cryptographic hash function, by finding preimages that produce values in a given smaller domain.) In more detail, we first extract and analyze the core of the Bitcoin protocol, which we term the Bitcoin backbone, and prove two fundamental properties of its "blockchain" approach which we call "common prefix" and "chain quality." The consensus protocols can then be built as applications on top of the backbone protocol, with the Agreement and Validity properties following from common prefix and chain quality, respectively. The first protocol works assuming the adversary's hashing power is bounded by 1/3 of the network's total hashing power. The second consensus protocol is more elaborate, relies on the notion of robust transaction ledgers, which capture the essence of Bitcoin's operation as a cryptocurrency, and works assuming the adversary's hashing power is strictly less than 1/2.