Homework 3 has been posted, and is due on Friday 2/17 on Gradescope.
[Note: this lecture is based on material in Elaine Shi's textbook and the Decentralized Thoughts blog posts on consensus, Bracha Reliable Broadcast.]
The last two lectures, we studied the Byzantine Broadcast problem under different assumptions. We introduced two protocols:
Reminder of what Byzantine Broadcast is:
There are a total of $n$ parties, including the sender where $f$ generals can be potentially be byzantine (including the commander) .
However, the generals cannot gather in a single location. They can only send messages back and forth to each other, one at a time.
This restriction is similar to how the Internet works today.
Reminder of the Dolev-Strong protocol. This protocol allows $N$ parties to solve the Byzantine Broadcast problem in the following settings:
The protocol guarantees termination, agreement, and validity even if any subset $f \leq n - 2$ of the parties are corrupted (dishonest majority).
The protocol requires $f + 1$ rounds of communication to reach agreement.
Relying on a PKI can be dangerous and unstable!
Pros vs Cons:
Reminder of the Phase-King protocol. This protocol allows N parties to solve the Byzantine Broadcast problem in the following settings:
Any number of parties $n$, of which $f$ are corrupted with $f \leq \frac{n-1}{3}$ (honest majority).
The protocol requires 3(f+1) rounds of communication to reach agreement.
Pros vs Cons:
Comparing Dolev-Strong protocol with Phase-King in terms of the underlying assumptions:
| Dolev-Strong |
Phase-King |
|
|---|---|---|
| PKI | YES |
NO |
| Synchronous network |
YES | YES |
| Number of fauly parties |
f ≤ n - 2 | f ≤ (n-1)/(3) |
| Number of rounds |
f+1 | 3(f+1) |
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.
Goal for this lecture: Can we build a reliable broadcast that is asynchronous, no trusted setup, and can tolerate the maximum number of faulty parties $f \leq \frac{n-1}{3}$?
| Dolev-Strong |
Phase-King |
Goal Protocol |
|
|---|---|---|---|
| PKI | YES |
NO | NO |
| Synchronous network |
YES | YES | NO |
| Number of fauly parties |
f ≤ n - 2 | f ≤ (n-1)/(3) | f ≤ (n-1)/(3) |
| Number of rounds |
f+1 | 3(f+1) | constant |
Why not stick with Synchronous?
So far, both protocols we have seen, have been synchronous. 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 t. 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. The internet is unpredictible and we have clock drifts!
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.
Recall the broadcast properties we have seen:
In asynchronous broadcast, the properties are slightly different in two ways.
Reason for no termination: The adversary can delay messages arbitrarly, there is no failure detector. Parties don't know whether they are dealing with a slow message/party or a failed party that didn't send anything. If a dealer is malicious they can simply choose not to send anything and everyone would be waiting forever.
Reason for using the word "eventually": The attacker can delay messages but has to eventually let them pass between honest parties.
Asynchronous Reliable Broadcast Properties:
In this section, we will study Bracha's reliable broadcast. This protocol is one of the most important building blocks for Asynchronous Byzantine Fault tolerant protocols.
Before we begin, here are some helpful tips to keep in mind when working in an asynchronous system:
A party cannot decide an action based on a timer or the ending of a round. Example: A party cannot decide on doing an action if it doesn't hear from a party after some time (let's say a few seconds).
In an asynchronous system, an honest party cannot wait for more than $n-f$ parties to send messages. If an honest party waits for more than $n-f$, it risks waiting forever since there is $f$ parties that can be faulty and never send anything. The honest party would be waiting for a failed party that never sends anything.
If a party hears from $n-f$ parties, $f$ of those $n-f$ parties might be malicious and are just playing a long. If $n \geq 3f+1$, this means that there are at least $f+1$ parties that are honest (out of the $n-f$ parties that replied).
We will begin with a very simple protocol that has a relaxed notion of agreement but has the same validity property.
We will seperate the protocol into three phases. In each phase, an honest party would send a maximum of only one message.
input v
//broadcast phase
send <broadcast, v> to all parties
//echo phase, the point of view of party i
upon hearing <broadcast, v> from the dealer for the first time
send <echo, v> to all parties
//output phase, the point of view of party i
upon hearing $n-f$ <echo, v> coming from $n-f$ disctinct parties:
output v
Validity proof: If the sender is honest then every honest party is going to hear the value $v$ and echo it to every other party. 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 is only $f$ malicious parties, the attacker cannot convince any other honest party to output a different value $v'$.
Relaxed Agreement Proof: The proof is done by contradiction.
Assume two parties $p_1$ and $p_2$ output two different values $v_1$ and $v_2$ respectively. This means that $p_1$ heard $n-f$ echo messages from $n-f$ different parties with the same value $v_1$, where at least $f+1$ 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 $f+1$ came from honest parties. Since $n \geq 3f+1$, there cannot exist two disjoint sets of f+1 honest parties and there was at least one honest party that sent two different echo messages, one with the value $v_1$ to $p_1$ and another with $v_2$ to $p_2$. Contradiction: An honest party must stick to the protocol and send the same echo message with the same value v to everyone.
Our job in this section is to strengthen the agreement property of the previous protocol. So far, we have consistency between the parties that finish. In the sense that 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. (sometimes this is a whole seperate property called totality)
Goal:
We would want an extra step (let's call it ready phase), where if an honest party were to finish, it will wait for other honest parties to finish. Only when the honest party makes sure that everyone can else can finish, then it can itself finish.
Attempt 1: The idea is if a party hears $n-f$ ready then it makes sure that all honest parties would also finish!
Broadcast phase: This is the phase where the sender sends one value $v$ to all parties.
Echo phase: When a party hears $v$ the first time from the dealer, it sends an echo message $v$ to everyone.
Ready phase: If a party hears $n-f$ echo messages coming from $n-f$ different parties with same $v$. The party terminates with v sends a ready with $v$
Output Phase: If a party hears $n-f$ ready messages coming from $n-f$ different parties then output $v$
input v
//broadcast phase
send <broadcast, v> to all parties
//echo phase, the point of view of party i:
upon hearing <broadcast, v> from the dealer for the first time
send <echo, v> to all parties
//ready phase, the point of view of party i:
upon hearing $n-f$ <echo, v> coming from $n-f$ disctinct parties:
send <ready, v> to all parties
//output phase
upon hearing $n-f$ <ready, v> coming from $n-f$ disctinct parties:
<output v>
This doesn't work: Remember my hint number 3.
"If a party hears from $n-f$ parties, $f$ of those $n-f$ parties might be malicious and are just playing a long. If $n \geq 3f+1$, this means that there are at least $f+1$ parties that are honest (out of the $n-f$ parties that replied)."
If a party hears $n-f$ ready then it only makes sure that $f+1$ of those parties are honest and really ready! It could be the case that the other $f$ parties are malicious and will not send any ready messages to the rest of the honest parties. This will break agreement because some honest parties would finish with $v$ while others won't.
Can you think of a way to fix it and make it all work?
The solution to this is to add an amplification step. We should amplify the number of readys coming from the $f+1$ honest parties to $n-f$, that way all honest parties can eventually finish!
input v
//broadcast phase
send <broadcast, v> to all parties
//echo phase, the point of view of party i:
upon hearing <broadcast, v> from the dealer for the first time
send <echo, v> to all parties
//ready phase, the point of view of party i:
upon hearing $n-f$ <echo, v> coming from $n-f$ disctinct parties:
send <ready, v> to all parties
//amplification step
upon hearing $f+1$ <ready, v> and not previously send a ready
send <ready, v> to all parties
//output phase
upon hearing $n-f$ <ready, v> coming from $n-f$ disctinct parties:
<output v>
Validity Proof: If the sender is honest then every honest party is going to hear the value $v$ and echo it to every other party. Every honest party will eventually hear at least $n-f$ echo messages with the value $v$ coming from $n-f$ distinct honest parties and will send a ready message with $v$. Therefore, every honest party will eventually hear at least $n-f$ ready messages with the same $v$ and at most $f$ ready for other values.
Lemma: If two honest parties send a ready, then they would send a ready for the same $v$.
Assume two parties $p_1$ and $p_2$ that send two different readys with $v_1$ and $v_2$ respectively. This means that $p_1$ either heard $n-f$ echo messages from $n-f$ different parties with the same value $v_1$, or heard $f+1$ readys for the same value $v_1$ where at least one honest party have heard $n-f$ echos for the same value $v_1$. Similarly, $p_2$ either heard $n-f$ echo messages from $n-f$ different parties with the same value $v_2$, or there exist an honest party that heard $n-f$ echos for the same $v_2$. Since $n \geq 3f+1$, there cannot exist two disjoint sets of f+1 honest parties and there was at least one honest party that sent two different echo messages, one with the value $v_1$ with the value $v_2$. Contradiction: An honest party must stick to the protocol and send the same echo message with the same value $v$ to everyone.
Agreement (weak consistency + totality): If an honest party output $v$ then all honest parties will eventually output $v$.
By the previous lemma, we know that all honest parties that do send a ready, will send a ready for the same value $v$. So if an honest party outputs $v$, this means it has seen $n−f$ distinct ready messages with $v$, of which at least f+1 came from honest parties. So all honest parties will either send a ready $v$ due to seeing $n−f$ echoes or eventually due to seeing the ready messages from these $f+1$ honest parties.