In a previous post, we show that State Machine Replication for any $f<n$ failures is possible in the synchronous model when the adversary can only cause parties to crash. In this post, we show that omission failures are more challenging. Implementing SMR requires at most $f<n/2$ omission failures, even in...| decentralizedthoughts.github.io
In addition to limiting the adversary via a communication model synchrony, asynchrony, or partial synchrony, we need a way to limit the adversary’s power to corrupt parties. Power tends to corrupt, and absolute power corrupts absolutely. – John Dalberg-Acton 1887 As John observed almost 150 years ago, if the adversary’s...| decentralizedthoughts.github.io
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. In the three previous posts we (1) defined the problem and discussed the FLP...| decentralizedthoughts.github.io
We continue to explore the marvelous world of consensus in the Asynchronous model. In this post, we present Ben-Or’s classic protocol from 1983. In the next post, we will present a more modern version that is a simplified version from our paper. In the previous post we defined the problem...| decentralizedthoughts.github.io
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: Validity: If the broadcaster is non-faulty then eventually all non-faulty parties...| decentralizedthoughts.github.io
In this third post, we conclude with the celebrated Fischer, Lynch, and Paterson impossibility result from 1985. It is the fundamental lower bound for consensus in the asynchronous model. Theorem 1 (FLP85): Any protocol $\mathcal{P}$ solving consensus in the asynchronous model that is resilient to even just one crash failure...| decentralizedthoughts.github.io
Post updated in March 2021 Different modeling assumptions under which we construct BFT protocols often make it hard to compare two protocols and understand their relative contributions. In this post we discuss synchronous protocols in the authenticated model (assuming a PKI). A protocol runs in the synchronous model if it...| decentralizedthoughts.github.io
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. {% for post in paginator.posts %} {{ post.title }} {% if post.subtitle %} {{ post.subtitle }}...| decentralizedthoughts.github.io
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. DAG-Rider: All You Need Is...| decentralizedthoughts.github.io
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. In this model, agreement concerns only non-faulty parties. Omission-faulty parties may disagree, and validity is weak: the output must equal some party’s input....| Decentralized Thoughts
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. In this post, we highlight six key...| Decentralized Thoughts
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. We then extend the result to $n=3f+2p-1$ for $0<p\leq f$ that obtains liveness for...| decentralizedthoughts.github.io
In this series of three posts, we discuss two of the most important consensus lower bounds: Lamport, Fischer [1982]: any protocol solving consensus in the synchronous model that is resilient to $t$ crash failures must have an execution with at least $t+1$ rounds. Fischer, Lynch, and Patterson [1983, 1985]: any...| decentralizedthoughts.github.io
We all broadly understand “consensus” as the notion of different parties agreeing with each other. In distributed computing, Consensus is one of the core functionalities. In this post, we define the consensus problem and discuss some variants and their differences. In modern parliaments, the passing of decrees is hindered by...| decentralizedthoughts.github.io
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...| decentralizedthoughts.github.io
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...| decentralizedthoughts.github.io
In this post, we highlight an amazing result: Shamir’s secret sharing scheme. This is one of the most powerful uses of polynomials over a finite field in distributed computing. Intuitively, this scheme allows a $Dealer$ to commit to a secret $s$ by splitting it into shares distributed to $n$ parties....| decentralizedthoughts.github.io
In a previous post we covered the basics of Asynchronous Verifiable Information Dispersal (AVID) and the classic AVID of Cachin and Tessaro, 2004. That protocol allows a sender to disperse a message of $O(n\log n)$ bits at a cost of just $O(n^2 \log^2 n)$ bits. However, It incurs a $O(\log...| Decentralized Thoughts
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. A new parameter $p$...| Decentralized Thoughts
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. Recall that a group is a non-empty set $G$ and a...| Decentralized Thoughts
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...| decentralizedthoughts.github.io
Proof of Work (PoW) Blockchains implement a form of State Machine Replication (SMR). Unlike classical SMR protocols, they are open, i.e., anyone can join the system, and the system incentivizes participants, called miners, to follow the protocol. Therefore, unlike classical SMR protocols, reasoning about blockchain security relies not only on...| decentralizedthoughts.github.io
Bitcoin’s underlying consensus protocol, now known as Nakamoto consensus, is an extremely simple and elegant solution to the Byzantine consensus problem. One may expect this simple protocol to come with a simple security proof. But that turns out not to be the case. The Bitcoin white paper did not provide...| decentralizedthoughts.github.io
Guest post by Zhuolun Xiang In the previous post, we presented a summary of our good-case latency results for Byzantine broadcast and Byzantine fault tolerant state machine replication (BFT SMR), where the good case measures the latency to commit given that the leader/broadcaster is honest. In this post, we describe...| decentralizedthoughts.github.io
Guest post by Zhuolun Xiang State Machine Replication and Broadcast Many existing permission blockchains are built using Byzantine fault-tolerant state machine replication (BFT SMR), which ensures all honest replicas agree on the same sequence of client inputs. Most of the practical solutions for BFT SMR are based on the Primary-Backup...| decentralizedthoughts.github.io
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...| decentralizedthoughts.github.io
If anyone asks you: how can I scale my State Machine Replication (Blockchain) system? You should answer back with a question: what is your bottleneck? Is it Data, Consensus or Execution? Data: Shipping the commands to all the replicas. For example, if a block contains 1MB of commands, then you...| decentralizedthoughts.github.io
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...| decentralizedthoughts.github.io
In this post, we will demystify Merkle trees using three examples of problems they solve: Maintaining integrity of files stored on Dropbox.com, or file outsourcing, Proving a transaction between Alice and Bob occurred, or set membership, Transmitting files over unreliable channels, or anti-entropy. $$ \def\mht{\mathsf{MHT}} \def\mrh{h_{\mathsf{root}}} \def\vect#1{\boldsymbol{\vec{#1}}} $$ By the...| decentralizedthoughts.github.io
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...| decentralizedthoughts.github.io
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...| decentralizedthoughts.github.io
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...| decentralizedthoughts.github.io
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...| decentralizedthoughts.github.io
In this series of posts, we explore the marvelous world of consensus in the Asynchronous model. In this post, we start by simply defining the problem. Recall the FLP theorem: FLP theorem 1985: Any protocol where no two non-faulty parties decide different values in the asynchronous model that is resilient...| decentralizedthoughts.github.io
In this second post, we show the fundamental lower bound on the number of rounds for consensus protocols in the synchronous model. Theorem: Any protocol solving consensus in the synchronous model for $n$ parties that is resilient to $n-2 \geq t \geq 1$ crash failures must have an execution with...| decentralizedthoughts.github.io
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...| Decentralized Thoughts
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. Setting There are $n$ parties, at most $t<n/3$ of them...| Decentralized Thoughts
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). In this post, we discuss key principles behind the design of partially synchronous blockchain protocols. These principles, in some form, apply to all of...| decentralizedthoughts.github.io
In this post, we prove a result of Abraham, Hubert Chan, Dolev, Nayak, Pass, Ren, Shi, 2019 showing that: Theorem: Any broadcast protocol in synchrony that is resilient to $f$ strongly adaptive omission failures and has less than $1/8$ probability of error must have an expected communication of at least...| decentralizedthoughts.github.io
In this post, we show how to solve Validated Asynchronous Byzantine Agreement via the multi-world VABA approach of Abraham, Malkhi, and Spiegelman 2018. What is Validated Asynchronous Byzantine Agreement? Given $n$ parties, and at most $f<n/3$ of them can be malicious (this is the optimal ratio for consensus with asynchronous...| Decentralized Thoughts
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: The FLP result says that any protocol, even a randomized protocol, must have a non-terminating execution where every configuration is bivalent...| decentralizedthoughts.github.io
After we fix the communication model, synchrony, asynchrony, or partial synchrony, and a threshold adversary we still have 5 important modeling decisions about the adversary power: The type of corruption (passive, crash, omission, or Byzantine). The computational power of the adversary (unbounded, computational, or fine-grained). The adaptivity of the adversary...| decentralizedthoughts.github.io
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? In this post we will highlight how divide and...| Decentralized Thoughts
We continue our series of posts on State Machine Replication (SMR). In this post we discuss the most simple form of SMR: Primary-Backup for crash failures. We will assume synchronous communication. For simplicity, we will consider the case with two replicas, out of which one can crash. Recall that when...| decentralizedthoughts.github.io
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. This post explains three principal speculation approaches and...| decentralizedthoughts.github.io
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. In the PKC paradigm with clients and servers, clients authenticate to servers...| decentralizedthoughts.github.io
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...| decentralizedthoughts.github.io
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. We evaluated Shoal++ against state-of-the-art DAG BFT protocols, such as Bullshark and Shoal — as well as a concurrent DAG effort, Mysticeti...| decentralizedthoughts.github.io
In a consensus protocol parties have an input (at least two possible values, say 0 or 1) and may output a decision value such that: Uniform Agreement: all decision values are the same. Validity: if all inputs are the same, then this is the output value. The third property is...| decentralizedthoughts.github.io
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,...| decentralizedthoughts.github.io
In this post we explore adversary failure models that are in between crash and omission: Send Omissions (SO): the adversary can corrupt a party and decide to block any message that the party sends. The corrupted party is not aware that it is corrupted or that the message it wanted...| decentralizedthoughts.github.io
Many systems try to optimize executions that are failure free. If we absolutely knew that there will be no failures, parties could simply send each other messages with our inputs and reach consensus by outputting, say, the majority value. Thus completing the protocol after one round. What happens if there...| decentralizedthoughts.github.io
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. Recall that we are in an asynchronous model, assuming $f<n/3$, with at most $f$...| decentralizedthoughts.github.io
In the standard distributed computing model, the communication uncertainty is captured by an adversary that can control the message delays. The communication model defines the limits to the power of the adversary to delay messages. There are three basic communication models: the Synchronous model, the Asynchronous model, and the Partial...| decentralizedthoughts.github.io
Four years ago (time flies!), I made a post on a simple security proof for Nakamoto consensus. While the proof intuition, as outlined in that post, is still reasonably simple, the actual proof has become quite delicate and crafty over the years. What happened was that some colleagues – Chen...| decentralizedthoughts.github.io
A few years ago if you asked “Can blockchains scale?” most people would give three reasons why, fundamentally, the answer is “No!” Data: every transaction needs to be replicated by every miner (validator). So increasing security by adding more validators inherently causes more replication. Having $n$ validators implies that your...| decentralizedthoughts.github.io
This is Part-II of a two-part post on privacy in private proof-of-stake blockchains. In Part-I, we explored attacks on existing private PoS approaches. In this post, we will discuss some ways to obtain privacy (at the expense of safety and/or liveness). A Three-Way Trade-Off between Safety, Liveness, and Privacy Madathil...| decentralizedthoughts.github.io
In this two-part post, we focus on the challenges and subtleties involved in obtaining privacy in private proof-of-stake (PoS) blockchains. For instance, designs that attempt to obtain privacy for transaction details while still relying on PoS, such as Ouroboros Crypsinous. The first part explains attacks on existing approaches, and the...| decentralizedthoughts.github.io
In 1999, Fox and Brewer published a paper on the CAP principle, where they wrote: Strong CAP Principle. Strong Consistency, High Availability, Partition-resilience: Pick at most 2. At PODC 2000, Brewer gave an invited talk where he popularized the CAP theorem (an unproven conjecture at the time), which was later...| decentralizedthoughts.github.io
Our workshop on Blockchains + TEEs concluded last week. We had a fantastic series of talks and discussions on both days of the workshop. In this two part post, we highlight some key takeaways from each of the days. Natacha Crooks: In Trusted BFT Components, we (Mostly?) Trust In her...| decentralizedthoughts.github.io
We recently published our work HotStuff-2 on eprint, introducing a two-phase HotStuff variant which simultaneously achieves $O(n^2)$ worst-case communication, optimistically linear communication, a two-phase commit regime within a view, and optimistic responsiveness in partially-synchronous BFT. The main takeaway is that two phases are enough for BFT after all. In this...| decentralizedthoughts.github.io
What is the simplest setting where randomization can help solve consensus? Assume lock-step (synchrony) with $f<n$ crash failures. We know that in the worst case reaching agreement takes at least $f+1$ rounds. This lower bound holds even if the protocol is randomized so the natural question is: Can randomization help...| decentralizedthoughts.github.io