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.
- 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 as the number of Byzantine nodes
Reliant on a synchronous system model
t=0: sender sends a signed value to all other nodes
t=1: nodes echo msg from sender to all other nodes, signed again (cross-checking)
t=2: each node chooses output by majority vote (at most one vote from sender, at most from other peers). Break ties consistently (e.g. lexicographically)
Solves BB for , . Doesn’t hold for Byzantine sender, only Byzantine peers.
Trying to generalize the naive approach for potentially Byzantine senders by utilizing signature chains
In essence, node is only convinced of value at time if it receives a message that
- references the value
- is signed first by the sender
- is also signed by other distinct nodes (none of which are node )
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 rounds of cross-checking (one round per possible Byzantine node), if node 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 , but really only useful at for state machine replication. If then we can take majority vote to arrive at consistent state (not the case if ). This bypasses the PSL-FLM Impossibility Result because we assume PKI exists