Vérification formelle avancée des preuves à connaissance nulle : comment vérifier une instruction ZK

Afin de comprendre en profondeur comment la technologie de vérification formelle est appliquée à zkVM (machine virtuelle à connaissance nulle), cet article se concentrera sur la vérification d'une seule instruction. Pour la situation globale de la vérification formelle avancée de ZKP (preuve à connaissance nulle), veuillez vous référer à l'article « Vérification formelle avancée de la blockchain à preuve de connaissance nulle » que nous avons publié en même temps.

Qu'est-ce que la vérification des instructions ZK ?

zkVM (machine virtuelle à connaissance nulle) est capable de créer de courts objets de preuve comme preuve qu'un programme spécifique peut s'exécuter sur certaines entrées et se terminer avec succès. Dans le domaine Web3.0, l'application de zkVM permet un débit élevé car le nœud L1 n'a besoin que de vérifier une courte preuve de la transition du contrat intelligent de l'état d'entrée à l'état de sortie, et l'exécution réelle du code du contrat peut être effectuée hors chaîne.

Le prouveur zkVM exécutera d'abord le programme pour générer un enregistrement d'exécution de chaque étape, puis convertira les données de l'enregistrement d'exécution en un ensemble de tableaux numériques (ce processus est appelé « arithmétique »). Ces nombres doivent satisfaire un ensemble de contraintes (c'est-à-dire des circuits), qui incluent les équations de connexion entre des cellules de tableau spécifiques, des constantes fixes, des contraintes de recherche dans la base de données entre les tables et les contraintes qui doivent être satisfaites entre chaque paire de lignes polynomiales adjacentes. équations (alias « portes »). La vérification en chaîne peut confirmer qu'il existe bien un tableau qui satisfait à toutes les contraintes, tout en garantissant que les nombres spécifiques du tableau ne seront pas visibles.

L'exécution de chaque instruction VM est confrontée à de nombreuses contraintes de ce type. Nous appelons ici cet ensemble de contraintes de l'instruction VM son « instruction ZK ». Vous trouverez ci-dessous un exemple de contrainte d'instruction de chargement de mémoire zkWasm écrite en Rust.

ZK La vérification formelle des instructions se fait en effectuant un raisonnement formel sur ces codes, que nous traduisons d'abord dans un langage formel.

Même si une seule contrainte contient une erreur, il est possible pour un attaquant de soumettre une preuve ZK malveillante. Le tableau de données correspondant à la preuve malveillante ne correspond pas au fonctionnement légal du contrat intelligent. Contrairement aux chaînes non ZK telles qu'Ethereum, qui comportent de nombreux nœuds exécutant différentes implémentations EVM (Ethereum Virtual Machine), ce qui rend peu probable que le même bug se produise au même endroit au même moment, une chaîne zkVM n'a qu'une seule implémentation de VM. . De ce seul point de vue, la chaîne ZK est plus fragile que le système Web3.0 traditionnel.

Ce qui est pire, c'est que contrairement aux chaînes non-ZK, puisque les détails de calcul des transactions zkVM ne sont pas soumis et stockés sur la chaîne, après qu'une attaque se produit, il est non seulement très difficile de découvrir les détails spécifiques de l'attaque, mais aussi même identifier l’attaque peut également devenir très difficile en soi.

Le système zkVM nécessite une inspection extrêmement stricte. Malheureusement, l'exactitude du circuit zkVM est difficile à garantir.

Pourquoi est-il difficile de vérifier les instructions ZK ?

VM (Virtual Machine) est l'une des parties les plus complexes de l'architecture système Web3.0. Les fonctions puissantes des contrats intelligents sont au cœur de la prise en charge des capacités Web3.0. Leur puissance vient des machines virtuelles sous-jacentes, qui sont à la fois flexibles et complexes : pour accomplir les tâches générales de calcul et de stockage, ces machines virtuelles doivent être capables de prendre en charge de nombreuses instructions. et les États. Par exemple, l'implémentation geth de l'EVM nécessite plus de 7 500 lignes de code en langage Go. De même, le circuit ZK qui contraint l’exécution de ces instructions est tout aussi volumineux et complexe. Comme dans le projet zkWasm, l'implémentation du circuit ZK nécessite plus de 6000 lignes de code Rust.

Architecture de circuit zkWasm

Comparés aux circuits ZK dédiés utilisés dans les systèmes ZK conçus pour des applications spécifiques (telles que les paiements privés), les circuits zkVM sont beaucoup plus grands : leurs règles contraignantes Le nombre peut être un ou deux ordres de grandeur supérieurs, et le tableau arithmétique peut comprendre des centaines de colonnes contenant des millions de cellules numériques.

Que signifie la vérification des instructions ZK ?

Nous voulons ici vérifier l'exactitude de l'instruction XOR dans zkWasm. Techniquement parlant, la table d'exécution de zkWasm correspond à une séquence d'exécution légale de Wasm VM. Donc d'un point de vue macro, ce que nous voulons vérifier, c'est que chaque exécution de cette instruction générera toujours un nouvel état légal de zkVM : chaque ligne du tableau correspond à un état légal de la VM, et la ligne suivante est toujours générée par exécuter les instructions VM correspondantes. La figure ci-dessous montre le théorème formel de l'exactitude de l'instruction XOR.

Ici, "state_rel i st" indique que l'état "st" est l'état zkVM légal du contrat intelligent à l'étape "i". Comme vous pouvez le deviner, prouver "state_rel (i+1)..." n'est pas anodin.

Comment vérifier la commande ZK ?

Malgré la sémantique informatique d'un entier, effectuez un calcul XOR, puis stockez le nouvel entier calculé dans la même pile. De plus, les étapes d'exécution de cette instruction doivent être intégrées dans l'ensemble du processus d'exécution du contrat intelligent, et l'ordre et le calendrier de son exécution doivent être corrects.

Par conséquent, l'effet d'exécution de l'instruction XOR devrait être d'extraire deux nombres de la pile de données, de pousser leurs résultats XOR et en même temps d'incrémenter le compteur du programme pour pointer vers l'instruction suivante du contrat intelligent.

Il n'est pas difficile de voir que la définition des propriétés d'exactitude ici est généralement très similaire à la situation à laquelle nous sommes confrontés lors de la vérification des VM de bytecode traditionnelles (telles que l'interpréteur EVM dans les nœuds Ethereum L1). Elle s'appuie sur une définition abstraite de haut niveau de l'état de la machine (ici la mémoire de la pile et le flux d'exécution) et une définition du comportement attendu de chaque instruction (ici la logique arithmétique).

Cependant, comme nous le verrons ci-dessous, en raison de la nature particulière de ZKP et zkVM, le processus de vérification de leur exactitude est souvent très différent de celui des VM classiques. Le simple fait de vérifier l'instruction unique que nous avons ici dépend de l'exactitude de nombreuses tables dans zkWASM : parmi elles se trouve une table de plage utilisée pour limiter la taille de la valeur, une table de bits (table de bits) utilisée pour le résultat intermédiaire du calcul des bits binaires. , Une table d'exécution qui stocke l'état de la VM de taille constante par ligne (similaire aux données dans les registres et les verrous d'un processeur physique) et la mémoire qui représente dynamiquement l'état de la VM de taille variable (mémoire, pile de données et pile d'appels), ainsi que les sauts. les tables.

Première étape : pile de mémoire

Semblable à une VM traditionnelle, nous devons nous assurer que les deux paramètres entiers de l'instruction peuvent être lus à partir de la pile et que leurs valeurs de résultat XOR sont correctement réécrites dans la pile. La représentation formelle de la pile semble également assez familière (il existe également de la mémoire globale et de la mémoire tas, mais l'instruction XOR ne les utilise pas).

zkVM utilise un schéma complexe pour représenter les données dynamiques car le prouveur ZK ne prend pas en charge nativement les structures de données telles que les piles ou les tableaux. Au contraire, pour chaque valeur placée sur la pile, la table mémoire enregistre une ligne distincte et certaines colonnes sont utilisées pour indiquer l'heure effective de l'entrée. Bien entendu, les données de ces tables peuvent être contrôlées par des attaquants. Certaines contraintes doivent donc être imposées pour garantir que les entrées de la table correspondent réellement aux instructions réelles de la pile lors de l'exécution du contrat. Ceci est réalisé en calculant soigneusement le nombre de poussées de pile pendant l'exécution du programme. Lors de la vérification de chaque instruction, nous devons nous assurer que ce décompte est toujours correct. De plus, nous disposons d'une série de lemmes qui relient les contraintes générées par une seule instruction aux recherches de table et aux vérifications d'intervalles de temps qui implémentent les opérations de pile. Depuis le niveau supérieur, les contraintes de comptage pour les opérations de mémoire sont définies comme suit.

Étape 2 : Opérations arithmétiques

Semblable à la VM traditionnelle, nous voulons nous assurer que l'opération XOR au niveau du bit est correcte. Cela semble facile, après tout, les processeurs de nos ordinateurs physiques sont capables de le faire en une seule fois.

Mais pour zkVM, ce n'est en fait pas simple. Les seules instructions arithmétiques supportées nativement par le prouveur ZK sont l'addition et la multiplication. Afin d'effectuer des opérations sur les bits binaires, VM utilise un schéma plutôt complexe, dans lequel une table stocke les résultats des opérations au niveau des octets fixes, et l'autre table agit comme un « bloc-notes » pour montrer comment effectuer des opérations sur plusieurs lignes de la table. Le nombre de 64 bits est décomposé en 8 octets puis réassemblé pour donner le résultat.

Fragment de spécification de table de bits ZkWasm

est une opération XOR très simple dans les langages de programmation traditionnels, mais ici de nombreux lemmes sont nécessaires pour vérifier l'exactitude de ces tables auxiliaires. Pour nos instructions nous avons :

Troisième étape : Flux d'exécution

Semblable à une VM traditionnelle, nous devons nous assurer que la valeur du compteur du programme est correctement mise à jour. Pour les instructions séquentielles comme XOR, le compteur du programme doit être incrémenté de un après chaque étape.

Étant donné que zkWasm est conçu pour exécuter du code Wasm, il garantit également que la nature immuable de la mémoire Wasm est maintenue tout au long de l'exécution.

Les langages de programmation traditionnels prennent en charge nativement les types de données tels que les valeurs booléennes, les entiers 8 bits et les entiers 64 bits, mais dans les circuits ZK, les variables changent toujours dans la plage des entiers modulo les grands nombres premiers (≈ 2254) . Étant donné que les machines virtuelles fonctionnent généralement en 64 bits, les développeurs de circuits doivent utiliser un système de contraintes pour garantir qu'ils disposent des plages numériques correctes, et les ingénieurs de vérification formelle doivent suivre les propriétés invariantes de ces plages tout au long du processus de vérification. Le raisonnement sur les flux d'exécution et les tables d'exécution implique toutes les autres tables auxiliaires, nous devons donc vérifier que les plages de toutes les données des tables sont correctes.

Semblable au cas de la gestion des numéros d'opérations en mémoire, zkVM nécessite un ensemble similaire de lemmes pour vérifier le flux de contrôle. Plus précisément, chaque instruction d'appel et de retour nécessite l'utilisation d'une pile d'appels. La pile d'appels est implémentée à l'aide d'un schéma de table similaire à la pile de données. Pour l'instruction XOR, nous n'avons pas besoin de modifier la pile d'appels ; mais lors de la vérification de l'intégralité de l'instruction, nous devons toujours suivre et vérifier si le nombre d'opérations de flux de contrôle est correct.

Vérifiez cette instruction

Rassemblons toutes les étapes et vérifions le théorème d'exactitude de bout en bout de l'instruction zkWasm XOR. Les vérifications suivantes sont effectuées dans un environnement de preuve interactif, où chaque étape de construction formelle et de raisonnement logique est soumise aux contrôles automatiques les plus rigoureux.

Comme vu ci-dessus, la vérification formelle du circuit zkVM est réalisable. Mais il s’agit d’une tâche difficile qui nécessite de comprendre et de suivre de nombreuses propriétés invariantes complexes. Cela reflète la complexité du logiciel à vérifier : chaque lemme impliqué dans la vérification doit être traité correctement par le développeur du circuit. Compte tenu des enjeux élevés, il serait utile de les faire vérifier automatiquement par un système de vérification formel, plutôt que de s’en remettre uniquement à un examen humain minutieux.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!