Merkle木：大規模環境でのトランザクション完全性

Bitcoinのブロックには約2,000件のトランザクションが含まれます。2,000件すべてのトランザクションをダウンロードせずに、トランザクションTが含まれていることを証明するには、コンパクトな証明が必要です。Merkleツリーがこの問題を解決します。証明のサイズは、O(n)件のトランザクションではなく、O(log n)個のハッシュです。

リーフ: 各トランザクションのSHA256d（SHA-256を2回適用したもの）。親: SHA256d(left_child_hash || right_child_hash)。1つのルートハッシュになるまで繰り返します。ノード数が奇数の場合は、最後のノードを複製します。ルートはブロックヘッダーに保存されるMerkleルートです（32バイト）。

import hashlib def sha256d(x): return hashlib.sha256(hashlib.sha256(x).digest()).digest() def merkle_root(txids): if len(txids)%2: txids.append(txids[-1]) while len(txids)>1: txids=[sha256d(txids[i]+txids[i+1]) for i in range(0,len(txids),2)] return txids[0].hex()

トランザクションTが位置iにあることを証明するには、Tのリーフからルートまでの各レベルで、隣接する兄弟ノードのハッシュを提供します（O(log n)個のハッシュ）。検証者は、Tと兄弟ノードのパスからルートを再計算します。計算したルートがブロックヘッダーのMerkleルートと一致すれば、Tが含まれていることが証明されます。

1,024件のトランザクション → Merkle証明 = 10個のハッシュ = 320バイト。完全なブロック = 約1 MB。SPVクライアントは、関心のある各トランザクションについて、80バイトのヘッダーと320バイトのMerkle証明だけをダウンロードします。完全なブロックをダウンロードする場合と比べて、帯域幅を99.97%節約できます。

ツリー内のいずれかのトランザクションが変更されると、そのリーフハッシュが変わり、上位へ伝播してMerkleルートが変わります。変更後のルートは、PoWによって保護されたブロックヘッダーと一致しなくなります。トランザクションからルートを計算することで、あらゆる変更を検出できます。

Ethereumは、trie（Patricia Merkle Trie）によってMerkleツリーを拡張しています。これは、hex-prefixでエンコードされたradix trieで、各ノードがMerkleハッシュ化されます。アカウント残高のstate trie、transaction trie、receipt trieに使用されます。フルノードのデータがなくても、アカウント状態を効率的に証明できます。

Merkle Mountain Range（MMR）は、ログ形式のデータ向けの追記専用Merkle構造です。新しい要素を追加し、2のべき乗サイズのサブツリーのルートであるピークを維持します。Grin/MimbleWimbleやZCashで、追記専用ログに対する効率的でコンパクトな証明に使用されています。

Ethereumのロードマップ（EIP-6800）では、MerkleツリーをVerkleツリーに置き換えます。ハッシュの代わりに、ベクトルコミットメント（KZG多項式コミットメント）を使用します。証明サイズは、MerkleのO(log n)に対してO(1)です。これにより、ステートレスクライアントは完全なtrieを保存せずに状態を検証できます。

Certificate Transparency（RFC 6962）は、追記専用のMerkleログを使用します。各CA発行証明書がリーフになります。包含証明によって、証明書がログに記録されていることを検証します。一貫性証明によって、ログが追記専用であること（削除や挿入がないこと）を検証します。ブラウザベンダーは、このログを通じてSCTを検証します。

Gitのtree（ディレクトリのスナップショット）はMerkleツリーです。各treeノードは、ファイルのblobとサブツリーをハッシュします。コミットハッシュは、コードベース全体の状態を一意に識別します。これが、git checkout を実行すると常にまったく同じファイルが得られる理由です。

1,024個のリーフを持つツリーで包含を証明するには、Merkle証明にいくつのハッシュが必要ですか。

Merkleツリーによって、O(log n)の包含証明が可能になります。BitcoinはブロックヘッダーにMerkleルートを保存し、SPVクライアントは証明を使用します。EthereumはこれをPatricia Merkle Trieへ拡張しています。将来的には、O(1)の証明を実現するためにVerkleツリーがMerkleツリーに置き換わります。次は、Proof of Workのマイニングと難易度です。