Byzantine Broadcast is impossible in the synchronous system model if you have too many byzantine nodes (for ).

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
  • Without PKI, we get BB only if