Perhaps the archetypical trilemma is consensus - it requires three properties: agreement, liveness, and validity. Getting any two is easy, but all three together is what makes consensus such a facinating problem that continues to create new challenges even after 40 years of research.
[Read More]
Two Round HotStuff
In the first part of this post we describe a single-shot variation of Two Round HotStuff (see HotStuff v1 paper, march 2018 and this march 2018 post) using Locked Broadcast that follows a similar path as our previous posts on Paxos and Linear PBFT.
[Read More]
Linear PBFT: a gentle introduction to Practical Byzantine Fault Tolerance
PBFT is a foundational multi-year project led by Barbara Liskov and her students, obtaining major advances in both the theory and practice of Byzantine Fault Tolerance. The PBFT conference version, journal version, Castro’s thesis, Liskov’s talk, and follow-up work on BASE are all required reading for anyone who wants to deeply understand BFT systems.
[Read More]
From Single-Shot Agreement to State Machine Replication
In this post we explore the path from Single-Shot Agreement, via Write-Once Registers, to Log Replication, and finally to State Machine Replication. We begin by defining all four problems assuming minority omission failures and partial synchrony. This post continues our previous posts on Paxos from Recoverable Broadcast and on State Machine Replication.
[Read More]
On Paxos from Recoverable Broadcast
There are many ways to learn about the Paxos protocol (see Lampson, Cachin, Howard, Howard 2, Guerraoui, Kladov, Krzyzanowski, Lamport, Wikipedia and many more). The emphasis of this post is on a decomposition of Paxos for omission failures that will later help when we do a similar decomposition for Byzantine failures (for PBFT and HotStuff).
[Read More]
Provable Broadcast
We explore a family of broadcast protocols in the authenticated setting in which a designated sender wants to create a delivery-certificate of its input value. After describing the base protocol we call Provable Broadcast ($PB$), we explore the surprising power of simply running $PB$ two times in a row, then three times, and finally four times in a row.
[Read More]
What is a Blockchain?
TLDR: a Blockchain is a trusted coordination mechanism;
[Read More]
Dining Cryptographers and the additivity of polynomial secret sharing
David Chaum’s dining cryptographer problem is a pioneering work on the foundations of privacy. It shows the amazing power of information-theoretic Secure Multi Party Computation. The original paper from 1988 is super accessible and fun to read. Many systems in the last 20 years for anonymity and privacy-preserving communication are based on the Dining Cryptographers problem. Herbivore, Dissent, Riposte, Blinder, and many others.
[Read More]
The BGW Verifiable Secret Sharing Protocol
In this post, we present the classic Ben-or, Goldwasser, and Wigderson, 1988 (BGW) Verifiable Secret Sharing protocol (VSS) with the simplifications of Feldman, 1988. The analysis and notation in this post are based on the full proof of the BGW MPC protocol of Asharov and Lindell. This post is a continuation of our previous posts on secret sharing for passive and crash failures.
[Read More]
Polynomial Secret Sharing with crash failures
We continue our series on polynomial secret sharing. In the previous post of this series we discussed secret sharing with a passive adversary. In this post we assume crash failures and in later posts we extend to malicious failures. As before, we must assume parties have private channels: the adversary cannot see the content of messages sent between two non-faulty parties.
[Read More]
A new Dolev-Reischuk style Lower Bound
In a previous post we discussed Crusader Broadcast and showed a $O(n^2)$ words, $O(1)$ time solution for $f<n$ and assuming a PKI. In this post, we overview a new Dolev-Reischuk style bower bound (see our full paper):
[Read More]
He-HTLC - Revisiting Incentives in HTLC
Hashed Time-locked Contracts (HTLC) find many useful applications in the L2 Layer such as the lightning network and atomic swaps. In this post, we will focus on discussing protocols for implementing HTLC when taking into consideration incentives for parties in the system. We will discuss a line of work — WHF’19, MAD-HTLC, He-HTLC — towards developing an HTLC protocol secure in the presence of rational parties.
[Read More]
DAG Meets BFT - The Next Generation of BFT Consensus
This post explains in simple words a recent development in the theory and practice of directed acyclic graph-based (DAG-based) Byzantine Fault Tolerance (BFT) consensus, published in three prestigious peer-reviewed conferences, and currently being implemented by several Blockchain companies, e.g., Aptos, Celo, Mysten Labs, and Somelier.
[Read More]
Safe Permissionless Consensus
Nakamoto’s consensus protocol works in a permissionless model, where nodes can join and leave without notice. However, it guarantees agreement only probabilistically. Is this weaker guarantee a necessary concession to the severe demands of supporting a permissionless model?
[Read More]
Crusader Broadcast
In previous posts we showed that the classic Dolev-Strong broadcast protocol takes $O(n^3)$ words and $t+1$ rounds and that Dolev Reischuk show that $\Omega(n^2)$ is needed and it is also known that $t+1$ rounds are needed. So while the number of rounds is optimal, to this day it remains an open question of obtaining $O(n^2)$ broadcast against a strongly adaptive adversary (see post for recent progress).
[Read More]
Phase-King through the lens of Gradecast: A simple unauthenticated synchronous Byzantine Agreement protocol
In this post we overview a simple unauthenticated synchronous Byzantine Agreement protocol that is based on the Phase-King protocol of Berman, Garay, and Perry 1989-92. We refer also to Jonathan Katz’s excellent write-up on this same protocol from 2013. We offer a modern approach that decomposes the Phase-King protocol into a Graded Consensus building block.
[Read More]
Approximate Agreement: definitions and the robust midpoint protocol
This post covers the basics of Approximate Agreement. We define the problem, explain in what way its an interesting variation of classic Agreement, and describe the idea behind the robust midpoint protocol.
[Read More]
Asynchronous Agreement Part 5: Binary Byzantine Agreement from a strong common coin
In this post we show how to use Binding Crusader Agreement from the previous post, along with a strong common coin to get a simple and efficient Binary Byzantine Agreement with only an expected $O(n^2)$ message complexity. This is a simplified version from our paper.
[Read More]
Asynchronous Agreement Part 4: Crusader Agreement and Binding Crusader Agreement
In this post we introduce a key building block in the Byzantine Model called Binding Crusader Agreement. We show how to use it in the next post. This is a simplified version extracted from our paper.
[Read More]
Asynchronous Agreement Part Three: a Modern version of Ben-Or's protocol
In this series of posts, we explore the marvelous world of consensus in the Asynchronous model. In this third post, we present a modern version of Ben-Or’s classic protocol that is part of our new work on Asynchronous Agreement. In the first post we defined the problem and in the second post we presented Ben-Or’s protocol. This is a simplified version extracted from our paper.
[Read More]