Résumé technique : Échanges atomiques probabilistes pour Bitcoin et ses pairs

1. Énoncé du problème

Les échanges atomiques sont un primitif cryptographique fondamental permettant un échange inter-chaîne sans confiance d'actifs numériques avec une garantie « tout ou rien » : soit les deux parties reçoivent leurs actifs convenus, soit aucune ne le fait. Bien que puissante, cette nature déterministe exclut les échanges où le résultat souhaité est probabiliste. Les solutions existantes pour les échanges probabilistes (par exemple, loteries, paris ou allocation aléatoire) sur les blockchains font face à des limitations significatives :

• Complexité et coût : Elles nécessitent souvent des contrats intelligents complexes ou des mécanismes intricés au niveau des scripts, entraînant une taille de transaction plus grande, des frais plus élevés et une portabilité réduite vers des chaînes avec un support de script limité (comme Bitcoin).
• Vie privée et fongibilité : Des scripts complexes rendent le comportement sur la chaîne distinguable, affaiblissant la vie privée et la fongibilité.
• Contraintes de participation : De nombreux protocoles de loterie existants nécessitent un ensemble fixe et connu de participants, les rendant inadaptés aux environnements ouverts et sans permission.
• Vulnérabilité aux biais : Les approches antérieures échouent souvent à empêcher une partie de prédire le résultat et d'annuler sélectivement si le résultat est défavorable, biaisant ainsi la probabilité effective.

Le défi central consiste à étendre les échanges atomiques à un cadre probabiliste — où une partie paie pour une chance fixe et publiquement spécifiée de recevoir une récompense plus importante — sans modifier l'empreinte minimale sur la chaîne des protocoles d'échanges atomiques existants ni introduire d'intermédiaires de confiance.

2. Méthodologie et conception du protocole

Les auteurs introduisent les échanges atomiques probabilistes, un nouveau primitif cryptographique qui réalise un échange équitable avec une distribution de résultats prescrite. Le protocole implique deux parties : un Marchand (D) et une Partie (P). P transfère un montant fixe (par exemple, 1 pièce) en échange d'une probabilité $p$ de recevoir une récompense plus importante ($\nu$ pièces) de la part de D. Si l'événement probabiliste ne se produit pas, P ne reçoit rien et D conserve le paiement.

Blocs de construction cryptographiques principaux

La construction repose sur trois composants principaux, tous compatibles avec les scripts standards de type Bitcoin (signatures numériques et verrouillages temporels) :

1. Signatures adaptatrices : Utilisées pour assurer l'atomicité. Elles permettent d'adapter une pré-signature en une signature complète uniquement si un témoin spécifique (secret) est connu. Cela lie la révélation des secrets à l'achèvement des transactions sur la chaîne.
2. Fonctions pseudo-aléatoires aveugles (OPRF) : Utilisées pour encoder le résultat probabiliste. Le Marchand agit comme un serveur OPRF détenant une clé secrète $sk_D$. La Partie détient une entrée (un « pari » $y_{gss}$). L'OPRF permet à la Partie d'obtenir l'évaluation $OPRF(sk_D, y_{gss})$ sans que le Marchand apprenne le pari, et sans que la Partie apprenne la clé.
3. Preuves à divulgation nulle de connaissance (NIZK) : Utilisées pour prouver la bonne forme des déclarations du protocole, garantissant que le Marchand ne peut pas manipuler la distribution de probabilité.

Flux du protocole

Le protocole est divisé en quatre phases :

1. Configuration et financement :

   • Le Marchand échantillonne une valeur cible $y_{tgt}$ à partir d'un domaine de taille $m$ (où $p = 1/m$).
   • Le Marchand calcule un « témoin gagnant » $y_{win} = OPRF.Eval(sk_D, y_{tgt})$ et construit une déclaration $Y_{win} = g^{y_{win}}$.
   • Le Marchand fournit $Y_{win}$ et une preuve NIZK de bonne forme à la Partie.
   • Les deux parties verrouillent leurs fonds dans des scripts verrouillés temporellement contrôlés par une paire de clés temporaire (générée via un protocole DKG à 2 parties).

2. Réclamation du Marchand (Évaluation OPRF en tant que service) :

   • La Partie sélectionne un pari $y_{gss}$ et envoie une demande OPRF aveuglée au Marchand.
   • Le Marchand évalue l'OPRF, chiffre le résultat sous une clé éphémère $Z$, et fournit le texte chiffré ainsi qu'une preuve NIZK de correction.
   • Crucialement, le Marchand pré-signe également la transaction de paiement de la Partie en utilisant $Z$ comme déclaration adaptatrice.
   • Le Marchand adapte cette pré-signature en utilisant la clé de déchiffrement $z$ (le témoin pour $Z$) et diffuse la transaction pour réclamer le paiement de la Partie.
   • Atomicité : La Partie ne peut extraire $z$ de la signature sur la chaîne qu'après que le Marchand a été payé. $z$ est requis pour déchiffrer la réponse OPRF.

3. Réclamation de la Partie :

   • La Partie extrait $z$, déchiffre la réponse OPRF et calcule le témoin candidat $y'_{win}$.
   • Si $y'_{win}$ correspond au témoin gagnant (c'est-à-dire $y_{gss} = y_{tgt}$), la Partie adapte la pré-signature du Marchand pour réclamer la récompense.
   • Si le pari est incorrect, la Partie n'apprend rien d'utile pour l'adaptation.

4. Expiration / Remboursement :

   • Si le Marchand échoue à réclamer le paiement dans un délai imparti, la Partie rembourse ses fonds verrouillés.
   • Si la Partie échoue à réclamer la récompense dans un délai imparti, le Marchand rembourse ses fonds verrouillés.

Preuves de bonne forme

Une contribution technique critique consiste à prouver que $Y_{win}$ correspond à une évaluation OPRF valide sur une valeur dans le domaine correct, sans révéler la cible. Les auteurs proposent deux instanciations :

• Bulletproofs : Utilise des contraintes R1CS pour prouver la structure de l'OPRF 2HashDH. Il offre une taille de preuve et un temps de vérification constants mais nécessite l'instanciation d'oracles aléatoires.
• Coupe et choix : Une technique où le Marchand fournit plusieurs instances, et la Partie vérifie un sous-ensemble aléatoire. Les auteurs modifient l'OPRF pour permettre d'ouvrir des instances sans révéler la valeur cible, garantissant que la probabilité de gagner reste exactement $1/m$ même si le Marchand triche. Cette approche est plus efficace pour les probabilités de gagner élevées ($p \ge 1/2^{12}$).

3. Contributions clés

• Nouveau primitif : Introduction des échanges atomiques probabilistes, définis formellement via une fonctionnalité idéale qui généralise les échanges atomiques déterministes aux résultats probabilistes.
• Empreinte minimale sur la chaîne : Le protocole ne nécessite que des scripts Bitcoin standards (signatures et verrouillages temporels). Il ne requiert pas de contrats intelligents complexes ni de nouveaux opcodes, le rendant immédiatement déployable sur Bitcoin, Litecoin et d'autres chaînes supportant les échanges atomiques.
• Évaluation OPRF pour les paiements : Les auteurs développent un mécanisme novateur pour l'échange atomique d'évaluations OPRF liées aux paiements. Cela garantit que le Marchand est payé avant que la Partie ne connaisse le résultat, empêchant ainsi le biais. Cet outil est noté comme ayant un intérêt indépendant pour des applications telles que la limitation de débit pilotée par les paiements.
• Sécurité formelle : Le protocole est prouvé sécurisé dans le modèle basé sur la simulation contre les corruptions statiques, satisfaisant les propriétés de l'atomicité probabiliste (équité, absence de biais et atomicité).
• Implémentation pratique : Une implémentation complète en Rust, testée sur les testnets Bitcoin et Litecoin, et une variante pour le Lightning Network (utilisant des HTLC et des preuves de lien hors chaîne).

4. Résultats et benchmarks

• Déploiement sur testnet : Les auteurs ont exécuté avec succès des échanges atomiques probabilistes inter-chaînes entre les testnets Bitcoin et Litecoin. Un échange gagnant complet impliquait exactement quatre transactions Taproot standards.
• Taille de transaction : Chaque transaction était d'environ 575 Unités de Poids (WU).
• Performance :
  • Bulletproofs : Temps de preuve $\approx 5,6$s, vérification $\approx 0,35$s, taille de preuve $\approx 2,8$Ko (constant quelle que soit la probabilité).
  • Coupe et choix : Le temps de preuve est plus rapide pour de petits $\ell$ (par exemple, $0,27$s pour $\ell=10$) mais s'étend de manière exponentielle avec la taille du domaine. Pour $\ell=16$, la preuve prend $\approx 16$s avec une preuve de 16 Mo.
  • Prototype Lightning : Une variante basée sur HTLC a été implémentée, avec un temps d'exécution en ligne total d'environ 1,30s pour trois tours (incluant la précalcul).
• Coût : Les frais étaient comparables aux échanges atomiques standards (par exemple, 1550 sat pour une transaction de financement de 616WU sur le testnet Bitcoin).

5. Signification et affirmations

L'article affirme que les échanges atomiques probabilistes résolvent une limitation fondamentale des échanges atomiques classiques en permettant des échanges décentralisés sans confiance avec des résultats randomisés. La signification réside dans :

• Permettre de nouveaux cas d'usage : Réaliser la vision de « OP_RAND » sur Bitcoin, permettant des paris, des loteries et des échanges inter-chaînes probabilistes sans maisons de confiance.
• Préserver la vie privée et la fongibilité : En évitant les scripts complexes, l'empreinte sur la chaîne du protocole est indiscernable des échanges atomiques ordinaires, préservant ainsi la vie privée et la fongibilité des actifs.
• Accessibilité : La dépendance à un support de script minimal rend le protocole déployable sur une large gamme de blockchains existantes et de réseaux de couche 2 (comme le Lightning Network, une fois les PTLC actifs ou via des variantes HTLC).
• Sécurité : Le protocole fournit des garanties cryptographiques rigoureuses que le résultat est impartial et suit la probabilité annoncée, même en présence d'acteurs malveillants, sans nécessiter de tiers de confiance.

Les auteurs notent explicitement que, bien que leur protocole prenne en charge les échanges probabilistes asymétriques (une partie paie pour une chance), les échanges probabilistes à deux sens (où les deux parties ont des résultats probabilistes) sont probablement impossibles sur des blockchains minimales en raison d'asymétries inhérentes dans la prise de décision séquentielle, une limitation qu'ils discutent mais ne tentent pas de surmonter.