Simulation, Indistinguishability, and the Necessity of PKI

In the last article we discussed the possibility result for a protocol to satisfy consistency and liveness under a set of assumptions (Permission, synchronous, PKI), and we proved that no matter how many Byzantine nodes we have in the system, Dolev-Strong protocol always allows us to achieve consistency and liveness.

In this article, we will discuss the impossibility result in which there is no protocol that satisfies consistency and liveness with a set of faulty (Byzantine) nodes $f \geq n/3$ ($f$: faulty node, $n$: node)

1. The FLM Impossibility Result

1.1 Statement of the Impossibility Result

Theorem: In the synchronous model with $f \geq n/3$, there is no Byzantine broadcast protocol that satisfies termination, agreement, and validity.

But wait! Didn't we just prove in the last article that Dolev-Strong protocol solves the Byzantine general problem no matter how many byzantine nodes we have in the system?

Yes, and neither of these proofs is incorrect or contradictory, the point is that each model uses a different set of assumptions that we will figure out throughout this lecture.

1.2 Intuition

Let's focus on the simplest use case of the impossibility result where $n=3$ and $f=1$ ($n$: node, $f$: faulty/Byzantine node)

We have 3 nodes Alice, Bob, and Carol. Each of the three nodes can communicate with the other two.

Let's assume that Alice is the sender, from point of view of Bob, he might hear conflicting messages one from Alice the sender, and the other from Carol (non-sender). Bob knows that one of the nodes is Byzantine but he has no idea which one. One scenario might be that Alice is sending conflicting messages to both Bob and Carol, or the other scenario where Carol is attempting to frame what she heard from Alice.

Think of the case where we have $n=4$ and $f=1$, in this case, Bob could figure out the right output by using the majority vote of the three other nodes, whereas in the case of $n=3$ we have a problem.

2. The FLM Proof of Theorem

Let's prove the theorem by contradiction.

We assume that the theorem is false, and in fact, there's a protocol (we call it $\pi$) for the Byzantine broadcast problem with $n=3$ and $f=1$.

If we can derive a contradiction from this we completed the proof. (The protocol $\pi$ could be any arbitrarily crazy event-driven piece of code, we don't care)

The Hexagon

The Fischer-Lynch-Merritt (FLM) proof is a genius step to prove the result of this theorem.

We're going to buy 6 nodes, three nodes for Alice, Bob, and Carol, and the other three are copies of each of the first three nodes. Then we run the protocol $\pi$ on each of them.

There are 3 things we expect to be known first for a node $i$ before firing the protocol $\pi$:

• If node $i$ is the sender, its private input
• Among node $i$ and the two other nodes, which one is the sender
• The IP address of the two other nodes

Experiment Instruction:

Buy node A and set it up with the following 3 initializations as mentioned above:

• A neighbors are B and C (A knows B and C IP addresses);
• A is a sender while B, and C' are non-senders;
• A private input is 0.

Buy node B and set it up with the following 3 initializations:

• B neighbors are A and C' (B knows A and C' IP addresses);
• A is a sender while B, C' are non sender;

Buy node C and set it up with the following 3 initializations:

• C neighbors are A and B' (C knows A and B' IP adress);
• A is a sender while B, and C' are non senders;

Buy node A' and set it up with the following 3 initializations:

• A' neighbors are B' and C' (A' knows B' and C' IP address);
• A' is a sender while B', and C' are non-senders;
• A private input is 1.

Buy node B' and set it up with the following 3 initializations:

• B' neighbors are A' and C (B' knows A' and C IP addresses);
• A' is a sender while B', and C are non-senders;

Buy node C' and set it up with the following 3 initializations:

• C' neighbors are A' and B (C' knows A' and B IP addresses);
• A is a sender while B, and C' are non-senders;

This experiment is well defined and legit because from the perspective of each node it satisfies the three properties of the protocol $\pi$. Once all the initialization is set up on all the nodes, we press the Play button simultaneously on all six machines to run the protocol $\pi$.

Proof Strategy

Let's assume we have a protocol $\pi$ that satisfies validity and agreement for $n=3$ and $f=1$. Now, remember it's not accurate to say that agreement and validity carry over the thought experiment where we have 6 nodes.

Our goal is to derive a contradiction from the protocol $\pi$.

We're not going to use these assumptions on the thought experiment (6 nodes Hexagon), because we don't know even what validity and agreement mean in 6 cycles. So we need to come up with some bonafide of the Byzantine Broadcast with only 3 nodes.

Proof: Scenario #1

In scenario 1 we have $B$ and $C'$ are non-senders that are running the protocol $\pi$, and $X$ is a byzantine sender that can do whatever it wants.

Strategy for node $X$: simulate the behavior of the four nodes $A, C, B', A'$ by setting up four local virtual machines, each running protocol $\pi$ with the appropriate initialization.

So $X$ communicates with $C'$ as if it were $A'$ in the hexagon, and communicates with $B$ as if it were $A$.

The point is to keep the honest nodes $B$ and $C'$ in the dark. They cannot distinguish which is the actual reality and must operate the same in both cases.

Result 1: Since $\pi$ satisfies termination and agreement, nodes $B$ and $C'$ output the same value (no matter the strategy used by $X$) in the triangle and in the hexagon.

Proof: Scenario #2

Strategy for node $X$: simulate the behavior of the four nodes $C, B', A', C'$.

Result 2: In this case $A$ is an honest sender, using the validity property, $A$ and $B$ should both output $0$ ($A$'s private input). $A$ and $B$ are kept in the dark. They don't know if they are running in a triangle or a hexagon with 6 nodes.

Proof: Scenario #3

The third scenario is similar to the second one, with an honest sender $A'$ with private input $1$.

Strategy for node $X$: simulate the behavior of the four nodes $B, A, C, B'$.

Result 3: In this case $A'$ is an honest sender, using the validity property, $A'$ and $C'$ should both output $1$ ($A'$ private input).

Conclusion

These 3 results assert that nodes $B$ and $C'$ must terminate and output the same value (from result 1); $B$ must output $0$ (from result 2); $C'$ must output $1$ (from result 3).

This concludes our contradiction since the experiment can't possibly satisfy these three mutually inconsistent constraints at the same time.

This implies that the assumed protocol $\pi$ cannot exist. That is, there cannot be a Byzantine broadcast protocol with $n = 3$ and $f = 1$ that guarantees termination, agreement, and validity.