We have recently announced a technical report on Tenderbake, a classical BFT style consensus algorithm inspired by Tendermint and motivated by Tezos. This work is a joint effort with CEA List.
Why a new consensus algorithm?
Our main motivation was to experiment with consensus algorithms offering deterministic finality while relaxing the synchrony** assumption usual in Nakamoto-style consensus algorithms.
Why Tendermint?
At the time we began our experiments, Tendermint was the first adaptation of classical BFT style consensus algorithms to the blockchain context. In particular, Tendermint improved the message complexity of the classical algorithms DLS and PBFT. Tendermint also came with a correctness proof.
What is our contribution?
Our contribution is mostly at a theoretical level: we adapted Tendermint’s system model to Tezos, changed the algorithm accordingly, and provided proofs that the consensus properties still hold.
Concretely, the system model we considered does not include the less standard “gossip communication” assumption used in Tendermint. This assumption states that communication is reliable (messages cannot be lost) even during periods of asynchrony. We dropped this assumption and assume instead that communication is reliable only in the synchronous periods. We further assume that nodes are equipped with loosely synchronised clocks, as is the case in Tezos. Thanks to clocks, we can achieve round synchronization without relying on timers. This in turn implies that message buffers can have a constant size. (This is not the case with Tendermint where message buffers can theoretically grow unboundedly large.) Having constant size buffers is important for security reasons, it makes it difficult for a node to be spammed.
Another consequence of the fact the communication may be unreliable in the asynchronous periods is that we need to attach quorum certificates*** to messages. This means that some consensus messages are larger than in Tendermint. However, the message size can be considerably reduced by using modern cryptography (for instance aggregatable signatures). By resending quorum certificates, Tenderbake can achieve faster finalization than Tendermint.
How about next steps?
Regarding Tenderbake, we are working on a prototype implementation of the algorithm. We are also investigating how to use modern cryptography to reduce both message complexity and message size. Finally, the most challenging part is to have an economic analysis of Tenderbake, that is, answer questions like what are the right incentives in the presence of rational players.
Relaxing the synchrony assumption currently used in Tezos, by using partial synchrony instead, has the consequence that one can only tolerate weaker adversaries, that is, adversaries with up to a third of the stake, while under synchrony one can tolerate adversaries with up to a half of the stake. To tolerate stronger adversaries, one approach would be to take “the best of both worlds” and combine a Nakamoto-style consensus algorithm with a classical BFT style algorithm, like in existing finality gadgets such as Afgjort, Doomslug, Grandpa, Thunderella.
Finally, we remark that we would propose a new consensus algorithm only when there is evidence that it is substantially better than the current algorithm.
** By synchrony we mean that there is an upper bound on message delays. By partial synchrony we mean that periods of asynchrony alternate with periods of synchrony.
*** A quorum certificate is a set of signatures from at least two thirds of the validators for one level.
