Simplex is a recent partially synchronous Byzantine Fault Tolerant (BFT) protocol that is gaining popularity. We take this opportunity to rehash several classic results in the Simplex style. The first post explained the key difference between Simplex and Tendermint. This second post is on 2-round BFT. The next post will explore protocols that integrate concurrent 2-round and 3-round paths.
[Read More]
From Tendermint to Simplex
Simplex is a partially synchronous Byzantine Fault Tolerant (BFT) protocol designed by Ben Chan and Rafael Pass in 2023. It is being incorporated by Commonware library and (with modifications) by Solana. It is a simple and clean protocol, especially for beginners, and Ben did a great job explaining it from scratch. But if you are already familiar with other BFT protocols such as PBFT or Tendermint, you may be wondering...
[Read More]
Reasoning about Distributed Protocols with Smart Casual Verification
Here at decentralized thoughts, we spend a lot of time reasoning about distributed protocols. Often, we focus on solving distributed consensus, personally it’s my favorite CS problem, but it’s also famously one of the most difficult and subtle problems in distributed computing. Reasoning about distributed algorithms is hard at the best of times, with state split across remote nodes, asynchrony, concurrency, and non-determinism in the order that events, such as...
[Read More]
Verifiable Multi-Exponentiation and Multi-Scalar Multiplication (MSM)
Multi-exponentiations and multi-scalar multiplications (MSMs) are computations that are widely used in cryptographic proof systems, mostly in proof generation and proof verification. This note outlines an efficient method for verifying the results of these computations, which opens the door to outsourcing them. In particular, by employing this technique it is possible to have the prover in a cryptographic proof system perform a significant portion of the computation that is usually...
[Read More]
Practical Byzantine Fault Tolerant Consensus (PBFT)
In this post, we will present (a variant of) PBFT, which is the first practical solution to Byzantine fault tolerant state machine replication under partial synchrony. The protocol follows the key ideas presented in the previous post on partial synchrony.
[Read More]
Key Principles Underlying Partial Synchrony BFT
Many blockchain protocols work under partial synchrony. Examples include PBFT, SBFT, Cosmos (Tendermint), Diem (DiemBFT), Jolteon, Espresso Systems (HotStuff), Dfinity (Internet Computer Consensus) and Ethereum (Casper).
[Read More]
Agreement against strongly adaptive adversaries needs quadratic communication
In this post, we prove a result of Abraham, Hubert Chan, Dolev, Nayak, Pass, Ren, Shi, 2019 showing that:
[Read More]
Multi-world Validated Asynchronous Byzantine Agreement
In this post, we show how to solve Validated Asynchronous Byzantine Agreement using the multi-world VABA approach from Abraham, Malkhi, and Spiegelman 2018.
[Read More]
Living with asynchrony and eventually reaching agreement by combining binding and randomness
The prevailing view on fault-tolerant agreement is that it is impossible in asynchrony for deterministic protocols, but adding randomization solves the problem. This statement is confusing in two aspects:
[Read More]
Divide and Conquer in Distributed Computing - synchronous BFT with quadratic communication via recursive phase king
The idea of decomposing a hard problem into easier problems is a fundamental algorithm design pattern in Computer Science. Divide and Conquer is used in so many domains: sorting, multiplication, and FFT, to mention a few. But what about distributed computing?
[Read More]
HotStuff-1 and the Prefix Speculation Dilemma in BFT Consensus
Several approaches aim to reduce the number of network hops to reach finality in BFT Consensus protocols through speculation. They differ in their methods and in their guarantees, yet they all face a common phenomenon referred to as the prefix speculation dilemma.
[Read More]
The SAP theorem for storing secret keys
Public key cryptography (PKC) is a fundamental technology that is a key enabler to the Internet and the whole client-server paradigm. Without public key cryptography, the modern Internet economy, from cryptocurrencies to online banking and retail, would simply not exist.
[Read More]
What is Verifiable Information Dispersal?
Verifiable Information Dispersal (or VID) has its roots in the work of Michael Rabin, 1989 which introduced the notion of Information Dispersal (ID). Adding verifiability (referred to as binding in this post) to obtain VIDs was done by Garay, Gennaro, Jutla, and Rabin, 1998 (called SSRI). Cachin and Tessaro, 2004 introduced the notion of Asynchronous VID (or AVID). See LDDRVXG21 for the state-of-the-art.
[Read More]
Shoal++: High Throughput DAG-BFT Can Be Fast!
TL;DR: Shoal++ is a novel DAG-BFT system that supercharges Shoal to achieve near-optimal theoretical latency while preserving the high throughput and robustness of state-of-the-art certified DAG BFT protocols.
[Read More]
Sailfish: Improving the Latency of DAG-based BFT
In this blog post, we will explain the core ideas behind Sailfish, a latency-efficient DAG-based protocol. In essence, Sailfish is a reliable-broadcast (RBC) based DAG protocol that supports leaders in every RBC round. It commits leader vertices within 1RBC + $\delta$ time and non-leader vertices within 2RBC + $\delta$ time, outperforming the state-of-the-art in terms of these latencies (where $\delta$ represents the actual network delay).
[Read More]
Decentralization of Ethereum Builder Market
Decentralization is a core underpinning of blockchains. Is today’s blockchain really decentralized?
[Read More]
Consensus with One Mobile Crash in Synchrony or One Crash in Asynchrony Has Infinite Executions
TL;DR: We give a simple, unified proof that consensus with one mobile crash in synchrony, or one crash in asynchrony, inevitably admits infinite executions. The proof uses a single reduction to a mobile delay adversary, a weaker but expressive fault model and then shows that every consensus protocol resilient to it must fail to terminate. This approach streamlines the classic FLP83 and SW89 results and highlights the close connection between...
[Read More]
In between Crash and Omission failures
In this post we explore adversary failure models that are in between crash and omission:
[Read More]
Early Stopping, Same but Different: Two Rounds Are Needed Even in Failure Free Executions
TL;DR: Even in failure-free executions, consensus protocols resilient to crash failures often require at least two rounds. This follows from the early stopping lower bound: executions with $f$ actual crashes require at least $\min {f+2, t+1}$ rounds when tolerating $t$ possible failures. Thus, the possibility of a failure forces extra rounds, even when no failures occur.
[Read More]
Gather with Binding and Verifiability
We extend the Gather protocol with two important properties: Binding and Verifiability. This post is based on and somewhat simplifies the information theoretic gather protocol in our recent ACS work with Gilad Asharov and Arpita Patra.
[Read More]