Reliable Broadcast is an important building block of many Asynchronous protocols. There is a broadcaster that has some input value, $v$, and a non-faulty party that terminates needs to output a value. Reliable Broadcast is defined via two properties:
[Read More]
Optimal Communication Complexity of Authenticated Byzantine Agreement
Communication complexity of Byzantine Agreement (BA) has been studied for decades. Dolev and Reischuk showed that quadratic communication is necessary for BA with perfect security, i.e., without error. Berman, Garay, and Perry showed that this lower bound is tight for the unauthenticated setting (without signatures) with $f < n/3$. However, for $f \ge n/3$, the best solution so far is still the Dolev-Strong protocol with cubic communication, so a linear...
[Read More]
Information Theoretic HotStuff (IT-HS): Part One
This post is the first of two on Information Theoretic HotStuff (IT-HS). Information Theoretic HotStuff is a Byzantine Consensus protocol in the partially synchronous model. It replaces all of HotStuff’s cryptographic signatures with simple information theoretic message passing techniques over authenticated channels. Information theoretic protocols are often easy to reason about, form a great introduction for learning the basics of consensus, have less of an attack surface, and highlight useful...
[Read More]
The Private Set Intersection (PSI) Protocol of the Apple CSAM Detection System
In this post, we will discuss the cryptographic construction used in Apple’s new system for detecting CSAM - Child Sexual Abuse Material. This cryptographic construction implements a new variant of PSI - Private Set Intersection. While a lot of attention has been paid to the broad implications of this system, the technical details of the PSI construction have not been highlighted, even though Apple published a detailed technical description of...
[Read More]
Simplifying Raft with Chaining
Raft is a consensus algorithm for deciding a sequence of commands to execute on a replicated state machine. Raft is famed for its understandability (relative to other consensus algorithms such as Paxos) yet some aspects of the protocol still require careful treatment. For instance, determining when it is safe for a leader to commit commands from previous leaders or when it is safe for servers to delete or overwrite commands...
[Read More]
Neither Non-equivocation nor Transferability alone is enough for tolerating minority corruptions in asynchrony
In this post, we explore a theorem of Clement, Junqueira, Kate, and Rodrigues from PODC 2012 regarding the limits of non-equivocation. Informally, this theorem says that neither Non-equivocation nor Transferability alone is enough for tolerating minority corruptions in asynchrony.
[Read More]
Benign Hotstuff
In this post we describe a variant of Paxos (or Raft or Lock-Commit) that is inspired by looking through the lens of HotStuff and Blockchain protocols. The most noticeable difference is that while Paxos and Raft aim to maintain a stable Primary/Leader (and change views infrequently), in Benign Hotstuff (as in HotStuff), the Primary is rotated every round! A more subtle difference is that in Paxos and Raft each block...
[Read More]
Living with Asynchrony: the Gather protocol
A very useful tool in Asynchronus distributed computing is Reliable Broadcast, or simply called Broadcast. It allows a leader to send a message, knowing that all parties will eventually receive the same message, even if a malicious adversary control $f$ parties and $f<n/3$. Broadcast is deterministic and takes just a constant number of rounds.
[Read More]
Good-case Latency of Byzantine Broadcast: the Synchronous Case
In our first post, we presented a summary of our good-case latency results for Byzantine broadcast (BB) and state machine replication (SMR), where the good case measures the latency to commit given that the broadcaster or leader is honest. In our second post, we discussed our results for partial synchrony, and described a new BFT SMR protocol named (5f-1)-SMR that can commit a decision within $2$ rounds in the good...
[Read More]
2-round BFT SMR with n=4, f=1
Guest post by Zhuolun Xiang
[Read More]
Good-case Latency of Byzantine Broadcast: a Complete Categorization
Guest post by Zhuolun Xiang
[Read More]
What is a Merkle Tree?
In this post, we will demystify Merkle trees using three examples of problems they solve:
[Read More]
Raft does not Guarantee Liveness in the face of Network Faults
Last month, Cloudflare published a postmortem of a recent 6-hour outage caused by a partial switch failure which left etcd unavailable as it was unable to establish a stable leader. This outage has understandably led to discussion online about exactly what liveness guarantees are provided by the Raft consensus algorithm in the face of network failures.
[Read More]
A Simple and Succinct Zero Knowledge Proof
There is a popular belief that succinct proofs and zero-knowledge proofs are a type of moon math. In this post, our goal is to present a simple proof system that can provide an introduction and intuition to this space. Perhaps surprisingly, the only tool we will use is the Theorem that non-trivial degree-at-most-$d$ polynomials over a field have at most $d$ roots.
[Read More]
The Lock-Commit Paradigm: Multi-shot and Mixed Faults
In this follow to our Lock-Commit post, we show two important extensions. The first is how to extend from single-shot to multi-shot. Multi-shot is the bases of State Machine Replication. The second is how to tolerate mix faluts: both $f$ omission failures and $k$ crash failures given k+2f < n.
[Read More]
The Lock-Commit Paradigm
In this post, we explore one of the most celebrated and widely used techniques for reaching consensus: the Lock-Commit paradigm. This approach is a key technique of DLS88, Lamport’s Paxos, and many subsequent protocols. Protocols like Raft, PBFT, Tendermint, SBFT, Casper FFG, HotStuff, etc., are all based on this paradigm.
[Read More]
BFT Protocol Forensics
An important property satisfied by any Byzantine fault tolerant consensus protocol is agreement, which requires non-faulty replicas to not decide on conflicting values. Depending on the network model, typical consensus protocols tolerate only a fraction of Byzantine replicas. In particular, under partial synchrony or asynchrony, no consensus protocol with $n$ replicas can tolerate more than $n/3$ Byzantine faults. If the number of Byzantine replicas exceed this number, the protocols do...
[Read More]
Resolving the Availability-Finality Dilemma
Guest post by Joachim Neu, Ertem Nusret Tas, and David Tse
[Read More]
Living with Asynchrony: Bracha's Reliable Broadcast
In this series of posts, we explore what can be done in the Asynchronous model. This model seems challenging because the adversary can delay messages by any bounded time. By the end of this series, you will see that almost everything that can be done in synchrony can be obtained in asynchrony. The next posts in this series are about gather, round complexity, and finally our series on Asynchronous Agreement....
[Read More]
Broadcast from Agreement and Agreement from Broadcast
In this post, we highlight the connection between Broadcast and Agreement in the synchronous model.
Broadcast and Agreement: How can you implement one from the other?
[Read More]