Au cours de l'année écoulée ou deux, plusieurs propositions d'extensions proposant des conventions ont été faites pour Bitcoin, mais il y a toujours eu une suspicion parmi les experts selon laquelle les conventions pourraient être possibles sans aucune extension. Les preuves en faveur de cela se présentent sous deux formes : un répertoire en expansion de calculs auparavant considérés comme impossibles (culminant dans le projet BitVM visant à implémenter chaque opcode RISC-V) et une série de "presque-réussites" par lesquelles les développeurs de Bitcoin ont trouvé des moyens par lesquels les conventions auraient été possibles, si ce n'était pour une bizarrerie historique obscure du .

Ethan Heilman, Avihu Levy, Victor Kobolov et moi avons développé un schéma qui prouve que cette suspicion était bien fondée. Notre schéma, Collider*, permet des covenants sur Bitcoin aujourd'hui, sous des hypothèses cryptographiques assez raisonnables et à un coût probable d'environ 50 millions de dollars par transaction (plus quelques travaux de R&D matériels).

Malgré les coûts exorbitants pour utiliser Collider, sa mise en place est très bon marché, et le faire (avec un mécanisme de dépenses ordinaire, en utilisant Taproot pour les séparer) pourrait bien sauver vos pièces au cas où un ordinateur quantique apparaîtrait de nulle part et ferait exploser le .

Sans aucun doute, de nombreux lecteurs, après avoir lu ces affirmations, lèvent un sourcil vers le ciel. À la fin de la lecture de cet article, l'autre sera tout aussi haut.

Conventions

Le contexte de cette discussion, pour ceux qui ne le connaissent pas, est que Bitcoin possède un langage de programmation intégré, appelé Bitcoin, qui est utilisé pour autoriser les dépenses de pièces. Dans ses premiers jours, Bitcoin contenait un ensemble riche de codes opérationnels arithmétiques qui pouvaient être utilisés pour mettre en œuvre des calculs arbitraires. Mais à l'été 2010, Satoshi a désactivé bon nombre de ces codes opérationnels afin de résoudre une série de bugs graves. (Le retour à la version d'avant 2010 de Bitcoin est l'objectif du projet de restauration Great Restoration ; OP_CAT est une proposition moins ambitieuse dans la même direction.) L'idée de contrats - des transactions qui utilisent Bitcoin pour contrôler la quantité et la destination de leurs pièces - n'est apparue que plusieurs années plus tard, et la réalisation que ces codes opérationnels auraient été suffisants pour mettre en œuvre des contrats n'est venue que plus tard. À ce moment-là, la communauté était trop grande et prudente pour simplement "réactiver" les anciens codes opérationnels de la même manière qu'ils avaient été désactivés.

Les covenants sont des constructions hypothétiques qui permettraient aux utilisateurs de contrôler non seulement les conditions dans lesquelles les pièces sont dépensées, mais aussi leur destination. C'est la base de nombreuses constructions potentielles sur Bitcoin, des voûtes et des portefeuilles à limitation de taux, aux nouveaux mécanismes de marché des frais comme les pools de paiement, en passant par des constructions moins recommandables comme la finance distribuée et MEV. Des millions de mots ont été dépensés à débattre de la désirabilité des covenants et de ce qu'ils feraient à la nature de Bitcoin.

Dans cet article, je vais contourner ce débat et soutenir simplement que des alliances sont déjà possibles sur Bitcoin ; que nous découvrirons éventuellement comment elles sont possibles (sans grand coût informatique ou hypothèses cryptographiques douteuses) ; et que notre débat sur de nouvelles extensions à Bitcoin ne devrait pas être présenté comme si des changements individuels constituaient la ligne de démarcation entre un avenir sans alliance ou un avenir covenant-ful pour Bitcoin.

Histoire

Au fil des ans, une tradition s'est développée consistant à trouver des moyens créatifs de faire des choses non triviales même avec des ressources limitées. Le Lightning Network en est une instance, tout comme des idées moins connues telles que les paiements probabilistes ou les primes de collision pour les fonctions de hachage. Des cas marginaux obscurs, tels que le bug SIGHASH_SINGLE ou l'utilisation de la récupération de clé publique pour obtenir un "hash de transaction" dans l'interpréteur, ont été remarqués et explorés, mais personne n'a jamais trouvé de moyen de les rendre utiles. Pendant ce temps, Bitcoin lui-même a évolué pour être plus étroitement défini, fermant beaucoup de ces portes. Par exemple, Segwit a éliminé le bug SIGHASH_SINGLE et a séparé explicitement les données du programme des données de témoin ; Taproot s'est débarrassé de la récupération de clé publique, qui offrait de la flexibilité au détriment de potentiellement miner la sécurité des signatures adaptables ou des multisignatures.

Malgré ces changements, le piratage a continué, tout comme la croyance parmi les irréductibles que, d'une manière ou d'une autre, un cas particulier pourrait être découvert pour permettre la prise en charge des alliances dans Bitcoin. Au début des années 2020, deux développements en particulier ont fait sensation. L'un a été ma propre découverte selon laquelle les alliances basées sur les signatures n'étaient pas mortes avec la récupération de la clé publique, et en particulier, si nous avions même un seul opcode désactivé en arrière -- OP_CAT -- cela serait suffisant pour une construction d'alliance assez efficace. L'autre était BitVM, une nouvelle façon de réaliser de gros calculs dans 01928374656574839201 à travers plusieurs transactions, ce qui a inspiré une quantité énorme de recherche sur les calculs de base au sein de transactions uniques.

Ces deux développements ont suscité beaucoup d'activité et d'excitation autour des alliances, mais ils ont également cristallisé notre réflexion sur les limitations fondamentales de . En particulier, il semblait que les alliances pourraient être impossibles sans de nouveaux codes opérationnels, puisque les données de transaction étaient uniquement alimentées dans par des signatures de 64 octets et des clés publiques de 32 octets, tandis que les codes opérationnels prenant en charge BitVM ne pouvaient fonctionner qu'avec des objets de 4 octets. Ce fossé a été appelé "Small " et "Big ", et trouver un pont entre les deux est devenu synonyme (du moins dans mon esprit) de trouver une construction d'alliance.

Chiffrement fonctionnel et PIPEs

Il a également été observé qu'en faisant un peu de mathématiques lunaires, il pourrait être possible de réaliser des covenants entièrement au sein des signatures elles-mêmes, sans jamais quitter Big . Cette idée a été formulée par Jeremy Rubin dans son article FE'd Up Covenants, qui décrit comment mettre en œuvre des covenants à l'aide d'une primitive cryptographique hypothétique appelée chiffrement fonctionnel. Des mois plus tard, Misha Komorov a proposé un schéma spécifique appelé PIPEs qui semble rendre cette idée hypothétique une réalité.

Il s'agit d'un développement passionnant, bien qu'il souffre de deux limitations majeures : l'une est qu'il nécessite une configuration de confiance, ce qui signifie que la personne qui crée le pacte peut contourner ses règles. (C'est bien pour quelque chose comme les coffres-forts, dans lesquels le propriétaire des pièces peut être considéré comme digne de confiance pour ne pas compromettre sa propre sécurité ; mais ce n'est pas bien pour quelque chose comme les pools de paiement où les pièces dans le pacte ne sont pas détenues par le créateur du pacte.) L'autre limitation est qu'il implique une cryptographie de pointe avec des propriétés de sécurité peu claires. Cette dernière limitation disparaîtra avec plus de recherche, mais la configuration de confiance est inhérente à l'approche de chiffrement fonctionnel.

Collider

Cet aperçu nous amène à la situation actuelle : nous aimerions trouver un moyen de mettre en œuvre des pactes en utilisant la forme existante de Bitcoin, et nous croyons que la manière de le faire est de trouver une sorte de pont entre le "Big " des signatures de transaction et le "Small " des calculs arbitraires. Il semble qu'aucun code opératoire ne puisse former directement ce pont (voir l'annexe A dans notre article pour une classification de tous les codes opératoires en termes de leur taille d'entrée et de sortie). Un pont, s'il existait, serait une sorte de construction qui prendrait un seul grand objet et démontrerait qu'il était exactement égal à la concaténation de plusieurs petits objets. Il semble, sur la base de notre classification des codes opératoires, que cela est impossible.

Cependant, en cryptographie, nous affaiblissons souvent les notions telles que « exactement égal », utilisant plutôt des notions telles que « indistinguables computationnellement » ou « indistinguables statistiquement », et évitons ainsi les résultats impossibles. Peut-être, en utilisant les constructions cryptographiques intégrées de Big - hachages et signatures de courbes elliptiques - et en les reflétant à l'aide des constructions BitVM en Small, pourrions-nous trouver un moyen de montrer qu'un grand objet est « indistinguable computationnellement » d'une série de petits objets ? Avec Collider, c'est exactement ce que nous avons fait.

Que signifie tout cela? Eh bien, rappelez-vous la prime de collision de la fonction de hachage que nous avons mentionnée plus tôt. La prémisse de cette prime est que quiconque peut "entrer en collision" avec une fonction de hachage, en fournissant deux entrées ayant le même résultat de hachage, peut prouver en Big qu'il l'a fait, et ainsi revendiquer la prime. Puisque l'espace d'entrée d'une fonction de hachage est beaucoup plus grand (toutes les chaînes de caractères jusqu'à 520 octets de taille) que l'espace de sortie (chaînes de caractères exactement 32 octets de taille), mathématiquement parlant, il doit y avoir de nombreuses collisions. Et pourtant, à l'exception de SHA1, personne n'a trouvé de moyen plus rapide de trouver ces collisions que d'appeler simplement la fonction de hachage encore et encore et de vérifier si le résultat correspond à celui d'une tentative antérieure.

Cela signifie que, en moyenne, pour une fonction de hachage de 160 bits comme SHA1 ou RIPEMD160, un utilisateur devra effectuer au moins 2^80 opérations, soit un million de millions de millions de millions d'itérations, pour trouver une collision. (Dans le cas de SHA1, il existe un raccourci si l'utilisateur est en mesure d'utiliser des entrées d'une forme particulière; mais notre construction interdit cela, donc pour nos besoins, nous pouvons ignorer cette attaque.) Cela suppose que l'utilisateur dispose d'une quantité de mémoire effectivement infinie à utiliser; avec des hypothèses plus réalistes, nous devons ajouter un autre facteur d'environ cent.

Si nous imaginons que SHA1 et RIPEMD160 peuvent être calculés aussi efficacement que les ASIC Bitcoin calculent SHA256, alors le coût d'un tel calcul serait à peu près le même que 200 blocs, soit environ 625 BTC (46 millions de dollars). C'est beaucoup d'argent, mais de nombreuses personnes ont accès à une telle somme, donc c'est possible.

Pour trouver une collision triple, ou trois entrées qui équivalent à la même chose, il faudrait environ 2^110 travaux, même avec des hypothèses très généreuses concernant l'accès à la mémoire. Pour obtenir ce nombre, nous devons ajouter un autre facteur de 16 millions à notre coût -- portant notre total à plus de 700 billions de dollars. C'est aussi beaucoup d'argent, et à quoi personne n'a accès aujourd'hui.

L'essentiel de notre construction est le suivant : pour prouver qu'une série de petits objets est équivalente à un seul grand objet, nous trouvons d'abord une collision de hachage entre notre objet cible (que nous supposons pouvoir être rerandomisé d'une manière ou d'une autre, sinon nous ferions une recherche de "deuxième pré-image" plutôt qu'une recherche de collision, ce qui serait beaucoup plus difficile) et un objet de test d'équivalence. Ces objets de test d'équivalence sont construits de manière à ce qu'ils puissent être facilement manipulés à la fois en Big et en Small.

Notre construction vérifie ensuite, en Bitcoin, que notre grand objet entre en collision avec notre testeur d'équivalence (en utilisant exactement les mêmes méthodes que dans la prime de collision de hash) et que notre série de petits objets entre en collision avec le testeur d'équivalence (en utilisant des constructions complexes partiellement empruntées au projet BitVM, et décrites en détail dans l'article). Si ces vérifications réussissent, alors soit nos petits et grands objets étaient les mêmes, soit l'utilisateur a trouvé une triple-collision : deux objets différents qui entrent tous deux en collision avec le testeur. Par notre argument ci-dessus, cela est impossible.

Conclusion

La construction d'une passerelle entre Small et Big est la partie la plus difficile de notre construction de covenant. Pour passer de cette passerelle à un covenant réel, il y a quelques étapes supplémentaires, qui sont comparativement faciles. En particulier, un covenant demande d'abord à l'utilisateur de signer la transaction à l'aide de la clé spéciale "clé de générateur", que nous pouvons vérifier à l'aide de l'opcode OP_CHECKSIG. À l'aide de la passerelle, nous divisons cette signature en tronçons de 4 octets. Nous vérifions ensuite que son nonce était également égal à la clé de générateur, ce qui est facile à faire une fois que la signature a été divisée. Enfin, nous utilisons des techniques issues de l'astuce de Schnorr pour extraire les données de transaction de la signature, qui peuvent ensuite être contraintes de la manière souhaitée par le covenant.

Il y a quelques autres choses que nous pouvons faire : l'appendice C décrit une construction de signature d'anneau qui permettrait aux pièces d'être signées par l'une d'un ensemble de clés publiques, sans révéler laquelle a été utilisée. Dans ce cas, nous utilisons le bridge pour diviser la clé publique, plutôt que la signature. Ce faisant, cela nous donne une amélioration significative de l'efficacité par rapport à la construction du pacte, pour des raisons techniques liées à Taproot et détaillées dans le document.

Une dernière application à laquelle je veux attirer l'attention, brièvement discutée dans la section 7.2 du document, est que nous pouvons utiliser notre construction de convention pour extraire le hachage de la transaction à partir d'une signature Schnorr, puis simplement resigner le hachage en utilisant une signature Lamport.

Pourquoi ferions-nous cela? Comme argumenté dans le lien ci-dessus, signer de la manière de Lamport rend la signature sécurisée quantiquement sur les données de transaction; si cette construction était le seul moyen de signer pour certaines pièces, elles seraient à l'abri du vol par un ordinateur quantique.

Bien sûr, étant donné que notre construction nécessite des dizaines de millions de dollars pour être utilisée, personne ne ferait de cette construction le seul moyen de signer pour leurs pièces. Mais rien n'empêche quelqu'un d'ajouter cette construction à leurs pièces, en plus de leurs méthodes existantes non sécurisées quantiquement de dépenses.

Ensuite, si nous nous réveillions demain pour découvrir que des ordinateurs quantiques bon marché existaient et étaient capables de casser les signatures Bitcoin, nous pourrions proposer une mise à jour logicielle d'urgence qui désactiverait toutes les signatures de courbe elliptique, y compris les dépenses de clé Taproot et l'opcode OP_CHECKSIG. Cela gèlerait effectivement les fonds de tout le monde ; mais si l'alternative était que les fonds de tout le monde puissent être librement volés, cela ne ferait peut-être aucune différence. Si cette mise à jour logicielle désactivant les signatures permettait l'opcode OP_CHECKSIG lorsqu'il est appelé avec la clé du générateur (de telles signatures ne fournissent de toute façon aucune sécurité et ne sont utiles que comme élément de base pour des constructions complexes comme la nôtre), alors les utilisateurs de notre construction de signature Lamport pourraient continuer à dépenser librement leurs fonds, sans craindre la saisie ou le vol.

Bien sûr, ils devraient dépenser des dizaines de millions de dollars pour le faire, mais c'est bien mieux que "impossible"! Et nous prévoyons et espérons voir ce coût Goutte de manière spectaculaire, alors que les gens s'appuient sur nos recherches.

Ceci est un article invité d'Andrew Poelstra. Les opinions exprimées sont entièrement les leurs et ne reflètent pas nécessairement celles de BTC Inc ou de Bitcoin Magazine.