Connaissance complète

de James Austgen, Kushal Babel, Vitalik Buterin, Phil Daian, Ari Juels et Mahimna Kelkar

« Dans cette vie, nous ne voulons que des faits, monsieur ; rien que des faits !'

— Charles Dickens, Temps difficiles

Dans un article que nous avons publié aujourd'hui , nous introduisons une nouvelle notion cryptographique que nous appelons preuves de connaissance complète (CK). Nous rendons également compte d'un prototype qui offre un moyen de rendre CK pratique pour une utilisation avec les smartphones.

Les preuves de connaissance, comme leur nom l'indique, permettent à une partie, par exemple Alice, de convaincre une autre partie, par exemple Bob, qu'elle connaît un secret particulier, comme une clé privée SK . Les signatures numériques en sont un exemple. Considérez une transaction de crypto-monnaie T créée par Alice qui dépense des fonds depuis son adresse A . Pour être valide, T doit être signé numériquement avec la clé privée valide SK pour A . La signature numérique prouve ici qu'Alice, en tant que créatrice de T , connaît la clé SK . C'est cette preuve de connaissance de SK qui rend la transaction valide : Dans un système de crypto-monnaie, le propriétaire de l'adresse Aest par définition celui qui connaît SK .

Les preuves de connaissance sont un pilier de la conception de systèmes cryptographiques. Il s'avère, cependant, que les systèmes de preuve de connaissance existants ont une sérieuse limitation : Alice peut être capable de créer une preuve convaincante qu'elle connaît SK , mais elle ne le sait peut-être toujours pas vraiment .

Voici une analogie. Supposons que Mallory veuille apparaître en tant que concurrent sur Jeopardy . Elle fait une interview avec l'animateur de l'émission (Mayim Bialik). Mallory sait qu'elle recevra des questions lors de l'entretien sur les capitales des États américains, ce qu'elle n'a jamais appris à l'école. (Elle était occupée à retourner des NFT pendant les cours de géographie.) Alors elle décide de tricher. Alice, l'amie de Mallory, connaît toutes les capitales des États de la moitié est des États-Unis, tandis que son ami Bob connaît celles de l'ouest. Mallory cache donc un appareil de communication sans fil dans chaque oreille. Celui de son oreille gauche communique avec Alice. Celui de son oreille droite communique avec Bob. Grâce à la tromperie de Mallory, lorsqu'elle est interrogée sur les capitales de divers États américains lors de son entretien, elle répond toujours correctement.

Mais Mallory connaît-il toutes les capitales des États américains ? Clairement pas. Est-ce qu'Alice ou Bob? La réponse est toujours non. On peut peut-être dire qu'Alice et Bob connaissent ensemble toutes les capitales des États américains. Mais supposons qu'Alice soit étrangement superstitieuse et refuse de répondre aux questions sur la capitale de l'État le vendredi. Peut-on encore dire qu'Alice et Bob connaissent ensemble toutes les capitales des états américains ? Oui et non. La connaissance existe dans la tête d'Alice et de Bob, mais il n'est pas forcément possible de l'extraire comme on le souhaite . Si Mallory fait son interview pour Jeopardy un vendredi, elle a des ennuis.

Une connaissance complète comble une lacune de ce genre dans ce que signifie avoir des connaissances. Dans notre analogie, le refus d'Alice de répondre aux questions un vendredi est une restriction d'accès à la connaissance que nous appelons encombrement . Pour expliquer où les preuves de connaissances existantes en cryptographie sont insuffisantes, il est utile de commencer par quelques exemples potentiellement problématiques d'encombrement des clés secrètes en particulier.

Le problème de l'encombrement

Deux technologies différentes peuvent encombrer des secrets : les environnements d'exécution de confiance (TEE) et le calcul multipartite sécurisé (MPC).

Les TEE sont des environnements de calcul qui ressemblent à des boîtes noires : leur état interne est opaque et inviolable. Utilisant du matériel ou des logiciels, ils renforcent à la fois l' intégrité et la confidentialité des applications en cours d'exécution, offrant des protections contre la falsification et l'observation, même par le propriétaire de la machine même sur laquelle le code s'exécute. Les exemples de TEE incluent les enclaves (par exemple, ARM Trustzone) sur les appareils mobiles et Intel Software Guard eXtensions (SGX), qui est disponible sur certains serveurs cloud.

D'autre part, MPC est une approche algorithmique pour atteindre à peu près les mêmes objectifs de sécurité. Il répartit les secrets et les calculs entre un ensemble de serveurs souvent appelé comité. La sécurité de MPC repose sur un quorum de serveurs au sein du comité (par exemple, une majorité) se comportant correctement.

Comme les TEE sont beaucoup plus pratiques et répandus que les MPC aujourd'hui, nous nous concentrerons sur les TEE dans les exemples suivants, en commençant par une attaque basée sur TEE sur les systèmes de vote blockchain. Voici un exemple impliquant une attaque contre les systèmes de vote.

Le problème de la corruption forte et furtive dans cet exemple affecte non seulement les schémas de vote blockchain conçus naïvement, mais même ceux spécifiquement conçus pour résister à la corruption, tels que l' infrastructure minimale anti-collusion (MACI) .

Pire encore, un TEE peut inciter et développer furtivement une communauté d'utilisateurs en montant une attaque unifiée contre un protocole - un concept que nous avons précédemment surnommé Dark DAO . De telles attaques pourraient impliquer non seulement de falsifier les votes, mais aussi de manipuler les prix des actifs et éventuellement d'attaquer des systèmes hors chaîne .

Ce qui est particulièrement pernicieux, c'est que si Alice envoie une transaction signée à un contrat intelligent à l'aide d'une clé encombrée SK , le contrat n'a aucun moyen de le dire. La transaction d'Alice sera identique à celle créée avec une clé libre. Il semble donc qu'il soit tout simplement impossible d'empêcher les attaques de corruption du type illustré dans notre exemple.

Mais est-ce vraiment ?

Assurer une connaissance complète

Il s'avère qu'il existe un moyen de s'assurer qu'une clé SK n'est pas encombrée - en particulier que quelqu'un a un accès direct à SK . De manière informelle, c'est ce que nous entendons par connaissance complète. L'effet de CK est que les schémas de corruption comme celui de notre exemple ne fonctionneront pas, car il n'y a aucun moyen pour un utilisateur malveillant comme Mallory d'empêcher un utilisateur d'utiliser sa clé comme il le souhaite.

Il existe deux approches de base pour appliquer CK. Les deux permettent de générer ce que nous appelons des preuves de connaissance complète (PoCK), et plus particulièrement celles qui sont à connaissance nulle , c'est-à-dire qui ne révèlent pas SK :

1. L' approche du feu par le feu

La plupart des utilisateurs ont des TEE sur leurs combinés mobiles. Nous montrons dans notre article comment ils peuvent les utiliser dans un schéma CK pour voter ou toute autre application.

Comme nous en discutons dans notre article, cependant, il existe certaines limites techniques aux TEE, en particulier celles des téléphones mobiles. Nous considérons donc également une deuxième approche.

2. Une approche basée sur la preuve de travail

Cette approche est légèrement contre-intuitive. Cela implique l'utilisation d'un ASIC minier, c'est-à-dire une plate-forme matérielle de minage de preuve de travail, telle que celle utilisée pour Bitcoin. Les ASIC ont deux propriétés intéressantes aux fins de CK. Ils peuvent effectuer certains calculs, à savoir le hachage , bien plus rapidement que les CPU ou GPU ordinaires — de l'ordre d'un million de fois plus vite qu'un CPU à la pointe de la technologie ! Et ils n'incluent pas les TEE.²

En s'inspirant et en modifiant les techniques de la littérature sur la théorie des preuves de connaissance, nous avons conçu un protocole qui implique l'utilisation d'un ASIC pour l'exploitation minière d'une manière qui implique SK (mais le cache intelligemment). Ce protocole génère une preuve que SK a été envoyé à l'ASIC, c'est-à-dire un PoCK. Étant donné que l'ASIC n'a pas de TEE, cela signifie que SK est effectivement exposé à l'utilisateur de l'ASIC. Cette propriété est essentiellement équivalente à ce qui est fait par l'application spéciale TEE de RBU : cracher SK directement à l'utilisateur. Étant donné que l'ASIC est tellement plus rapide que les plates-formes qui prennent en charge les TEE, il n'y a aucun moyen de générer un PoCK équivalent à l'aide d'un TEE.

Notre article montre expérimentalement que même en utilisant un ASIC bon marché (environ 200 $) et obsolète (vers 2017), il est possible de mettre en œuvre un PoCK haute sécurité.

Applications de CK au-delà de la résistance à la corruption

Bien que nous ayons initialement conçu CK pour faire face à la menace de corruption dans les systèmes de vote, il existe de nombreuses autres applications. CK peut aider à prévenir l'encombrement des identifiants d'identité décentralisés, par exemple, l'attestation qu'un utilisateur a fait l'objet d'une diligence anti-blanchiment d'argent. Ceci est essentiel pour éviter les nombreux types de méfaits possibles si les utilisateurs peuvent louer leurs informations d'identification, par exemple, un marché des informations d'identification pour contourner les sanctions.

CK a également des applications intéressantes sur les marchés NFT. Par exemple, cela peut aider à assurer l'exécution des paiements de redevances pour les artistes. Aujourd'hui, les redevances ne sont appliquées qu'en dehors de la chaîne, c'est-à -dire volontairement , par les places de marché NFT. Au lieu de cela, ils pourraient en principe être appliqués en chaîne dans un contrat intelligent, auquel cas l'application serait obligatoire. L'une des raisons pour lesquelles les paiements de redevances obligatoires ne sont pas considérés comme une bonne pratique est qu'il serait injuste pour les utilisateurs transférant des NFT entre leurs propres adresses de devoir payer des redevances. Le problème est qu'il n'y a aucun moyen de faire la distinction entre une adresse d'expéditeur S et une adresse de destinataire R appartenant à un même utilisateur et les adresses S et Rappartenant à des utilisateurs distincts. Il n'y a donc aucun moyen de faire la distinction entre un transfert mono-utilisateur et un changement de propriétaire d'un NFT.

Avec CK, cependant, il est possible de faire la distinction. Un contrat de place de marché NFT pourrait exiger pour les transferts sans redevance qu'un PoCK soit appliqué simultanément à R et S , prouvant qu'une seule entité connaît les deux . Cette propriété est une assez bonne approximation de la propriété individuelle. Au moins, nous pensons que cette approche basée sur CK pourrait fortement dissuader l'évasion des redevances.³

Une autre application intéressante de CK aux NFT est une notion que nous appelons Atomic NFT . Il est courant de fractionner les NFT coûteux, c'est-à-dire de subdiviser leur propriété en petits morceaux, comme cela s'est produit par exemple avec le Doge NFT .

Un certain nombre d'artistes avec qui nous avons parlé préfèrent cependant que leurs œuvres soient détenues et appréciées par une seule personne. Les NFT atomiques offrent un moyen de créer des NFT qui respectent ce désir et garantissent une propriété exclusive. Pour démontrer ces capacités, nous avons créé notre propre petite collection de NFT atomiques, illustrée ici.

Conclusion

Les preuves de connaissance sont un concept bien étudié et vieux de plusieurs décennies en cryptographie. Mais de nouvelles technologies (plutôt) puissantes telles que les TEE et les MPC menacent de bouleverser le paysage classique de la preuve de connaissance en encombrant les secrets. CK offre un moyen d'éviter un tel encombrement et de restaurer l'idée intuitive que la connaissance est attribuable à une seule entité ou à un seul individu. En plus d'offrir un remède aux attaques basées sur la charge, telles que la corruption dans les systèmes de vote, il offre également une gamme de nouvelles applications.

Nous croyons que CK peut être pratique. Nous avons mis en place un système basé sur ASIC de bout en bout avec un contrat intelligent qui vérifie les preuves PoCK. Notre système prototype comprend un registre d'adresses basé sur des contrats intelligents qui s'est avéré conforme à CK. Nous avons également mis en place un système prototype utilisant des TEE basés sur des téléphones mobiles. Nos prototypes ne sont pas encore prêts pour les heures de grande écoute, mais nous pensons qu'il existe une voie vers un déploiement pratique en production. Vous pouvez trouver une version open-source de nos outils ici . Nous accueillons la collaboration de projets intéressés à le réaliser.

¹ Heureusement, les TEE ne peuvent pas être imbriqués, il n'y a donc aucun moyen intelligent pour Mallory d'encapsuler l'application TEE de RBU et d'encombrer ainsi les clés des utilisateurs.

² La plupart des ASIC ont très peu de sécurité intégrée. Ils ne prennent même pas en charge les réseaux cryptés, comme nous l'avons découvert lorsque notre ASIC a apparemment été compromis par un pirate distant à plusieurs reprises au cours de nos expériences.

³ Il y a une mise en garde ici. Comme nous en discutons dans notre article, si les mécanismes de récupération sociale devenaient monnaie courante, les preuves CK de la connaissance simultanée des clés ne fonctionneraient plus.