Tag Index

 BFT (4) SMR (14) VID (2) approximate-agreement (4) asynchrony (13) blockchain (29) blockchain101 (6) consensus (49) consensus101 (12) crash (6) cryptography (12) cryptography101 (3) dist101 (7) incentives (6) lowerbound (29) math (3) models (10) omission (8) privacy (3) randomness (5) research (49)

 BFT (4)

Carry: HotStuff Linearity with Tail-Forking-Resilience
Variants of Simplex with Reduced Bad-case Latency: C-Simplex and Kuplex
What’s DAG got to do with it?
2-round BFT in Simplex style for n=5f-1

 SMR (14)

The CAP Theorem and why State Machine Replication for Two Servers and One Crash Failure is Impossible in Partial Synchrony
From Single-Shot Agreement to State Machine Replication
The Ideal State Machine Model: Multiple Clients and Linearizability
Simplifying Raft with Chaining
Benign Hotstuff
2-round BFT SMR with n=4, f=1
Resolving the Availability-Finality Dilemma
Commit-Notify Paradigm for Synchronous Consensus with Omission Faults
Sync HotStuff, A Simple and Practical State Machine Replication
State Machine Replication for Two Servers and One Omission Failure is Impossible even in a lock-step model
Primary-Backup State Machine Replication for Crash Failures
A Payment Channel is a two person BFS-SMR system
Flavours of State Machine Replication
Consensus for State Machine Replication

 VID (2)

Graded dispersal with perfect security
What is Verifiable Information Dispersal?

 approximate-agreement (4)

A Lower Bound for Approximate Agreement with Send Omissions
Byzantine Approximate Agreement: Grade, Detect, Average
Approximate Agreement with Omissions: From Midpoints to Averages
Byzantine Approximate Agreement: From One Round to a Complete Protocol

 asynchrony (13)

Multi-world Validated Asynchronous Byzantine Agreement
Living with asynchrony and eventually reaching agreement by combining binding and randomness
Asynchronous Agreement on a Core Set
Asynchronous Agreement Part 5: Binary Byzantine Agreement from a strong common coin
Asynchronous Agreement Part 4: Crusader Agreement and Binding Crusader Agreement
Asynchronous Agreement Part Three: a Modern version of Ben-Or's protocol
Asynchronous Agreement Part Two: Ben-Or's protocol
Asynchronous Agreement Part One: Defining the problem
Living with Asynchrony: the Gather protocol
Living with Asynchrony: Bracha's Reliable Broadcast
Asynchronous Fault Tolerant Computation with Optimal Resilience
The FLP Impossibility, Asynchronous Consensus Lower Bound via Uncommitted Configurations
Consensus Lower Bounds via Uncommitted Configurations

 blockchain (29)

Time Is Money: Incentivized Causal Transaction Ordering
Lutris: Safe Composition of Broadcast and Consensus
Beyond censorship resistance: hiding, simultaneous binding, and accountable last look
Strong Chain Quality
Mysticeti: Revolutionizing Consensus on Sui
Finality Is in the Eye of the Behodler
An Analysis of Latency and Block Capacity in Nakamoto Consensus
Simpler Security proof for Nakamoto Consensus
Scaling Blockchains: the Power of Batching
Can we Obtain Privacy in a Private Proof-of-Stake Blockchain? Part-II
Can we Obtain Privacy in a Private Proof-of-Stake Blockchain? Part-I
Blockchains + TEEs Day 2 Summary
Blockchains + TEEs Day 1 Summary
What is the difference between PBFT, Tendermint, HotStuff, and HotStuff-2?
What are Blockchains Useful for, Really?
Player Replaceability - Towards Adaptive Security and Sub-quadratic Communication Simultaneously (Part II)
Player Replaceability - Towards Adaptive Security and Sub-quadratic Communication Simultaneously (Part I)
He-HTLC - Revisiting Incentives in HTLC
Consensus by Dfinity - Part I
Consensus by Dfinity - Part II (Internet Computer Consensus)
EIP-1559 In Retrospect
Colordag: From always-almost to almost-always 50% selfish mining resilience
Blockchain Resource Pools and a CAP-esque Impossibility Result
Benign Hotstuff
Streamlet: A Simple Textbook Blockchain Protocol
Blockchain Selfish Mining
Data, Consensus, Execution: Three Scalability Bottlenecks for State Machine Replication
Security proof for Nakamoto Consensus
Dont Trust. Verify. and Checkpoint?

 blockchain101 (6)

Simpler Security proof for Nakamoto Consensus
What is a Blockchain?
Nakamoto's Longest-Chain Wins Protocol
The First Blockchain or How to Time-Stamp a Digital Document
A Payment Channel is a two person BFS-SMR system
Do Bitcoin and Ethereum have any trusted setup assumptions?

 consensus (49)

Designated Sets in Concurrent Simplex and Alpenglow
Two Round Information-Theoretic Chained BFT at n=5f-1
Chapter: Lower Bounds
Information-Theoretic Kuplex
Chapter: Simplex
Lutris: Safe Composition of Broadcast and Consensus
From Single-Shot Simplex to Chained Simplex
Fast Simplex on a Fixed View Schedule
Simplex on a Fixed View Schedule
From Simplex to Complex
Latency cost of censorship resistance
Deconstructing Simplex
Synchronized Clocks, Fixed View Schedules, and Simultaneous Agreement
From Benign Simplex to Byzantine Simplex
What’s DAG got to do with it?
2-round BFT in Simplex style for n=5f-1
Concurrent 2-round and 3-round Simplex-style BFT
2-round BFT in Simplex style
From Tendermint to Simplex
Reasoning about Distributed Protocols with Smart Casual Verification
Key Principles Underlying Partial Synchrony BFT
Divide and Conquer in Distributed Computing - synchronous BFT with quadratic communication via recursive phase king
HotStuff-1 and the Prefix Speculation Dilemma in BFT Consensus
Shoal++: High Throughput DAG-BFT Can Be Fast!
Sailfish: Improving the Latency of DAG-based BFT
Asynchronous Agreement on a Core Set
$3f+1$ is needed in Partial Synchrony even against a Rollback adversary
Randomization and Consensus - synchronous binary agreement for minority omission failures
Randomization and Consensus - synchronous binary agreement for crash failures with a perfect common coin
What about Validity?
Two Round HotStuff
Linear PBFT: a gentle introduction to Practical Byzantine Fault Tolerance
Provable Broadcast
A new Dolev-Reischuk style Lower Bound
DAG Meets BFT - The Next Generation of BFT Consensus
Crusader Broadcast
Phase-King through the lens of Gradecast: A simple unauthenticated synchronous Byzantine Agreement protocol
Approximate Agreement: definitions and the Robust Midpoint protocol
Asynchronous Agreement Part 5: Binary Byzantine Agreement from a strong common coin
Asynchronous Agreement Part 4: Crusader Agreement and Binding Crusader Agreement
Asynchronous Agreement Part Three: a Modern version of Ben-Or's protocol
Asynchronous Agreement Part Two: Ben-Or's protocol
Asynchronous Agreement Part One: Defining the problem
Distributed consensus made simple (for real this time!)
Raft does not Guarantee Liveness in the face of Network Faults
The Lock-Commit Paradigm: Multi-shot and Mixed Faults
Commit-Notify Paradigm for Synchronous Consensus with Omission Faults
Dolev-Strong Authenticated Broadcast
Consensus for State Machine Replication

 consensus101 (12)

Practical Byzantine Fault Tolerant Consensus (PBFT)
Randomization and Consensus - synchronous binary agreement for crash failures with a perfect common coin
Phase-King through the lens of Gradecast: A simple unauthenticated synchronous Byzantine Agreement protocol
Asynchronous Agreement Part Two: Ben-Or's protocol
Asynchronous Agreement Part One: Defining the problem
Consensus cheat sheet
Distributed consensus made simple (for real this time!)
The Lock-Commit Paradigm
Broadcast from Agreement and Agreement from Broadcast
Sync HotStuff, A Simple and Practical State Machine Replication
What is Consensus?
Byzantine Agreement is impossible for $n \leq 3 f$ under partial synchrony

 crash (6)

The CAP Theorem and why State Machine Replication for Two Servers and One Crash Failure is Impossible in Partial Synchrony
Randomization and Consensus - synchronous binary agreement for crash failures with a perfect common coin
On Paxos from Recoverable Broadcast
Simplifying Raft with Chaining
Benign Hotstuff
Primary-Backup State Machine Replication for Crash Failures

 cryptography (12)

Information Checking Protocols
Verifiable Multi-Exponentiation and Multi-Scalar Multiplication (MSM)
Dining Cryptographers and the additivity of polynomial secret sharing
The BGW Verifiable Secret Sharing Protocol
Polynomial Secret Sharing with Crash Failures
The Private Set Intersection (PSI) Protocol of the Apple CSAM Detection System
A Simple and Succinct Zero Knowledge Proof
Private Set Intersection #2
The Marvels of Polynomials over a Field
Bilinear Accumulators for Cryptocurrency Enthusiasts
Private Set Intersection
Range Proofs from Polynomial Commitments, Re-explained

 cryptography101 (3)

What is a Merkle Tree?
What is a Cryptographic Hash Function?
Polynomial Secret Sharing and the Lagrange Basis

 dist101 (7)

Optimal Clock Synchronization When There Are No Failures or Drift
Benign Simplex
Test your understanding of the basics of fault tolerant distributed computing
Flavours of Partial Synchrony
The threshold adversary
The power of the adversary
Synchrony, Asynchrony and Partial synchrony

 incentives (6)

An Analysis of Latency and Block Capacity in Nakamoto Consensus
Decentralization of Ethereum Builder Market
He-HTLC - Revisiting Incentives in HTLC
EIP-1559 In Retrospect
Colordag: From always-almost to almost-always 50% selfish mining resilience
Blockchain Selfish Mining

 lowerbound (29)

A Lower Bound for Approximate Agreement with Send Omissions
Optimal Clock Synchronization When There Are No Failures or Drift
Why BFT with Byzantine and Crash Faults Needs Three Rounds
Chapter: Lower Bounds
Synchronized Clocks, Fixed View Schedules, and Simultaneous Agreement
Why BFT Needs Three Rounds
Agreement against strongly adaptive adversaries needs quadratic communication
The SAP theorem for storing secret keys
Consensus with One Mobile Crash in Synchrony or One Crash in Asynchrony Has Infinite Executions
In between Crash and Omission failures
Early Stopping, Same but Different: Two Rounds Are Needed Even in Failure Free Executions
The CAP Theorem and why State Machine Replication for Two Servers and One Crash Failure is Impossible in Partial Synchrony
$3f+1$ is needed in Partial Synchrony even against a Rollback adversary
What about Validity?
A new Dolev-Reischuk style Lower Bound
Blockchain Resource Pools and a CAP-esque Impossibility Result
Crusader Agreement with $\leq 1/3$ Error is Impossible for $n\leq 3f$ if the Adversary can Simulate
The round complexity of Reliable Broadcast
Neither Non-equivocation nor Transferability alone is enough for tolerating minority corruptions in asynchrony
Good-case Latency of Byzantine Broadcast: the Synchronous Case
Good-case Latency of Byzantine Broadcast: a Complete Categorization
Asynchronous Fault Tolerant Computation with Optimal Resilience
The FLP Impossibility, Asynchronous Consensus Lower Bound via Uncommitted Configurations
Synchronous Consensus Lower Bound via Uncommitted Configurations
Consensus Lower Bounds via Uncommitted Configurations
State Machine Replication for Two Servers and One Omission Failure is Impossible even in a lock-step model
The Dolev and Reischuk Lower Bound: Does Agreement need Quadratic Messages?
Byzantine Agreement is Impossible for $n \leq 3 f$ if the Adversary can Simulate
Byzantine Agreement is impossible for $n \leq 3 f$ under partial synchrony

 math (3)

Lagrange's Theorem through the algorithmic lens
The Fast Fourier Transform over finite fields
The Marvels of Polynomials over a Field

 models (10)

Partial Synchrony variants
Test your understanding of the basics of fault tolerant distributed computing
In between Crash and Omission failures
What is Responsiveness?
The Ideal State Machine Model: Multiple Clients and Linearizability
Flavours of Partial Synchrony
The Trusted Setup Phase
The threshold adversary
The power of the adversary
Synchrony, Asynchrony and Partial synchrony

 omission (8)

Agreement under omission failures: non-uniformity and weak validity
Randomization and Consensus - synchronous binary agreement for minority omission failures
Responsiveness under omission failures
From Single-Shot Agreement to State Machine Replication
On Paxos from Recoverable Broadcast
Simplifying Raft with Chaining
Raft does not Guarantee Liveness in the face of Network Faults
State Machine Replication for Two Servers and One Omission Failure is Impossible even in a lock-step model

 privacy (3)

Can we Obtain Privacy in a Private Proof-of-Stake Blockchain? Part-II
Can we Obtain Privacy in a Private Proof-of-Stake Blockchain? Part-I
Pairing-based Anonymous Credentials and the Power of Re-randomization

 randomness (5)

Scalable Agreement - Near Linear Communication and Constant Expected Time
Living with asynchrony and eventually reaching agreement by combining binding and randomness
Randomization and Consensus - synchronous binary agreement for minority omission failures
Randomization and Consensus - synchronous binary agreement for crash failures with a perfect common coin
Pairing-based Anonymous Credentials and the Power of Re-randomization

 research (49)

Authenticated Broadcast in $\widetilde O(n^{2.5})$ Communication
Two Round Information-Theoretic Chained BFT at n=5f-1
DPaaS - Improving Decentralization by Removing Relays in Ethereum PBS
Concurrent 2-round and 3-round Simplex-style BFT
Reasoning about Distributed Protocols with Smart Casual Verification
Agreement against strongly adaptive adversaries needs quadratic communication
Multi-world Validated Asynchronous Byzantine Agreement
HotStuff-1 and the Prefix Speculation Dilemma in BFT Consensus
The SAP theorem for storing secret keys
Shoal++: High Throughput DAG-BFT Can Be Fast!
Sailfish: Improving the Latency of DAG-based BFT
Gather with Binding and Verifiability
Can we Obtain Privacy in a Private Proof-of-Stake Blockchain? Part-II
Can we Obtain Privacy in a Private Proof-of-Stake Blockchain? Part-I
What is the difference between PBFT, Tendermint, HotStuff, and HotStuff-2?
Can we Obtain Player Replaceability and Forensic Support Simultaneously?
Player Replaceability - Towards Adaptive Security and Sub-quadratic Communication Simultaneously (Part II)
Player Replaceability - Towards Adaptive Security and Sub-quadratic Communication Simultaneously (Part I)
Responsiveness under omission failures
Set Replication - fault tolerance without total ordering
What is Responsiveness?
Provable Broadcast
A new Dolev-Reischuk style Lower Bound
DAG Meets BFT - The Next Generation of BFT Consensus
Safe Permissionless Consensus
Asynchronous Agreement Part 5: Binary Byzantine Agreement from a strong common coin
Asynchronous Agreement Part 4: Crusader Agreement and Binding Crusader Agreement
Asynchronous Agreement Part Three: a Modern version of Ben-Or's protocol
Consensus by Dfinity - Part I
Consensus by Dfinity - Part II (Internet Computer Consensus)
EIP-1559 In Retrospect
Colordag: From always-almost to almost-always 50% selfish mining resilience
Blockchain Resource Pools and a CAP-esque Impossibility Result
Good-case Latency of Rotating Leader Synchronous BFT
The round complexity of Reliable Broadcast
Optimal Communication Complexity of Authenticated Byzantine Agreement
Information Theoretic HotStuff (IT-HS): Part One
Neither Non-equivocation nor Transferability alone is enough for tolerating minority corruptions in asynchrony
Good-case Latency of Byzantine Broadcast: the Synchronous Case
2-round BFT SMR with n=4, f=1
Good-case Latency of Byzantine Broadcast: a Complete Categorization
BFT Protocol Forensics
Resolving the Availability-Finality Dilemma
Encrypted Blockchain Databases (Part II)
Encrypted Blockchain Databases (Part I)
On the Optimality of Optimistic Responsiveness
Sync HotStuff, A Simple and Practical State Machine Replication
Authenticated Synchronous BFT
What is the difference between PBFT, Tendermint, SBFT and HotStuff ?