Comment concevoir un meilleur schéma de récursivité de preuve ?
Presque tous les problèmes rencontrés dans les pistes zkRollup et zkEVM sont essentiellement des problèmes algorithmiques. La principale raison pour laquelle l’accélération matérielle ZK-Proof est fréquemment mentionnée est que les algorithmes actuels sont généralement lents.
Afin d'éviter de tomber dans la situation embarrassante du « l'algorithme ne suffit pas, le matériel est utilisé pour inventer », nous devons résoudre le problème à partir de l'essence de l'algorithme. Concevoir une récursion exquise à l'épreuve des livraisons Le schéma est la clé pour résoudre ce problème.
Avec le développement continu des contrats intelligents, de plus en plus d'applications Web3 apparaissent progressivement, et le volume de transactions de la couche 1 traditionnelle, comme Ethereum, augmente rapidement et des congestions peuvent survenir à tout moment. Comment obtenir une plus grande efficacité tout en garantissant la sécurité fournie par la couche 1 est devenu un problème urgent à résoudre.
Pour Ethereum, zkRollup utilise l'algorithme de preuve de connaissance nulle comme composant sous-jacent pour déplacer les calculs coûteux qui devaient initialement être effectués sur la couche 1 hors chaîne et fournir une preuve de l'exactitude de l'exécution à la chaîne. La piste comprend des projets tels que StarkWare, zkSync, défilement, ainsi que Renard Tech.
En fait, dans la conception de zkRollup, les exigences d'efficacité sont très élevées : on espère que la valeur de preuve soumise est suffisamment petite pour réduire la quantité de calcul de la couche 1. Afin d'obtenir une longueur de preuve suffisamment petite, chaque Le projet zkRollup améliore la conception de l'algorithme et de l'architecture. Par exemple, Fox a développé son algorithme de preuve FOAKS en combinaison avec le dernier algorithme de preuve à connaissance nulle pour obtenir le temps et la longueur de preuve optimaux.
De plus, au stade de la vérification des preuves, le moyen le plus trivial consiste à générer des preuves de manière linéaire et à les vérifier séquentiellement. Afin d'améliorer l'efficacité, la première chose à laquelle tout le monde pense est de regrouper plusieurs preuves en une seule, communément appelée agrégation de preuves.
Intuitivement parlant, la vérification des preuves générées par zkEVM est un processus linéaire, et le vérificateur doit vérifier tour à tour chaque valeur de preuve générée. Cependant, l’efficacité de cette méthode de vérification est relativement faible et la surcharge de communication est relativement importante. Pour le scénario zkRollup, une surcharge plus élevée côté vérificateur signifie davantage de calculs de couche 1, ce qui entraînera également des frais de gaz plus élevés.
Regardons d'abord un exemple : Alice veut prouver au monde qu'elle est allée à Fox Park du 1er au 7 de ce mois. Pour cette raison, elle peut prendre une photo dans le parc avec le journal du jour chaque jour du 1er au 7, et ces sept photos serviront de preuve.
Mettre sept photos directement dans une enveloppe dans l'exemple ci-dessus est une agrégation de preuves au sens intuitif, qui correspond à connecter différentes preuves entre elles et à les vérifier linéairement en séquence, c'est-à-dire vérifier d'abord la première preuve, puis vérifier la deuxième preuve.
Deux preuves et preuves ultérieures. Le problème est que cette approche ne changera ni la taille de la preuve ni le temps de la preuve, ce qui revient à prouver et vérifier un par un. Si vous souhaitez obtenir une compression d'espace logarithmique, vous devez utiliser la preuve de récursion mentionnée ci-dessous.
Schéma de récursivité de preuve utilisé par Halo2 et STARK
Afin de mieux expliquer ce qu'est une preuve récursive, revenons à l'exemple ci-dessus.
Les sept images d'Alice sont sept preuves. Pensez maintenant à les fusionner, pour qu'Alice puisse prendre une photo le 1er, prendre cette photo le 2ème et le journal le 2ème, et prendre la photo le 2ème et le journal le 3ème photo. Par analogie, Alice a pris la dernière photo le 7 avec la photo du 6 et le journal le 7, et d'autres amis peuvent vérifier qu'ils sont du 1er au 7 lorsqu'ils voient la dernière photo du 7.
Alice est toutes allées au parc. On peut voir que les sept photos d’épreuve précédentes ont été compressées en une seule. Et une compétence clé dans ce processus est « les photos contenant des photos », ce qui équivaut à imbriquer de manière récursive des photos précédentes dans des photos suivantes. C'est différent de rassembler beaucoup de photos et de prendre une seule photo.
L'astuce de preuve récursive de zkRollup peut considérablement compresser la taille de la preuve. Concrètement, chaque transaction générera une preuve. Nous définissons le circuit de calcul de transaction d'origine comme C0, P0 comme preuve d'exactitude de C0 et V0 comme processus de calcul de vérification de P0.
Le prouveur convertit également V0 en circuit correspondant, noté C0′. Actuellement, pour le processus de calcul de la preuve C1 d'une autre transaction, les circuits de C0' et C1 peuvent être fusionnés. De cette manière, une fois la preuve d'exactitude P1 du circuit fusionné vérifiée, cela équivaut à vérifier les deux circuits ci-dessus en même temps. L'exactitude de la transaction, c'est-à-dire la compression, est obtenue.
En regardant le processus ci-dessus, on peut constater que le principe de la compression est de convertir le processus de vérification et de preuve en un circuit, puis de générer « preuve pour preuve », donc de ce point de vue, c'est une opération qui peut se répéter continuellement. vers le bas, donc également connue sous le nom de preuve récursive.
Le schéma de récursion de preuve adopté par Halo2 et STARK peut générer des preuves en parallèle et combiner plusieurs preuves, de sorte que l'exactitude de plusieurs exécutions de transactions puisse être vérifiée tout en vérifiant une valeur de preuve, ce qui peut comprimer la surcharge de calcul, améliorant ainsi considérablement l'efficacité du système.
Cependant, une telle optimisation reste toujours au-dessus de l’algorithme spécifique de preuve de connaissance nulle. Afin d’améliorer encore l’efficacité, nous avons besoin d’une optimisation et d’une innovation de niveau inférieur. L'algorithme FOAKS conçu par Fox fait cela en appliquant jusqu'à présent des idées récursives dans une preuve.
Schéma de récursivité de preuve utilisé par FOAKS
Fox Tech est un projet zkRollup basé sur zkEVM. Dans son système de preuve, la technique de preuve récursive est également utilisée, mais la connotation est différente de la méthode récursive mentionnée ci-dessus. La principale différence est que Fox utilise l'idée de récursion dans une preuve. Afin d’exprimer l’idée centrale de la preuve récursive utilisée par Fox pour réduire continuellement le problème à prouver jusqu’à ce que le problème réduit soit suffisamment simple, nous devons donner un autre exemple.
Dans l'exemple ci-dessus, Alice prouve qu'elle est allée à Fox Park un certain jour en prenant une photo, donc Bob propose une suggestion différente. Il pense que le problème de prouver qu'Alice est allée au parc peut se réduire à prouver que le téléphone portable d'Alice est allé au parc. Et prouver cette affaire peut se réduire à prouver que l'emplacement du téléphone portable d'Alice se situe dans le périmètre du parc.
Par conséquent, afin de prouver qu'Alice est allée au parc, il lui suffit d'envoyer une localisation avec son téléphone portable pendant qu'elle est dans le parc. De cette manière, la taille de l'épreuve passe d'une photo (données de très haute dimension) à des données tridimensionnelles (latitude, longitude et heure), ce qui permet de réduire efficacement les coûts.
Cet exemple n'est pas tout à fait approprié car certaines personnes peuvent se demander si le téléphone portable d'Alice est allé à Fox Park ne signifie pas qu'Alice y a été, mais dans des situations réelles, ce processus de réduction est strictement mathématique.
Plus précisément, l'utilisation de la preuve récursive de Fox est une récursion au niveau du circuit. Lors de l'exécution d'une preuve sans connaissance, nous écrirons le problème à prouver dans un circuit, puis calculerons certaines équations qui doivent être satisfaites via le circuit. Et au lieu de montrer que ces équations sont satisfaites, nous écrivons à nouveau ces équations sous forme de circuits, et ainsi de suite, jusqu'à ce que finalement les équations pour prouver la satisfaction deviennent suffisamment simples pour que nous puissions facilement la prouver directement.
De ce processus, nous pouvons voir que cela est plus proche du sens de « récursion ». Il convient de mentionner que tous les algorithmes ne peuvent pas utiliser cette technique récursive, en supposant que chaque récursion transformera la preuve de complexité O(n) en une preuve de O(f(n)) et le calcul du processus récursif lui-même.
La complexité est O(g(n)), alors la complexité informatique totale devient O1(n)=O(f(n))+O(g(n)) après une récursion, et O2(n) après deux récursions ) =O(f(f(n)))+O(g(n))+O(g(f(n))), après trois fois c'est O3(n)=O(f(f(f(n ) )))+O(g(n))+O(g(f(n)))+O(g(f(f(n)))), …, et ainsi de suite.
Par conséquent, une telle technique récursive ne peut fonctionner efficacement que lorsque les deux fonctions de f et g correspondant aux caractéristiques de l’algorithme satisfont Ok(n)
Conclusion
La complexité de la preuve a toujours été l’une des clés les plus importantes dans l’application des preuves à connaissance nulle. La nature de la complexité de la preuve deviendra de plus en plus importante à mesure que les éléments à prouver deviendront de plus en plus complexes, en particulier dans les applications ZK géantes comme zkEVM.
Dans ce scénario, la complexité de la preuve aura un impact décisif sur les performances du produit et l’expérience utilisateur. Parmi les nombreuses façons de réduire la complexité de la preuve finale, l’optimisation de l’algorithme de base est la plus importante.
Fox a conçu un système de preuve de livraison exquis basé sur l'algorithme le plus avancé et utilise cette technologie pour créer le zkEVM le plus approprié. L'algorithme ZK-FOAKS devrait devenir le leader en termes de performances dans l'industrie zkRollup.
Avertissement: Les informations sur ce site Web sont fournies à titre de commentaire général du marché et ne constituent pas un conseil en investissement. Nous vous encourageons à faire vos propres recherches avant d'investir.
Rejoignez-nous pour suivre l'actualité : https://linktr.ee/coincu
Harold
Coincu Actualité
Auteur
Connaissance
Comment concevoir un meilleur schéma de récursivité de preuve ?
Presque tous les problèmes rencontrés dans les pistes zkRollup et zkEVM sont essentiellement des problèmes algorithmiques. La principale raison pour laquelle l’accélération matérielle ZK-Proof est fréquemment mentionnée est que les algorithmes actuels sont généralement lents.
Afin d'éviter de tomber dans la situation embarrassante du « l'algorithme ne suffit pas, le matériel est utilisé pour inventer », nous devons résoudre le problème à partir de l'essence de l'algorithme. Concevoir une récursion exquise à l'épreuve des livraisons Le schéma est la clé pour résoudre ce problème.
Avec le développement continu des contrats intelligents, de plus en plus d'applications Web3 apparaissent progressivement, et le volume de transactions de la couche 1 traditionnelle, comme Ethereum, augmente rapidement et des congestions peuvent survenir à tout moment. Comment obtenir une plus grande efficacité tout en garantissant la sécurité fournie par la couche 1 est devenu un problème urgent à résoudre.
Pour Ethereum, zkRollup utilise l'algorithme de preuve de connaissance nulle comme composant sous-jacent pour déplacer les calculs coûteux qui devaient initialement être effectués sur la couche 1 hors chaîne et fournir une preuve de l'exactitude de l'exécution à la chaîne. La piste comprend des projets tels que StarkWare, zkSync, défilement, ainsi que Renard Tech.
En fait, dans la conception de zkRollup, les exigences d'efficacité sont très élevées : on espère que la valeur de preuve soumise est suffisamment petite pour réduire la quantité de calcul de la couche 1. Afin d'obtenir une longueur de preuve suffisamment petite, chaque Le projet zkRollup améliore la conception de l'algorithme et de l'architecture. Par exemple, Fox a développé son algorithme de preuve FOAKS en combinaison avec le dernier algorithme de preuve à connaissance nulle pour obtenir le temps et la longueur de preuve optimaux.
De plus, au stade de la vérification des preuves, le moyen le plus trivial consiste à générer des preuves de manière linéaire et à les vérifier séquentiellement. Afin d'améliorer l'efficacité, la première chose à laquelle tout le monde pense est de regrouper plusieurs preuves en une seule, communément appelée agrégation de preuves.
Intuitivement parlant, la vérification des preuves générées par zkEVM est un processus linéaire, et le vérificateur doit vérifier tour à tour chaque valeur de preuve générée. Cependant, l’efficacité de cette méthode de vérification est relativement faible et la surcharge de communication est relativement importante. Pour le scénario zkRollup, une surcharge plus élevée côté vérificateur signifie davantage de calculs de couche 1, ce qui entraînera également des frais de gaz plus élevés.
Regardons d'abord un exemple : Alice veut prouver au monde qu'elle est allée à Fox Park du 1er au 7 de ce mois. Pour cette raison, elle peut prendre une photo dans le parc avec le journal du jour chaque jour du 1er au 7, et ces sept photos serviront de preuve.
Mettre sept photos directement dans une enveloppe dans l'exemple ci-dessus est une agrégation de preuves au sens intuitif, qui correspond à connecter différentes preuves entre elles et à les vérifier linéairement en séquence, c'est-à-dire vérifier d'abord la première preuve, puis vérifier la deuxième preuve.
Deux preuves et preuves ultérieures. Le problème est que cette approche ne changera ni la taille de la preuve ni le temps de la preuve, ce qui revient à prouver et vérifier un par un. Si vous souhaitez obtenir une compression d'espace logarithmique, vous devez utiliser la preuve de récursion mentionnée ci-dessous.
Schéma de récursivité de preuve utilisé par Halo2 et STARK
Afin de mieux expliquer ce qu'est une preuve récursive, revenons à l'exemple ci-dessus.
Les sept images d'Alice sont sept preuves. Pensez maintenant à les fusionner, pour qu'Alice puisse prendre une photo le 1er, prendre cette photo le 2ème et le journal le 2ème, et prendre la photo le 2ème et le journal le 3ème photo. Par analogie, Alice a pris la dernière photo le 7 avec la photo du 6 et le journal le 7, et d'autres amis peuvent vérifier qu'ils sont du 1er au 7 lorsqu'ils voient la dernière photo du 7.
Alice est toutes allées au parc. On peut voir que les sept photos d’épreuve précédentes ont été compressées en une seule. Et une compétence clé dans ce processus est « les photos contenant des photos », ce qui équivaut à imbriquer de manière récursive des photos précédentes dans des photos suivantes. C'est différent de rassembler beaucoup de photos et de prendre une seule photo.
L'astuce de preuve récursive de zkRollup peut considérablement compresser la taille de la preuve. Concrètement, chaque transaction générera une preuve. Nous définissons le circuit de calcul de transaction d'origine comme C0, P0 comme preuve d'exactitude de C0 et V0 comme processus de calcul de vérification de P0.
Le prouveur convertit également V0 en circuit correspondant, noté C0′. Actuellement, pour le processus de calcul de la preuve C1 d'une autre transaction, les circuits de C0' et C1 peuvent être fusionnés. De cette manière, une fois la preuve d'exactitude P1 du circuit fusionné vérifiée, cela équivaut à vérifier les deux circuits ci-dessus en même temps. L'exactitude de la transaction, c'est-à-dire la compression, est obtenue.
En regardant le processus ci-dessus, on peut constater que le principe de la compression est de convertir le processus de vérification et de preuve en un circuit, puis de générer « preuve pour preuve », donc de ce point de vue, c'est une opération qui peut se répéter continuellement. vers le bas, donc également connue sous le nom de preuve récursive.
Le schéma de récursion de preuve adopté par Halo2 et STARK peut générer des preuves en parallèle et combiner plusieurs preuves, de sorte que l'exactitude de plusieurs exécutions de transactions puisse être vérifiée tout en vérifiant une valeur de preuve, ce qui peut comprimer la surcharge de calcul, améliorant ainsi considérablement l'efficacité du système.
Cependant, une telle optimisation reste toujours au-dessus de l’algorithme spécifique de preuve de connaissance nulle. Afin d’améliorer encore l’efficacité, nous avons besoin d’une optimisation et d’une innovation de niveau inférieur. L'algorithme FOAKS conçu par Fox fait cela en appliquant jusqu'à présent des idées récursives dans une preuve.
Schéma de récursivité de preuve utilisé par FOAKS
Fox Tech est un projet zkRollup basé sur zkEVM. Dans son système de preuve, la technique de preuve récursive est également utilisée, mais la connotation est différente de la méthode récursive mentionnée ci-dessus. La principale différence est que Fox utilise l'idée de récursion dans une preuve. Afin d’exprimer l’idée centrale de la preuve récursive utilisée par Fox pour réduire continuellement le problème à prouver jusqu’à ce que le problème réduit soit suffisamment simple, nous devons donner un autre exemple.
Dans l'exemple ci-dessus, Alice prouve qu'elle est allée à Fox Park un certain jour en prenant une photo, donc Bob propose une suggestion différente. Il pense que le problème de prouver qu'Alice est allée au parc peut se réduire à prouver que le téléphone portable d'Alice est allé au parc. Et prouver cette affaire peut se réduire à prouver que l'emplacement du téléphone portable d'Alice se situe dans le périmètre du parc.
Par conséquent, afin de prouver qu'Alice est allée au parc, il lui suffit d'envoyer une localisation avec son téléphone portable pendant qu'elle est dans le parc. De cette manière, la taille de l'épreuve passe d'une photo (données de très haute dimension) à des données tridimensionnelles (latitude, longitude et heure), ce qui permet de réduire efficacement les coûts.
Cet exemple n'est pas tout à fait approprié car certaines personnes peuvent se demander si le téléphone portable d'Alice est allé à Fox Park ne signifie pas qu'Alice y a été, mais dans des situations réelles, ce processus de réduction est strictement mathématique.
Plus précisément, l'utilisation de la preuve récursive de Fox est une récursion au niveau du circuit. Lors de l'exécution d'une preuve sans connaissance, nous écrirons le problème à prouver dans un circuit, puis calculerons certaines équations qui doivent être satisfaites via le circuit. Et au lieu de montrer que ces équations sont satisfaites, nous écrivons à nouveau ces équations sous forme de circuits, et ainsi de suite, jusqu'à ce que finalement les équations pour prouver la satisfaction deviennent suffisamment simples pour que nous puissions facilement la prouver directement.
De ce processus, nous pouvons voir que cela est plus proche du sens de « récursion ». Il convient de mentionner que tous les algorithmes ne peuvent pas utiliser cette technique récursive, en supposant que chaque récursion transformera la preuve de complexité O(n) en une preuve de O(f(n)) et le calcul du processus récursif lui-même.
La complexité est O(g(n)), alors la complexité informatique totale devient O1(n)=O(f(n))+O(g(n)) après une récursion, et O2(n) après deux récursions ) =O(f(f(n)))+O(g(n))+O(g(f(n))), après trois fois c'est O3(n)=O(f(f(f(n ) )))+O(g(n))+O(g(f(n)))+O(g(f(f(n)))), …, et ainsi de suite.
Par conséquent, une telle technique récursive ne peut fonctionner efficacement que lorsque les deux fonctions de f et g correspondant aux caractéristiques de l’algorithme satisfont Ok(n)
Conclusion
La complexité de la preuve a toujours été l’une des clés les plus importantes dans l’application des preuves à connaissance nulle. La nature de la complexité de la preuve deviendra de plus en plus importante à mesure que les éléments à prouver deviendront de plus en plus complexes, en particulier dans les applications ZK géantes comme zkEVM.
Dans ce scénario, la complexité de la preuve aura un impact décisif sur les performances du produit et l’expérience utilisateur. Parmi les nombreuses façons de réduire la complexité de la preuve finale, l’optimisation de l’algorithme de base est la plus importante.
Fox a conçu un système de preuve de livraison exquis basé sur l'algorithme le plus avancé et utilise cette technologie pour créer le zkEVM le plus approprié. L'algorithme ZK-FOAKS devrait devenir le leader en termes de performances dans l'industrie zkRollup.
Avertissement: Les informations sur ce site Web sont fournies à titre de commentaire général du marché et ne constituent pas un conseil en investissement. Nous vous encourageons à faire vos propres recherches avant d'investir.
Rejoignez-nous pour suivre l'actualité : https://linktr.ee/coincu
Harold
Coincu Actualité
Autres articles
Articles Similaires
Actualité
FSOCIETY menace une fuite massive de données Bitfinex : 400,000 XNUMX utilisateurs en danger
Actualité
Les agriculteurs de LayerZero Sybil Airdrop sont désormais considérablement bloqués pour fraude
Actualité
La déception nuage le lancement de Friend Tech v2 malgré de nouvelles fonctionnalités intéressantes
Actualité
De nouveaux jetons MakerDAO sont lancés pour promouvoir la gouvernance du protocole
Actualité
L'investissement de Pantera Capital TON vise à améliorer les capacités de paiement P2P
Actualité
Le président de la SEC accusé de tromperie concernant la légitimité d'Ethereum !
Analyse
Avril est le pire mois pour Bitcoin au milieu des sorties d'ETF : rapport
Actualité
Roger Ver arrêté en Espagne et accusé de fraude fiscale de 48 millions de dollars
Actualité
Une erreur d'adresse entraîne une perte WBTC de 68 millions de dollars et la victime tombe dans une escroquerie par hameçonnage
Meilleurs projets
Top 10 des meilleurs robots Crypto Telegram en 2024
Connaissance
Minage de Bitcoin : combien de temps faut-il pour extraire 1 Bitcoin ?
Connaissance
Prédictions électorales américaines : effets et importance du nouveau président américain
Connaissance
Candidats potentiels aux élections américaines de 2024 : qui va gagner ?
Actualité
