Rejoignez-Nous sur

zkSNARKS et accumulateurs cryptographiques | par Coinbase | Août 2020

1*sOUHMeHiuXv4v3iu1cSDsQ

News

zkSNARKS et accumulateurs cryptographiques | par Coinbase | Août 2020

Par Michael Lodder

Les preuves Zero-Knowledge (ZKP) sont un moyen de plus en plus populaire d'améliorer la confidentialité à la fois dans l'identité et la crypto-monnaie. Les idées initiales de preuve de zéro connaissance ont été publiées pour la première fois dans les années 1980, qui à l'époque ont été rejetées comme de la cryptographie qui n'irait nulle part. À cette époque, David Chaum a lancé l'idée de permettre les paiements électroniques sans connaissance. Malheureusement, ces idées sont accompagnées de redevances et de brevets et n’ont donc pas été largement appliquées. Dernièrement, les ZKP ont été appliqués à diverses crypto-monnaies afin de cacher à la fois les parties à la transaction et les montants échangés entre elles. Les ZKP peuvent également être utilisés pour réduire la taille de la blockchain afin que les validateurs et les observateurs puissent valider plus rapidement les transactions.

Dans le monde de la crypto-monnaie, le commerce et les dépenses ne fonctionnent que si les transactions ne peuvent pas être dépensées deux fois. Ainsi, deux vérifications sont effectuées: premièrement, une transaction doit être valide; et deuxièmement, une transaction ne doit pas avoir été dépensée. Essentiellement, le premier contrôle est un test d'appartenance d'ensemble, et le second est un test de non-appartenance d'ensemble. Un test d'appartenance est utilisé pour déterminer si un élément est présent dans un ensemble de valeurs. Un test de non-appartenance est utilisé pour déterminer l'absence d'un élément dans un ensemble de valeurs. L'ensemble de valeurs le plus populaire en production est Merkle-Trees, car vérifier si une valeur est dans l'ensemble ne nécessite pas la connaissance de l'ensemble de l'arborescence, mais seulement assez du sous-ensemble pour valider un chemin spécifique vers une valeur. Pourtant, appliquer des ZKP à un Merkle-Tree est compliqué. La raison d'utiliser les ZKP est de masquer la valeur et le chemin en cours de vérification pour préserver la confidentialité. Mais pour ce faire, des ZKP basés sur des circuits personnalisés doivent être conçus en tenant compte des différents paramètres de configuration:

  • Quelle fonction de hachage cryptographique utiliser?
  • Quelle est la profondeur maximale?
  • Les transactions peuvent-elles être élaguées?
  • Sélection de courbes elliptiques
  • Prouver le temps et les exigences de calcul
  • Temps de vérification
  • Taille de l'épreuve
  • Prouver la taille de la clé
  • Définir la taille

zkSNARK est la technique qui reçoit le plus d'attention et de recherche pour optimiser le paysage. Coda applique zkSNARKS de manière récursive pour réduire la taille de la blockchain à des fins de validation. ZCash utilise SNARKS pour anonymiser les parties et masquer les montants échangés en effectuant plusieurs preuves: l'une pour la validation de la signature, l'autre pour s'assurer que la transaction est valide. Cependant, les SNARK présentent certains inconvénients. D'une part, le circuit arithmétique souhaité doit être conçu pour qu'une chaîne de référence commune (CRS) appropriée puisse être générée. Le CRS est les paramètres publics du système (ZCash). Alors, quel système le SNARK doit-il utiliser? spartiate, Halo, Hyrax, Balance, Sonique, Pinard, Marlin… Chacun a des compromis entre les configurations fiables, la taille d'épreuve, les appariements bilinéaires ou d'autres courbes elliptiques, la génération d'épreuves et le temps de génération. Les SNARKS ne sont pas les seuls systèmes basés sur des circuits qui peuvent être utilisés. Bulletproofs, Pare-balles +, STARKS, SNARGS… la liste est longue mais il n'y a pas de gagnant clair et tous nécessitent des connaissances avancées en cryptographie. Heureusement, une autre primitive cryptographique existe pour effectuer des preuves d'appartenance (et de non-appartenance) à set rapide qui préserve la confidentialité (en ce que l'élément en cours de vérification n'est pas révélé), et fournit des preuves succinctes. Ces derniers sont appelés accumulateurs cryptographiques.

Les accumulateurs permettent aux parties de prouver qu'un élément X est dans un ensemble S ou pas quel que soit le nombre d'éléments dans S, sans divulguer quel élément a été vérifié. Les accumulateurs fonctionnent en ajoutant une valeur x à (ou retrait d'un) accumulateur de taille constante UNE, et prouvant que le témoin d'adhésion u, lorsqu'il est combiné avec X, égal à accumulateur UNE. Les valeurs d'accumulateur sont de courts résumés de longueur fixe (similaires aux fonctions de hachage), mais prennent également en charge de courtes preuves pour les vérifications d'appartenance et de non-appartenance pour tout élément de l'ensemble. En d'autres termes, un accumulateur représente l'ensemble des éléments par une seule valeur, la taille est indépendante du nombre d'éléments. Un accumulateur est dynamique si des éléments peuvent être ajoutés ou supprimés efficacement de l'ensemble. Sinon, l'accumulateur est statique. UNE universel L'accumulateur est dynamique et prend en charge les preuves d'adhésion et de non-adhésion. Sinon, on dit que l'accumulateur ne prend en charge que les preuves d'adhésion.

En raison de la configuration plus simple et des preuves plus courtes, celles-ci offrent une alternative intéressante aux SNARK. Ce n'est pas un nouveau concept pour remplacer la partie test d'adhésion des preuves par un accumulateur (voir OWWB19). cependant, OWWB19 propose d'utiliser un accumulateur dans le SNARK plutôt que de laisser tomber complètement des SNARK. Ils montrent que la combinaison d'accumulateurs SNARK a des exigences de coût moins coûteuses en termes d'espace et de performances, comme le montre également cet article.

Les accumulateurs appartiennent aux trois catégories suivantes: ordre inconnu, par ex. (Sander97, BP97, BM93, CL02, LLX07, Lèvre12, BCDLRSY17, BBF18, OWWB19, DGS20), Cartes bilinéaires (Nguyen05, ATSM09, CKS08, DT08, Thakur19, VB20) et basé sur le hachage (CHKO08). Chacun offre des compromis entre les paramètres de configuration, les tailles d'accumulateur, les performances et l'espace des témoins et des preuves. Les accumulateurs d'ordre inconnu sont subdivisés en RSA et Hyperelliptique (ordres de classe). Le reste de cet article se concentre sur l'histoire de la mise en œuvre de l'accumulateur basé sur RSA et de son fonctionnement.

Les accumulateurs RSA offrent le compromis le plus efficace entre le nombre de paramètres de configuration, la mise à jour des exigences des témoins, le calcul de la preuve et la concision. La valeur de l'accumulateur et le témoin sont de la taille d'un module RSA. Quand mis en œuvre, le module, la valeur de l'accumulateur et les témoins sont de 256 octets avec des éléments de 32 octets, et les preuves d'appartenance font 800 octets et ne nécessitent que 90 millisecondes (ms) pour calculer, utilise 2 Ko de RAM et 30 ms pour vérifier. Les mises à jour des témoins peuvent être calculées en 5 à 10 ms selon le système sous-jacent. Les preuves sans adhésion nécessitent la création de deux preuves, mais les preuves peuvent être calculées en parallèle, ce qui prend le même temps mais deux fois plus d'espace avec 1,6 Ko.

Comparez cela à celui de ZCash JubJub SNARK qui nécessite de télécharger l'intégralité de Merkle-Tree, qui fait quelques gigaoctets, de télécharger la clé de preuve autour de 32 Mo, de générer un témoin de 458 Ko en 1 seconde en utilisant 150 Mo de RAM, de générer la preuve en utilisant 106 Mo de RAM, en prenant 3 secondes, et en produisant un Preuve d'octet de 1,4 Ko (CryptQuest2018). L'avantage des accumulateurs cryptographiques est que les preuves sont succinctes et rapides à calculer.

Pour configurer un accumulateur RSA, il faut générer deux nombres premiers sûrs (p, q) de taille suffisante (≥ 1024 bits) pour calculer le module de coprime n et créer un générateur qui est un résidu quadratique g, trouve essentiellement un nombre aléatoire et calcule la quadrature modulaire. g est la valeur de l'accumulateur vide et utilisée pour créer des preuves de non-adhésion. La génération de (p, q) est généralement effectuée avec un revendeur de confiance, mais certaines méthodes distribuées permettent de le faire de manière décentralisée (AVD19) (sans confiance) bien que plus compliqué. Chaque élément à accumuler doit être un nombre premier unique. Les valeurs peuvent être mappées à des nombres premiers par une fonction qui est généralement une table de recherche ou un algorithme de hachage et ajoutée à l'ensemble S. La valeur de l'accumulateur est calculée comme suit:

Les valeurs sont accumulées en calculant l'exponentiation modulaire de la valeur actuelle de l'accumulateur vers le nouvel élément. Les suppressions peuvent être calculées de deux manières: avec la connaissance de p, q Et sans. Le créateur (ou revendeur) de l'accumulateur de confiance utilise p, q pour calculer le totient d'Euler et calculer:

Attention à votre p et q's, car sans eux, l'accumulateur doit être recalculé en multipliant tous les éléments de l'accumulateur par une exponentiation modulaire, encore une fois. Un utilisateur a un témoin d'appartenance ou de non-adhésion (ou les deux) selon le type de preuve attendu par une partie de confiance. Le témoin d'adhésion u est calculé:

Le témoin doit être mis à jour pour refléter toute modification apportée à l'accumulateur, sinon les preuves seront invalides. Les utilisateurs peuvent mettre à jour efficacement leurs témoins à mesure que des éléments sont ajoutés et supprimés de l'accumulateur. Malheureusement, la mise en œuvre de la variante de non-adhésion était beaucoup plus compliquée que la version d'adhésion. le papier de dosage montre le témoin non-membre comme

Cela fonctionne bien, les preuves sont calculées normalement et fonctionnent très bien. La mise en garde se produit lors de la tentative de mise à jour du témoin w. Le papier de dosage fait référence à un autre papier LLX07 pour ce calcul. Au début, le calcul semble simple dans la section 4.2 où il est dit de faire ce qui suit pour l'addition:

Pour vérifier l'exactitude de la mise à jour, calculez un témoin non membre actuel sans effectuer de mise à jour et comparez pour l'égalité. Cependant, ils ne correspondent pas (bureau de renversement).

Pour vérifier si la correspondance fonctionne correctement, j'insère plusieurs instructions assert qui vérifient les hypothèses faites dans LLX07. Tous passent moins l'hypothèse finale. Après avoir été perplexe pendant un moment, j'ai lu le LLX07 depuis le début et découvrez que le témoin de non-appartenance diffère par un signe, Bg-b. J'ai fait ce changement et les mises à jour sans abonnement fonctionnent correctement, mais maintenant les preuves sont cassées. La seule option est de retravailler les calculs pour s’assurer que les choses se vérifient et cherchent là où elles ne le sont pas. L'équation fautive ici est la preuve qui calcule la preuve de connaissance des exposants (POE, preuve que les exposants sont connus du prouveur sans les révéler) avec l'accumulateur courant UNE et valeur de non-adhésion une. Au lieu d'inverser V, le générateur g devait être inversé, déplaçant l'opération inverse modulaire. Voici un avant et un après:



Traduction de l’article de Coinbase : Article Original

BlockBlog

Le Meilleur de l'Actualité Blockchain Francophone & Internationale | News, Guides, Avis & Tutoriels pour s'informer et démarrer facilement avec Bitcoin, les Crypto-Monnaies et le Blockchain. En Savoir Plus sur L'Équipe BlockBlog

Commenter cet Article

Commenter cet Article

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Plus dans News

Les Plus Populaires

Acheter des Bitcoin

Acheter des Alt-Coins

Sécuriser vos Cryptos

Vêtements et Produits Dérivés

Top