In Byzantine broadcast (BB) or Byzantine reliable broadcast (BRB), there is a designated sender that sends its input value to all parties, and all non-faulty parties must deliver the same value.

Assumptions:

- Honest users all output a message if the leader is honest (termination)
- Honest users never output different messages (consistency)

One way to do it is using a single leader, but what happens if the leader crashes/becomes unavailable? We can just manually failover: human operator chooses a new leader and reconfigures each node to use new leader, but this is non-ideal.

Normally, we solve BB using consensus algorithms to solve this. Some common consensus algorithms include (all assume partially synchronous, crash-recovery system model):

- Paxos: single-value consensus
- Multi-Paxos: generalization to total order broadcast
- Raft, Viewstamped Replication, Zab: total order broadcast by default

Blockchain consensus models are slightly different as they assume partially synchronous Byzantine system model.

For all approaches below, we assume

- Public Key Infrastructure exists (i.e. nodes know the mapping of public key to entity)
- Internet exists (i.e. there is a reliable way to send message between nodes)

We denote $f$ as the number of Byzantine nodes

## Naive Approach

Reliant on a synchronous system model

`t=0`

: sender sends a signed value $v_{∗}$ to all other nodes`t=1`

: nodes echo msg from sender to all other nodes, signed again (cross-checking)`t=2`

: each node $i$ chooses output $v_{i}$ by majority vote (at most one vote from sender, at most $n−2$ from other peers). Break ties consistently (e.g. lexicographically)

Solves BB for $f≤1$, $n≥4$. Doesn’t hold for Byzantine sender, only Byzantine peers.

## Dolev-Strong (1983)

Trying to generalize the naive approach for potentially Byzantine senders by utilizing signature chains

In essence, node $i$ is only convinced of value $v$ at time $t$ if it receives a message that

- references the value $v$
- is signed first by the sender
- is also signed by $≥t−1$ other distinct nodes (none of which are node $i$)

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

At the end of $f$ rounds of cross-checking (one round per possible Byzantine node), if node $i$ is convinced of exactly one value, that is the correct value. Otherwise, output the. default value (e.g. an empty list of txs)

Solves BB for $f<n$, but really only useful at $f<2n $ for state machine replication. If $f<2n $ then we can take majority vote to arrive at consistent state (not the case if $f≥2n $). This bypasses the PSL-FLM Impossibility Result because we assume PKI exists