マーチェルツリー: ブロックチェーンがノートをすべて記憶する仕組み

Annkkitaaaによるオリジナル研究

数百万のコミットメントを一つの小さな指紋で要約する

シリーズ: Zcashから第一原理 . 第4回. マーチェルツリー
対象読者: 新規ユーザー。第3回（ハッシュとコミットメント）に続きます。指紋とコミットメントの概念がわかれば、準備は整っています。 得られるもの: マーチェルツリーについて直感的で正しいイメージを獲得し、特定のアイテムを明らかにせずにメンバーシップを証明する方法、そしてそれがZcashのノートコミットメントツリーになる仕組みを理解します。

第0回では、「公開掲示板」としてすべてのノートが作成され、かつ常に増えるものについて説明しました。今や、そこに貼り付けられているのはコミットメント(第3回)、つまり封筒です。しかし現実の掲示板には数百億個のそれがあります。ネットワークはそれをどのように保存し、検証し、あなたがその封筒が掲示板にあることを証明するのに、それを指摘することなく行うのでしょうか？答えはコンピュータ科学で最も洗練された構造の一つであるマーチェルツリーです。

1. なぜあなたが関心を持つべきか？

巨大な公開リストにコミットメントがあると同時に2つの問題が現れます。

問題1: スケールでの整合性。 リストに3億件のエントリがある場合、誰もが一つも秘密裏に変更されていないことを確認するにはどうすればよいでしょうか？毎回すべての3億件を再チェックすることは不可能です。

問題2: 暗号化されたメンバーシップ。 ノートを支払うために（第0回）、あなたのコミットメントが実際に掲示板にあることを証明する必要があります。しかし、それを指摘して「それは4,201,337番目のエントリです！」と述べると、あなたは匿名性を失ってしまいます。あなたは、「私の封筒はこの掲示板のどこかにあります」と証明する必要があり、どの封筒であるかは明らかにできません。

マーチェルツリーは両方の問題を同時に解決します。それは全体のリストを単一の指紋に圧縮し、位置情報を隠した小さな証明でメンバーシップを証明できるようにします。

2. 直感: 指紋のトーナメント

淘汰戦のブラケットを想像してください。ただし、プレイヤーが進む代わりに指紋が組み合わさるのです。

• 最下部では、各データは独自の指紋（第3回で説明したハッシュ）を持ちます。これらは葉です。
• それらをペアにして、それぞれのペアの2つの指紋を一緒にハッシュして1つの親指紋にします。
• 親たちもペアにして、そのペアを一緒にハッシュし、同様に続けます。
• 最終的に単一の指紋が上部に達するまで続ける。そのチャンピオンはマーチェルルートです。

最も重要な性質はアバランチ効果（第3回）から直接導かれます：

ルートは下にあるすべてのものを指紋としています。 どんな葉を1ビットでも変更すると、その指紋が変わり、親も変わり、さらに上の親も変わり、最終的にルートも変わります。つまり、小さなルート値一つで全体リストの整合性を証明できます。これにより問題1は解決します。

3. 実際のツリー: 完全に計算された例

A, B, C, Dという葉（読みやすさのためにディジェストが切り取られています）を使って、上の4つの葉を持つツリーを実際に構築してみましょう：

hA = 559aead08264...     hB = df7e70e50215...
hC = 6b23c0d5f35d...     hD = 3f39d5c348e5...

hAB = H(hA , hB) = 63956f0ce48e...
hCD = H(hC , hD) = 98a2fbfddbc7...

ROOT = H(hAB , hCD) = 1b3faa3fcc5e...

すべては「何かをハッシュし、そのハッシュのペアをハッシュする」だけです。第3回よりも何が特別かというと、ツリー構造に並べただけです。

4. 革新的な部分: 位置情報を明らかにせずにメンバーシップを証明する

今や問題2。あなたは、ルートだけを知っている人に葉Cがツリーにあることを証明したいとします。あなたは全体のツリーを渡すことはしません。代わりに、Cからルートへと登るのに必要な指紋のみを渡します。それは認証パス(またはマーチェル証明)と呼ばれます：

Cがツリーにあることを証明するには以下のものを提供してください：

• その兄弟ノードhD、および
• その叔父ノードhAB。

検証者はルートだけを知っていても、再計算して登ることができます：

step 1:  H(hC , hD)        = hCD       (Cとその兄弟を組み合わせる)
step 2:  H(hAB , hCD)      = ROOT?     (叔父と組み合わせる)

実際に計算すると、1b3faa3fcc5e...という値が得られ、ルートと一致します。葉はツリーに存在することが証明されます。

この方法の強さを二つ挙げます：

• 非常に小さい。 4つの葉に対して2つのハッシュを提供しました。n個の葉を持つツリーでは、約log_2(n)のハッシュだけを提供します。10億の葉がある場合でも、約30のハッシュで済みます。ツリーが巨大になっても証明はわずかに成長するだけです。
• プライバシーの種。 証明はあなたの葉がどこかにあることを示します。このチェックがゼロ知識証明(第5回)内で行われる場合、パス自体も隠れるため、「私のノートはツリーに存在する」と証明しつつ、ノートそのものや位置を明らかにしません。これにより問題2は完全に解決します。

5. マーチェルツリーからZcashのノートコミットメントツリーへ

今や、第0回で述べた「公開掲示板」が実際に何であるかを正確に説明できます：

ノートコミットメントツリーは、葉がノートコミットメントであるマーチェルツリーです。世界のどこでもノートが作成されるたびに、そのコミットメントが次の葉として追加され、ルートは更新されます。

いくつかの実際の詳細：

• 常に成長する。 葉は追加され、削除されることはありません。これはインクリメンタルマーチェルツリーと呼ばれます。（第0回で述べた「掲示板が何かを破壊しない」に一致します。）
• ルートはアンカーと呼ばれる。 あなたが支払う際、あなたのトランザクションは最近のアンカーを参照し、ゼロ知識証明内で、あなたのノートコミットメントがそのルートを持つツリーにあることを証明します。
• 固定された深さ。 Zcashのシールド付きツリーの深さは32で、最大2^(32)（40億以上）のノートを保持できます。
• ゼロ知識に最適なハッシュ。 ツリーはSHA-256で構築されていません。Saplingではペドセンハッシュを使用し、Orchardではシンセミラ（どちらも第3回）を使用してツリーをハッシュします。これにより、回路内でメンバーシップの証明が安価になります。

ツリーが処理しないこと: 二重支払い

ツリーはノートが存在することを証明します。それ自体では、同じノートを二回使うことを防ぐことはできません。その役割は第0回のヌリファイアーセットにあります：「無効トークン」の別々なコレクションです。あなたが支払う際、ノートのヌリファイアーを公開し、ネットワークは以前に見たことのあるヌリファイアーを拒否します。

したがって、この2つの公開構造は補完的な役割を果たし、それらを分離することで、ノートの誕生と死をリンクから切り離しています：

6. 正直な免責事項

通常通りの簡略化です。実際のインクリメンタルマーチェルツリーは「フロンティア」ノードを追跡し、すべてを再構築することなくルートを更新できます；ネットワークは最新のアンカーだけでなく、最近のアンカーのウィンドウを保持しており、新しいブロックがウォレットに破壊しないようにします；空の葉は定義されたパディング値を使用します。また、二進ツリーは整った2のべき乗で描画しました。これらすべては直感を変えません：コミットメントの葉、ペアごとにハッシュされ、一つのルートに至り、短いメンバーシップ証明を持つ。正確な記帳はプロトコル記事に戻ります。

7. 要約

• マーチェルツリーはデータを葉にハッシュし、それからペアごとに上向きにハッシュして、最終的に単一のルートが残る。
• アバランチ効果のおかげで、ルートは全体リストの指紋です：1つの葉を変更するとルートも変わります。小さな値一つで巨大なデータセットを証明できます。
• **メンバーシップ証明（認証パス）とは、ルートへの登り道に沿った兄弟ノードのハッシュ、つまり約log_2(n)**のハッシュであり、億単位の葉でも証明は小さく保たれます。
• ゼロ知識証明内で行われると、そのメンバーシップチェックはどの葉を指しているかを隠し、「私のノートはツリーに存在する」と証明しつつ、ノートや位置を明らかにしません。
• Zcashのノートコミットメントツリーはインクリメンタルなマーチェルツリーで、深さ32、そのルートはアンカーであり；Saplingではペドセン、Orchardではシンセミラを使用してハッシュされます。
• ツリーは存在性を証明します；別途のヌリファイアーセットが二重支払いを防ぎます。それらを分離することで、ノートの誕生と死のリンクが切断されます。

用語集

FAQ

なぜツリーではなく単なるハッシュリストを使うのか？ 平らなリストではメンバーシップを証明するためにはすべてのエントリを開示または処理しなければならない。ツリーは対数サイズの証明と、整合性のために単一のルートを提供します。

検証者は全体のツリーが必要か？ いいえ。検証者はルートに加えてあなたの短い認証パスだけが必要です。それが全部の目的です。

なぜ深さ32なのか？ それは約40億ノートを保持できる上限を提供し、メンバーシップ証明（およびその回路内でのコスト）を固定かつ管理可能なサイズに保つためです。

もしルートが新しいノートごとに変化するなら、古い証明はどのようにして有効なままなのか？ ネットワークは最近のルート（アンカー）のウィンドウを記憶しており、わずかに古いアンカーに対して作成された証明も検証されます。プロトコル記事でこの点が正確に説明されています。

直感テスト

4つの葉を持つツリーにおいて、攻撃者が秘密裏に葉Cを別の値と交換し、公開されたルートは変更せずに残した場合、何が彼らにとって問題になり、なぜ静かに修正できないのか？（答えは下記。）

次のステップ

第5回. ゼロ知識証明: 高潮。これまではノート、コミットメント、ツリーを構築し、「ゼロ知識で証明する」と繰り返してきました。第5回はようやく、あなたが述べた文の真偽を証明し、あなたのノートがツリーに存在すること、あなたのヌリファイアーが正しいこと、資金のバランスが取れていることを証明しつつ、それらを一切明らかにしない方法を説明します。

ZecHub（https://zechub.org）向けの Zcash from First Principles シリーズの一部。CC BY-SA 4.0ライセンス。