Classic PBFT Clause Samples

Classic PBFT like algorithms‌ It is interesting to see that most partially synchronous con- sensus algorithms already collect forms of cryptographic ev- idence like signatures or certificates to guarantee agreement upon decision. While this is a characteristic of PBFT [11], this is the case of modern algorithms that build upon it including Tendermint [8] and HotStuff [33]. One could naturally be tempted to reuse these signatures and certificates to piggy- back practical justifications in the existing messages of the original consensus algorithms to turn them into account- able consensus algorithms. Although threshold signatures do not convey enough information to identify which process is guilty, signatures are generally sufficient. We show below that, unfortunately, this transformation cannot work. L L The intuition of the proof is split in the four following steps while the full proof is deferred to our technical report. First, we define the class of ‘classic’ or PBFT-like consensus algo- rithms and denote it . Second, we show that HotStuff [33], PBFT [11] and Tendermint [4] belong to this class . Third, we define a practical extension of PBFT-like consensus al- gorithms that piggybacks messages. By ‘practical’ we mean that piggybacked messages have a bounded staleness to pre- vent the justification communication to be superlinear (e.g., quadratic) in 𝑛. Finally, we prove that there exist executions leading to disagreement with different sets of Byzantine pro- cesses that correct processes cannot distinguish. L L (1) Class of PBFT-like algorithms. contains algo- rithms that all rely on a leader that rotates in a round-▇▇▇▇▇ fashion across views and proposes a suggestion in its view. Two local variables per process, preparation and decision, have values that relate with each other such that for a pro- cess 𝑗 to have a decision, 𝑛 − 𝑡0 processes, including 𝑗 itself, must have had the same value as a preparation. During view changes, if 𝑡 < 𝑡0, then a preparation implies a propagation of a value to the leader within messages announcing the new view. L L −