Streamlined Blockchains: A Simple and Elegant Approach (A Tutorial and Survey)

Elaine Shi

Abstract

A blockchain protocol (also called state machine replication) allows a set of nodes to agree on an ever-growing, linearly ordered log of transactions. The classical consensus literature suggests two approaches for constructing a blockchain protocol: 1) through composition of single-shot consensus instances often called Byzantine Agreement; and 2) through direct construction of a blockchain where there is no clear-cut boundary between single-shot consensus instances. While conceptually simple, the former approach precludes cross-instance optimizations in a practical implementation. This perhaps explains why the latter approach has gained more traction in practice: specifically, well-known protocols such as Paxos and PBFT all follow the direct-construction approach. In this tutorial, we present a new paradigm called “streamlined blockchains” for directly constructing blockchain protocols. This paradigm enables a new family of protocols that are extremely simple and natural: every epoch, a proposer proposes a block extending from a notarized parent chain, and nodes vote if the proposal’s parent chain is not too old. Whenever a block gains enough votes, it becomes notarized. Whenever a node observes a notarized chain with several blocks of consecutive epochs at the end, then the entire chain chopping off a few blocks at the end is final. By varying the parameters highlighted in blue, we illustrate two variants for the partially synchronous and synchronous settings respectively. We present very simple proofs of consistency and liveness. We hope that this tutorial provides a compelling argument why this new family of protocols should be used in lieu of classical candidates (e.g., PBFT, Paxos, and their variants), both in practical implementation and for pedagogical purposes.

Available format(s)
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in ASIACRYPT 2019
Keywords
byzantine agreementconsensusblockchain
Contact author(s)
runting @ gmail com
History
2020-02-05: revised
See all versions
Short URL
https://ia.cr/2020/087

CC BY

BibTeX

@misc{cryptoeprint:2020/087,
author = {Elaine Shi},
title = {Streamlined Blockchains: A Simple and Elegant Approach (A Tutorial and Survey)},
howpublished = {Cryptology ePrint Archive, Paper 2020/087},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/087}},
url = {https://eprint.iacr.org/2020/087}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.