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 these fundamental questions.
[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]
The Trusted Setup Phase
co-authored with Avishay Yanai
[Read More]
Do Bitcoin and Ethereum have any trusted setup assumptions?
What is Consensus?
We all broadly understand “consensus” as the notion of different parties agreeing with each other. In distributed computing, Consensus is one of the core functionalities. In this post, we define the consensus problem and discuss some variants and their differences.
[Read More]
Byzantine Agreement is impossible for $n \leq 3 f$ under partial synchrony
Lower bounds in distributed computing are very helpful. Obviously, they prevent you from wasting time trying to do impossible things :-). Even more importantly, understanding them well often helps in finding ways to focus on what is optimally possible or ways to circumvent them by altering the assumptions or problem formulation.
[Read More]
What is the difference between PBFT, Tendermint, SBFT and HotStuff ?
In this post I will try to compare four of my favorite protocols for Byzantine Fault Tolerant (BFT) State Machine Replication (SMR):
[Read More]
The threshold adversary
Once we fix the communication model (synchrony, asynchrony, or partial synchrony see here), we then need some way to limit the power of the adversary.
[Read More]
The power of the adversary
Once we fix the communication model (synchrony, asynchrony, or partial synchrony see here), and we fix a threshold adversary we still need to make important modeling decisions about the adversary power.
[Read More]
Synchrony, Asynchrony and Partial synchrony
In the standard distributed computing model, the communication uncertainty is captured by an adversary that can control the message delays. The communication model defines the limits to the power of the adversary to delay messages.
[Read More]
Where do I even start?
I have been wanting to start a blog for a long time. Here we go!