# Generalized Paxos Made Byzantine
## 5 Byzantine Fault Tolerant Protocol
### Agreement Protocol
```
1:local variables:\(leader=\bot\), \(view=0,bal_{a}=0\), \(val_{a}=\bot\), \(fast\_bal=\bot\), \(proven=\bot\)
2:upon receive(\(P1A,ballot\), \(view_{l}\)) from leader \(l\)do
3:if\(view_{l}==view\) and \(bal_{a}<ballot\)then
4:\(\textsc{send}(P1B,ballot\), \(bal_{a}\), \(proven,val_{a},proofs[bal_{a}])\) to leader
5:\(bal_{a}=ballot\)
6:\(val_{a}=\bot\)
7:upon receive(\(FAST,ballot\), \(view_{l}\)) from leader do
8:if\(view_{l}==view\)then
9:\(fast\_bal[ballot]=true\)
10:
11:upon receive(\(VERIFY,view_{i},ballot_{i},val_{i}\), \(proof\)) from acceptor \(i\)do
12:if\(proof_{pub}==\langle ballot_{i},val_{i}\rangle\) and \(view==view_{i}\)then
13:\(proofs[ballot_{i}][val_{i}][i]=proof\)
14:if\(\#(proofs[ballot_{i}][val_{i}])\geq N-f\)then
15:\(proven=val_{i}\)
16:\(\textsc{send}(P2B,ballot_{i},val_{i},proofs[ballot_{i}][value_{i}])\) to learners
17:
18:upon receive(\(P2A\_CLASSIC,ballot\), \(view\), \(value\)) from leader do
19:if\(view_{l}==view\)then
20:\(\textsc{phase\_2B\_classic}(ballot,value)\)
21:
22:upon receive(\(P2A\_FAST,value\)) from proposer do
23:\(\textsc{phase\_2B\_FAST}(value)\)
24:
25:function\(\textsc{phase\_2B\_classic}(ballot,value)\)
26:\(univ\_commut=\textsc{isUniversallyCommutative}(val_{a})\)
27:if\(ballot\geq bal_{a}\) and \(val_{a}==\bot\) and \(!fast\_bal[bal_{a}]\) and (\(univ\_commut\) or \(proven==\bot\) or \(proven==\textsc{subsequence}(value,0,\#(proven))\)) then
28:\(bal_{a}=ballot\)
29:if\(univ\_commut\)then
30:\(\textsc{send}(P2B,bal_{a},value)\) to learners
31:else
32:\(val_{a}=value\)
33:\(proof=\langle ballot,val_{a}\rangle_{pri_{a}}\)
34:\(proofs[ballot][val_{a}][a]=proof\)
35:\(\textsc{send}(VERIFY,view,ballot,val_{a},proof)\) to acceptors
36:endfunction
37:
38:function\(\textsc{phase\_2B\_FAST}(ballot,value)\)
39:if\(ballot==\overline{bal_{a}}\) and \(fast\_bal[bal_{a}]\)then
40:if\(\textsc{isUniversallyCommutative}(value)\)then
41:\(\textsc{send}(P2B,bal_{a},value)\) to learners
42:else
43:\(val_{a}=val_{a}\bullet value\)
44:\(proof=\langle ballot,val_{a}\rangle_{pri_{a}}\)
45:\(proofs[ballot][val_{a}][a]=proof\)
46:\(\textsc{send}(VERIFY,view,ballot,val_{a},proof)\) to acceptors
47:endfunction
```
**Algorithm 9** Byzantine Generalized Paxos--Acceptor a (agreement)

**Step 3: Acceptors to learners**. Similarly to what happens in classic ballots, the fast ballot equivalent of the _phase 2b_ message, which is sent from acceptors to learners, contains the current ballot number, the command sequence and the \(N-f\) proofs gathered in the verification round. One could think that, since acceptors are already gathering proofs that a value will eventually be committed, learners are not required to gather \(N-f\) votes and they can wait for a single _phase 2b_ message and validate the \(N-f\) proofs contained in it. However, this is not the case due to the possibility of learners learning sequences without the leader being aware of it. If we allowed the learners to learn after witnessing \(N-f\) proofs for just one acceptor then that would raise the possibility of that acceptor not being present in the quorum of _phase 1b_ messages. Therefore, the leader wouldn't be aware that some value was proven and learned. The only way to guarantee that at least one correct acceptor will relay the latest proven sequence to the leader is by forcing the learner to require \(N-f\)_phase 2b_ messages since only then will one correct acceptor be in the intersection of the two quorums. **Arbitrating an order after a conflict**. When, in a fast ballot, non-commutative commands are concurrently proposed, these commands may be incorporated into the sequences of various acceptors in different orders and, therefore, the sequences sent by the acceptors in _phase 2b_ messages will not be equivalent and will not be learned. In this case, the leader subsequently runs a classic ballot and gathers these unlearned sequences in _phase 1b_. Then, the leader will arbitrate a single serialization for every previously proposed command, which it will then send to the acceptors.