Search

# PSL-FLM Impossibility Result

Last updated Jul 1, 2022 Edit Source

Byzantine Broadcast is impossible in the synchronous system model if you have too many byzantine nodes (for $f \geq \frac n 3$).

Vague intuition for the result, imagine 3 nodes A (Byzantine), B (honest), and C (Byzantine)

1. Node A is the sender
2. A could tell B + C conflicting things
3. B + C can compare histories but C can try to frame A
4. B can’t distinguish which of A or C are responsible for conflict

This result breaks down in the presence of PKI (you can’t forge signatures from other nodes!!)

• Thus, with PKI we get BB for all $f$
• Without PKI, we get BB only if $f < \frac n 3$