This is a re-exposition of a post here by Dan Boneh, Ben Fisch, Ariel Gabizon, and Zac Williamson, with a few more details on why the polynomial relations hold.
[Read More]
Blockchain Selfish Mining
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 bounding the number of malicious participants. One should crucially ask whether miners are indeed incentivized to follow the prescribed protocol....
[Read More]
Dolev-Strong Authenticated Broadcast
This post is about the classic result from 1983 on authenticated broadcast against a Byzantine adversary:
[Read More]
The FLP Impossibility, Asynchronous Consensus Lower Bound via Uncommitted Configurations
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.
[Read More]
Synchronous Consensus Lower Bound via Uncommitted Configurations
In this second post, we show the fundamental lower bound on the number of rounds for consensus protocols in the synchronous model.
[Read More]
Consensus Lower Bounds via Uncommitted Configurations
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 protocol solving consensus in the asynchronous model that is resilient to even one crash failure must have an infinite execution....
[Read More]
Data, Consensus, Execution: Three Scalability Bottlenecks for State Machine Replication
If anyone asks you: how can I scale my State Machine Replication (Blockchain) system?
[Read More]
Security proof for Nakamoto Consensus
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 a proof. Several academic papers (e.g. Garay, Kiayias, Leonardos, and Pass, Seeman, shelat and Kiffer, Rajaraman, shelat) later presented rigorous...
[Read More]
Sync HotStuff, A Simple and Practical State Machine Replication
In the previous post, we discussed progress in authenticated synchronous consensus protocols. In this post, we will discuss one of the recent protocols Sync HotStuff, which is a simple and practical Byzantine Fault Tolerant SMR protocol to tolerate $f < n/2$ faults.
[Read More]
Authenticated Synchronous BFT
Post updated in March 2021
[Read More]
State Machine Replication for Two Servers and One Omission Failure is Impossible even in a lock-step model
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 synchrony.
[Read More]
Primary-Backup State Machine Replication for Crash Failures
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 a party crashes, it irrevocably terminates.
[Read More]
A Payment Channel is a two person BFS-SMR system
This posts views payment channels as essentially a two person BFS-SMR system along with a carefully implemented mechanism for safe termination (channel closing) under assumptions of synchrony.
[Read More]
Flavours of State Machine Replication
State Machine Replication is a fundamental approach in distributed computing for building fault tolerant systems. This post is a followup to our basic post on Fault Tolerant State Machine Replication.
[Read More]
Flavours of Broadcast
What is the difference between broadcast, crusader broadcast, gradecast, weak broadcast, detectable broadcast, and broadcast with abort? This post is a follow up to our basic post on: What is Broadcast?
[Read More]
Consensus for State Machine Replication
We introduced definitions for consensus, Byzantine Broadcast (BB) and Byzantine Agreement (BA), in an earlier post. In this post, we discuss how consensus protocols are used in State Machine Replication (SMR), a fundamental approach in distributed computing for building fault-tolerant systems. We compare and contrast this setting to that of traditional BB and BA. A follow-up post discusses the reductions from one abstraction to the other in the omission failure...
[Read More]
Flavours of Partial Synchrony
This is a follow-up post to the post on Synchrony, Asynchrony and Partial synchrony. The partial synchrony model of DLS88 comes in two flavors: GST and Unknown Latency. In this post we discuss:
[Read More]
Dont Trust. Verify. and Checkpoint?
Imagine that that Aliens land on earth with a new superfast SHA256 machine. Imagine this machine always gives them more than 51% of the current world Bitcoin hash power (but not enough hash power to completely break SHA256). Suppose they decide to build a chain from the Bitcoin Genesis block that is longer than any other chain on earth and put only empty blocks on it. Could they erase all...
[Read More]
The Dolev and Reischuk Lower Bound: Does Agreement need Quadratic Messages?
How scalable is Byzantine agreement? Specifically, does solving agreement require the non-faulty parties to send a quadratic number of messages (in the number of potential faults)? In this post, we highlight the Dolev and Reischuk lower bound from 1982 that addresses this fundamental question.
[Read More]
Byzantine Agreement is Impossible for $n \leq 3 f$ if the Adversary can Simulate
The Fischer, Lynch, and Merritt, 1985 lower bound states that Byzantine agreement is impossible if the adversary controls $f>n/3$ parties. It is well known that this lower bound does not hold if there is a PKI setup.
[Read More]