# Generalized Paxos Made Byzantine
## 5 Byzantine Fault Tolerant Protocol
### Agreement Protocol
This is because, of the \(N-f\) messages it received, \(f\) may not have participated in the quorum and another \(f\) may be Byzantine and lie about their vote, which only leaves one correct acceptor that participated in the quorum and a single vote is not enough to determine if the sequence was learned or not. If the leader picks the wrong sequence, it would be proposing a sequence \(s^{\prime}\) that is non-commutative to a learned sequence \(s\). Since the learning of \(s\) was delayed before reaching \(l_{2}\), \(l_{2}\) could learn \(s^{\prime}\) and be in a conflicting state with respect to \(l_{1}\), violating consistency. In order to prevent this, sequences accepted by a quorum of acceptors must be monotonic extensions of previous accepted sequences. Regardless of the order in which a learner learns a set of monotonically increasing sequences, the resulting state will be the same. The additional verification phase is what allows acceptors to prove to the leader that some sequence was accepted by a quorum. By gathering \(N-f\) proofs for some sequence, an acceptor can prove that at least \(f+1\) correct acceptors voted for that sequence. Since there are only another \(2f\) acceptors in the system, no other non-commutative value may have been voted for by a quorum. Next, we explain each of the protocol's steps for fast ballots in greater detail. **Step 1: Proposer to acceptors**. To initiate a fast ballot, the leader informs both proposers and acceptors that the proposals may be sent directly to the acceptors. Unlike classic ballots, where the sequence proposed by the leader consists of the commands received from the proposers appended to previously proposed commands, in a fast ballot, proposals can be sent to the acceptors in the form of either a single command or a sequence to be appended to the command history. These proposals are sent directly from the proposers to the acceptors. **Step 2: Acceptors to acceptors**. Acceptors append the proposals they receive to the proposals they have previously accepted in the current ballot and broadcast the resulting sequence and the current ballot to the other acceptors, along with a signed tuple of these two values. Intuitively, this broadcast corresponds to a verification phase where acceptors gather proofs that a sequence gathered enough support to be committed. These proofs will be sent to the leader in the subsequent classic ballot in order for it to pick a sequence that preserves consistency. To ensure safety, correct learners must learn non-commutative commands in a total order. When an acceptor gathers \(N-f\) proofs for equivalent values, it proceeds to the next phase. That is, sequences do not necessarily have to be equal in order to be learned since commutative commands may be reordered. Recall that a sequence is equivalent to another if it can be transformed into the second one by reordering its elements without changing the order of any pair of non-commutative commands (in the pseudocode, proofs for equivalent sequences are being treated as belonging to the same index of the _proofs_ variable, to simplify the presentation). By requiring \(N-f\) votes for a sequence of commands, we ensure that, given two sequences where non-commutative commands are differently ordered, only one sequence will receive enough votes even if \(f\) Byzantine acceptors vote for both sequences. Outside the set of (up to) \(f\) Byzantine acceptors, the remaining \(2f+1\) correct acceptors will only vote for a single sequence, which means there areonly enough correct processes to commit one of them. As in the non-Byzantine protocol, the fact that proposals are sent as extensions to previous sequences makes the protocol robust against the network reordering of non-commutative commands.