this page is a dynamically changing index of all our posts, it’s one more place to start reading Decentralized Thoughts (you can read chronologically here).

Basics, Foundations, and Classics

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 more about Partial Synchrony and about different relaxations of Broadcast.

One of the classic protocols of distributed computing is the Dolev-Strong Authenticated Broadcast protocol.

State Machine Replication

We begin by defining State Machine Replication (SMR) and talk about different degrees of SMR fault tolerance. The scalability and performance of a State Machine Replication system is not just about Consensus, but also about Data and Execution.

We start with a simple SMR for crash failures. We later extend this to omission failures. First via single shot and then via the Lock-commit paradigm to multi-shot consensus.

Living with Asynchrony

One of the core challenges in fault-tolerant distributed computing is Asynchrony. The classic FLP lower bound is a fundamental result. The basic building blocks are Reliable Broadcast and Gather.

Lower Bounds

• Folklore: Consensus with Ommsion failures requires $f<n/2$.

• DLS lower bound: Byzantine Consensus in Partial Synchrony requires $f<n/3$.

• FLM lower bound: Byzantine Consensus with no PKI (or more generally when the adversary can simulate) requires $f<n/3$.

• Dolev and Reischuk lower bound: Consensus often needs a quadratic number of messages.

• 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).

• BKR lower bound: Asynchronous Verifiable Secret Sharing must have a non-zero probability of not terminating.

• Raft does not guarantee liveness under omission faults.

Blockchains

What was the first blockchain (or how to timestamp a digital document)? Do Proof of work Blockchains need any setup assumptions?, what checkpointing a blockchain mean? A simple security proof for Nakamoto Consensus. What is the problem of Selfish Mining? The simplest L2 solution is a Payment Channel.

Cryptography

The basics:

• Cryptographic hash function and Merkle Trees

• Polynomials over a finite field and their use for Polinomial secret sharing and even Zero knowledge proofs

More advanced:

• Bilinear Accumulators and range proofs.

• Private set intersection: part 1 and part 2

Research oriented posts

• What is the difference between PBFT, Tendermint, SBFT, and HotStuff ?

• Survay of modern Authenticated Synchronous BFT protocols (updated in march 2021).

• Sync HotStuff.

• Streamlet.

• Optimal Optimistic Responsivness.

• Encrypted Blockchain Databases part 1 and part 2.

• Asynchronous Fault-Tolerant Computation with Optimal Resilience.

• Resolving the Availability-Finality Dilemma.

• BFT Protocol Forensics.

• Good-case Latency of Byzantine Broadcast: the Synchronous Case and a Complete Categorization.

• 2-round BFT SMR with n=4, f=1.