• Model
• BA protocol
• Protocol Process

Model

n = 3f+1, f faulty nodes.

BA protocol

Agreement: All honest players agree on a value. Consistency: If all honest players agree on value v, they finally reach consistency on v.

Protocol Process

\(Q_{r} = H(R, r)\) R is the random quantity, and r is the round number.

• Receive b and $SIG_j(Q_r)$ at the rounds r-1, goal is to
  • Reach agreement at the end of the round with prob >1/3
  • Remaining agreement if in agreement.
• If the number of players receiving (0) > 2n/3, then $b_i^r = 0$
• if the number of players receiving (1) > 2n/3, then $b_i^r = 1 $
• Else, $rand_r = min H(SIG_j(Q_r))$ and $b_i^r = LSB(rand_r)$ LSB is the last bit in the hash string.

Analysis:

Suppose everyone does not see more than 2n/3 zeros or ones. In that case, they use $rand_r$, the probability of reaching an agreement on zero = $2/3 * 1/3 = 1/3$, where 2/3 is the probability of honest users, and 1/2 is the probability of getting zero on the last bit of $rand_r$.

---

• ← Previous Post
• Next Post →