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 via the multi-world VABA approach of 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]
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]
Decentralization of Ethereum Builder Market
Decentralization is a core underpinning of blockchains. Is today’s blockchain really decentralized?
[Read More]
Consensus with One Mobile Crash in Synchrony or One Crash in Asynchrony Must Have Infinite Executions
In a consensus protocol, parties have an input (with at least two possible values, such as 0 or 1) and must output a decision value that satisfies the following properties:
[Read More]
In between Crash and Omission failures
In this post we explore adversary failure models that are in between crash and omission:
[Read More]
Early Stopping is same but different: two rounds are needed even in failure free executions
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 may be a crash failure? Say you have 100 servers and at most one can crash, can you devise a...
[Read More]
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]
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]
Scaling Blockchains: the Power of Batching
A few years ago if you asked “Can blockchains scale?” most people would give three reasons why, fundamentally, the answer is “No!”
[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]