Construction et vérification d'arbres Merkle à l'aide de OP_CAT

Suite à notre série n°1, nous montrons comment construire et vérifier des arbres Merkle à l'aide de OP_CAT. Dans Bitcoin, les arbres Merkle sont utilisés comme structure de données pour vérifier les données, la synchronisation et relier efficacement les transactions et les blocs de la blockchain.

This post was first published on Medium.

Cet article a été publié pour la première fois sur Medium.

Following our series #1, we demonstrate how to construct and verify Merkle trees using OP_CAT.

Suite à notre série n°1, nous montrons comment construire et vérifier des arbres Merkle à l'aide de OP_CAT.

In Bitcoin, Merkle trees are used as the data structure for verifying data, synchronizing the blockchain, and efficiently linking transactions and blocks together. The OP_CAT opcode, which allows for the concatenation of two stack variables, can be used with SHA256 hashes of public keys to streamline the Merkle tree verification process within Bitcoin Script. OP_CAT uniquely allows for the creation and opening of entries in Merkle trees, as the fundamental operation for building and verifying Merkle trees involves concatenating two values and then hashing them.

Dans Bitcoin, les arbres Merkle sont utilisés comme structure de données pour vérifier les données, synchroniser la blockchain et relier efficacement les transactions et les blocs entre eux. L'opcode OP_CAT, qui permet la concaténation de deux variables de pile, peut être utilisé avec les hachages SHA256 de clés publiques pour rationaliser le processus de vérification de l'arborescence Merkle dans Bitcoin Script. OP_CAT permet uniquement la création et l'ouverture d'entrées dans les arbres Merkle, car l'opération fondamentale de construction et de vérification des arbres Merkle implique la concaténation de deux valeurs, puis leur hachage.

There are many applications for Merkle trees. Here are a few prominent examples:

Il existe de nombreuses applications pour les arbres Merkle. Voici quelques exemples marquants :

Merkle proof

Preuve Merkle

A Merkle proof is a cryptographic method used to verify that a particular transaction is included in a Merkle tree without having to download the entire blockchain. This is especially useful for lightweight clients and improving the efficiency of data verification.

Une preuve Merkle est une méthode cryptographique utilisée pour vérifier qu'une transaction particulière est incluse dans un arbre Merkle sans avoir à télécharger l'intégralité de la blockchain. Ceci est particulièrement utile pour les clients légers et améliore l’efficacité de la vérification des données.

Tree signature

Signature de l'arbre

A tree signature is a cryptographic method that improves the security and efficiency of digital signatures using tree structures, especially Merkle trees. This approach is used to generate a more compact and private proof that a message or set of messages has been signed by a particular key, compared to regular Multisig.

Une signature arborescente est une méthode cryptographique qui améliore la sécurité et l'efficacité des signatures numériques à l'aide de structures arborescentes, notamment les arbres Merkle. Cette approche est utilisée pour générer une preuve plus compacte et privée qu'un message ou un ensemble de messages a été signé par une clé particulière, par rapport au Multisig classique.

Zero-Knowledge Proof

Preuve de connaissance zéro

STARK (Succinct Transparent Arguments of Knowledge) is a type of zero-knowledge proof system. STARKs are designed to allow a prover to prove the validity of a computation to a verifier without revealing any sensitive information about the computation itself. If OP_CAT were to be added to Bitcoin, it could potentially enable the implementation of a STARK verifier in Bitcoin Script, with work already underway on this. This would allow for secure and private transactions on the Bitcoin network. Compared to pairing-based proof systems like SNARK, STARK is considered to be more Bitcoin-friendly.

STARK (Succinct Transparent Arguments of Knowledge) est un type de système de preuve sans connaissance. Les STARK sont conçus pour permettre à un prouveur de prouver la validité d'un calcul à un vérificateur sans révéler aucune information sensible sur le calcul lui-même. Si OP_CAT devait être ajouté à Bitcoin, cela pourrait potentiellement permettre la mise en œuvre d'un vérificateur STARK dans Bitcoin Script, des travaux étant déjà en cours à ce sujet. Cela permettrait des transactions sécurisées et privées sur le réseau Bitcoin. Comparé aux systèmes de preuve basés sur le couplage comme SNARK, STARK est considéré comme plus convivial pour Bitcoin.

Implementation

Mise en œuvre

The implementation of the Merkle tree using sCrypt is straightforward. The following code calculates the root hash of a merkle tree, given a leaf and its merkle path, typically used in verifying a merkle proof.

L'implémentation de l'arborescence Merkle à l'aide de sCrypt est simple. Le code suivant calcule le hachage racine d'un arbre Merkle, en fonction d'une feuille et de son chemin Merkle, généralement utilisé pour vérifier une preuve Merkle.

Full code is at https://github.com/sCrypt-Inc/scrypt-btc-merkle.

Le code complet se trouve sur https://github.com/sCrypt-Inc/scrypt-btc-merkle.

A single run results in the following transactions:

Une seule exécution entraîne les transactions suivantes :

Check the transaction on Mempool

Vérifier la transaction sur Mempool

Check the transaction on Mempool

Vérifier la transaction sur Mempool

Script versions

Versions de scripts

There are alternative implementations in bare scripts, like the one below. One major benefit of using sCrypt for implementing merkle trees is its readability and maintainability. Scripts are often very difficult to read and work on.

Il existe des implémentations alternatives dans des scripts nus, comme celle ci-dessous. L'un des avantages majeurs de l'utilisation de sCrypt pour implémenter des arbres Merkle est sa lisibilité et sa maintenabilité. Les scripts sont souvent très difficiles à lire et à travailler.

OP_EXISTS

OP_EXISTE

Plz tell me you had a compiler to generate that

S'il vous plaît, dites-moi que vous aviez un compilateur pour générer ça

— Jerry – Bitcoin Bay (@Lightswarm) March 1, 2024

– Jerry – Bitcoin Bay (@Lightswarm) 1er mars 2024

Stay tuned for more OP_CAT use cases.

Restez à l'écoute pour plus de cas d'utilisation d'OP_CAT.

Watch: sCrypt Hackathon students realize there’s more to blockchain

Regarder : les étudiants du sCrypt Hackathon se rendent compte qu'il y a plus dans la blockchain

New to blockchain? Visit CoinGeek’s Blockchain for Beginners section, the ultimate resource guide to learn more about blockchain technology.

Nouveau sur la blockchain ? Visitez la section Blockchain pour débutants de CoinGeek, le guide de ressources ultime pour en savoir plus sur la technologie blockchain.