Lecture 12: Aynchronous Byzantine Broadcast

In the synchronous setting, our goal is to design a protocol – that is, a method that each party can use to decide what messages to send and to whom – that protects the honest parties as follows.

• Termination: All honest parties eventually complete the protocol and output something (i.e., the protocol doesn’t go on forever).
• Validity: If the leader is honest and sends the bit \(b\), then all honest parties should output \(b\)
• Consistency: If two honest parties output \(b\) and \(b'\) respectively, then \(b = b'\).

So far, we have two protocols that provide Byzantine Broadcast in the synchronous setting: the Dolev-Strong protocol and the phase-king protocol.

• We can make the phase-king protocol take a much smaller number of rounds (in fact, a constant number that is independent of \(f\)) using randomness, at the cost of introducing a small probability of error.
• The phase-king protocol’s bound of \(f \leq \frac{n-1}{3}\) is in fact optimal.

Theorem. In a plain pairwise authenticated channel model without any setup assumptions such as a PKI, Byzantine Broadcast is impossible if at least \(n/3\) parties are corrupt.

Finally, starting from synchronous broadcast, we can construct a blockchain in the synchronous, permissioned setting.

At this point you may be asking yourself: why not stick with the synchronous network assumption? So far, both protocols we have seen have been synchronous.

However, this is a strong assumption to make. We can’t assume that the network delays are always predictable and that the messages will arrive within some time bound \(\Delta\). We can’t assume that all the clocks of the nodes are synchronized and that all nodes can enter and exist rounds at the exact time.

Basically: the internet is unpredictible and clocks are imprecise!

Today, we will examine a new model, known as the asynchronous model, that eliminates the requirement for nodes to have their own clocks.

Within an asynchronous consensus protocol, each node is only activated when it receives a message from the network, at which point it performs some computation and selects messages to send (if any). This model looks challenging because the adversary can delay messages by any bounded time.

The only good news about an asynchronous network is that we still assume that the adversary cannot drop messages in transit. So if a message is sent from honest Alice to honest Bob, it will eventually arrive at its destination… even if it takes awhile.

(On the other hand, messages sent from a malicious Mallory might never arrive – because the malicious party might never have sent it in the first place!)

Still, we are making progress. This protocol satisfies a relaxed notion of consistency.

• Weak consistency: If an honest party outputs a value \(v\), then any other honest party that happens to complete the protocol must also output \(v\). (However, honest parties might never terminate.)

Theorem. If \(n \geq 3f + 1\), then the Simplified Bracha protocol satisfies validity and weak consistency.

Proof of validity:

• If the leader is honest, then every honest party is going to hear the value \(v\) after the leader step, and therefore every honest party will echo \(v\) to all other parties.
• Hence, every honest party will eventually hear at least \(n-f\) echo messages with the value \(v\) coming from the honest parties and will be able to terminate.
• Since there are only \(f\) malicious parties, the adversary Mallory cannot convince even a single honest party to output a different value \(v'\).

Proof of weak consistency:

• This proof is done by contradiction. Assume for the sake of contradiction that two parties \(P_1\) and \(P_2\) output two different values \(v_1\) and \(v_2\) respectively.
• This means that party \(P_1\) heard \(n-f\) echo messages from \(n-f\) different parties with the same value \(v_1\), where at least \(n-2f\) came from honest parties.
• Similarly, \(p_2\) heard \(n-f\) echo messages from \(n-f\) different parties with the same value \(v_2\), where at least \(n-2f\) came from honest parties.
• Since \(n \geq 3f+1\), any two disjoint sets of size \(n - 2f\) must have at least \(f + 1\) parties in common, by the pigeonhole principle. Since at most \(f\) parties are malicious, this means there is at least one honest party that sent two different echo messages, one with the value \(v_1\) to party \(P_1\) and another with value \(v_2\) to party \(P_2\).
• This is a contradiction, because an honest party must stick to the protocol and send the same echo message with the same value \(v\) to everyone.
• As a result, it is not possible for two honest parties to complete the protocol with different output values. (It remains possible for some honest parties not to complete the protocol at all, however.)

Our goal here is to strengthen the consistency property of the previous protocol. So far, we have a weaker notion of consistency between the parties that finish. That is:

• From the honest parties that do finish, they will all output the same value \(v\).
• However, we have no guarantee that if some honest party finishes then all parties should finish.

Bracha’s idea is to add a third communication, called the “ready step.” The idea is that if an honest party received enough echos of a single message to be happy with it in the previous protocol, then it will send it along one more time and wait for other honest parties to finish the protocol.

Only when the honest party makes sure that everyone can else has the ability to determine the output value, then it can itself finish the protocol and output the desired value. In this way, either all honest parties complete the protocol, or none of them do.

Specifically, there are now two events that will cause an honest party to send a ready message: either it has received \(n - f\) echo messages or it has received \(f + 1\) ready messages. The latter constraint means that at least one honest party is ready to finish the protocol.

input: the leader has an input message v, other parties have no input

leader_send: the leader party P_1 sends <leader, v> to all parties (the other parties send nothing)

echo: upon hearing <leader, v> from the leader P_1 for the first time,
      send <echo, v> to all parties

ready_event1: upon hearing n-f <echo, v> messages from n-f distinct parties containing the same value v,
              send <ready, v> to all parties
    
ready_event2: upon hearing f+1 <ready, v> messages from f+1 distinct parties containing the same v, and not having previously sent a ready,
              send <ready, v> to all parties    

output: upon hearing n-f <ready, v> messages coming from n-f distinct parties containing the same value v,
        output v
        (implicitly, otherwise output nothing, i.e., never terminate)

This fixes the only remaining problem, and the construction is now complete!

Theorem. If \(n \geq 3f + 1\), then Bracha’s protocol is an asynchronous Byzantine reliable broadcast protocol.

Proof of validity: This proof is largely similar to the previous proof for the simplified Bracha protocol, only now each party communicates up to three times.

It remains to prove consistency. To do so, it is helpful first to consider the following lemma.

Lemma. If two honest parties send a ready message, then they must send it for the same value \(v\).

Proof of the lemma. This is also a proof by contradiction.

Now we can complete the proof of Bracha’s broadcast protocol.

Proof of consistency. We want to show that: if an honest party outputs \(v\), then all honest parties will eventually output \(v\).

Note that it still remains possible that no honest parties reach the state of being able to output a message. Hence, asynchronous protocols need not terminate; they can stall forever.

Actually, this doesn’t quite work. The problem is that Bracha’s broadcast protocol doesn’t guarantee termination.

The synchronous blockchain protocol that we designed last time relied on the idea that each party takes a turn being the designated leader and creating a new block (first party \(P_1\), then party \(P_2\), and so on). But in the asynchronous setting, we may never be certain when the epoch where Party 1 is the designated leader has ended, so that we can move on to the next epoch with Party 2 as the designated leader.

At first glance, this looks to be an insurmountable problem. It is actually impossible to build an asynchronous Byzantine Broadcast protocol that guarantees termination. The problem is that the designated leader might simply refuse to participate in the protocol, and the honest parties will wait forever to listen for a message that may never arrive.

In some sense, the problem here stems from the fact that we are putting all of our faith in a single party to serve as the designated leader.

So let’s back away from that. We can define a new, slightly more general question called Byzantine Agreement. This is like Byzantine Broadcast, except that now everyone gets to send a message at the same time.

For this new problem:

• There is no longer a commanding general. Instead, every general has their own opinion on whether to attack or retreat.
• The goal of the protocol is to ensure that all honest generals make the same decision. Furthermore, if the generals all happened to have the same opinion, then this common opinion should be the end result.

Let’s modify our properties from Byzantine Broadcast to work in the new, more sophisticated setting of Byzantine Agreement.

Consistency is the same as before:

all honest parties output the same value.

Validity only needs to hold if everyone starts with the same message… or at least, all the honest parties do, since we can never be sure what the malicious parties are doing. Formally, we guarantee that:

if all honest parties start with the same input value, then this shared value is guaranteed to become the output value.

Liveness is the asynchronous version of what we used to call termination. It states that:

all honest nodes output eventually (assuming that messages are delivered eventually, albeit with arbitrary delays)

In the synchronous setting, there are many ways to build Byzantine Agreement. One simple approach is to run \(n\) copies of a Byzantine Broadcast protocol (e.g., Dolev-Strong) in parallel, where everyone is the designated leader in one of them, and then take a majority vote of the results.

This works as long as \(f < \frac{n}{2}\), since otherwise the malicious parties are in the majority and can overrule the honest parties’ values. (And it turns out that \(f < \frac{n}{2}\) is the best that one can do.)

But the asynchronous setting is where things really get interesting. It turns out that:

• It is impossible to construct a deterministic protocol that achieves asynchronous Byzantine Agreement, even in the easiest possible setting where there is only \(f = 1\) malicious party!

• But: using a CommonCoin, it is possible to build a randomized protocol for asynchronous Byzantine Agreement that can withstand up to \(f < \frac{n}{3}\) malicious parties!

In other words, we can achieve liveness with Byzantine Agreement, even though it was impossible to accomplish with Byzantine Broadcast. This is because we are no longer relying on a single leader who might just refuse to participate in the protocol; instead, everyone is allowed to contribute equally.

I don’t have time to describe the randomized protocol for asynchronous Byzantine Agreement in today’s class. You will read it for yourself in Chapter 13 of Elaine Shi’s textbook.

Hopefully this insight also provides better context for Satoshi Nakamoto’s contribution. The Bitcoin blockchain also achieves consistency and liveness in an asynchronous network. It does so in a permissionless setting where up to 1/2 of the computing power can be malicious (rather than up to \(1/3\) of parties).

This is just one of many amazing applications of a CommonCoin! Next time, we will explore in more detail the problem of generating common randomness.