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 works in the synchronous and authenticated setting. In this setting, we assume a PKI infrastructure. We denote the signature of message $m$ by party $i$ as $sign(m,i)$. We assume signature unforgeability.

Let us try to obtain the following: if some honest party receives a value sent by the leader, all honest parties will receive it. Thus, at the end of the protocol, all honest parties would receive the same set of values, and deterministically agree on the same value.

Here is an attempt to put the above intuition in a protocol that can handle one malicious party:

// Attempt 1:

Round 1: Leader (party 1) sends message <v, sign(v,1)> to all parties
then sends <v, sign(v,1)> to all
Round 3: If party i receives only a single leader-signed value v,
then output v
Otherwise output a default value \bot


Observe: If the leader is honest, then all parties will see the leader’s value. Even if a Byzantine leader sends its value to some honest in round 1, all honest parties will receive it at the beginning of round 3. So does this protocol work?

No! the problem is that a Byzantine leader can send no value in round 1, but send a value to only a few honest parties in round 2. The honest parties who receive the value will output that value whereas other honest parties will output a $\bot$. Dolev-Strong fixes this by building a chain of signatures containing:

// Attempt 2:

Round 1: Leader (party 1) sends message <v, sign(v,1)> to all parties.
Round 3: If party i receives only a single leader-signed value $v$,