本文へスキップ
ecdsa.com

マークルツリー

各内部ノードが 2 つの子のハッシュを計算する二分ハッシュ木で、1 つのルートハッシュがすべてのリーフに対するコミットメントになるため、要素が含まれていることや追記のみで成長していることを対数サイズの証明で示せます。
別表記hash treeMerkle rootinclusion proofconsistency proof

Certificate Transparency(RFC 6962 §2.1、RFC 9162 §2.1)は、ほとんどの透明性ログが使うハッシュの計算方法を定めています。リーフは SHA-256(0x00 ‖ data)、ノードは SHA-256(0x01 ‖ left ‖ right) で、このプレフィックスにより、リーフを内部ノードと偽ることができなくなります。1,000,000 件のエントリから 1 件を示す包含証明には、約 20 個のハッシュが必要です。一貫性証明は、新しいツリーが履歴を書き換えずに古いツリーを拡張していることを示します。

この構造は、CT ログ、Sigstore の Rekor、Go のチェックサムデータベース(sum.golang.org)、Bitcoin のトランザクションルート(構成の異なる二重 SHA-256 を使い、重複リーフに関する既知の癖があります)、Git と大半のコンテンツアドレス型ストレージ、そしてハッシュベース署名の XMSS、LMS、SLH-DSA の基盤になっています。

透明性ログは署名付きツリーヘッド(チェックポイント)を公開し、ウィットネスがそれに連署します。そのため、クライアントごとに異なる履歴を見せるログを検出できます。

規格と参考文献

すべての用語