The Fischer, Lynch, and Merritt, 1985 lower bound states that synchronous Byzantine agreement is impossible if the adversary controls $f>n/3$ parties. It is well known that this lower bound holds in the unauthenticated setting and does not hold in a setting with a PKI setup. Naively, one might think that the lower bound always holds if there is no PKI setup, but Nakamoto consensus shows that this is not the...
[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?
Consensus broadly means different parties reaching agreement. In distributed computing, Consensus is a core functionality. In this post, we define the consensus problem and its variants.
[Read More]
Byzantine Agreement is impossible for $n \leq 3 f$ under partial synchrony
Lower bounds in distributed computing are very helpful. They prevent us from wasting time on impossible tasks :-). More importantly, they help us focus on what is optimally possible or how to circumvent them by altering 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
In addition to limiting the adversary via a communication model synchrony, asynchrony, or partial synchrony, we need a way to limit the adversary’s power to corrupt parties.
[Read More]
The power of the adversary
After we fix the communication model, synchrony, asynchrony, or partial synchrony, and a threshold adversary there are still five important modeling decisions regarding the adversary’s power:
[Read More]
Synchrony, Asynchrony and Partial synchrony
In the standard distributed computing model, communication uncertainty is modeled by an adversary that controls 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!