Imran Bashir - Blockchain Consensus: An Introduction to Classical, Blockchain, and Quantum Consensus Protocols

Blockchain ConsensusAn Introduction to Classical,Blockchain, and QuantumConsensus ProtocolsImran BashirBlockchain Consensus: An Introduction to Classical, Blockchain, and QuantumConsensus Protocols Imran Bashir London, UK ISBN-13 (pbk): 978-1-4842-8178-9 ISBN-13 (electronic): 978-1-4842-8179-6 https://doi.org/10.1007/978-1-4842-8179-6 Copyright 2022 by Imran Bashir This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. Trademarked names, logos, and images may appear in this book. Rather than use a trademark symbol with every occurrence of a trademarked name, logo, or image we use the names, logos, and images only in an editorial fashion and to the benefit of the trademark owner, with no intention of infringement of the trademark. The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. While the advice and information in this book are believed to be true and accurate at the date of publication, neither the authors nor the editors nor the publisher can accept any legal responsibility for any errors or omissions that may be made.

The publisher makes no warranty, express or implied, with respect to the material contained herein. Managing Director, Apress Media LLC: Welmoed Spahr Acquisitions Editor: Aditee Mirashi Development Editor: Laura Berendson Coordinating Editor: Aditee Mirashi Cover designed by eStudioCalamar Cover image designed by Freepik (www.freepik.com) Distributed to the book trade worldwide by Springer Science+Business Media New York, 1 New York Plaza, Suite 4600, New York, NY 10004-1562, USA. Phone 1-800-SPRINGER, fax (201) 348-4505, e-mail orders-ny@springer-sbm.com, or visit www.springeronline.com. Apress Media, LLC is a California LLC and the sole member (owner) is Springer Science + Business Media Finance Inc (SSBM Finance Inc). SSBM Finance Inc is a Delaware corporation. For information on translations, please e-mail booktranslations@springernature.com; for reprint, paperback, or audio rights, please e-mail bookpermissions@springernature.com.

Apress titles may be purchased in bulk for academic, corporate, or promotional use. eBook versions and licenses are also available for most titles. For more information, reference our Print and eBook Bulk Sales web page at http://www.apress.com/bulk-sales. Any source code or other supplementary material referenced by the author in this book is available to readers on GitHub (github.com/apress). For more detailed information, please visit http://www.apress. com/source- code.

Printed on acid-free paper This book is dedicated to my father, the most affectionate,selfless, and hard-working person Ive ever known.If you are stuck at a research problem, rigorously readall relevant literature, you will find the answer.Scientist Bashir Ahmed KhanTable of Contents About the Author xv About the Technical Reviewer xvii Acknowledgments xix Introduction xxi Chapter 1: Introduction 1 Distributed Systems 1 Characteristics 2 Why Build Distributed Systems 4 Challenges 7 Parallel vs Distributed vs Concurrency 10 Centralized vs Decentralized vs Distributed 10 Distributed Algorithm 12 Elements of Distributed Computing/Pertinent Terms/Concepts 14 Types of Distributed Systems 19 Software Architecture Models 19 Distributed System Model 25 Synchrony and Timing 31 Time, Clocks, and Order 37 Physical Clocks 39 Happens-Before Relationship and Causality 50 CAP Theorem 61 Consistency 61 Availability 61 Partition Tolerance 61 v Table of ConTenTs Cryptography in Distributed Systems 63 Summary 64 Bibliography 65 Chapter 2: Cryptography 67 Introduction 67 A Typical Cryptosystem 68 Cryptographic Primitives 70 Symmetric Cryptography 70 Stream Ciphers 71 Block Ciphers 73 Advanced Encryption Standard 77 Some Basic Mathematics 79 Prime 79 Modular Arithmetic 80 Group 80 Abelian Group 80 Field 80 Finite Field (Galois Field) 80 Prime Fields 80 Generator 81 Public Key Cryptography 81 Diffie-Hellman Key Exchange 82 Digital Signatures 85 RSA 85 Elliptic Curve Cryptography 88 Digital Signatures 94 Authenticity 94 Unforgeability (Nonrepudiation) 94 Nonreusability 95 ECDSA Signatures 96 vi Table of ConTenTs Multisignatures 97 Threshold Signatures 98 Aggregate Signatures 99 Ring Signatures 100 Hash Functions 101 Preimage Resistance 101 Second Preimage Resistance 101 Collision Resistance 102 Design of Secure Hash Algorithms (SHA) 103 Design of SHA-3 (Keccak) 105 Message Authentication Codes 107 Hash-Based MACs (HMACs) 108 Verifiable Delay Functions 109 Verifiable Random Functions 110 Summary 111 Bibliography 111 Chapter 3: Distributed Consensus 113 Broadcast Primitives 113 Best-Effort Broadcast 115 Reliable Broadcast 116 Uniform Reliable Broadcast 117 FIFO Reliable Broadcast 118 Causal Reliable Broadcast 119 Total Order Reliable Broadcast or Atomic Reliable Broadcast 119 FIFO Total Order Broadcast 120 Relationship Between Broadcasts and Consensus 122 Agreement 123 Reliable Broadcast 123 Total Order Broadcast 124 The Byzantine Agreement Problem 124 vii Table of ConTenTs System Models 128 Distributed System 128 Timing Model/Synchrony 129 Process Failures 130 Channel Reliability 131 History 131 Two Generals Problem 132 Byzantine Generals Problem 133 Replication 135 Active Replication 137 Passive Replication 137 Pros and Cons 137 Primary Backup Replication 138 Chain Replication 139 Fundamental Results 147 Quorums 160 Crash FaultTolerant Quorums 161 Byzantine Quorums 162 Read and Write Quorums 162 Where Are We Now 162 Classical Consensus 163 Nakamoto and Post-Nakamoto Consensus 163 Summary 163 Bibliography 164 Chapter 4: Blockchain 167 What Is Blockchain 167 Laymans Definition 167 Technical Definition 168 Background 168 Digital Cash Creation Attempts 168 Benefits of Blockchain 170 viii Table of ConTenTs Types of Blockchain 172 Blockchain Is a Distributed System 174 CAP and Permissionless Blockchain 174 CAP and Permissioned Blockchain 174 Blockchain Ledger Abstraction 175 How Blockchain Works 178 Anatomy of a Blockchain 179 Block 180 Platforms 181 Bitcoin 181 Ethereum 192 Ethereum Network 192 Cryptography in Ethereum 196 Transactions and Executions 197 Blocks and Blockchain 199 Mining in Ethereum 201 Ethereum Virtual Machine and Smart Contracts 202 Summary 203 Bibliography 204 Chapter 5: Blockchain Consensus 207 Background 208 Blockchain Consensus 210 Traditional BFT 210 Nakamoto Consensus 211 System Model 213 Public Blockchain System Model (Permissionless) 213 Consortium Blockchain System Model (Permissioned) 214 First Blockchain Consensus 214 How PoW Works 216 Pedagogical Explanation of PoW 217 PoW Formula 221 ix Table of ConTenTs Similarities Between PoW and Traditional BFT 237 PoW As State Machine Replication 238 PoW Concerns 251 Summary 256 Bibliography 256 Chapter 6: Early Protocols 259 Introduction 259 Distributed Transactions 262 Two-Phase Commit 263 Three-Phase Commit 266 Oral Message Algorithm 268 Signed Message Solution to Byzantine Generals Problem 272 DLS Protocols Under Partial Synchrony 275 Ben-Or Algorithms 278 Consensus Using Failure Detectors 284 Summary 287 Bibliography 287 Chapter 7: Classical Consensus 291 Viewstamped Replication 291 Protocol Steps 293 View Change 294 Paxos 296 Failure Scenarios 301 Safety and Liveness 304 In Practice 305 Variants 305 Multi-Paxos 306 RAFT 308 Leader Election 310 Log Replication 311 Guarantees and Correctness 314 x Table of ConTenTs PBFT 315 Certificates in PBFT 319 PBFT Advantages and Disadvantages 323 Safety and Liveness 324 Blockchain and Classical Consensus 327 Summary 328 Bibliography 328 Chapter 8: Blockchain Age Protocols 331 Introduction 331 Proof of Stake 333 Chain-Based PoS 335 Committee-Based PoS 335 BFT-Based PoS 336 Delegated PoS 337 Liquid PoS 337 Attacks 338 Ethereums Proof of Work 339 Solana 342 Proof of History 343 Tendermint 347 HotStuff 353 Linear View Change 353 Optimistic Responsiveness 354 Chain Quality 354 Hidden Lock 354 Pacemaker 355 Better Participant Organization Topology 355 Polkadot 359 Consensus in Polkadot 361 xi Table of ConTenTs Ethereum 2 368 Casper 370 Summary 374 Bibliography 375 Chapter 9: Quantum Consensus 377 Introduction 377 What Is a Quantum Computer? 378 Qubit 380 Superposition 382 Entanglement 382 Quantum Gates 384 Hadamard 384 T 385 CNOT 385 Toffoli (CCNOT) 385 Z 385 NOT 385 Swap Gate 385 Measurement 386 Quantum Circuits 386 Teleportation Circuit 387 GHZ Circuit 387 W State Circuit 388 Quantum Algorithms 388 Quantum Computational Complexity 389 P Polynomial 391 NP Nondeterministic Polynomial 391 BPP Bounded Error Probabilistic Polynomial Time 391 BQP Bounded Error Quantum Polynomial Time 392 PSPACE Polynomial Space 392 xii Table of ConTenTs Other Quantum Systems 393 Quantum Networks 393 Quantum Internet 393 Quantum Distributed Systems Distributed Quantum Computing 394 Quantum Blockchain 395 Quantum Cryptography 396 Quantum Consensus 398 Fast Quantum Byzantine Agreement 399 How to Refute FLP Impossibility 401 Enhanced Distributed Consensus 403 Quantum Leader Election and Consensus 405 Other Algorithms 406 Summary 407 Bibliography 408 Chapter 10: Conclusion 411 Introduction 411 Other Protocols 411 PoET 412 Proof of Authority 413 HoneyBadger BFT 413 Avalanche 415 DAG-Based Consensus Protocols 415 Ebb-and-Flow Protocols 416 Formal Verification 417 Impossibility Results 420 Complexity and Performance 422 Message Complexity 422 Communication Complexity (Bit Complexity) 422 Time Complexity 423 Space Complexity 423 xiii Table of ConTenTs Comparison of Protocols 424 Network Model 426 Research Directions 428 Summary 430 Bibliography 430 Index 431 xiv