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 . Whenever a block gains votes, it becomes notarized. Whenever a node observes a notarized chain with blocks of consecutive epochs at the end, then the entire chain chop** off blocks at the end is final.
By varying the parameters highlighted in , 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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Our exposition in spirit illustrates the ideas behind most classical blockchain constructions although our exposition is not necessarily faithful to any particular protocol. In fact, we give a simplified exposition of the technical ideas to maximally aid understanding.
- 2.
References
Abraham, I., Gueta, G., Malkhi, D.: Hot-stuff the linear, optimal-resilience, one-message BFT devil. CoRR, abs/1803.05069 (2018)
Abraham, I., Malkhi, D., Nayak, K., Ren, L., Yin, M.: Sync HotStuff: simple and practical synchronous state machine replication. Cryptology ePrint Archive, Report 2019/270 (2019). https://eprint.iacr.org/2019/270
Castro, M., Liskov, B.: Practical Byzantine fault tolerance. In: OSDI (1999)
Hubert Chan, T.-H., Pass, R., Shi, E.: Pala: a simple partially synchronous blockchain. Manuscript (2018). https://eprint.iacr.org/2018/981
Hubert Chan, T.-H., Pass, R., Shi, E.: Pili: a simple, fast, and robust family of blockchain protocols. Cryptology ePrint Archive, Report 2018/980 (2018). https://eprint.iacr.org/2018/980
Dwork, C., Lynch, N., Stockmeyer, L.: Consensus in the presence of partial synchrony. J. ACM 35, 288–323 (1988)
Guo, Y., Pass, R., Shi, E.: Synchronous, with a chance of partition tolerance. Cryptology ePrint Archive (2018)
Hanke, T., Movahedi, M., Williams, D.: Dfinity technology overview series: consensus system. https://dfinity.org/tech
Lamport, L.: The part-time parliament. ACM Trans. Comput. Syst. 16(2), 133–169 (1998)
Lamport, L., Shostak, R., Pease, M.: The Byzantine generals problem. ACM Trans. Program. Lang. Syst. 4(3), 382–401 (1982)
Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system (2008)
Pass, R., Shi, E.: Hybrid consensus: efficient consensus in the permissionless model. In: DISC (2017)
Pass, R., Shi, E.: Rethinking large-scale consensus. In: CSF (2017)
Pass, R., Shi, E.: Thunderella: blockchains with optimistic instant confirmation. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 3–33. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_1
Schneider, F.B.: Implementing fault-tolerant services using the state machine approach: a tutorial. ACM Comput. Surv. 22(4), 299–319 (1990)
Griffith, V., Buterin, V.: Casper the friendly finality gadget. https://arxiv.org/abs/1710.09437
Acknowledgments
We gratefully acknowledge Kartik Nayak, Ling Ren, Robbert van Renesse, and Steven Galbraith for helpful feedback on improving the writeup. The author would like to thank T-H. Hubert Chan and Rafael Pass for inspiring discussions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
A Notations
A Notations
Variable | Meaning |
---|---|
\({{\mathsf{chain}}} \) | Blockchain |
\({{\mathsf{chain}}} [:\ell ]\) | Prefix of \({{\mathsf{chain}}} \) upto and including the \(\ell \)-th block |
\({{\mathsf{chain}}} [:-\ell ]\) | Prefix of \({{\mathsf{chain}}} \) after removing the trailing \(\ell \) blocks |
\(\Delta \) | maximum network delay between honest nodes (during a period of synchrony) |
e | Epoch number, i.e., a collection of \(2\Delta \) rounds |
n | Number of nodes |
\(h_{-1}\) | Parent hash encoded in a block |
\({\mathsf{TXs}} \) | Application-specific payload in a block, e.g., a set of transactions to confirm |
H | Collision-resistant hash function for hashing blockchains |
\(H^*\) | A random oracle for proposer election |
Rights and permissions
Copyright information
© 2019 International Association for Cryptologic Research
About this paper
Cite this paper
Shi, E. (2019). Streamlined Blockchains: A Simple and Elegant Approach (A Tutorial and Survey). In: Galbraith, S., Moriai, S. (eds) Advances in Cryptology – ASIACRYPT 2019. ASIACRYPT 2019. Lecture Notes in Computer Science(), vol 11921. Springer, Cham. https://doi.org/10.1007/978-3-030-34578-5_1
Download citation
DOI: https://doi.org/10.1007/978-3-030-34578-5_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-34577-8
Online ISBN: 978-3-030-34578-5
eBook Packages: Computer ScienceComputer Science (R0)