BenOr Randomized BFT Consensus

Notes

  • Asynchronous network
  • Solves binary consensus
  • \(n>5t\) for \(t\) Byzantine faults
  • Protocol
    1. Set \(r \leftarrow 1\)
    2. Wait till \(n-t\) messages of type \((1,r,*)\) are received. If more than \((n+t)/2\) messages have the same value \(v\), then send the message \((2,r,v,D)\) to all the processes. Else, send the message \((2,r,?)\) to all processes.
    3. Wait till \(n-t\) messages of type \((2,r,*)\) to arrive.
      1. If there are at least \(t+1\) D-messages \((2,r,v,D)\), then set \(v_i \leftarrow v\)
      2. If there are more than \((n+t)/2\) D-messages then output \(v\)
      3. Else set \(v_i \in \{0,1\}\) with probability 1/2.
    4. Set \(r\leftarrow r+1\) and go to step 1.
  • If all processes start with the same value \(v\), then within one round they will all output \(v\).
  • If for some round \(r\), some correct server outputs \(v\), then all other correct servers will output \(v\) in the next round.
  • All process will eventually output the same value. The worst-case number of rounds necessary is