Byzantine Broadcast
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.
One way to do it is using a single leader, but what happens if the leader crashes/becomes unavailable? Manual failover: human operator chooses a new leader and reconfigures each node to use new leader, but this is non-ideal.
- Common consensus algorithms (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 assume partially synchronous Byzantine system model
FLP Result states that these consensus algorithms cannot assume an asynchronous system model without giving up either safety or liveness.
Assumptions:
- Honest users all output a message if the leader is honest (termination)
- Honest users never output different messages (consistency)
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 nodest=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 \leq 1$, $n \geq 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 $\geq 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 < \frac n 2$ for state machine replication. If $f < \frac n 2$ then we can take majority vote to arrive at consistent state (not the case if $f \geq \frac n 2$). This bypasses the PSL-FLM Impossibility Result because we assume PKI exists