Blockchain Consensus: An Introduction to Classical, Blockchain, and Quantum Consensus Protocols

Table of Contents
About the Author
About the Technical Reviewer
Acknowledgments
Introduction
Chapter 1: Introduction
	Distributed Systems
		Characteristics
		Why Build Distributed Systems
			Reliability
			Performance
				Responsiveness
				Throughput
			Resource Sharing
			Inherently Distributed
		Challenges
			Fault Tolerance
			Security
			Heterogeneity
			Distribution Transparency
			Timing and Synchronization
			Global State
			Concurrency
		Parallel vs. Distributed vs. Concurrency
		Centralized vs. Decentralized vs. Distributed
		Distributed Algorithm
		Elements of Distributed Computing/Pertinent Terms/Concepts
			Processes
			Events
			State
			Global State
			Execution
			Cuts
		Types of Distributed Systems
		Software Architecture Models
			Client-Server
			Multiserver
			Proxy Servers
			Peer to Peer
		Distributed System Model
			Processes
				Crash-Stop Failure
				Omission Failure
				Crash with Recovery
				Eavesdropping
				Arbitrary (Byzantine)
			Network
				Link Failures
				Fair-Loss Links
					Fair-Loss
					Finite Duplication
					No Creation
				Stubborn Links
					Stubborn Delivery
					No Creation
				Perfect (Reliable) Links
					Reliable Delivery
					No Duplication
					No Creation
				Logged Perfect Links
				Authenticated Perfect Links
				Arbitrary Links
		Synchrony and Timing
			Synchronous
			Asynchronous
			Partially Synchronous
			Eventually Synchronous
				Formal Definitions
			Adversary Model
				Threshold Adversary
				Dynamic Adversary
				Static Adversary
				Passive Adversary
		Time, Clocks, and Order
		Physical Clocks
			Clock Skew vs. Drift
			Atomic Clocks
			Synchronization Algorithms for Physical Clocks
				NTP
				GPS As a Time Source
				UTC Time
			Types of Physical Clocks
				Set
				Relation
				Partial Order
					Reflexivity
					Antisymmetry
					Transitivity
				Irreflexive Partial Order
					Irreflexive
				Total Order
		Happens-Before Relationship and Causality
			Logical Clocks
			Lamport Clocks
			Vector Clocks
			Faults and Fault Tolerance
				Crash-Stop
				Fail-Stop
				Omission Faults
					Send Omission
					Receive Omission
					General Omission
				Covert Faults
				Computation Faults
				Byzantine Faults
					Byzantine Faults with Authentication
					Byzantine Faults Without Authentication
				Timing Faults
			Safety and Liveness
			Forms of Fault Tolerance
	CAP Theorem
		Consistency
		Availability
		Partition Tolerance
	Cryptography in Distributed Systems
	Summary
	Bibliography
Chapter 2: Cryptography
	Introduction
	A Typical Cryptosystem
	Cryptographic Primitives
	Symmetric Cryptography
		Stream Ciphers
		Block Ciphers
			Electronic Codebook
			Cipher Block Chaining
			Counter Mode
			Keystream Generation Mode
			Message Authentication Mode
			Cryptographic Hash Mode
		Advanced Encryption Standard
	Some Basic Mathematics
		Prime
		Modular Arithmetic
		Group
		Abelian Group
		Field
		Finite Field (Galois Field)
		Prime Fields
		Generator
	Public Key Cryptography
		Diffie-Hellman Key Exchange
		Digital Signatures
			Entity Authentication
			Key Agreement
		RSA
			Key Pair Generation
			Encryption and Decryption
				Example of Key Generation, Encryption, and Decryption
		Elliptic Curve Cryptography
			Point Addition
			Point Doubling
			Scalar Point Multiplication
			Elliptic Curve Discrete Logarithm Problem
	Digital Signatures
		Authenticity
		Unforgeability (Nonrepudiation)
		Nonreusability
		ECDSA Signatures
		Multisignatures
		Threshold Signatures
		Aggregate Signatures
		Ring Signatures
	Hash Functions
		Preimage Resistance
		Second Preimage Resistance
		Collision Resistance
		Design of Secure Hash Algorithms (SHA)
			Design of SHA-256
				Preprocessing
				Hash Computation
		Design of SHA-3 (Keccak)
	Message Authentication Codes
		Hash-Based MACs (HMACs)
	Verifiable Delay Functions
	Verifiable Random Functions
	Summary
	Bibliography
Chapter 3: Distributed Consensus
	Broadcast Primitives
		Best-Effort Broadcast
			Validity
			No Duplication
			No Creation
		Reliable Broadcast
			Validity
			Agreement
			Remarks
		Uniform Reliable Broadcast
			Uniform Agreement
		FIFO Reliable Broadcast
			FIFO Delivery
		Causal Reliable Broadcast
		Total Order Reliable Broadcast or Atomic Reliable Broadcast
			Validity
			Agreement
			Integrity
			Total Order
		FIFO Total Order Broadcast
			Probabilistic Validity
			Integrity
		Relationship Between Broadcasts and Consensus
	Agreement
		Reliable Broadcast
		Total Order Broadcast
		The Byzantine Agreement Problem
			The Basic Byzantine Generals Problem or BGP
			The Interactive Consistency Problem
			The Consensus Problem
	System Models
		Distributed System
		Timing Model/Synchrony
		Process Failures
		Channel Reliability
	History
	Two Generals’ Problem
	Byzantine Generals Problem
	Replication
		Active Replication
		Passive Replication
		Pros and Cons
		Primary Backup Replication
		Chain Replication
			State Machine Replication
				Same Initial State
				Deterministic Operations
				Coordination
				Safety
				Liveness
				Linearizability
				Sequential Consistency
				Eventual Consistency
				SMR Using Weaker Broadcast Abstractions
		Fundamental Results
			Impossibility Results
			Minimum Number of Processes
			Crash Failure
			Byzantine Failure
			Minimum Connectivity
			Minimum Rounds
			FLP Impossibility
				Synchrony Assumptions
				Random Oracles
				Hybrid Models
				Failure Detectors
					Strong Completeness
					Weak Completeness
					Strong Accuracy
					Weak Accuracy
					Eventual Strong Accuracy
					Eventual Weak Accuracy
					Perfect Failure Detector P
					Strong Failure Detector S
					Eventually Perfect Failure Detector – Diamond P
					Eventually Strong Failure Detector – Diamond S
					Weak Failure Detector W
					Eventually Weak Failure Detector (Diamond W)
					Detector Q or V
					Eventually Detector Q (Diamond Q) or Diamond V
				Leader Elector Failure Detector
			Solving Consensus Using Failure Detectors
	Quorums
		Crash Fault–Tolerant Quorums
		Byzantine Quorums
		Read and Write Quorums
	Where Are We Now
		Classical Consensus
		Nakamoto and Post-Nakamoto Consensus
	Summary
	Bibliography
Chapter 4: Blockchain
	What Is Blockchain
		Layman’s Definition
		Technical Definition
	Background
		Digital Cash Creation Attempts
			The First Blockchain?
	Benefits of Blockchain
	Types of Blockchain
	Blockchain Is a Distributed System
		CAP and Permissionless Blockchain
		CAP and Permissioned Blockchain
		Blockchain Ledger Abstraction
			Properties
				Consistency
				Fault Tolerant
				Finality
				Immutability
				Append Only
				Tamper Resistant/Proof
				Validity
				Termination Guarantee of Blockchain Operations: get(), append(), verify()
				Order
				Verifiable
	How Blockchain Works
	Anatomy of a Blockchain
		Block
	Platforms
		Bitcoin
			Bitcoin Node and Architecture
			Cryptography in Bitcoin
				Public Keys and Private Keys
			Addresses and Accounts
			Transactions and UTXO Model
			Bitcoin Script and Miniscript
				Blocks and Blockchain
				Mining
				Bitcoin As a Platform
	Ethereum
		Ethereum Network
		Cryptography in Ethereum
			Accounts and Addresses
		Transactions and Executions
		Blocks and Blockchain
			Transaction Trie
			World State Trie
			Transaction Receipts Trie
			Account Storage Trie
		Mining in Ethereum
		Ethereum Virtual Machine and Smart Contracts
	Summary
	Bibliography
Chapter 5: Blockchain Consensus
	Background
	Blockchain Consensus
		Traditional BFT
			Agreement
			Validity
			Termination
			Integrity
			Chain Progress (Liveness)
			Instant Irrevocability
			Consensus Finality
		Nakamoto Consensus
			Agreement
			Validity
			Termination
			Consensus Finality
			Chain Progress (Liveness)
			Consistent/Consistency
			Eventual Irrevocability
	System Model
		Public Blockchain System Model (Permissionless)
		Consortium Blockchain System Model (Permissioned)
	First Blockchain Consensus
		How PoW Works
		Pedagogical Explanation of PoW
		PoW Formula
			Task of Miners
			Properties of PoW
				Completeness
				Computationally Complex – Difficult to Compute – Slow Creation
				Auto-adjustable Cost – Dynamic Cost
				Quick and Efficient Verification – Quick Verification
				Progress Free
				Probabilistic Aspects of Dynamic Parameters
			Probability of an Attacker Catching Up
			PoW Algorithm
			Game Theory and Proof of Work
				Prisoner’s Dilemma
				PoW and Game Theory
		Similarities Between PoW and Traditional BFT
			Common Prefix
			Chain Quality
			Chain Growth
		PoW As State Machine Replication
			Leader Election Algorithm
			Log Replication
				New Block Propagation
				Block Validation
				Append to the Blockchain
				Fork Resolution
				Sybil Resistance
				Significance of Block Timestamp
				A Caveat
				PoW As a Solution to Byzantine Generals Problem
					Agreement
					Validity – Predicate Based
					Termination
		PoW Concerns
			51% Attack
			Selfish Mining
			Race Attack
			Finney Attack
			Vector76 Attack
			Eclipse Attack
			ESG Impact
			Variants of PoW
				CPU-Bound PoW
				Memory-Bound PoW
	Summary
	Bibliography
Chapter 6: Early Protocols
	Introduction
	Distributed Transactions
		Two-Phase Commit
		Three-Phase Commit
	Oral Message Algorithm
		Signed Message Solution to Byzantine Generals Problem
	DLS Protocols Under Partial Synchrony
	Ben-Or Algorithms
		Consensus Using Failure Detectors
	Summary
	Bibliography
Chapter 7: Classical Consensus
	Viewstamped Replication
		Protocol Steps
		View Change
	Paxos
		Failure Scenarios
		Safety and Liveness
		In Practice
		Variants
		Multi-Paxos
	RAFT
		Leader Election
		Log Replication
		Guarantees and Correctness
	PBFT
		Certificates in PBFT
			Types of Messages
			View Change
			The Checkpoint Subprotocol
		PBFT Advantages and Disadvantages
			Strengths
			Weaknesses
		Safety and Liveness
			Order Within a View
			Order Across Views
	Blockchain and Classical Consensus
	Summary
	Bibliography
Chapter 8: Blockchain Age Protocols
	Introduction
	Proof of Stake
		Chain-Based PoS
		Committee-Based PoS
		BFT-Based PoS
		Delegated PoS
		Liquid PoS
		Attacks
			Nothing-at-Stake Problem
			Long-Range Attacks
			Other Attacks
	Ethereum’s Proof of Work
	Solana
		Proof of History
	Tendermint
	HotStuff
		Linear View Change
		Optimistic Responsiveness
		Chain Quality
		Hidden Lock
		Pacemaker
		Better Participant Organization Topology
			How It Works
				Prepare
				Pre-commit
				Commit
				Decide
				Safety and Liveness
	Polkadot
		Consensus in Polkadot
			BABE – Blind Assignment for Blockchain Extension
				Genesis Phase
				Normal Phase
				Epoch Update
				Safety and Liveness
					Chain Growth
					Chain Quality
					Chain Density
					Common Prefix
			GRANDPA – GHOST-Based Recursive Ancestor Deriving Prefix Agreement
				GRANDPA Protocol Steps
					Safety
					Liveness
	Ethereum 2
		Casper
			Casper FFG
	Summary
	Bibliography
Chapter 9: Quantum Consensus
	Introduction
	What Is a Quantum Computer?
		Qubit
		Superposition
		Entanglement
			Maximal Coordination
			Monogamy
	Quantum Gates
		Hadamard
		T
		CNOT
		Toffoli (CCNOT)
		Z
		NOT
		Swap Gate
		Measurement
	Quantum Circuits
		Teleportation Circuit
		GHZ Circuit
		W State Circuit
	Quantum Algorithms
	Quantum Computational Complexity
		P – Polynomial
		NP – Nondeterministic Polynomial
		BPP – Bounded Error Probabilistic Polynomial Time
		BQP – Bounded Error Quantum Polynomial Time
		PSPACE – Polynomial Space
	Other Quantum Systems
		Quantum Networks
		Quantum Internet
		Quantum Distributed Systems – Distributed Quantum Computing
		Quantum Blockchain
		Quantum Cryptography
	Quantum Consensus
		Fast Quantum Byzantine Agreement
		How to Refute FLP Impossibility
		Enhanced Distributed Consensus
		Quantum Leader Election and Consensus
		Other Algorithms
	Summary
	Bibliography
Chapter 10: Conclusion
	Introduction
	Other Protocols
		PoET
		Proof of Authority
		HoneyBadger BFT
		Avalanche
		DAG-Based Consensus Protocols
			Block-Based DAG
			Transaction-Based DAG
		Ebb-and-Flow Protocols
	Formal Verification
	Impossibility Results
	Complexity and Performance
		Message Complexity
		Communication Complexity (Bit Complexity)
		Time Complexity
		Space Complexity
	Comparison of Protocols
		Network Model
			Synchronous
			Eventual Synchrony
			Partial Synchrony
			Weak Synchrony
			Asynchronous
	Research Directions
	Summary
	Bibliography
Index