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.
The modern view of this lower bound is that it holds if the adversary can simulate $n+f$ parties.
The ability to simulate a polynomial number of honest parties is trivial with a traditional poly-time adversary (assuming no PKI setup). A key modern observation is that in the proof-of-work setting, an adversary controlling $f$ parties cannot simulate $n+f$ parties. So the FLM lower bound does not hold in these models. Indeed Byzantine Agreement may be possible even of there is no PKI setup (in the proof-of-work setting)!
When nothing is known, anything is possible Margaret Drabble
In this series of posts we are revisiting classic lower bounds from the 1980’s. Most of them focused on deterministic protocols and computationally unbounded adversaries. Part of our goal is to provide a more modern view that also considers randomized protocols and computational restrictions on the adversary.
In this post we discuss another classic impossibility result. This time in the synchronous model. This lower bound shows that with $n \leq 3f$ parties, one cannot solve Byzantine agreement in the face of an adversary controlling $f$ parties. We show the version where $n=3$ and $f=1$.
Informally this lower bound captures the following: if there are only three parties $A,B,C$ and say $B$ and $C$ blame each other for lying and provide no proof-of-malice to $A$, then $A$ has no way to decide between $B$ and $C$. $A$ has no way to know who to trust and agree with.
The high-level approach to the lower bound will be similar to our previous lower bound. We will use two powerful techniques: indistinguishability (where some parties can not tell between two potential worlds) and hybridization (where we build intermediate worlds between the two contradicting worlds and use a chain of indistinguishability arguments for a contradiction.).
In the previous lower bound, we used messages delays due to partial synchrony to create the indistinguishability arguments. In this lower bound, we are crucially going to rely on the ability of an adversary to simulate different worlds and present different views of the worlds to different parties.
We prove this result by contradiction. Suppose there is a protocol that can achieve Byzantine agreement with three parties. We will define worlds 1, 2, and 3:
In World 1, parties $A$ and $B$ start with input 1. Corrupt party $C$ simulates the worlds of four players, $C, A’, B’, C’$ connected in a peculiar fashion as shown in the figure. $C$ starts with input 1 whereas, $A’, B’$ and $C’$ start with input 0. Thus, $B$ interacts with an instance of $C$ that starts with input 1 and $A$ interacts with an instance of $C$ (i.e., $C’$) that starts with input 0. Intuitively, by sending messages to $B$ based on what it receives from $A’$, $C$ is framing $A$ as if $A$ started with input 0. Similarly, $C’$ is framing $B$ by sending messages received from $B’$. The connections in the peculiar order ensures that the simulated parties can send appropriate messages to $A$ and $B$.
Now, since validity property holds despite what the corrupt party $C$ does, $A$ and $B$ commit to 1.
In World 2, parties $B$ and $C$ start with input 0. Corrupt party $A$ simulates the worlds of four players, $A$, $B’$, $C’$, and $A’$ connected as shown in the figure. The simulation is similar to world 1. Here, when $A$ is sending messages to $B$, it is framing $C$ to have sent 1. Similarly, $A’$ is framing $B$. Again, since the validity property holds, $B$ and $C$ commit to 0.
In World 3, party $A$ starts with 1 and $C$ starts with 0. Corrupt party $B$ simulates the worlds of four players, $B$, $C’$, $A’$, and $B’$ as shown in the figure. Parties $B$ and $C’$ start with input 1 whereas $A’$ and $B’$ start with input 0.
The question is: what do $A$ and $C$ output?
We argue that $A$ outputs 1 and $C$ outputs 0. Why?
Observe that from party $A$’s perspective, World 3 is the same as World 1. From the figure, it can be seen that if we start from a double-circled $A$ and go clock-wise, the connections and inputs from parties are exactly the same. Intuitively, observe that in World 1, $C’$ started with input 0 and framed $B$ to have input 0 (the fully connected hexagon is necessary to make the argument more formal). However, $A$ decided to output 1 in World 1. Since party $A$ sees exactly the same set of messages in World 3, party $A$ outputs 1. By a similar argument party $C$ outputs 0.
Thus, if the validity property holds in Worlds 1 and 2, the agreement property cannot hold in World 3 (we cannot show absence of validity in World 3 since the honest parties started with different values).
Simulation of parties by the adversary
The main thing to observe is that the lower bound requires the adversary to simulate $4$ parties (in general, $n+f$ parties). So this lower bound does not hold if the adversary cannot simulate. Here are a couple of interesting cases:
- Trusted setup: Under the classic computational assumptions that assume the adversary is polynomially bounded, this lower bound still holds assuming there is not setup. If there is a trusted PKI setup, then the adversary will not be able to simulate any of the other parties.
Computationally bounded adversaries: Under more fine grained assumptions where the adversaries’ power to solve certain computational puzzles is restricted, it is in fact possible to circumvent this lower bound - without any trusted setup. See KMS, AD, and GGLP.
- In particular, Nakamoto Consensus is an example of a Byzantine Agreement protocol that only requires a fresh random genesis as a setup and can withstand $(n/2)(1+\epsilon)>f>n/3$ corruptions (see GKL) or this blog post.
The other thing to observe is that when the FLM bound holds, it holds in a strong way for randomized protocols, disallowing even protocols that reach agreement with a small constant probability of error. See the unpublished manuscript of KY.
[FLM 85 modern version] It is impossible to solve synchronous agreement with probability $> 2/3$ against a Byzantine adversary that can simulate $n+f$ parties if $f \geq n/3$.
Finally we note that this lower bound holds even for Broadcast, not just for Agreement.
Please leave comments on Twitter
Acknowledgment. We thank Georgios Konstantopoulos and Avishay Yanai for identifying typographical errors and helping improve the post.