Vitalik Buterin via le Blog de Vitalik Buterin
Ceci est un miroir du message de https://medium.com/@VitalikButerin/zk-snarks-sous-le-hood-b33151a013f6
Ceci est la troisième partie d'une série d'articles expliquant comment fonctionne la technologie derrière les zk-SNARK ; les articles précédents sur programmes d'arithmétique quadratique ainsi que le appariements de courbes elliptiques sont des lectures obligatoires, et cet article supposera la connaissance des deux concepts. Une connaissance de base de ce que sont les zk-SNARK et de ce qu'ils font est également supposée. Voir également L'article de Christian Reitwiessner ici pour une autre introduction technique.
Dans les articles précédents, nous avons présenté le programme d'arithmétique quadratique, une manière de représenter tout problème informatique avec une équation polynomiale qui se prête beaucoup plus à diverses formes de supercherie mathématique. Nous avons également introduit des appariements de courbes elliptiques, qui permettent une forme très limitée de cryptage homomorphe unidirectionnel qui vous permet de vérifier l'égalité. Maintenant, nous allons reprendre là où nous nous sommes arrêtés et utiliser des paires de courbes elliptiques, ainsi que quelques autres astuces mathématiques, afin de permettre à un prouveur de prouver qu'il connaît une solution pour un QAP particulier sans rien révéler d'autre sur le solution réelle.
Cet article portera sur la Protocole Pinocchio par Parno, Gentry, Howell et Raykova de 2013 (souvent appelé PGHR13) ; il existe quelques variantes du mécanisme de base, donc un schéma zk-SNARK mis en œuvre dans la pratique peut fonctionner légèrement différemment, mais les principes de base resteront en général les mêmes.
Pour commencer, revenons sur l’hypothèse cryptographique clé qui sous-tend la sécurité du mécanisme que nous allons utiliser : le *connaissance de l'exposant* hypothèse.
Fondamentalement, si vous obtenez une paire de points � et �, où �⋅�=�, et que vous obtenez un point �, alors il n'est pas possible de trouver �⋅� à moins que � soit "dérivé" de � d'une manière ou d'une autre. que vous connaissez. Cela peut sembler intuitivement évident, mais cette hypothèse ne peut en réalité être dérivée d'aucune autre hypothèse (par exemple, la dureté logarithmique discrète) que nous utilisons habituellement pour prouver la sécurité des protocoles basés sur des courbes elliptiques, et donc les zk-SNARK reposent en fait sur une base quelque peu Une fondation plus fragile que la cryptographie à courbe elliptique en général – bien qu’elle soit encore suffisamment solide pour que la plupart des cryptographes l’acceptent.
Voyons maintenant comment cela peut être utilisé. Supposons qu’une paire de points (�,�) tombe du ciel, où �⋅�=�, mais personne ne sait quelle est la valeur de �. Maintenant, supposons que je trouve une paire de points (�,�) où �⋅�=�. Ensuite, l’hypothèse de KoE implique que la seule façon pour moi d’obtenir cette paire de points était de prendre � et � et de multiplier les deux par un facteur r. que je connais personnellement. Notez également que grâce à la magie des appariements de courbes elliptiques, vérifier que �=�⋅� cela ne nécessite pas vraiment de le savoir � – au lieu de cela, vous pouvez simplement vérifier si �(�,�)=�(�,�) ou non.
Faisons quelque chose de plus intéressant. Supposons que dix paires de points tombent du ciel : (�1,�1),(�2,�2)…(�10,�10). Dans tous les cas, ��⋅�=��. Supposons que je vous fournisse ensuite une paire de points (�,�) où �⋅�=�. Que sais-tu maintenant ? Vous savez que � est une combinaison linéaire �1⋅�1+�2⋅�2+…+�10⋅�10, où je connais les coefficients �1,�2…�10. Autrement dit, la seule façon d’arriver à une telle paire de points (�,�) est de prendre quelques multiples de �1,�2…�10 et de les additionner, et de faire le même calcul avec �1,�2… �10.
Notez que, étant donné tout ensemble spécifique de �1…�10 points pour lequel vous souhaiterez peut-être vérifier des combinaisons linéaires, vous ne pouvez pas réellement créer les �1…�10 points qui l'accompagnent sans savoir ce que � signifie, et si vous savez quoi � c'est alors que vous pouvez créer une paire (�,�) où �⋅�=� pour tout ce que vous voulez, sans vous soucier de créer une combinaison linéaire. Par conséquent, pour que cela fonctionne, il est absolument impératif que celui qui crée ces points soit digne de confiance et les supprime réellement – une fois qu'il a créé les dix points. C’est de là que vient le concept de « configuration de confiance ».
Rappelons que la solution d'un QAP est un ensemble de polynômes (�,�,�) tel que �(�)⋅�(�)−�(�)=�(�)⋅�(�), où :
- � est une combinaison linéaire d’un ensemble de polynômes {�1…��}
- � est la combinaison linéaire de {�1…��} de mêmes coefficients
- � est une combinaison linéaire de {�1…��} avec les mêmes coefficients
Les ensembles {�1…��},{�1…��} et {�1…��} et le polynôme � font partie de l'énoncé du problème.
Cependant, dans la plupart des cas réels, �,� et � sont extrêmement grands ; pour quelque chose avec plusieurs milliers de portes de circuit comme une fonction de hachage, les polynômes (et les facteurs pour les combinaisons linéaires) peuvent avoir plusieurs milliers de termes. Par conséquent, au lieu de demander au prouveur de fournir directement les combinaisons linéaires, nous allons utiliser l’astuce que nous avons introduite ci-dessus pour que le prouveur prouve qu’il fournit quelque chose qui est une combinaison linéaire, mais sans rien révéler d’autre.
Vous avez peut-être remarqué que l'astuce ci-dessus fonctionne sur les points de la courbe elliptique, et non sur les polynômes. Par conséquent, ce qui se passe réellement, c'est que nous ajoutons les valeurs suivantes à la configuration de confiance :
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
Vous pouvez considérer t comme un « point secret » auquel le polynôme est évalué. � est un « générateur » (un point aléatoire de la courbe elliptique spécifié dans le protocole) et �,��,�� et �� sont des « déchets toxiques », des nombres qu’il faut absolument supprimer à tout prix, sinon celui qui les possède pourra faire de fausses preuves. Maintenant, si quelqu'un vous donne une paire de points �, � tels que �⋅��=� (rappel : nous n'avons pas besoin de �� pour vérifier cela, car nous pouvons faire une vérification d'appariement), alors vous savez que ce qu'ils vous donne est une combinaison linéaire de polynômes �� évalués à �.
Par conséquent, jusqu’à présent, le prouveur doit donner :
- ��=�⋅�(�),��′=�⋅�(�)⋅��
- ��=�⋅�(�),��′=�⋅�(�)⋅��
- ��=�⋅�(�),��′=�⋅�(�)⋅��
Notez que le prouveur n'a pas réellement besoin de connaître (et ne devrait pas savoir !) ��,��,�� ou �� pour calculer ces valeurs ; le prouveur devrait plutôt être capable de calculer ces valeurs uniquement à partir des points que nous ajoutons à la configuration de confiance.
L'étape suivante consiste à s'assurer que les trois combinaisons linéaires ont les mêmes coefficients. Nous pouvons le faire en ajoutant un autre ensemble de valeurs à la configuration de confiance : �⋅(��(�)+��(�)+��(�))⋅�, où � est un autre nombre qui doit être considéré comme « toxique ». déchets » et jetés dès que la configuration fiable est terminée. Nous pouvons ensuite demander au prouveur de créer une combinaison linéaire avec ces valeurs avec les mêmes coefficients, et d'utiliser la même astuce d'appariement que ci-dessus pour vérifier que cette valeur correspond au « + » + fourni.
Enfin, nous devons prouver que �⋅�−�=�⋅�. Nous faisons cela encore une fois avec une vérification d'appariement :
�(��,��)/�(��,�)?=�(�ℎ,�⋅�(�))
Où �ℎ=�⋅�(�). Si le lien entre cette équation et �⋅�−�=�⋅� n’a pas de sens pour vous, revenez en arrière et lisez le article sur les accords.
Nous avons vu ci-dessus comment convertir �,� et � en points de courbe elliptique ; � est juste le générateur (c'est-à-dire l'équivalent du point de courbe elliptique du nombre un). Nous pouvons ajouter �⋅�(�) à la configuration de confiance. � est plus difficile ; � n’est qu’un polynôme, et nous prédisons très peu à l’avance quels seront ses coefficients pour chaque solution QAP individuelle. Par conséquent, nous devons ajouter encore plus de données à la configuration de confiance ; spécifiquement la séquence:
�,�⋅�,�⋅�2,�⋅�3,�⋅�4….
Dans la configuration de confiance de Zcash, la séquence va ici jusqu'à environ 2 millions ; c'est le nombre de puissances de � dont vous avez besoin pour vous assurer que vous serez toujours capable de calculer �(�), au moins pour l'instance QAP spécifique qui les intéresse. Et ainsi, le prouveur peut fournir toutes les informations permettant au vérificateur d’effectuer le contrôle final.
Il y a encore un détail dont nous devons discuter. La plupart du temps, nous ne voulons pas simplement prouver de manière abstraite qu’une solution existe à un problème spécifique ; nous voulons plutôt prouver soit l'exactitude d'une solution spécifique (par exemple, prouver que si vous prenez le mot « vache » et que SHA3 le hache un million de fois, le résultat final commence par 0x73064fe5), soit qu'une solution existe si vous restreignez certains des paramètres. Par exemple, dans une instanciation de crypto-monnaie où les montants des transactions et les soldes des comptes sont cryptés, vous souhaitez prouver que vous connaissez une clé de décryptage k telle que :
decrypt(old_balance, k) >= decrypt(tx_value, k)
decrypt(old_balance, k) - decrypt(tx_value, k) = decrypt(new_balance, k)
Le crypté old_balance
, tx_value
ainsi que le new_balance
doit être précisé publiquement, car ce sont les valeurs spécifiques que nous cherchons à vérifier à ce moment précis ; seule la clé de déchiffrement doit être masquée. Quelques légères modifications du protocole sont nécessaires pour créer une « clé de vérification personnalisée » qui correspond à une restriction spécifique sur les entrées.
Maintenant, prenons un peu de recul. Tout d'abord, voici l'algorithme de vérification dans son intégralité, gracieuseté de ben Sasson, Tromer, Virza et Chiesa:
La première ligne concerne la paramétrisation ; essentiellement, vous pouvez considérer sa fonction comme étant de créer une « clé de vérification personnalisée » pour le cas spécifique du problème où certains des arguments sont spécifiés. La deuxième ligne est la vérification de la combinaison linéaire pour �,� et � ; la troisième ligne est la vérification que les combinaisons linéaires ont les mêmes coefficients, et la quatrième ligne est la vérification du produit �⋅�−�=�⋅�.
Au total, le processus de vérification comprend quelques multiplications de courbes elliptiques (une pour chaque variable d'entrée « publique ») et cinq contrôles d'appariement, dont l'un comprend une multiplication d'appariement supplémentaire. La preuve contient huit points de courbe elliptique : une paire de points chacun pour �(�),�(�) et �(�), un point �� pour �⋅(�(�)+�(�)+�(� )), et un point �ℎ pour �(�). Sept de ces points se trouvent sur la courbe �� (32 octets chacun, car vous pouvez compresser la coordonnée � en un seul bit), et dans l'implémentation Zcash, un point (��) se trouve sur la courbe torsadée en ��2 (64 octets), donc la taille totale de la preuve est d'environ 288 octets.
Les deux parties les plus difficiles en termes de calcul dans la création d'une preuve sont :
- Diviser (�⋅�−�)/� pour obtenir � (algorithmes basés sur le Transformée de Fourier Rapide peut le faire en un temps sub-quadratique, mais cela reste assez gourmand en calcul)
- Effectuer les multiplications et les ajouts de courbes elliptiques pour créer les valeurs �(�),�(�),�(�) et �(�) et leurs paires correspondantes
La raison fondamentale pour laquelle créer une preuve est si difficile est le fait que ce qui était une seule porte logique binaire dans le calcul d'origine se transforme en une opération qui doit être traitée cryptographiquement via des opérations sur courbe elliptique si nous en faisons une preuve sans connaissance. . Ce fait, associé à la superlinéarité des transformées de Fourier rapides, signifie que la création d'une preuve prend environ 20 à 40 secondes pour une transaction Zcash.
Une autre question très importante est la suivante : pouvons-nous essayer de rendre la configuration de confiance un peu… moins exigeante en matière de confiance ? Malheureusement, nous ne pouvons pas le rendre complètement sans confiance ; l’hypothèse de KoE elle-même interdit de créer des paires indépendantes (��,��⋅�) sans savoir ce qu’est �. Cependant, nous pouvons augmenter considérablement la sécurité en utilisant le calcul multipartite, c'est-à-dire en construisant une configuration de confiance entre les parties de telle sorte que tant qu'au moins un des participants supprime ses déchets toxiques, tout va bien. .
Pour avoir une idée de la façon dont vous procéderiez, voici un algorithme simple pour prendre un ensemble existant (�,�⋅�,�⋅�2,�⋅�3…) et « ajouter » votre propre secret. de sorte que vous avez besoin à la fois de votre secret et du secret précédent (ou de l'ensemble de secrets précédent) pour tricher.
L’ensemble de sortie est simplement :
�,(�⋅�)⋅�,(�⋅�2)⋅�2,(�⋅�3)⋅�3…
Notez que vous pouvez produire cet ensemble en connaissant uniquement l'ensemble et les s d'origine, et que le nouvel ensemble fonctionne de la même manière que l'ancien ensemble, sauf qu'il utilise désormais �⋅� comme « déchet toxique » au lieu de �. Tant que vous et la ou les personnes qui ont créé l’ensemble précédent ne manquez pas tous les deux de supprimer vos déchets toxiques et de vous entendre ultérieurement, l’ensemble est « sûr ».
Faire cela pour la configuration de confiance complète est un peu plus difficile, car plusieurs valeurs sont impliquées et l'algorithme doit être réalisé entre les parties en plusieurs tours. Il s'agit d'un domaine de recherche actif pour voir si l'algorithme de calcul multi-parties peut être davantage simplifié et nécessiter moins de tours ou rendu plus parallélisable, car plus vous pouvez en faire, plus il devient possible d'inclure de parties dans la procédure de configuration de confiance. . Il est raisonnable de comprendre pourquoi une configuration de confiance entre six participants qui se connaissent tous et travaillent ensemble pourrait mettre certaines personnes mal à l'aise, mais une configuration de confiance avec des milliers de participants serait presque impossible à distinguer d'une absence de confiance du tout - et si vous êtes vraiment paranoïaque , vous pouvez accéder et participer vous-même à la procédure de configuration, et être sûr que vous avez personnellement supprimé votre valeur.
Un autre domaine de recherche actif est l'utilisation d'autres approches qui n'utilisent pas de couplages et le même paradigme de configuration fiable pour atteindre le même objectif ; voir La récente présentation d'Eli ben Sasson pour une alternative (mais attention, c'est au moins aussi compliqué mathématiquement que les SNARK !)
Un merci spécial à Ariel Gabizon et Christian Reitwiessner pour la révision.
- Contenu propulsé par le référencement et distribution de relations publiques. Soyez amplifié aujourd'hui.
- PlatoData.Network Ai générative verticale. Autonomisez-vous. Accéder ici.
- PlatoAiStream. Intelligence Web3. Connaissance Amplifiée. Accéder ici.
- PlatonESG. Carbone, Technologie propre, Énergie, Environnement, Solaire, La gestion des déchets. Accéder ici.
- PlatoHealth. Veille biotechnologique et essais cliniques. Accéder ici.
- Décalages de bloc. Modernisation de la propriété des compensations environnementales. Accéder ici.
- La source: Intelligence de données Platon.