# Generalized Paxos Made Byzantine
## 5 Byzantine Fault Tolerant Protocol
### Agreement Protocol
```
1:\(learned=\bot\), \(messages=\bot\)
2:upon receive(P2B, \(ballot\), \(value\), \(proofs\)) from acceptor \(a\)do
3:\(valid\_proofs=0\)
4:for\(i\)in\(acceptors\)do
5:\(proof=proofs[i]\)
6:if\(proof_{pub}==\langle ballot,value\rangle\)then
7:\(valid\_proofs++=1\)
8:if\(valid\_proofs\geq N-f\)then
9:\(messages[ballot][value][a]=proofs\)
10:if\(\#(messages[ballot][value])\geq N-f\)then
11:\(learned=\textsc{merge\_sequences}(learned,value)\)
12:
13:upon receive(P2B, \(ballot\), \(value\)) from acceptor \(a\)do
14:if\(\textsc{isUniversallyCommutative}(value)\)then
15:\(messages[ballot][value][a]=true\)
16:if\(\#(messages[ballot][value])>f\)then
17:\(learned=learned\bullet value\)
```

**Algorithm 10** Byzantine Generalized Paxos--Learner 1

This state equivalence between learners is ensured by the correct execution of the protocol since every vote in a fast ballot is equal to the previous vote with a sequence appended at the end (Algorithm 9 lines [43; 44; 45; 46]) and every vote in a classic ballot is equal to all the learned votes concatenated with unlearned votes and new proposals (Algorithm 7 lines [42; 43; 44; 45]) which means that new votes will be extensions of previous proven sequences. However, this begs the question of how the protocol fares when Byzantine faults occur. In particular, the worst case scenario occurs when both \(f\) acceptors and the leader are Byzantine (remember that a process can have multiple roles, such as leader and acceptor). In this scenario, the leader can purposely send _phase 2a_ messages for a sequence that is not prefixed by the previously accepted values. Coupled with an asynchronous network, this malicious message can be delivered before the correct votes of the previous ballot, resulting in different learners learning sequences that may not be extensible to equivalent sequences. To prevent this scenario, the acceptors must ensure that the proposals they receive from the leader are prefixed by the values they have previously voted for. Since an acceptor votes for its \(val_{a}\) sequence after receiving \(N-f\) verification votes for an equivalent sequence and stores it in its _proven_ variable, the acceptor can verify that it is a prefix of the leader's proposed value (i.e., \(proven\sqsubseteq value\)). A practical implementation of this condition is simply to verify that the subsequence of \(value\) starting at the index \(0\) up to index \(length(proven)-1\) is equivalent to the acceptor's _proven_ sequence. ### Checkpointing

BGP includes an additional feature that deals with the indefinite accumulation of state at the acceptors and learners. This is of great practical importance since it can be used to prevent the storage of commands sequences from depleting the system's resources. This feature is implemented by a special command \(C^{*}\), proposed by the leader, which causes both acceptors and learners to safely discard previously stored commands. However, the reason acceptors accumulate state continuously is because each new proven sequence must contain any previous proven sequence. This ensures that an asynchronous network cannot reorder messages and cause learners to learn in different orders. In order to safely discard state, we must implement a mechanism that allows us to deal with reordered messages that do not contain the entire history of learned commands. To this end, when a learner learns a sequence that contains a checkpointing command \(C^{*}\) at the end, it discards every command in its _learned_ sequence except \(C^{*}\) and sends a message to the acceptors notifying them that it executed the checkpoint for some command \(C^{*}\). Acceptors stop participating in the protocol after sending _phase 2b_ messages with checkpointing commands and wait for \(N-f\)notifications from learners. After gathering a quorum of notifications, the acceptors discard their state, except for the command \(C^{*}\), and resume their participation in the protocol.