Tendermint Consensus Algorithm

L'algorithme de consensus utilisé par Tendermint, est un algorithme de consensus byzantin.
L'avantage de ce dernier est qu'il ne nécessite pas de minage pour apporter une solution au problème des généraux byzantins.

Avant de commencer, un peu de vocabulaire. Les participants dans le protocole sont appelés des validators. A chaque tour de consensus appelé round, un validator est choisi selon l'algorithme de round-robin pour proposer le prochain bloc.

Un round est composé de 3 étapes qui prennent chacune 1/3 du temps d'un round :

• Propose ✅
• Prevote 🙋‍♂️
• Precommit 🔒

Il y a par ailleurs 2 phases supplémentaires : Commit and NewRound.

Propose

Un seul est choisi parmi tous les validators pour proposer le prochain bloc.
Il envoie sa proposition de bloc signée à tous ses pairs, qui le relayent à leur tour.

• Si le validator proposant le bloc est locked sur un bloc, il propose ce bloc.
  Le caractère locked d'un bloc est expliqué dans la suite.

Structure d'une proposition

Source : https://tendermint.com/static/docs/tendermint.pdf

Prevote

Chaque validator vérifie la validité du bloc proposé puis envoie à tous les autres un message prevote signé pour le bloc proposé.

• S'il n'a reçu aucune proposition de bloc, ou si le bloc proposé est invalide, il envoie un message signé nil prevote.
• Si le validator est locked sur un bloc du round précédent, il envoie un prevote pour ce bloc.

Aucun bloc ne peut être locked dans cette étape.

Precommit

Chaque validator vérifie les messages prevote reçus.

• Si le nombre de prevote pour un bloc est supérieur à 2/3 du nombre total de noeuds, alors le validator envoie un message precommit signé à tous et le bloc est locked en abandonnant l'ancien bloc locked.
• Au contraire, si le nombre de nil prevote est supérieur à 2/3 du nombre total de noeuds, alors le bloc locked est unlocked.

Un seul bloc peut être locked à la fois.

• Dans tous les 2 cas, les prevotes sont rassemblés dans un proof-of-lock pour la proposition du prochain round.
• Dans les autres cas, aucun bloc n'est signé ou locked.

A la fin de cette étape, si les noeuds ont reçu plus de 2/3 de precommit pour un bloc, alors on entre dans la phase commit ; sinon on recommence à partir de l'étape propose.

Commit

Il faut 2 conditions pour finaliser le round :

• le noeud doit avoir reçu le bloc en question (car on peut entrer dans cette phase sans avoir reçu le bloc à la fin de l'étape precommit). Une fois le bloc reçu, un message commit est envoyé à tous les autres noeuds avec le bloc signé.
• le nombre de commit pour ce bloc doit être supérieur à 2/3 du nombre total de noeuds.

Dès que ces 2 conditions sont remplies, le noeud affecte au CommitTime le temps actuel et passe à la phase NewRound.
Pour que le consensus soit maintenu, il faut que les horloges de tous les noeuds restent précises pendant toute la durée du consensus.

NewRound

Tant que le consensus sur le bloc proposé n'aboutit pas, il faut réitérer les étapes propose, prevote et precommit.
Voici quelques exemples de cas où le consensus ne peut aboutir :

• Si le noeud proposant le bloc est déconnecté
• Si la connexion réseau est mauvaise, le bloc proposé n'arrive pas à temps
• Si le noeud proposant le bloc est malicieux, il peut proposer un bloc invalide
• Si le bloc proposé est valide, mais le nombre de prevote pour ce bloc est inférieur à 2/3 du nombre total de noeuds ; soit parce que les prevote n'ont pas été reçus à temps avant de passer à l'étape precommit, soit parce qu'il y a eu assez de validators qui n'ont pas voté ou qui ont voté nil
• Si le bloc proposé est valide, et le nombre de prevote pour ce bloc est supérieur à 2/3 du nombre total de noeuds, mais le nombre de precommit pour ce bloc est inférieur à 2/3 du nombre total de noeuds

Conclusion

Vue d'ensemble des différentes étapes

Source : https://tendermint.com/static/docs/tendermint.pdf

Sources

• https://medium.com/softblocks/explaining-how-tendermint-consensus-works-433066cbc465
• https://cosmos-network.gitbooks.io/cosmos-academy/content/introduction-to-the-cosmos-ecosystem/tendermint-bft-consensus-algorithm.html
• https://tendermint.com/static/docs/tendermint.pdf