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.

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]

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

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

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

Simpler Security proof for Nakamoto Consensus

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 Feng at UBC and Dongning Guo at Northwestern – identified very subtle flaws in the proof, and clever mathematical maneuvers... [Read More]

The Fast Fourier Transform over finite fields

The Fast Fourier Transform (FFT) developed by Cooley and Tukey in 1965 has its origins in the work of Gauss. The FFT, its variants and extensions to finite fields, are a fundamental algorithmic tool and a beautiful example of interplay between algebra and combinatorics. There are many great resources on FFT, see ingopedia’s curated list. [Read More]
Tags: math

Asynchronous Agreement on a Core Set

A challenging step in many asynchronous protocols is agreeing on a set of parties that completed some task. For example, an asynchronous protocol might start off with parties reliably broadcasting a value. Due to asynchrony and having $\leq f$ corruptions, honest parties can only wait for $n-f$ parties to complete the task. Parties may need to agree on a core set of $n-f$ such broadcasts and use them in the... [Read More]

Can we Obtain Privacy in a Private Proof-of-Stake Blockchain? Part-I

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 second part focuses on potential workarounds using differential privacy. These posts explain the intuitive ideas behind the works of Madathil... [Read More]

Blockchains + TEEs Day 2 Summary

This is the second of the two part post on the workshop on Blockchains + TEEs that concluded last week. Here are the key ideas from Day 2. You can find the post summarizing Day 1 here. [Read More]
Tags: blockchain

Blockchains + TEEs Day 1 Summary

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. [Read More]
Tags: blockchain

Randomization and Consensus - synchronous binary agreement for minority omission failures

Continuing the series on simple ways where randomization can help solve consensus. The model is lock-step (synchrony) with $f<n/2$ omission failures. We know that in the worst case reaching agreement takes at least $f+1$ rounds. Can randomization help reduce the expected number of rounds? In the post, we show a simple randomized consensus algorithm including a simple weak coin protocol that works against a weak adaptive adversary. [Read More]

Randomization and Consensus - synchronous binary agreement for crash failures with a perfect common coin

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: [Read More]