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
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 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 −
