This page is a dynamically changing index of all posts on Decentralized Thoughts. Over time it will contain material for a graduate course on Blockchains (currently with a focus on consensus, but stay tuned). You can read all the posts chronologically here.
We would love to get your feedback and thoughts on Twitter.
Basics, Foundations, and Classics
You can start with the definition of Consensus and Agreement. Then learn about the network model, the threshold adversary model, and the power of the adversary. Finally, many protocols need a trusted setup phase. You can learn about different relaxations of Broadcast.
Checkout out our consensus cheat sheet for a quick overview of what is possible and impossible.
Approximate agreement is a variation that considers rational input values.
Synchronous Protocols
Under synchrony, a classic Byzantine Broadcast protocol is the Dolev-Strong Authenticated Broadcast protocol. You can read about more recent protocols such as Sync HotStuff, an optimal optimistically responsive synchronous protocol, and simple streamlined synchronous protocol called Streamlet. For more related work there is a survey of authenticated protocols under the synchrony assumption.
For a simple and classic Synchronous Byzantine agreement protocol, checkout Phase-King.
For a simple non-equivocation protocol, checkout Crusader Broadcast.
Partially Synchronous Protocols
Partial synchrony is one of the most used models in real word systems today.
Modern variants of the classic protocols of Paxos and Raft are covered in Benign Hotstuff and Simplifing Raft with Chaining. Log Paxos is a modern take on multi-Paxos. It’s both surprisingly simple and concretely efficient.
For Byzantine adversaries, checkout Information Theoretic HotStuff.
Asynchronous Protocols
One of the core challenges of distributed computing is tolerating failures in an asynchronous network. The classic FLP lower bound is a fundamental result showing the impossibility of consensus under even one crash fault.
A fundamental building block in asynchrony is the Reliable Broadcast protocol.
How do you measure round complexity in asynchrony (and can you improve the round complexity of reliable broadcast)?
The multi-leader generalization of reliable broadcast is called Reliable Gather.
Our series on the marvels of Asynchronous Agreement: we (1) define the problem; (2) present Ben-Or’s protocol; (3) provide a modern version; (4) Introduce Crusader Agreement and Binding Crusader Agreement; and (5) use it to efficiently solve Binary Byzantine Agreement from a strong common coin.
State Machine Replication
We begin by defining state machine replication (SMR) and talk about different degrees of SMR fault tolerance and the ideal state machine model and Linearizability. The scalability and performance of a State Machine Replication system is not just about consensus, but also about data and execution.
Start with a simple SMR for crash failures. Extend SMR to omission failures. First via single shot and then via the lock-commit paradigm to multi-shot consensus.
In partial synchrony, Log Paxos shows how to extend Paxos to multi-Paxos in a straightforward and efficient manner.
Lower Bounds
Lower bounds give us powerful tools to understand the fundamental limitations and model assumptions.
-
Folklore: Consensus with Omission failures requires $f<n/2$.
-
Dwork, Lynch, Stockmeyer 1988 (DLS) lower bound: Byzantine Consensus in Partial Synchrony requires $f<n/3$.
-
Fischer, Lynch, Merritt (FLM)lower bound: Byzantine Consensus with no PKI (or more generally when the adversary can simulate) requires $f<n/3$.
-
Strengthening the FLM lower bound: Crusader Agreement with $\leq 1/3$ Error is Impossible for $n\leq 3f$ if the Adversary can Simulate.
-
Dolev and Reischuk 1982 (DR) lower bound: Consensus often needs a quadratic number of messages.
-
Fischer, Lynch, Paterson 1985 (FLP) lower bound: Consensus must have some initial state that is uncommitted and this imples executions with at least $f+1$ rounds in Synchrony and non-terminating executions in Asynchrony (the FLP impossibility).
-
Ben-Or, Kelmer, Rabin 1994 (BKR) lower bound: Asynchronous Verifiable Secret Sharing must have a non-zero probability of not terminating.
-
Raft does not guarantee liveness under omission faults.
-
CJKR lower bound: Neither Non-equivocation nor Transferability alone is enough for tolerating minority corruptions in asynchrony.
Blockchains
What was the first blockchain (or how to timestamp a digital document)? Do proof-of-work blockchains need any setup assumptions? What does checkpointing a blockchain mean? What is Nakamoto Consensus? How do you prove it is secure. What is the problem of selfish mining?
The simplest L2 solution is a payment channel.
Cryptography
Some basics:
-
Polynomials over a finite field and their use for Polynomial secret sharing and even Zero knowledge proofs
More advanced:
-
Private set intersection: part 1 and part 2. Apple is using PSI for CSAM detection.
Research oriented posts
-
What is the difference between PBFT, Tendermint, SBFT, and HotStuff ?
-
Survey of modern Authenticated Synchronous BFT protocols (updated in March 2021).
-
Asynchronous Fault-Tolerant Computation with Optimal Resilience.
-
Good-case Latency of Byzantine Broadcast: the Synchronous Case and a Complete Categorization.
-
Optimal Communication Complexity of Authenticated Byzantine Agreement
-
Colordag: From always-almost to almost-always 50% selfish mining resilience
-
Consensus by Dfinity: in synchrony and Consensus by Dfinity - Part II (Internet Computer Consensus): in partial synchrony