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.

## 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]

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

## 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 Gradecast building block. [Read More]
Tags: dist101

## 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]

## EIP-1559 In Retrospect

On August 5, 2021, Ethereum implemented Ethereum Improvement Proposal 1559 (EIP-1559) on its mainnet as part of the London Hardfork, which modified the transaction fee mechanism on Ethereum from a first price auction to one that involves blocks of varying sizes, separating transaction fees as history-dependent base fees and tips, and burning of the base fees. How does such a mechanism fare in practice? [Read More]

## Colordag: From always-almost to almost-always 50% selfish mining resilience

The Selfish mining attack against blockchain protocols was discovered and formalized in 2013 by Eyal and Sirer (also see our blog post). The Bitcoin community has mentioned similar types of attacks in 2010. This attack remains a vulnerability of all operational blockchains we are aware of. For Bitcoin’s blockchain algorithm (under reasonable network assumptions), a coalition controlling over 1/4 of the mining power can improve its revenue using this attack.... [Read More]

## Blockchain Resource Pools and a CAP-esque Impossibility Result

The consensus layers of different blockchain protocols can look very different from one another. For example, to achieve sybil-resistance, some protocols use proof-of-work (selecting each block producer randomly, with probability proportional to its computational power), while some use proof-of-stake (with probabilities proportional to the amount of locked-up stake). To achieve consensus, some blockchain protocols use a longest-chain rule to resolve forks in-protocol, while others use BFT-style consensus to (with high... [Read More]

## Good-case Latency of Rotating Leader Synchronous BFT

Synchronous consensus protocols can tolerate $f &lt; n/2$ Byzantine failures but for $n/3 &lt;f &lt;n/2$ must depend on the maximum network delay $\Delta$ for their safety and progress. So these protocols must set $\Delta$ to be much larger than the actual network delay $\delta \ll \Delta$. The good news is in the multi-shot (blockchain) scenarios, modern synchronous protocols such as Sync HotStuff can essentially pipeline the $\Delta$-dependent delay: [Read More]

## Consensus cheat sheet

Crash Omission Byzantine Synchrony $f&lt;n$ is possible $f+1$ round executions must exist $f \geq n/2$ is impossible $f&lt;n/2$ possible with PKI / PoW $f \geq n/3$ impossible without PKI/PoW Partial Synchrony $f \geq n/2$ is impossible $f&lt;n/2$ is possible $f&lt;n/3$ is possible $f \geq n/3$ is impossible Asynchrony non terminating executions must exist $f&lt;n/2$ possible in $O(1)$ expected $f&lt;n/3$ possible in $O(1)$ expected [Read More]
Tags: dist101

## Nakamoto's Longest-Chain Wins Protocol

In this post, we will cover Nakamoto’s Consensus protocol presented in the Bitcoin whitepaper. There are a lot of posts and videos that explain this seminal and simple protocol. Our goal in this post will be to intuitively piece out the need for different aspects of the protocol, such as proof-of-work and how network synchrony plays a role in the protocol. [Read More]

## Crusader Agreement with $\leq 1/3$ Error is Impossible for $n\leq 3f$ if the Adversary can Simulate

The classic FLM lower bound says that in Synchrony, Byzantine Agreement is impossible when $n \leq 3f$. We discussed this important bound in a previous post. In this post we strengthen the FLM lower bound in two important ways: Maybe randomization allows circumventing the FLM lower bound? No! Even allowing $\leq 1/3$ error, this bound still holds (based on unpublished work of Yao and Karlin, see the work of Graham... [Read More]

## Distributed consensus made simple (for real this time!)

Multi-Paxos is the de facto solution for deciding a log of commands to execute on a replicated state machine, yet it’s famously difficult to understand, motivating the switch to ‘simpler’ consensus protocols such as Raft. The conventional wisdom is that the best way to use Paxos (aka Synod, or single-shot Paxos), to decide a log of commands is to run many instances of it, where the $i^{th}$ instance decides the... [Read More]
Tags: dist101 paxos