In this post, we study non-uniform agreement and weak validity under synchronous networks with general omission failures, where faulty parties may lose both incoming and outgoing messages.
[Read More]
What’s DAG got to do with it?
Since 2018, blockchain research has seen a surge in DAG-based BFT protocols aimed at achieving higher throughput. These protocols trace back to Hashgraph, 2018, Aleph, 2019, the theoretical work of All You Need is DAG, 2021, and systems papers like Narwhal and Bullshark.
[Read More]
2-round BFT in Simplex style for n=5f-1
In our previous post, we described a 2-round partially synchronous BFT protocol for $n = 5f+1$. In this follow-up post, we push the bound to $n = 5f-1$, achieving optimal 2-round commit in the Simplex style.
[Read More]
Graded dispersal with perfect security
In a previous post we covered the basics of Asynchronous Verifiable Information Dispersal (AVID) and the classic AVID of Cachin and Tessaro, 2004.
[Read More]
Concurrent 2-round and 3-round Simplex-style BFT
In the last two posts, we presented two partially synchronous BFT protocols in the Simplex-style: a 3-round protocol with $n\geq3f+1$ and a 2-round protocol with $n\geq 5f+1$. In this post, we describe a protocol that runs a 2-round commit rule and a 3-round commit rule concurrently.
[Read More]
Lagrange's Theorem through the algorithmic lens
Groups lie at the heart of many cryptographic constructions. In this post, we revisit the classic Lagrange’s theorem through a more algorithmic lens. Largange’s theorem is a simple structure theorem that will be useful for many more advanced results.
[Read More]
An Analysis of Latency and Block Capacity in Nakamoto Consensus
Achieving high throughput is essential for blockchain ecosystems to become competitive alternatives to their centralized counterparts across a wide range of domains. For example, high-frequency trading on decentralized platforms cannot be competitive unless transaction processing times are reduced to well below one second. The predominant strategy to address this challenge has been the development of Layer 2 (L2) scaling solutions. However, this approach often introduces trade-offs, potentially compromising decentralization and,...
[Read More]
2-round BFT in Simplex style
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 there would be no cryptocurrencies, no online bank accounts, no online retail, etc.
[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]