マークルツリー — 定義と意味

マークルツリーはデータのハッシュを木構造に配置し、頂点のマークルルートで対象集合を要約します。親ノードは規定の規則で子ノードから計算します。葉を変更すると、通常はルートまでの経路上のハッシュも変わります。

一つの項目を検証する

包含証明では集合全体ではなく、その経路の再計算に必要な隣接ハッシュを提示します。葉が八つある平衡二分木で一つの葉を証明するには、通常は三つの兄弟ハッシュと位置情報が必要です。検証者には対象項目またはそのハッシュと、信頼できるルートも必要です。

ビットコインは各ブロックヘッダーのマークルルートに取引IDの集合をコミットします。構築規則では取引順序、ペアのハッシュ化、ある階層の項目数が奇数の場合の複製方法を定めています。他のシステムでは異なる木構造や符号化規則を採用できます。

有効な証明は、ハッシュの安全性を前提として、項目が参照ルートの表す集合に含まれることを示します。取引の有効性、現在の未使用状態、チェーンのファイナリティを単独では証明しません。また、ルートから全元データが分かるわけでもありません。完全な検証には、そのデータを別途入手できる必要があります。