Le premier paiement conditionnel Zero-Knowledge réussi


Je suis heureux d’annoncer le premier paiement contingent sans connaissance (ZKCP) réussi sur le réseau Bitcoin.

ZKCP est un protocole de transaction qui permet à un acheteur d’acheter des informations à un vendeur utilisant Bitcoin de manière privée, évolutive, sécurisée et qui ne nécessite de faire confiance à personne : les informations attendues sont transférées si et seulement si le paiement est effectué. L’acheteur et le vendeur n’ont pas besoin de se faire confiance ou de dépendre de l’arbitrage d’un tiers.

Imaginez un « échange de porte-documents » de style cinématographique (une partie avec une mallette pleine d’argent, une autre contenant des documents secrets), mais sans le scénario potentiel d’un des cas rempli de papier journal déchiqueté et la scène de poursuite passionnante qui en résulte.

Le premier paiement conditionnel Zero-Knowledge réussi

Ce type de vente est intrinsèquement irréversible, traverse potentiellement plusieurs juridictions et implique des parties dont la stabilité financière est incertaine, ce qui signifie que les deux parties prennent de gros risques ou doivent prendre des dispositions difficiles. L’utilisation d’un ZKCP évite les coûts de transaction importants impliqués dans une vente qui, autrement, peuvent facilement mal tourner.

Dans la transaction d’aujourd’hui, j’ai acheté une solution à un puzzle Sudoku 16×16 pour 0,10 BTC de Sean Bowe, membre de l’équipe Zcash, dans le cadre d’une démonstration réalisée en direct à Financial Cryptography 2016 à la Barbade. J’ai joué mon rôle dans la transaction à distance depuis la Californie.

Le transfert impliquait deux transactions :

Presque tout le travail d’ingénierie derrière cette implémentation de ZKCP a été réalisé par Sean Bowe, avec le soutien de Pieter Wuille, moi-même et Madars Virza.

Voir les diapositives de la démo en direct.

Arrière-plan

J’ai d’abord proposé le protocole ZKCP en 2011 dans un article sur le Bitcoin Wiki comme exemple de la puissance énorme des primitives existantes dans Bitcoin Script.

Preuves de connaissance zéro

Mon protocole ZKCP nécessitait comme élément de base une preuve sans connaissance pour les programmes arbitraires. Il existe de nombreux types de preuves spécialisées à connaissance nulle  : les signatures numériques courantes en sont un exemple, tout comme les preuves de gamme dans Transaction confidentielle.

Une preuve de connaissance zéro pour le calcul général est un système cryptographique qui permet à une personne d’exécuter un programme arbitraire avec un mélange d’entrées publiques et secrètes et de prouver aux autres que ce programme spécifique a accepté les entrées, sans rien révéler de plus sur son fonctionnement ou le secret. contributions.

Si cela semble être une magie impossible, à des fins éducatives, j’ai proposé un système ZKP très simple mais inefficace qui n’utilise rien de plus sophistiqué que les circuits booléens et les hachages cryptographiques, ou voir l’exemple ZKP de coloration graphique de Matthew Green.

Comme mon article initial sur ZKCP l’a noté, aucun système de ce type n’était facilement disponible en 2011, mais on pensait qu’ils étaient possibles, en particulier sous des contraintes spécifiques qui auraient fonctionné pour ZKCP.

En 2012, Gennaro, Gentry, Parno et Raykova ont publié un article (« Quadratic Span Programs and Succinct NIZKs without PCPs ») qui décrivait une construction particulièrement efficace. Depuis lors, plusieurs groupes ont continué à faire avancer ce travail, créant des compilateurs, des améliorations de performances et, surtout, des outils pratiques comme libsnark. Le cryptosystème GGPR’12 nécessite une configuration de confiance, mais pour l’application ZKCP, ce n’est pas vraiment une limitation puisque l’acheteur peut l’exécuter. Grâce à ce travail, ZKCP peut maintenant devenir un outil pratique.

Lecture complémentaire :

Parce que ces ZKP efficaces sont une technologie de pointe qui dépend de nouvelles hypothèses cryptographiques fortes, leur sécurité n’est pas encore établie. Mais dans des applications comme ZKCP où nos seules alternatives sont la confiance de tiers.

Comment fonctionne ZKCP

Si vous acceptez l’existence du système de preuve à connaissance zéro comme une boîte noire, le reste du protocole ZKCP est assez simple.

L’acheteur crée d’abord un programme qui peut décider si l’entrée qui lui est fournie correspond aux données que l’acheteur souhaite acheter. Ce programme ne fait que vérifier les informations, il ne les produit pas – l’acheteur n’a même pas besoin d’avoir la moindre idée de comment les produire. (Par exemple, il est facile d’écrire un programme pour vérifier qu’une solution de Sudoku est correcte, mais plus difficile d’écrire un solveur de Sudoku, le Sudoku est NP-complet. L’acheteur ici n’a qu’à écrire le vérificateur de solution.)

L’acheteur effectue la configuration de confiance pour le système de preuve et envoie les informations de configuration résultantes au vendeur.

Le vendeur choisit une clé de cryptage aléatoire et crypte les informations que l’acheteur souhaite acheter.

En utilisant le système ZKP, le vendeur prouve une déclaration composite  :

  • Ex est un cryptage d’une entrée qui satisfait le programme de l’Acheteur
  • Y est le hachage sha256 de la clé de déchiffrement pour Ex

Le vendeur envoie Ex, Y, la preuve et sa clé publique à l’acheteur. Une fois que l’ordinateur de l’acheteur a vérifié la preuve, l’acheteur sait que s’il apprend l’entrée de SHA256 qui produit le hachage Y, il peut déchiffrer sa réponse.

Ainsi, l’acheteur voulait initialement acheter une entrée pour son programme, mais maintenant il serait tout aussi heureux d’acheter la préimage d’un hachage. Il s’avère que Bitcoin fournit déjà un moyen de vendre des préimages de hachage de manière sécurisée.

L’acheteur effectue son paiement sur la ScriptPubkey suivante  :

L’effet de ce paiement est que le vendeur peut le percevoir s’il fournit la préimage de hachage de Y et une signature avec sa clé. Pour éviter d’immobiliser les fonds de l’acheteur pour toujours, si le vendeur ne récupère pas son paiement dans (par exemple) un jour, l’acheteur peut réclamer le paiement.

De ce fait, lorsque le vendeur encaisse son paiement, il est contraint de révéler les informations dont l’acheteur a besoin pour décrypter la réponse. S’il ne le fait pas, l’acheteur récupère ses fonds.

Ce ScriptPubkey est également le même que celui qui serait utilisé pour un échange atomique inter-chaînes ou un canal de paiement éclair.

La prise en charge du portefeuille pour ces transactions a été implémentée pour Bitcoin Core dans PR # 7601.///zcash/pay-to-sudoku.

Le programme de l’acheteur peut être arbitrairement long et complexe sans ajouter de charge supplémentaire à la blockchain de Bitcoin – le seul impact serait l’augmentation du temps nécessaire à la configuration et à la vérification, qui se produisent toutes en dehors de Bitcoin. Personne en dehors de l’acheteur ou du vendeur n’apprend quoi que ce soit sur le programme de l’acheteur (c’est-à-dire qu’ils n’apprennent pas la nature des informations vendues).

Limites et alternatives

Cette approche est beaucoup plus évolutive et privée que la conduite de contrats intelligents à l’intérieur de la blockchain, et elle n’est pas susceptible d’être freinée par des limitations de performances ou de fonctionnalités dans les contrats intelligents de Bitcoin.

Il existe deux principales restrictions à cette approche. Tout d’abord, qu’il est interactif : l’acheteur ne peut pas simplement faire une offre diffusée et faire accepter le paiement par n’importe quel vendeur intéressé sans communication réciproque. Et deuxièmement, que le système ZKP, bien qu’assez rapide pour être pratique, n’est toujours pas très rapide. Par exemple, dans notre démo, le système ZKP prouve 5 exécutions de SHA256 et des contraintes Sudoku, et prend environ 20 secondes pour s’exécuter sur un ordinateur portable. (La vérification de la preuve ne prend que quelques millisecondes.)

Une alternative au ZKCP est le protocole « paypub » de Peter Todd en 2014. Dans Paypub, au lieu d’utiliser une preuve de connaissance zéro, l’acheteur voit un sous-ensemble aléatoire des données qu’il tente d’acheter, et le vendeur est obligé de déverrouiller le reste lorsqu’il perçoit son paiement. Paypub évite la complexité de traiter avec une preuve à connaissance nulle – et permet également l’échange d’informations que seuls les humains peuvent vérifier -, mais au prix d’une certaine vulnérabilité à la triche, et n’est utilisable qu’avec un ensemble relativement important d’informations vérifiables de manière aléatoire.

En général, je pense que les contrats intelligents «sans confiance» comme ceux-ci ont le plus de valeur là où il y a de fréquentes transactions automatisées de très faible valeur – de sorte que les frais généraux des méthodes traditionnelles de résolution des conflits privent les participants d’un accès significatif à la justice – ou pour très échanges de grande valeur où la vitesse, le manque de fiabilité (en particulier entre les juridictions) ou le manque de confidentialité de la résolution traditionnelle des conflits seraient inacceptables.

J’attends avec impatience les applications passionnantes que les gens trouveront pour eux à mesure que la technologie deviendra de plus en plus pratique.

Grégory Maxwell