Computing polyvalent basé sur la preuve avec Magnetar

En un coup d’œil

• Une nouvelle forme de calcul. Les preuves de zéro connaissance permettent de exécuter un travail et d’obtenir, en plus du résultat, une brève preuve que le programme s’est exécuté correctement. Quiconque peut vérifier cette preuve en quelques millisecondes, sans avoir à réexécuter le programme, sans avoir à faire confiance à celui qui l’a exécuté, et sans avoir besoin de données sur lesquelles le programme s’est exécuté.
• Trois défis majeurs ont entravé l’adoption générale : rendre les preuves suffisamment rapides pour être produites, les rendre accessibles aux programmes ordinaires sans expertise en cryptographie, et s’appuyer sur une cryptographie qui restera digne de confiance des décennies à venir.
• Le Magnetar fait des progrès majeurs sur les trois défis concernés. Il prouve que les programmes écrits en Rust, Go ou C fonctionnent en moyenne 10 à 39 fois plus rapidement que les systèmes les plus rapides antérieurs, et sa sécurité repose uniquement sur des fonctions de hachage standard. C’est le résultat le plus récent d’une décennie de recherche au Microsoft Research sur la mise en pratique des preuves sans connaissances.

Une nouvelle forme de calcul

Chaque résultat produit par un ordinateur comporte une question implicite : l’programme s’est-il exécuté comme prétendu et a-t-il donné des sorties correctes ? Aujourd’hui, répondre à cette question nécessite souvent un certain niveau de confiance, accompagné de vérifications. Nous faisons confiance à l’opérateur, au fournisseur, à la contrepartie ou à l’agent, et nous nous appuyons sur des contrats, des audits et des logs pour établir cette confiance.

Les preuves de zéro connaissance offrent une approche fondamentalement différente pour établir la confiance. Un programme s'exécute, et avec son sortie, il produit une petite preuve, un certificat cryptographique attestant que ce programme, avec ces entrées, a produit cette sortie. La preuve est de petite taille et facile à vérifier. Quiconque la reçoit peut confirmer le résultat en quelques millisecondes, sans avoir à réexécuter le programme, et peut transmettre la preuve à quiconque a besoin de cette même assurance. Avec la propriété de zéro-connaissance, la preuve ne révèle rien non plus concernant les entrées qui doivent rester privées.

Cela change ce que signifie la justesse dans le monde réel. Un résultat ne doit plus être considéré comme fiable en raison de la personne qui l’a produit. Il peut être vérifié en fonction de ce qui l’accompagne. Un agent IA agissant au nom d’une personne pourrait joindre une preuve montrant que chaque action respectait la politique donnée. Les institutions financières régulées pourraient prouver que les transactions ont été traitées correctement sans rendre leurs transactions publiques. Tout cela devient possible lorsque la production d’une preuve devient aussi routinière que l’exécution d’un programme.

Trois défis majeurs

Les preuves de zéro connaissance ont été inventées dans les années 1980, et les idées qui sous-tendent la preuve de l'exécution d'un programme existent depuis près du même temps. Ce qui les empêche de devenir un outil général est lié à trois défis qui ont résisté à être résolus en même temps.

Efficacité. Dans le passé, la production d’une preuve nécessitait des milliards de fois plus de calcul que l’exécution du programme lui-même. Des années de recherche ont permis de réduire cette surcharge, mais les systèmes les plus rapides ont atteint leur vitesse en faisant des compromis ailleurs.

Generalité et utilité. De nombreux systèmes de preuve exigent que les développeurs réécrivent manuellement leur programme en tant que circuit cryptographique, qui représente une description arithmétique fixe de cette computation exacte. Cela prend des mois. Chaque modification de l’application implique un nouveau circuit, et la traduction elle-même est souvent source d’erreurs de sécurité. Une alternative polyvalente consiste à prouver l’exécution d’un processeur ordinaire, afin que tout programme compilé puisse être prouvé tel quel. Jusqu’à récemment, cette polyvalence était au prix d’une performance ou d’une sécurité très limitées.

Sécurité. Une preuve n’est aussi forte que la cryptographie qui la sous-tend. De nombreux systèmes de preuve reposent sur des courbes elliptiques, qui peuvent être brisées par un ordinateur quantique suffisamment puissant. Microsoft aborde ce problème avec son programme Quantum Safe, qui fera passer ses produits et services vers la cryptographie post-quantique, une ambition qu’il a récemment repoussée à 2029. Les systèmes de preuve post-quantique existent déjà, mais certains reposent sur des hypothèses de réseau, et la plupart reposent sur de nouvelles fonctions cryptographiques inventées pour réduire les coûts de validation. Ces nouvelles fonctions cryptographiques n’ont pas été soumises aux décennies de vérification que l’on a fait subir à la cryptographie qui protège l’internet actuel, et certains reposent sur des conjectures mathématiques concernant les codes correcteurs d’erreurs qui ne sont pas prouvés. Ils ont obtenu leur rapidité grâce à de fortes hypothèses.

Série de podcasts

La Forme des Choses à venir

Rejoignez Doug Burger de Microsoft et les invités lorsqu’ils explorent les vérités fondamentales concernant l’IA et la manière dont elle va transformer l’avenir.

Plus d’une décennie de travail

Pendant plus d’une décennie, Microsoft Research a travaillé pour rendre les preuves de zéro connaissance et l’informatique vérifiable pratiques. Les recherches initiales ont suivi deux approches, toutes deux pratiques uniquement pour de petits programmes. La première (s’ouvre dans une nouvelle fenêtre) (s’ouvre dans une nouvelle fenêtre) permet à un verificateur de vérifier une longue computation en entrant une courte conversation avec le proposateur, en utilisant une technique appelée le protocole de vérification de la somme (s’ouvre dans une nouvelle fenêtre), mais cela ne s’applique qu’aux computations ayant une structure en couches particulière. La seconde (s’ouvre dans une nouvelle fenêtre) (s’ouvre dans une nouvelle fenêtre) utilise la cryptographie de courbes elliptiques pour créer des preuves très simples pour presque tous les calculs. Mais cela nécessite une configuration de confiance unique, impliquant des informations secrètes qui, si elles sont divulguées, permettraient à n’importe qui de fabriquer des preuves. Cette approche est également vulnérable aux ordinateurs quantiques.

En 2019, un nouveau système de preuve zéro-knowledge appelé Spartan est revenu à l’approche de vérification de somme et a permis son utilisation pour des programmes à usage général sans configuration de confiance. Spartan peut également être instancié avec différents blocs cryptographiques. Cette flexibilité a ensuite permis que le système de preuve soit construit uniquement sur des fonctions de hachage. Une série de résultats a alors complété les éléments restants :

• Phalanx (apparaît dans une nouvelle fenêtre), en 2021, a montré comment exploiter la répétition, comme un processeur exécutant le même cycle d’instructions à chaque étape, afin de prouver que les calculs sont une ordre de grandeur plus rapides que ceux effectués par Spartan. La description du processeur de Magnetar est basée sur cette idée.
• Nova (s’ouvre dans une nouvelle fenêtre), HyperNova (s’ouvre dans une nouvelle fenêtre), NeutronNova (s’ouvre dans une nouvelle fenêtre), Neo et SuperNeo (s’ouvre dans une nouvelle fenêtre) ont montré que l’arrêt précoce du Spartan et la combinaison des résultats partiels permettent de prouver les calculs de tout ordre à un coût beaucoup plus faible.
• Brakedown (s’ouvre dans une nouvelle fenêtre), en 2021, a introduit un système de engagement rapide basé sur les hachages et l’a combiné avec Spartan, donnant ainsi la première variante de Spartan dont la sécurité repose sur des fonctions de hachage standard.
• Spice (s’ouvre dans une nouvelle fenêtre), Lasso (s’ouvre dans une nouvelle fenêtre), Nebula (s’ouvre dans une nouvelle fenêtre), et ensuite Twist and Shout (s’ouvre dans une nouvelle fenêtre) ont permis de prouver que les opérations de mémoire au cœur d’un processeur polyvalent sont peu coûteuses, et Jolt (s’ouvre dans une nouvelle fenêtre) a montré que leur combinaison avec Spartan permet d’effectuer efficacement l’exécution d’un processeur complet.
• Plus tôt cette année, Vega (s’ouvre dans une nouvelle fenêtre) a appliqué cette technologie à l’identité numérique, prouvant les informations d’une carte gouvernementale en moins d’un dixième de seconde.
• Plus récemment, BinarySpartan (s’ouvre dans une nouvelle fenêtre) a introduit Spartan dans les domaines binaires, où la logique d’un processeur et les fonctions de hachage standard peuvent être exprimées efficacement. BinarySpartan s’appuie également sur Ligerito (s’ouvre dans une nouvelle fenêtre), un système de contrat de style Brakedown avec des preuves beaucoup plus courtes, ainsi que sur le déplacement de cercle (s’ouvre dans une nouvelle fenêtre), qui rend l’engagement de vecteurs de bits très efficace.

Chacun de ces éléments a résolu une partie du problème. Le magnetar est là où les éléments se rassemblent.

Magnetar

Magnetar est une machine virtuelle de zéro-knowledge, ou zkVM, et elle fait des progrès majeurs sur les trois défis en même temps.

Il est de usage général. Magnetar prouve l’exécution de RISC-V, une architecture de processeur ouverte dotée de compilateurs mûrs pour toutes les langues majeures. Un développeur écrit un programme en Rust, Go ou C, le compile comme d’habitude, et Magnetar prouve son exécution telle qu’elle est écrite. Considérez ce que cela signifie en pratique : une politique de business, un pipeline de données ou un interprète pour la Machine virtuelle Ethereum (EVM) ne sont que des programmes, et les ingénieurs qui les maintiennent peuvent prouver leur exécution exactement telle qu’elle est écrite. Par conséquent, la preuve devient une activité non spécialisée.

Il est plus rapide que les systèmes précédents de la même catégorie. Magnetar démontre 7,2 à 8,7 millions d’instructions processeur par seconde sur un ordinateur portable. À travers 15 programmes de benchmark, allant du hachage cryptographique aux transferts de tokens dans un petit interpréteur EVM, il est en moyenne 10 à 39 fois plus rapide que les zkVMs les plus rapides existants sur la même machine, et plus de 300 fois plus rapide que deux autres systèmes dans un benchmark de transfert de tokens. Un Magnetar optimisé démontre 9,5 à 12,8 millions de cycles par seconde, ce qui augmente chaque gain de vitesse rapporté ici d’environ 1,3×. Ses tests se terminent en environ 12 millisecondes.

Sa sécurité repose sur la cryptographie standard. Magnetar dépend d’une fonction de hachage standard telle que SHA-256 ou SHA-3, des primitives qui protègent déjà les systèmes de toutes les organisations. Il n’est pas nécessaire d’utiliser des courbes elliptiques, des réseaux de graphes, des fonctions de hachage à usage spécial, des configurations de confiance, ni de conjectures non prouvées concernant les codes de correction d’erreurs. Les fonctions de hachage sont les primitives les plus étudiées dans le toolkit cryptographique, et elles constituent la base des signatures basées sur les hachages sans état, qui ont été standardisées par le NIST en tant que option post-quantique conservatrice. Pour un système qui doit rester fiable pendant de nombreuses décennies à venir, compter uniquement sur des fonctions de hachage standard élimine toute nécessité de migration cryptographique.

La même décision de conception produit un deuxième avantage. Vérifier une preuve de Magnetar consiste principalement à évaluer des fonctions de hachage standard et l’arithmétique de champ binaire, qui sont précisément les opérations que Magnetar prouve efficacement. Vérifier donc une preuve représente une tâche ordinaire pour lui. C’est ce qui permet à Magnetar de prouver des calculs de tout volume, en les décomposant en parties puis en combinant ces parties. Cela permet également à Magnetar de prouver un système en cours de développement, tel qu’un livret ou une blockchain.

Le document technique fournit le design complet, l’analyse de sécurité et les mesures.

Regarder vers l’avenir

Magnetar progresse les preuves de zéro-connaissance et l’informatique vérifiable jusqu’à un niveau où elles peuvent être construites sur la cryptographie en laquelle les organisations ont déjà confiance, à des vitesses permettant leur utilisation par des ingénieurs qui écrivent du code normal. Magnetar permet une future où les preuves cryptographiques sont un résultat routinier de l’calcul. Nous nous attendons que les leaders technologiques cessent de poser des questions. Que les preuves d'exécution soient pratiques ou non et se concentrer plutôt sur ce qui donne des résultats serait Ils préfèrent vérifier plutôt que de prendre sur eux la confiance.

Si vous êtes intéressé par explorer comment les preuves de zéro connaissance peuvent soutenir votre cas d'usage, nous aimerions entendre votre avis (ouvert dans une nouvelle fenêtre).