Blockchain Consensus: An Introduction to Classical, Blockchain, and Quantum Consensus Protocols
- Length: 464 pages
- Edition: 1
- Language: English
- Publisher: Apress
- Publication Date: 2022-09-07
- ISBN-10: 1484281780
- ISBN-13: 9781484281789
- Sales Rank: #6824805 (See Top 100 Books)
This book is your comprehensive guide to understanding Blockchain and Blockchain consensus algorithms. It covers distributed systems, distributed consensus, and relevant system models. And you’ll explore how classical and modern consensus algorithms work. The book also covers quantum consensus and explains the role that quantum computing plays in distributed systems.
Consensus protocols allow participants in distributed systems to agree on a common value, despite faults. It’s a fundamentally important construct in distributed systems. As a result of rigorous and ground-breaking research over the last four decades, many consensus mechanisms have been developed and are used in the industry today. However, with the advent of Blockchain technology, a renewed interest has arisen in this area, resulting in more research and innovation.
The first Blockchain, Bitcoin, was invented in 2008 and introduced a novel consensus protocol called Nakamoto consensus, a solution to the Byzantine General’s problem formulated almost 30 years ago. Since the introduction of Bitcoin, the interest in Blockchain and consensus protocols has risen exponentially. As a result, researchers from academia and industry have proposed many new consensus mechanisms. While fundamental goals and some techniques remain the same as established classical protocols, these modern protocols introduce innovative methods to achieve consensus in Blockchain. Some classical algorithms have been modified to make them suitable for Blockchain and some new protocols have been developed.
This book is a detailed account of classical distributed consensus and Blockchain consensus algorithms. It explains why and how cryptocurrencies and Blockchain remain secure and decentralized without depending on a trusted third party. In addition, you’ll learn how Blockchain can endure, even with hundreds or thousands of participants, out of which some might be malicious. The book introduces quantum consensus, which deals with the problem of reaching agreement in quantum networks and how to enhance classical results.
What You Will Learn
- Understand distributed systems, distributed consensus, and relevant system models and protocols
- Understand Blockchain and Blockchain consensus algorithms
- Know how classical and modern consensus algorithms work
- Know the inner workings of Paxos, RAFT, PBFT, HotStuff, proof of work, proof of stake, GRANDPA, Casper, proof of history, and other consensus protocols
- Understand quantum Byzantine agreement and quantum consensus
Who This Book Is For
Distributed systems and Blockchain students and researchers, Blockchain practitioners, architects, designers, product managers, and developers
This book targets many audiences as well as those with curious minds. It explains the classical consensus mechanisms, Blockchain age consensus protocols, and the latest developments in distributed consensus. The book does not assume any advanced knowledge of Blockchain or distributed systems, but a general understanding of computing and appreciation of Blockchain technology is helpful. Early chapters provide the necessary background to read and understanding consensus-related content quickly.
Readers who already understand classical consensus protocols and distributed systems but want to learn about Blockchain consensus will find the book helpful as it covers Blockchain age protocols in detail. Readers who have come to the Blockchain world without any, or with little, background in distributed systems or classical consensus protocols will find this book equally helpful as it provides a solid understanding of classical consensus protocols.
If you have no experience in Blockchain or don’t understand distributed computing in general, this book will give you a solid understanding of both subjects and enable you to conduct further research in this exciting area of distributed computing.
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
IndexDonate to keep this site alive
How to download source code?
1. Go to: https://github.com/Apress
2. In the Find a repository… box, search the book title: Blockchain Consensus: An Introduction to Classical, Blockchain, and Quantum Consensus Protocols, sometime you may not get the results, please search the main title.
3. Click the book title in the search results.
3. Click Code to download.
1. Disable the AdBlock plugin. Otherwise, you may not get any links.
2. Solve the CAPTCHA.
3. Click download link.
4. Lead to download server to download.
