Tolérance aux pannes byzantines

La tolérance aux pannes byzantines est l'étude de la manière d'atteindre un accord lorsque certains processus peuvent échouer de manière arbitraire, y compris en envoyant des messages contradictoires ou malveillants.

Definition

Une panne byzantine est une déviation arbitraire par rapport à la spécification d'un composant, y compris un comportement malveillant ; la tolérance aux pannes byzantines est la capacité d'un protocole distribué à satisfaire ses conditions de correction malgré un nombre limité de participants défaillants de ce type.

Scope

Ce sujet couvre le problème des généraux byzantins et les limites strictes de résilience qu'il établit (au moins 3f+1 processus, ou des messages signés, pour tolérer f pannes arbitraires), les algorithmes d'accord synchrones par messages oraux et signés, ainsi que les protocoles pratiques asynchrones tolérants aux pannes byzantines tels que PBFT et leurs descendants. Il sous-tend les modèles de confiance des blockchains permissionnées et des services répliqués à haute intégrité.

Core questions

• Combien de processus corrects sont nécessaires pour tolérer un nombre donné de pannes arbitraires ?
• Comment les signatures numériques modifient-elles les limites de résilience pour l'accord byzantin ?
• Comment l'accord byzantin peut-il être rendu suffisamment efficace pour les systèmes asynchrones pratiques ?

Key theories

Limite des généraux byzantins

Avec des messages non authentifiés (oraux), l'accord byzantin n'est résoluble que si plus des deux tiers des processus sont corrects (n > 3f) ; les messages authentifiés avec des signatures infalsifiables assouplissent cette exigence.

Réplication BFT pratique

PBFT montre que l'accord byzantin peut fonctionner dans un système partiellement synchrone avec réplication d'automate à états finis en utilisant un primaire et un protocole en trois phases, atteignant des performances pratiques tout en tolérant jusqu'à un tiers de répliques défaillantes.

Algorithmes d'accord synchrones

Dans le modèle synchrone, les algorithmes récursifs de messages oraux et de messages signés atteignent un accord en f+1 tours, illustrant le coût en complexité de tours pour tolérer des pannes arbitraires.

Clinical relevance

La tolérance aux pannes byzantines est le fondement des systèmes qui doivent résister non seulement aux pannes, mais aussi aux compromissions ou aux comportements malveillants, y compris les blockchains permissionnées, les services répliqués à haute assurance, et les systèmes de contrôle avioniques et aérospatiaux où une défaillance arbitraire des composants ne peut être exclue.

History

Pease, Shostak et Lamport ont établi les limites d'accord en 1980 et les ont dramatisées sous le nom de problème des généraux byzantins en 1982 ; pendant près de deux décennies, l'accord byzantin a été considéré comme trop coûteux pour la pratique jusqu'à ce que le PBFT de Castro et Liskov en 1999 démontre une réplication byzantine asynchrone efficace, ravivant le domaine et influençant plus tard le consensus des blockchains.

Key figures

• Leslie Lamport
• Robert Shostak
• Marshall Pease
• Miguel Castro
• Barbara Liskov

Seminal works

• lamport1982byz
• castro1999
• pease1980

Frequently asked questions

Pourquoi la tolérance à f pannes byzantines nécessite-t-elle 3f+1 processus ?

Les processus corrects doivent parvenir à une décision majoritaire même lorsque f processus défaillants mentent et que f autres peuvent être lents ou inaccessibles ; ce n'est qu'avec plus de trois fois le nombre de processus défaillants que la majorité correcte peut toujours l'emporter sur la combinaison des participants défaillants et en retard.