Before Blockchains, There Was State Machine Replication (ft. Barbara Liskov and Tim Roughgarden)

Barbara Liskov, lauréate du prix Turing, discute de son parcours en informatique, de ses recherches pionnières sur les systèmes distribués et de la manière dont son travail a jeté les bases des systèmes de blockchain modernes. Elle partage ses réflexions sur l'évolution des protocoles de réplication, le paradigme de réplication de machines à états et l'impact de l'IA sur la recherche en systèmes. Liskov a commencé sa carrière dans la recherche sur les langages de programmation, travaillant sur des concepts tels que les types de données abstraits et l'encapsulation. En 1980, elle s'est tournée vers les systèmes distribués après avoir lu un article de Bob Kahn sur le rêve de l'informatique distribuée. Elle a vu un problème majeur dans la façon dont les programmes distribués pouvaient être construits. Son premier projet dans ce domaine était le langage de programmation Argus, une extension de son langage précédent, qui comprenait un nouveau type d'objet appelé "gardien". Ces gardiens résidaient sur des nœuds de réseau et fournissaient des opérations accessibles à distance, permettant aux programmes distribués d'être composés de nombreux gardiens communiquant entre eux. Argus a également introduit la gestion des pannes, en utilisant des transactions atomiques et un protocole de "commit en deux phases" pour garantir que les calculs distribués réussissent complètement ou n'aient aucun impact. Liskov a souligné l'importance de la modularité dans la construction de grands programmes, la comparant à la structure des théorèmes avec des lemmes. Vers le milieu des années 1980, Liskov et son étudiant Brian Oki se sont concentrés sur le problème de la réplication dans les systèmes distribués. L'idée était de créer des systèmes de fichiers répliqués où plusieurs utilisateurs pourraient accéder aux mêmes fichiers de manière fiable, même en cas de pannes de nœuds. L'approche dominante à l'époque utilisait le verrouillage, ce qui dépendait du bon comportement des autres utilisateurs. Liskov a proposé une approche différente, transférant le travail aux répliques elles-mêmes. Cela a conduit au développement du protocole de réplication "Viewstamped Replication". Ce protocole utilisait un "principal" qui dirigeait les répliques de "sauvegarde". Si le principal cessait de fonctionner, les sauvegardes pouvaient déclencher un nouveau protocole pour élire un nouveau principal, garantissant que l'historique des transactions était préservé. Liskov a noté que ce travail était basé sur des transactions atomiques et s'apparentait à la construction d'un registre distribué, bien qu'ils aient utilisé le terme "journal" à l'époque. Il est important de noter que Viewstamped Replication ne traitait que les "pannes bénignes" (machines qui tombent en panne ou sont silencieuses), et non les "pannes byzantines" (machines qui se comportent de manière malveillante). Liskov a décrit la communauté des systèmes à l'époque comme très soudée, avec des conférences comme SOSP réunissant des chercheurs de divers domaines tels que les bases de données, les réseaux et les systèmes d'exploitation. Elle a contrasté cela avec la fragmentation du domaine aujourd'hui. À la fin des années 1990, Liskov a été ramenée à la recherche sur la réplication avec le développement du protocole "Practical Byzantine Fault Tolerance" (PBFT). Ce travail a été motivé en partie par des appels à propositions de DARPA visant à lutter contre les attaques malveillantes sur Internet. Liskov a eu l'idée avec son étudiant Miguel Castro de développer un protocole de réplication capable de gérer ces attaques malveillantes. Ils ont tiré parti de leur expérience avec Viewstamped Replication, mais ont dû relever le défi des répliques qui mentent et de la manipulation des messages. Pour cela, ils ont utilisé la cryptographie pour assurer l'intégrité et l'authenticité des messages. Le principal défi était de gérer les répliques malveillantes, ce qui nécessitait un plus grand nombre de répliques (3f+1 pour f pannes byzantines, contre 2f+1 pour f pannes bénignes). Le protocole PBFT comprenait une phase supplémentaire pour gérer ce problème, où le groupe de répliques devait collectivement prouver ce qui s'était passé, en utilisant des certificats (composés de 2f+1 messages signés). Liskov a souligné que bien qu'ils aient utilisé des concepts issus du travail théorique sur les certificats, leur contribution était de les intégrer dans un protocole pratique. Liskov a également discuté de l'importance de la collaboration avec des agences de financement gouvernementales comme DARPA et la National Science Foundation (NSF), affirmant qu'elles ont été essentielles au financement de la recherche qui a conduit à l'Internet d'aujourd'hui. Elle a noté que le travail sur PBFT a jeté les bases de nombreux protocoles de blockchain modernes, y compris la façon dont ils prouvent l'ordre des transactions. Elle a également souligné l'idée d'un "service générique comme un service répliqué", un principe de séparation des préoccupations où le protocole de consensus (réplication) est séparé du moteur d'exécution. Ce concept est fondamental pour le paradigme de "réplication de machine à états", où le système est vu comme une machine à états dont les transitions sont déterminées par une séquence ordonnée d'opérations. Liskov a exprimé sa surprise face à la longue période avant que son travail ne soit largement adopté, notant qu'il a fallu environ 10 ans pour que Viewstamped Replication soit utilisé, et que les blockchains sont finalement apparues et ont commencé à adopter ces idées. Elle a reconnu que le protocole Bitcoin initial était différent de PBFT, mais que la communauté blockchain a progressivement réalisé que PBFT et ses successeurs étaient des outils fondamentaux pour résoudre leurs problèmes. Concernant les conseils pour la jeune génération, Liskov a décrit l'informatique comme étant à un "endroit très étrange" en raison de l'avènement de l'IA. Elle pense qu'il y a encore énormément de recherches à faire, en particulier dans le domaine des systèmes sous-jacents à l'IA. Elle a exprimé des inquiétudes quant à l'impact de l'IA sur le choix des études en informatique, mais a insisté sur le fait qu'il y aura toujours un besoin de comprendre comment construire des programmes et de vérifier leur exactitude, même avec l'aide de l'IA. Elle a fait référence à un cours qu'elle a développé avec John Guttag sur la façon de construire de grands programmes, axé sur la conception, la modularité, les spécifications et la vérification, suggérant que ces compétences seront essentielles pour les futurs codeurs qui géreront l'IA plutôt que de l'écrire de zéro. Enfin, Liskov a mentionné que le comportement malveillant est facilité par la plupart des technologies, et qu'il est important de rechercher des moyens de le modifier ou de le contenir. Elle a conclu en affirmant qu'il y a encore beaucoup de recherches passionnantes à faire, notamment dans le domaine des systèmes.