OP_CAT を使用したマークル ツリーの構築と検証

シリーズ #1 に続いて、OP_CAT を使用してマークル ツリーを構築および検証する方法を示します。ビットコインでは、マークル ツリーは、データの検証、同期、ブロックチェーンのトランザクションとブロックを効果的にリンクするためのデータ構造として利用されます。

This post was first published on Medium.

この投稿は最初に Medium で公開されました。

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

シリーズ #1 に続いて、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.

ビットコインでは、データの検証、ブロックチェーンの同期、トランザクションとブロックの効率的なリンクのためのデータ構造としてマークル ツリーが使用されます。 2 つのスタック変数の連結を可能にする OP_CAT オペコードは、公開鍵の SHA256 ハッシュとともに使用して、ビットコイン スクリプト内のマークル ツリー検証プロセスを効率化できます。 OP_CAT では、マークル ツリーの構築と検証の基本操作に 2 つの値の連結とハッシュ化が含まれるため、マークル ツリー内のエントリの作成とオープンが独自に可能になります。

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

マークル ツリーには多くのアプリケーションがあります。以下にいくつかの顕著な例を示します。

Merkle proof

マークル証明

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.

マークル証明は、ブロックチェーン全体をダウンロードすることなく、特定のトランザクションがマークル ツリーに含まれていることを検証するために使用される暗号化手法です。これは、軽量クライアントとデータ検証の効率の向上に特に役立ちます。

Tree signature

木の署名

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.

ツリー署名は、ツリー構造、特にマークル ツリーを使用してデジタル署名のセキュリティと効率を向上させる暗号化方法です。このアプローチは、通常のマルチシグと比較して、メッセージまたはメッセージのセットが特定の鍵で署名されていることを示す、よりコンパクトでプライベートな証明を生成するために使用されます。

Zero-Knowledge Proof

ゼロ知識証明

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 (Succict Transparent Arguments of Knowledge) は、ゼロ知識証明システムの一種です。 STARK は、計算自体に関する機密情報を明らかにすることなく、証明者が検証者に計算の正当性を証明できるように設計されています。 OP_CAT がビットコインに追加された場合、ビットコイン スクリプトでの STARK 検証器の実装が可能になる可能性があり、その作業はすでに進行中です。これにより、ビットコインネットワーク上で安全かつプライベートなトランザクションが可能になります。 SNARK のようなペアリングベースの証明システムと比較して、STARK はよりビットコインに優しいと考えられています。

Implementation

実装

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.

sCrypt を使用したマークル ツリーの実装は簡単です。次のコードは、リーフとそのマークル パスを指定して、マークル ツリーのルート ハッシュを計算します。通常、マークル証明の検証に使用されます。

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

完全なコードは https://github.com/sCrypt-Inc/scrypt-btc-merkle にあります。

A single run results in the following transactions:

1 回の実行により、次のトランザクションが発生します。

Check the transaction on Mempool

Mempoolでトランザクションを確認する

Check the transaction on Mempool

Mempoolでトランザクションを確認する

Script versions

スクリプトのバージョン

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.

以下のような、裸のスクリプトでの代替実装があります。マークル ツリーの実装に sCrypt を使用する主な利点の 1 つは、可読性と保守性です。多くの場合、スクリプトは読みにくく、作業するのが非常に困難です。

OP_EXISTS

OP_EXISTS

Plz tell me you had a compiler to generate that

それを生成するコンパイラがあったのか教えてください

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

— ジェリー – ビットコインベイ (@Lightswarm) 2024 年 3 月 1 日

Stay tuned for more OP_CAT use cases.

OP_CAT のさらなる使用例にご期待ください。

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

見る: sCrypt ハッカソンの学生がブロックチェーンにはそれだけではないことに気づく

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

ブロックチェーンは初めてですか? CoinGeekの初心者向けブロックチェーンセクションにアクセスして、ブロックチェーンテクノロジーについて詳しく学ぶための究極のリソースガイドをご覧ください。