Decentralized Thoughts is a group blog on decentralization, by decentralized thinkers, for decentralized thoughts, of decentralized matters. Decentralized Thoughts is a group blog on decentralization, by decentralized thinkers, for decentralized thoughts, of decentralized matters.

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]
Tags: consensus BFT

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]
Tags: VID

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]
Tags: math

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]
Tags: consensus

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]
Tags: consensus

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]
Tags: cryptography

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]
Tags: consensus101

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]
Tags: consensus

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]
Tags: VID

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]