We continue our series on polynomial secret sharing. In the previous post of this series we discussed secret sharing with a passive adversary. In this post we assume crash failures and in later posts we will extend to malicious failures. As before, we must assume parties have private channels: the adversary cannot see the content of messages sent between two non-faulty parties.
[Read More]
A new Dolev-Reischuk style Lower Bound
In a previous post we discussed Crusader Broadcast and showed a $O(n^2)$ words, $O(1)$ time solution for $f<n$ and assuming a PKI. In this post, we overview a new Dolev-Reischuk style bower bound (see our full paper):
[Read More]
He-HTLC - Revisiting Incentives in HTLC
Hashed Time-locked Contracts (HTLC) find many useful applications in the L2 Layer such as the lightning network and atomic swaps. In this post, we will focus on discussing protocols for implementing HTLC when taking into consideration incentives for parties in the system. We will discuss a line of work — WHF’19, MAD-HTLC, He-HTLC — towards developing an HTLC protocol secure in the presence of rational parties.
[Read More]
DAG Meets BFT - The Next Generation of BFT Consensus
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.
[Read More]
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]
Crusader Broadcast
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]
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]
Approximate Agreement: definitions and the robust midpoint protocol
This post covers the basics of Approximate Agreement. We define the problem, explain in what way its an interesting variation of classic Agreement, and describe the idea behind the robust midpoint protocol.
[Read More]
Asynchronous Agreement Part 5: Binary Byzantine Agreement from a strong common coin
In this post we show how to use Binding Crusader Agreement from the previous post, along with a strong common coin to get a simple and efficient Binary Byzantine Agreement with only an expected $O(n^2)$ message complexity. This is a simplified version from our paper.
[Read More]
Asynchronous Agreement Part 4: Crusader Agreement and Binding Crusader Agreement
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.
[Read More]
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]
Asynchronous Agreement Part Two: Ben-Or's protocol
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.
[Read More]
Asynchronous Agreement Part One: Defining the problem
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:
[Read More]
Consensus by Dfinity - Part I
This is part one of a two-part post on consensus protocols published by the Dfinity Foundation.
[Read More]
Consensus by Dfinity - Part II (Internet Computer Consensus)
This post is part two of a two-part post on consensus protocols published by the Dfinity Foundation; you can find part one here. This post will intuitively explain the Internet Computer Consensus.
[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 < n/2$ Byzantine failures but for $n/3 <f <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<n$ is possible $f+1$ round executions must exist $f \geq n/2$ is impossible $f<n/2$ possible with PKI / possible with PoW FLM: $f \geq n/3$ impossible without PKI/PoW Partial Synchrony CAP: $f\geq n/2$ is impossible Paxos: $f<n/2$ is possible $f<n/3$ is possible DLS: $f \geq n/3$ is impossible Asynchrony FLP: non-terminating executions must exist $f<n/2$ possible in $O(1)$ expected rounds $f<n/3$ possible in $O(1)$ expected...
[Read More]