Simulation, Indistinguishability, and the Necessity of PKI

FLM Impossibility Result

In the last article (link) 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 ≥ 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 ≥ 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 proof is incorrect or contradictory, the point is that each model uses a different set of assumptions that we will figure out throughout this lecture

2.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

impossibility results.

Let’s prove the theorem by contradiction.

We assume that the theorem is false, and in fact, there’s a protocol (we call it π) 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 π could be any arbitrarily crazy event-drive 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 π on each of them.

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

• 1- The IP address of the two other nodes;
• 2- among node i and the two other nodes, which one is the sender;
• 3- if node i is the sender, it’s private input.

Experiment Instruction

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

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

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

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

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

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

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

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

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

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

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

• 1- C’ neighbors are A’ and B (C’ knows A’ and B IP addresses);
• 2- 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 π, each node knows the address of two other nodes, among the three nodes we have one sender, and if node i is a sender it knows it’s private input.

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 π.

Proof Strategy

Let’s assume we have a protocol π 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.

Now our goal is to derive a contradiction from the protocol π.

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.

Now let’s see how we’re going to build the bridge between the assumed property of π and the well-defined Hexagon experiment.

Proof: Scenario #1

In scenario 1 we have B and C’ are non-senders that are running the protocol π, and X is a byzantine sender that I can do whatever I want with.

What we might do with a Byzantine node X?

As we know the idea of a byzantine node is to send inconsistent messages to both non-senders.

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 π 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

We will instruct the virtual machine A to send a message to it’s neighbor B (remember B is X’s neighbor in the Byzantine broadcast instance), and we do the same thing for A’ to send a message to C’.

What’s the point of all of that?

The point of that is to keep the honest nodes B and C’ in the dark, they cannot distinguish which is the actual reality (they don’t if they’re really running on a Byzantine Broadcast of 3 nodes, or in the Hexagon) and must operate in the same thing in both cases.

Let’s see the result of this scenario #:

💡 Result 1:

Since π satisfy 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:

In the first scenario, we relied on the agreement, in this scenario, and in the next one, we will rely on Validity.

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 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 (1), (2), and (3) 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 π cannot exist. That is, there cannot be a Byzantine broadcast protocol with n = 3 and f = 1 that guarantees termination, agreement, and validity.