This post is about the classic result from 1983 on authenticated broadcast against a Byzantine adversary:
Theorem (Dolev-Strong [1983]): there exists an authenticated protocol for solving broadcast, against any adversary controlling $t<n$ out of $n$ parties, in $t+1$ rounds, using $O(n^2t)$ words
Recall Broadcast properties: (1) Termination - all honest parties decide and terminate; (2) Validity - if the leader is honest, its value is the decision value; and (3) Agreement - all honest parties decide the same value.
The Dolev-Strong protocol requires: (1) a synchronous model, in this post, we will assume lock-step; (2) an authenticated setting. In this setting, we assume a PKI infrastructure. Denote the signature of message $m$ by party $i$ as $sign(m,i)$. We assume signature unforgeability.
As a first attempt, let’s try to implement Broadcast for $t=1$ in 2 rounds. In the first round, the leader sends a signed message. In the second round, an honest party forwards the leader message to everyone:
// Attempt 1:
Round 1: Leader (party 1) sends message <v, sign(v,1)> to all parties
Round 2: If party i receives <v, sign(v,1)> from leader,
then add v to V_i and send <v, sign(v,1)> to all
End of round 2:
If party i receives <v, sign(v,1)> from anyone
then add v to V_i
Decision rule:
If the set V_i contains only a single value v,
then output v
Otherwise output a default value bot
Validity: if the leader is honest then due to signature unforgeability, all honest parties will see exactly a single value.
Termination: All parties terminate at the end of round 2.
Agreement (partial): If a malicious leader sends a value to some honest in round 1, all honest parties will receive it at the end of round 2. If a malicious leader sends two different values in round 1, then all honest parties will see two different values and decide $\bot$.
So does this protocol work?
No! The problem is last-round reveals: a Byzantine leader may withhold a value in round 1 and release it to only a few parties in round 2. Those parties would decide on the value, while others output $\bot$, breaking agreement.
The core problem is that you may learn the decision value in the last round (round 2) but you are not sure that all other honest parties will also receive this value. You cannot forward your messages because this is the last round. Dolev and Strong show a very elegant way to guarantee agreement even if the value decided is revealed in the last round.
In round 1: accept a value if it’s signed by the leader, but in round 2: accept a value only if it’s signed by both the leader and another party.
// Attempt 2:
Round 1: Leader (party 1) sends message <v, sign(v,1)> to all parties
Round 2: If party i receives <v, sign(v,1)> from leader,
then add v to V_i and send <v, sign(v,1), sign(v,i)> to all
End of round 2:
If party i receives <v, sign(v,1), sign (v,j)> from j>1
then add v to V_i
Decision rule:
If the set V_i contains only a single value v,
then output v
Otherwise output a default value bot
This protocol is resilient to 1 Byzantine failure because you only accept a value in the last round if t+1=2 parties signed it! If there are two signatures then one of them is from an honest party, so all honest parties will see this value.
The principle is to only accept a value in the last round if its contents can certify that all parties have received this value. This leads to a very powerful idea in the synchronous model: The validity of a message is a function also of the time it is received
The Dolev-Strong protocol implements this idea via signatures chains. Signature chains have two essential properties that allow honest parties to agree on a value at the end of $t+1$ rounds.
- A signature chain consists of signatures from distinct parties. So, if we have a signature chain of length $t+1$, it will certainly contain an honest signature by honest party $h$. Party $h$ can send the value to all parties.
- In round $i$, an honest party will accept (consider valid) only a signature chain of length $i$. So even if the adversary forms a Byzantine-only chain of length $\leq t$, then if it sends this chain in round $t+1$ it will not be accepted.
Messages in the protocol are signature chains where a k-signature chain is defined recursively as follows:
A 1-signature chain on $v$ is a pair $(v, sign(v,1))$.
For $k>1$, a k-signature chain on $v$ is a pair $(m, sign (m,i))$ where $m$ is a $(k-1)$-signature chain on $v$ that does not contain a signature from $i$. In other words, a message (signature chain) received by party $i$ at the end of round $k$ is said to be valid if:
- The first signer of the signature chain is the leader
- All signers in the chain are distinct
- All signatures are valid
- The signature chain has length $k$
The protocol:
// Leader (party 1) with input v
Round 1: send <v, sign(v,1)> to all parties.
Party $i$ does the following:
// Party i in round j = 2 to t+1
For a message m received in round j-1:
if party i has sent less than two messages; and
if m is a valid (j-1)-signature chain on $v$ not already signed by i, then
add v to V
send <m, sign(m,i)> to all parties
For a message m received in round t+1:
if m is a valid (t+1)-signature chain on $v$ not already signed by i, then
add v to V
// Party i decision rule
Decision at the end of round t+1:
Let V be the set of values for party i received a valid signature chain
If |V|=0 or |V|>1, then decide default value bot
Otherwise decide v, where V={v}
The protocol satisfies agreement, validity, and termination:
Termination: The protocol is deterministic and terminates in $t+1$ rounds.
Validity: The (honest) leader will only sign one value, and this value will be sent to all honest parties in the first round. Due to the unforgeability of digital signatures, no other signature chain can exist.
Agreement. If an honest party receives a $k$-signature chain at the end of round $k$, then it will send it to all honest parties in round $k+1$. This holds for all rounds except the last round, round $t+1$. But since the honest party can only receive a $t+1$-sized chain in round $t+1$ and a $t+1$-sized chain contains at least one honest party $h$, $h$ must have already sent this value to all other honest parties. Thus, every value received by one honest party will be received by all other parties. (This does not hold in the case where the leader has sent more than two values. But the protocol ensures that all honest parties receive at least two of the values and hence they will agree on a default value).
Complexity measures and Notes
Every party sends at most two chains, each of length at most $t+1$ (that is, $O(t)$ signatures). The total communication is $O(n^2t)$ signatures.
Here is an open question: for $t<n$, reduce communication to $o(n^3)$ against some type of adaptive adversary, or perhaps show that $O(n^3)$ is required under some conditions.
Note that this protocol relies heavily on synchrony and does not work for $t \geq n/2$ in the client-server model where the clients are passive or maybe offline. In Dolev–Strong, a party must accept a length-$k$ chain only in round $k$, but offline clients cannot verify timing. Thus the protocol fails when $t \geq n/2$ or clients are not continuously online.
Another great description and proof of the Dolev-Strong protocol can be found in Jonathan Katz’s Advanced Topics in Cryptography course notes. In the blockchain space, the Dolev-Strong protocol is mentioned by Spacemesh. Buterin’s post explains how to implement Dolev-Strong in the synchronous model and hints at how it could be used as a finality gadget for stronger $99\%$ fault tolerance for online observers.
Historically, a very similar protocol for the authenticated setting was suggested by Lamport, Shostak, and Pease in their seminal paper The Byzantine Generals problem. However, it seems that the authenticated protocol in Section 4 does not explicitly mention that length $k$ chains must not be accepted at time $>k$.
See this post for the analog protocol for $f<n$ non-uniform omission failures with weak validity.
Please leave comments on Twitter