Clarifier le développement historique de la technologie ZK

ZK Proofs est une puissante primitive cryptographique qui permet à une partie (proverbe) de convaincre l’autre partie (verbe) qu’une déclaration donnée est vraie et valide sans révéler aucune information privée.Ces dernières années, ZK a attiré une large attention dans les domaines de l’informatique privée vérifiable, fournissant une preuve d’efficacité pour les programmes informatiques et la blockchain, et a joué un rôle positif significatif dans le développement du monde.

Bien que ZK soit une technologie émergente, ses idées et concepts de base remontent aux années 1980.Après avoir été combinée avec des blockchains tels que Bitcoin et Ethereum, le développement de la technologie ZK s’est considérablement accéléré.Parce que la blockchain peut prouver son efficacité par le snark et le stark, et améliorer considérablement son évolutivité, cela rend ZK populaire dans le champ de blockchain.

Comme l’a déclaré Eli Ben-Sasson, le fondateur de Starkware, nous avons été témoins de «l’explosion du Cambrien» du système de preuve cryptographique.Chaque système de preuve a ses propres forces et faiblesses uniques et est échangé lorsqu’il est conçu.L’avancement du matériel, de meilleurs algorithmes, de nouveaux arguments et des outils périphériques ont tous stimulé l’amélioration des performances du système ZK et la naissance d’un nouveau système.De nombreux systèmes de preuve ont été adoptés dans des applications pratiques, et les gens élargissent toujours les limites de ZK.

Cela incite également les gens à réfléchir profondément à une question:Existe-t-il un système universel de preuve ZK pour toutes les applications?Nous ne pensons pas que cela sera probablement très probable.Il y a trois raisons:

1. Diversité des applications;

2. Différents types de contraintes (y compris la mémoire, le temps de vérification et le temps de preuve);

3. La nécessité d’une robustesse (si un système de preuve est piraté, nous pouvons toujours passer à d’autres systèmes en tant qu’assurance).

Sur la base des raisons ci-dessus, le ZK prouve que le système devrait être diversifié.Mais même s’il existe de nombreux types de systèmes de preuve, il doit y avoir un point commun significatif: la preuve ZK peut être rapidement vérifiée.Et avoir une couche de vérification peut facilement s’adapter au nouveau système de preuve pour résoudre les difficultés pertinentes de la couche sous-jacente dont il dépend (comme Ethereum).

Dans le champ ZK, ZK-Snark est fréquemment mentionné.Il s’agit d’une forme de réalisation de la preuve de connaissances zéro, qui permet une preuve efficace de connaissances zéro en utilisant des outils mathématiques complexes tels que l’appariement bilinéaire et les circuits arithmétiques.La caractéristique de ZK-Snark est que le processus de preuve est simple et non interactif, et une seule communication est requise entre le prover et le vérificateur et le vérificateur, aucune interaction multiple n’est requise.aussi,La taille de preuve de ZK-Snark est très courte et a une efficacité de vérification élevée, ce qui le rend adapté à une utilisation dans des environnements liés aux ressources.

Et ZK-Stark est une autre forme courante conçue pour surmonter certaines limites de ZK-Snark.ZK-Stark ne compte pas sur des paramètres de confiance et utilise des systèmes de construction mathématique plus transparents tels que l’engagement polynomial et les opérations de domaine finie, les collisions de hachage, etc. pour générer et vérifier les preuves.ZK-Stark est plus évolutif que ZK-SNARK, adapté à l’informatique à plus grande échelle, ce qui prouve à générer plus rapidement, mais la preuve elle-même est généralement de plus grande taille.

On peut dire que ZK-Snark et ZK-Stark sont tous deux des formes couramment utilisées en preuve de connaissances zéro, mais elles varient en termes de transparence, d’évolutivité, de taille de preuve, etc.

Dans l’ensemble,Un système ZK Proof comprend généralement deux parties: PIOP (Polynomial Interactive Oracle) et PCS (Schéma d’engagement polynomial).Les solutions PIOP courantes incluent Plonkish, GKR, etc., tandis que les solutions PCS courantes incluent FRI, KZG, IPA, etc. Par exemple, la version ZCash de Halo2 utilise la méthode d’implémentation de Plonkish + IPA. être considéré comme un zk-snark spécial basé au vendredi.

S’il est plus détaillé, différents types de systèmes de preuve utiliseront différents schémas d’engagement polynomial (PC), schémas arithmétiques, preuves oracle interactives (IOP) ou preuves vérifiables de probabilité (PCP).

Plus loin,Différents systèmes d’épreuve ZK diffèrent souvent dans les indicateurs suivants:

Hypothèse cryptographique: fonction de hachage anti-collision, problèmes logarithmiques discrets sur les courbes elliptiques, connaissances exponentives
Paramètres transparents vs Paramètres de confiance
Chronophage pour générer des preuves: linéaire vs hyperlinear
Comparti à la vérification des preuves: temps constant, temps de journal, sublinéaire, linéaire
Prouver la taille de la taille
La simplicité de la récursivité
Schéma arithmétique
Univarié vs polynôme multivarié

Ci-dessous, nous parlerons brièvement de l’origine de la technologie ZK, explorerons ses blocs de construction de base et décrirons la montée et la chute de différents systèmes de preuve ZK.Dans le même temps, cet article ne procède pas à une analyse détaillée du système de preuve lui-même, mais se concentre sur ceux qui ont eu un impact profond sur le terrain.Après tout, le développement de n’importe quelle industrie n’est possible que par les grandes idées des pionniers et attrayant la pratique.

Le contexte de développement historique de ZK-Snark

Origine: 1980 aux années 1990

Comme nous l’avons mentionné, la preuve de connaissances zéro n’est pas un nouveau concept.La première apparition a été dans Goldwasser, Micali (fondateur d’Algorand) et les journaux de RackoffLa complexité des connaissances des systèmes de preuve interactifs« milieu.

etLes idées et protocoles clés que nous utilisons pour créer une technologie ZK-Snark ont été publiés dans les années 1990.Par exemple, le protocole Sumcheck simplifie la déclaration de somme d’évaluation de plusieurs polynômes à l’évaluation unique des points sélectionnés au hasard sur la courbe elliptique, qui jette une base importante pour la technologie ZK.

Par conséquent, l’émergence d’idées ZK est en fait bien plus tôt que l’émergence du bitcoin.Cependant, à ce moment-là, il y avait un manque général de cas applicables pour ZK, et les gens ne pouvaient pas fournir la puissante puissance informatique requise pour répondre au système de preuve ZK.

Protocole GKR (2007)

GKR (Goldwasser-Kalai-Rothblum) est un protocole interactif.Dans le protocole GKR, le prover et le vérificateur doivent s’entendre sur les résultats de l’opération du circuit arithmétique à double entrée dans un domaine fini, dont la profondeur est D, la couche D-th est la couche d’entrée et le 0-th La couche est la couche de sortie.Le protocole commence par une déclaration sur la sortie du circuit et la simplifie à une déclaration de la couche précédente par récursivement.Enfin, nous pouvons convertir la déclaration en sortie en une déclaration des paramètres d’entrée du circuit, qui est facilement vérifié.On peut dire que le protocole GKR est très simplifié en fonction du protocole Sumcheck susmentionné.

Solution d’engagement polynomial KZG (2010)

En 2010, trois experts dans le domaine ZK—— Kate de l’institution de recherche allemande MPI-SWS, Zaverucha de la société canadienne de cryptographie Certicom Research, et Goldberg de l’Université de Waterloo a publié conjointement un article « Engagements de taille constante envers les polynomiales et leurs applications》.Ce papierUn schéma d’engagement polynomial utilisant des groupes de paires bilinéaires est proposé, appelé KZG.

Cette promesse se compose d’un élément de groupe distinct, et l’engagement peut révéler efficacement toute évaluation correcte du polynôme, et à l’aide de la technologie de traitement par lots, l’évaluation de plusieurs polynômes peut être révélée.KZG a promis de devenir l’un des éléments constitutifs de base de certains systèmes de preuves ZK bien connus (tels que Halo2 utilisés par le groupe Ethereum PES), et il a également joué un rôle de base dans l’EIP-4844 d’Ethereum.Pour comprendre le concept de technologie de traitement par lots plus intuitivement, vous pouvez vous référer à l’article sur le pont Mina-Ethereum.

Référence: https://blog.lambdaclass.com/mina-to-ethereum-bridge/

Système pratique ZK-Snark basé sur les courbes elliptiques (2013)

La première structure pratique de ZK-Snark est apparue en 2013 et a nécessité une étape de prétraitement pour générer une clé de preuve et une clé de vérification, et est spécifique au programme ou au circuit et non universel.Ces clés peuvent être de grande taille et dépendre des paramètres secrets eux-mêmes;Dans ce système pratique ZK-Snark, pour convertir le code en une forme éprouvée, il est nécessaire de compiler le code en un ensemble de formes mathématiques de contraintes polynomiales.

Au début, le processus ci-dessus doit être terminé manuellement, ce qui prend du temps et sujets aux erreurs.Plus tard, en réponse aux changements technologiques dans cette direction, nous avons principalement essayé de résoudre les problèmes fondamentaux suivants:

Fournir une preuve plus efficace
Réduire le nombre de prétraitement
Implémenter des paramètres universels plutôt que spécifiques au circuit
Évitez les paramètres de confiance
Développer des méthodes pour décrire les circuits dans des langues de haut niveau, plutôt que d’écrire manuellement les contraintes polynomiales

Protocole Pinocchio (2013)

Le protocole Pinocchio est le premier système ZK-Snark à être réellement disponible.Sur la base d’un programme arithmétique quadratique (QAP), la taille de preuve initiale est de 288 octets.La chaîne d’outils de Pinocchio fournit un compilateur qui compile le langage C en circuits arithmétiques, qui peuvent être davantage convertis en QAP.Le protocole Pinocchio nécessite que le vérificateur génére des clés qui ne sont pas universelles mais spécifiques au circuit.La complexité de temps progressive de la génération du système et les paramètres clés du système de preuve est linéairement liée à l’échelle de calcul, et le temps de vérification est linéairement lié à la taille de l’entrée et de la sortie communes.

Groth16 (2016)

Groth a introduit un nouvel algorithme ZK-ILM qui a des performances plus élevées dans la gestion des R1C.R1CS est un système de contrainte de premier ordre, qui est une forme de contrainte polynomiale dans ZK-Snark.La preuve de Gorth est la plus petite taille de données (y compris seulement trois éléments de groupe), et la vitesse de vérification est très rapide.Faites simplement trois opérations d’appariement et une étape de prétraitement qui structure la chaîne de référence.Mais le principal inconvénient de Gorth est que chaque programme qui doit être prouvé nécessite des paramètres de confiance différents, ce qui est assez gênant dans les applications pratiques.

Plus tard, Groth16 a été utilisé dans Zcash, un projet de blockchain de confidentialité relativement célèbre (impliqué par le fondateur de Starkware Eli).

Bulletproofs et IPA (2016)

L’une des principales faiblesses du système d’engagement polynomial KZG susmentionné est la nécessité d’un cadre de confiance.Bootle et al. Ont proposé un système de preuve de connaissance zéro efficace qui analyse l’ouverture des engagements de Pedersen qui satisfont la relation du produit intrinsèque.La preuve de la preuve du produit interne avec la complexité linéaire prend du temps, le nombre d’interactions entre le prover et le vérificateur est logarithmique, mais le temps de vérification est linéaire.De plus, Bootle et al.Ces idées ont ensuite été adoptées par Halo2 et Kimchi.

Sonic, Marlin et Plonk (2019)

Sonic, Plonk et Marlin résolvent le problème que chaque programme de l’algorithme GROTH16 nécessite des paramètres de confiance, en introduisant une chaîne de référence structurée commune et mise à jour (utilisée pour implémenter des paramètres de confiance qui ne nécessitent qu’une seule fois).dans,Marlin fournit un système de preuve basé sur R1CS et est devenu la technologie de base d’Aleo.

PLONK présente un nouveau schéma arithmétique (connu plus tard sous le nom de Plonkish) et utilise un grand-produit pour vérifier les contraintes de réplication.Plonkish permet également l’introduction de portes de logique de circuit dédiées pour des opérations spécifiques, ce que l’on appelle des « portes personnalisées ».De nombreux projets bien connus de blockchain ont utilisé des versions personnalisées de Plonk, notamment Aztec, Zksync, Polygon Zkevm, Mina, Ethereum PSE et Scroll.

spartiate(2019)

Spartan fournit une PIO pour les circuits décrits à l’aide de R1CS, en utilisant les caractéristiques des polynômes multivariés et des protocoles de test SUM.En utilisant un schéma d’engagement polynomial approprié, il met en œuvre un système ZK-Snark transparent et la complexité temporelle de la génération de la preuve est linéaire.

Lookups (2020)

Gabizon et Williamson ont proposé PLOokup dans leur journal en 2020,Utilisation du grand-produit pour prouver qu’une valeur est incluse dans la table de vérité pré-calculée, montrant comment introduire des paramètres de plats dans l’algorithme PLONK.

Cependant, ces arguments de recherche ont un problème commun, et les provers doivent dépenser beaucoup d’argent pour construire une table de vérité complète, de sorte que le travail précédent autour des recherches a été consacré à la réduction du coût de la preuve.

Plus tard, Haböck a introduit Logup dans son article, qui utilise des dérivés de journal pour convertir la vérification du grand-produit en la somme des réciproques.Logup est essentiel pour les améliorations des performances dans les zkevms de polygone, car ils doivent diviser toute la table de vérité en plusieurs modules Stark.Ces modules doivent être correctement liés et les recherches de table croisée peuvent forcer cela.Depuis lors, l’introduction de LogUp-GKR a amélioré les performances de Logup via le protocole GKR.

Le callaute est la première solution pour faire de la relation de temps de temps éprouvée avec la taille du tableau de vérité.D’autres solutions ont suivi, comme Baloo, Flookup, CQ et Caulk +.En outre, Lasso propose plusieurs améliorations pour éviter de s’engager dans le tableau de vérité lorsqu’il a une structure spécifique.

Hyperplonk (2022)

Hyperplonk a été proposé dans le document « Hyperplonk: Plonk avec prover en temps linéaire et portes personnalisées à haut degré ».Hyperplonk est basé sur le concept de Plonk et adopte des polynômes multivariés.Au lieu d’utiliser la division pour vérifier l’exécution des contraintes, elle s’appuie sur le protocole SUM-Test.Dans le même temps, il prend également en charge les contraintes d’ordre supérieur sans affecter le temps de la génération de preuve.

Étant donné que les polynômes multivariés sont utilisés, il n’est pas nécessaire d’effectuer une transformée de Fourier rapide (FFT), il est prouvé que le temps généré est linéairement lié à l’échelle du circuit.Hyperplonk introduit également une nouvelle PIO de permutation pour les petits champs et adopte un protocole basé sur une somme qui réduit la charge de travail des provers, la taille de la preuve et le temps de vérification.

Système de preuve ZK utilisant la fonction de hachage anti-collision

Bien que Pinocchio ait été proposé en 2013, il existe des solutions pour générer des schémas de circuit / arithmétiques qui peuvent prouver que la machine virtuelle exécute correctement les instructions.Bien que le développement d’un schéma arithmétique pour une machine virtuelle soit plus complexe ou moins efficace que d’écrire des circuits dédiés pour certains programmes, il a un avantage important: peu importe la complexité du programme, prouvez simplement qu’il est exécuté correctement dans la machine virtuelle.

Certaines idées à Tinyram ont ensuite été améliorées dans la conception des machines virtuelles du Caire, suivie de ZK-EVM et du ZKVM à usage général.L’utilisation des fonctions de hachage résistantes aux collisions dans les systèmes de preuve élimine le besoin de paramètres de confiance ou d’opérations de courbe elliptique, mais au prix de la prestation plus longtemps.

Tinyram (2013)

Dans « Snarks for C », ils ont développé un système de preuve basé sur PCP pour prouver que les résultats d’exécution des programmes écrits en C sont corrects.Le programme est compilé dans Tinyram, une machine virtuelle simplifiée.La machine virtuelle a une mémoire aléatoire adressable au niveau des octets, et la taille du circuit augmente quasi-linéaire dans l’échelle de calcul et peut gérer efficacement les opérations telles que les boucles, les flux de contrôle et l’accès à la mémoire.

dans,Le PCP fait référence à une preuve de temps probabiliste, ce qui signifie que la preuve vérifiable de la probabilité.Contrairement aux systèmes de preuve traditionnels où les vérificateurs doivent vérifier l’ensemble de la preuve, le PCP ne nécessite qu’un aléatoire limité pour obtenir une vérification efficace.

Ligero (2017)

Ligero a introduit un système de preuve qui peut implémenter des preuves de taille O (√￣n), où n est la taille du circuit.Il organise des coefficients polynomiaux sous forme de matrice.Brakedown est construit sur Ligero et présente le concept d’un schéma d’engagement polynomial indépendant du domaine.

Starks (2018)

Des étoiles (arguments transparents évolutifs de connaissances) ont été proposés par Eli Ben-Sasson et al.Ils mettent en œuvre la complexité de la preuve de? (Log²⁡?), Ont des vitesses de vérification rapides, ne nécessitent pas de configuration de confiance et sont supposées être une sécurité post-Quantum.Ils sont utilisés par les machines virtuelles Starkware / Starknet et Cairo.Ses principales innovations incluent la représentation intermédiaire algébrique (AIR) et les protocoles rapides interactifs à l’épreuve des Oracle interactifs (FRI).De plus, les Starks sont également utilisés par de nombreux projets de blockchain bien connus (comme Polygon Miden, Risczero, Winterfell, Neptune, Zerosync, Zksync, etc.).

Nouvelle direction de développement

L’utilisation de différents systèmes de preuve dans des applications pratiques montre les avantages de différentes méthodes et favorise le développement de ZK.Par exemple, le schéma arithmétique de Plonkish offre un moyen facile d’inclure des portes logiques personnalisées et des arguments de recherche;Pendant ce temps, l’utilisation de grands-produits vérifiant l’air (air randomisé qui apporte le prétraitement) améliore ses performances et simplifie les paramètres d’accès à la mémoire.ZK-Stark devient de plus en plus populaire car il est meilleur dans l’efficacité de la génération et des fonctions de hachage plus adaptées à ZK sont introduites.

Nouveau système d’engagement polynomial (2023)

Avec l’émergence de SNARKS efficaces basés sur des polynômes multivariés, tels que Spartan ou Hyperplonk, il y a un intérêt croissant pour de nouveaux schémas d’engagement applicables à de tels polynômes.Binius, Zeromorph et Basefold proposent tous de nouvelles façons de promettre des polynômes multilinéaires.Binius a l’avantage de ne pas avoir de frais généraux supplémentaires lorsqu’il indique des types de données (tandis que de nombreux autres systèmes de preuve utilisent au moins des éléments de champ 32 bits pour représenter des bits uniques) et fonctionnent sur des domaines binaires.Le schéma d’engagement utilise une ligne de freinage conçue à des fins indépendantes sur le terrain.Basefold généralise FRI à en plus de Reed-Solomon, réalisant ainsi un schéma d’engagement polynomial indépendant du domaine (PCS).

Indépendant du domaine est une propriété d’un schéma d’engagement polynomial, qui fait référence au processus d’engagement dans un schéma d’engagement polynomial qui ne dépend pas de propriétés spécifiques d’un domaine particulier.Cela signifie que des engagements peuvent être pris envers les polynômes de toute structure algébrique, tels que des domaines finis, des courbes elliptiques et même des anneaux entiers.

Système de contrainte personnalisable (2023)

Le CCS généralise les R1C tout en capturant l’arithmétique des R1C, plonkish et air sans frais généraux supplémentaires.L’utilisation de CCS en combinaison avec une IOP Spartan peut générer Superspartan, qui prend en charge les contraintes de grande dimension sans avoir besoin de supporter le coût de chiffrement proportionnel à l’ordre de contrainte.En particulier, Superspartan fournit de l’air avec un snark linéaire à l’épreuve du temps.

Résumer

Cet article passe en revue les progrès de la technologie ZK depuis le milieu des années 80.Les progrès de l’informatique, des mathématiques et du matériel, associés à l’introduction de la blockchain, ont donné naissance à de nouveaux systèmes de preuve ZK plus efficaces, ouvrant la voie à de nombreuses applications qui peuvent changer la société.

Les chercheurs et les ingénieurs ont proposé des améliorations du système ZK en fonction de la demande, en se concentrant sur la taille de la preuve, l’utilisation de la mémoire, la transparence, la résistance à la sécurité quantique, le temps de preuve et le temps de vérification.Bien qu’il y ait toujours eu deux grandes catégories de solutions de mise en œuvre traditionnelles de ZK (Snark et Starks), les limites entre les deux se sont progressivement floues, et les avantages de différents systèmes de preuve sont combinés, comme la combinaison de solutions arithmétiques différentes avec de nouveaux engagements polynomiaux de ceux qui sont polynomiaux schème.

Nous pouvons nous attendre à ce que le nouveau système de preuve ZK continuera d’émerger et que les performances continueront de s’améliorer.Pour les applications utilisant ces systèmes de preuve, s’ils ne peuvent pas suivre le développement itératif des dernières technologies et reconstruire en continu et appliquer les derniers algorithmes, leur position de leader actuelle n’est que temporaire.

Lien original:https://blog.lambdaclass.com/our-highly-subjective-view-on-the-history-of-zero-knowledge-profts/