# Generalized Paxos Made Byzantine
## 5 Byzantine Fault Tolerant Protocol
### View Change  
The goal of the view change subprotocol is to elect a distinguished proposer process, called the leader (code for leader in Algorithm 7), that carries through the agreement protocol (i.e., enables proposed commands to eventually be learned by all the learners). The overall design of this subprotocol is similar to the corresponding part of existing BFT state machine replication protocols [9]. In this subprotocol, the system moves through sequentially numbered views, and the leader for each view is chosen in a rotating fashion using the simple equation \(\textit{leader(view)}=\textit{view mod N}\). The protocol works continuously by having acceptor processes monitor whether progress is being made on adding commands to the current sequence, and, if not, by multicasting a signed suspicion message for the current view to all acceptors suspecting the current leader. Then, if enough suspicions are collected, processes can move to the subsequent view. However, the required number of suspicions must be chosen in a way that prevents Byzantine processes from triggering view changes spuriously. To this end, acceptor processes will multicast a view change message indicating their commitment to starting a new view only after hearing that \(f+1\) processes suspect the leader to be faulty. This message contains the new view number, the \(f+1\) signed suspicions, and is signed by the acceptor that sends it. This way, if a process receives a view-change message without previously receiving \(f+1\) suspicions, it can also multicast a view-change message, after verifying that the suspicions are correctly signed by \(f+1\) distinct processes. This guarantees that if one correct process receives the \(f+1\) suspicions and multicasts the view-change message, then all correct processes, upon receiving this message, will be able to validate the \(f+1\) suspicions and also multicast the view-change message. ```
1:\(ballot_{l}=0,proposals=\bot,accepted=\bot,notAccepted=\bot,view=0\)
2:uponreceive(\(LEADER,view_{u},proofs\)) from acceptor \(a\)do
3:\(valid\_proofs=0\)
4:for\(p\)in\(acceptors\)do
5:\(view\_proof=proofs[p]\)
6:if\(view\_proof_{pub_{p}}==\langle view\_change,view_{a}\rangle\)then
7:\(valid\_proofs^{+}{=}1\)
8:if\(valid\_proofs>f\)then
9:\(view=view_{a}\)
10:upontrigger_next_ballot(\(type\))do
11:\(ballot_{l}+=1\)
12:\(\textsc{send}(BALLOT,type)\) to proposers
13:if\(type==fast\)then
14:\(\textsc{send}(FAST,ballot_{l},view)\) to acceptors
15:else
16:\(\textsc{send}(P1A,ballot_{l},view)\) to acceptors
17:
18:uponreceive(\(PROPOSE,prop\)) from proposer do
19:if\(\textsc{isUniversallyCommutative}(prop)\)then
20:\(\textsc{send}(P2A\_CLASSIC,ballot_{l},view,prop)\)
21:else
22:\(proposals=proposals\bullet prop\)
23:
24:uponreceive(\(P1B,ballot,bala_{a},proven,vala_{a},proofs\)) from acceptor \(a\)do
25:if\(ballot\
eq ballot_{l}\)then
26:return
27:\(valid\_proofs=0\)
28:for\(i\)in\(acceptors\)do
29:\(proof=proofs[proven][i]\)
30:if\(proof_{pub_{i}}==\langle b_{a},proven\rangle\)then
31:\(valid\_proofs+=1\)
32:if\(valid\_proofs>N-f\)then
33:\(accepted[ballot_{l}][a]=proven\)
34:\(notAccepted[ballot_{l}]=notAccepted[ballot_{l}]\bullet(val_{a}\setminus proven)\)
35:if\(\#(accepted[ballot_{l}])\geq N-f\)then
36:\(\textsc{phase\_2A}()\)
37:\(\textsc{phase\_2A}()\)
38:\(maxTried=\textsc{largeest\_seq}(accepted[ballot_{l}])\)
39:\(previousProposals=\textsc{remove\_DUplicates}(notAccepted[ballot_{l}])\)
40:\(maxTried=maxTried\bullet previousProposals\bullet\)proposals
41:\(\textsc{send}(P2A\_CLASSIC,ballot_{l},view,maxTried)\) to acceptors
42:\(proposals=\bot\)
43:endfunction
```  
**Algorithm 7** Byzantine Generalized Paxos--Leader 1  
Finally, an acceptor process must wait for \(N-f\) view-change messages to start participating in the new view (i.e., update its view number and the corresponding leader process). At this point, the acceptor also assembles the \(N-f\) view-change messages, proving that others are committing to the new view, and sends them to the new leader (cf. Algorithm 8).