# Generalized Paxos Made Byzantine
## 5 Byzantine Fault Tolerant Protocol
### Agreement Protocol
Therefore, if non-commutative commands are concurrently proposed in a fast ballot, they will be included in the subsequent classic ballot and the learners will learn them in a total order, thus preserving consistency. #### 5.3.2 Classic Ballots

Classic ballots work in a way that is very close to the original Paxos protocol [1]. Therefore, throughout our description, we will highlight the points where BGP departs from that original protocol, either due to the Byzantine fault model, or due to behaviors that are particular to our specification of the consensus problem. In this part of the protocol, the leader continuously collects proposals by assembling all commands that are received from the proposers since the previous ballot in a sequence (this differs from classic Paxos, where it suffices to keep a single proposed value that the leader attempts to reach agreement on). When the next ballot is triggered, the leader starts the first phase by sending _phase 1a_ messages to all acceptors containing just the ballot number. Similarly to classic Paxos, acceptors reply with a _phase 1b_ message to the leader, which reports all sequences of commands they voted for. In classic Paxos, acceptors also promise not to participate in lower-numbered ballots, in order to prevent safety violations [1]. However, in BGP this promise is already implicit, given (1) there is only one leader per view and it is the only process allowed to propose in a classic ballot and (2) acceptors replying to that message must be in the same view as that leader. As previously mentioned, _phase 1b_ messages contain \(N-f\) proofs for each learned sequence. By waiting for \(N-f\) such messages, the leader is guaranteed that, for any learned sequence \(s\), at least one of the messages will be from a correct acceptor that, due to the quorum intersection property, participated in the verification phase of \(s\). Please note that waiting for \(N-f\)_phase 1b_ messages is not what makes the leader be sure that a certain sequence was learned in a previous ballot. The leader can be sure that some sequence was learned because each _phase 1b_ message contains cryptographic proofs from \(2f+1\) acceptors stating that they would vote for that sequence. Since there are only \(3f+1\) acceptors in the system, no other non-commutative sequence could have been learned. Even though each _phase 1b_ message relays enough proofs to ensure the leader that some sequence was learned, the leader still needs to wait for \(N-f\) such messages to be sure that he is aware of any sequence that was previously learned. Please note that, since each command is signed by the proposer (this signature and its check are not explicit in the pseudocode), a Byzantine acceptor cannot relay made-up commands. However, it can omit commands from its _phase 1b_ message, which is why it is necessary for the leader to be sure that at least one correct acceptor in its quorum took part in the verification quorum of any learned sequence. After gathering a quorum of \(N-f\)_phase 1b_ messages, the leader initiates _phase 2a_ where it assembles a proposal and sends it to the acceptors. This proposal sequence must be carefully constructed in order to ensure all of the intended properties. In particular, the proposal cannot contain already learned non-commutative commands in different relative orders than the one in which they were learned, in order to preserve consistency, and it must contain unlearned proposals from both the current and the previous ballots, in order to preserve liveness (this differs from sending a single value with the highest ballot number as in the classic specification). Due to the importance and required detail of the leader's value picking rule, it will be described next in its own subsection. The acceptors reply to _phase 2a_ messages by broadcasting their verification messages containing the current ballot, the proposed sequence and proof of their committal to that sequence.