Randomized Byzantine Generals

Paper: Randomized byzantine generals. Michael O Rabin. 1983

This is an asynchronous Byzantine fault tolerant consensus protocol tolerating \(t

Setup

  • A setup where all nodes have \((n,t+1)\) secret shares1 of coins \(s_{r,i}\) for \(r\in [R]\) rounds and node \(i\in [n]\).2
  • PKI

Protocol

  • Variables:
    • \(value \leftarrow v_i\)
  • Protocol:
    • For rounds \(r \in \{1,\ldots,R\}\)
      • Send \(\left< value, round \right>_i\) to all nodes.
      • Collect \(n-t\) values from other nodes for round \(r\) in \(V_{r}\).
      • Let \(temp_r\) be the value which occurred most in \(V_r\).
      • Let \(count_r\) be the number of times \(temp_r\) occurs in \(V_r\).
      • Send round coin share \(s_{r,i}\) to all nodes.
      • Receive \(t\) different correct shares.
      • Compute round coin \(s_{r}\).
      • If \(s_r = 0\) and \(count_r \ge n/2\):
        • \(value \leftarrow temp_r\)
      • If \(s_r = 1\) and \(count_r \ge n-2t\):
        • \(value \leftarrow temp_r\)
      • Else:
        • $value ← $

References

Michael O Rabin. 1983. “Randomized byzantine generals.” http://ieeexplore.ieee.org/document/4568104/.

Footnotes:

1

I think $(n,n-t+1)$-secret shares will also work.

2

This implies \(n>2t\).