一般面接：Merkle 包含証明の検証

プロンプトと適用範囲

これは暗号データ構造およびプロトコル実装の問題です。Merkle 包含証明は、ツリー全体ではなく、対象のリーフをルートに接続するために必要な兄弟ノードのみを送信します。RFC 9162 ではリーフノードと内部ノードのハッシュをドメイン分離し、各レベルで左右を決定する際に検証器が leaf_index と tree_size を使用することを求めています。クライアントは信頼できるチャネルを通じて root_hash を取得したと仮定します。検証器自体はその信頼を確立しません。

面接官が見ているポイント

リーフハッシュ、内部ハッシュ、およびパス方向情報の識別。
境界およびパスの検証に対する leaf_index と tree_size の使用。
リーフのバイト列が内部ノードの入力と混同されないようにするためのドメイン分離の理解。
O(log n) の証明サイズと検証時間、および信頼できるルートの境界の説明。

最初に行うべき確認事項

ツリー仕様を確認します。RFC 9162 の可変サイズツリーか、固定の完全二分木か。リーフの正規化。ハッシュアルゴリズムとプレフィックス定数。そしてパスがリーフからルートの順序になっているかどうかです。また、追記専用（append-only）の一貫性証明や署名が必要なのか、それとも単一の包含証明のみでよいのかも確認してください。これらの規約がなければ、ハッシュのリストからルートを一意に特定することはできません。

30秒での回答

0 <= leaf_index < tree_size を確認し、パス長に上限を設定します。リーフを HASH(0x00 || leaf_bytes) として正規化し、fn = leaf_index、sn = tree_size - 1、および現在のハッシュ r を保持します。各レベルで、fn の下位ビットまたは条件 fn == sn を使用して兄弟ノードが左か右かを決定し、内部プレフィックス 0x01 を付けてハッシュ化し、両方のインデックスをシフトします。sn == 0 かつ r == root_hash の場合にのみ成功と判定します。

ステップごとの解決策

1. 入力規約とドメイン分離の確定

検証器には、バージョン管理されたハッシュアルゴリズム、リーフエンコーディング、パスの順序、およびツリーサイズのセマンティクスが必要です。RFC 9162 の Merkle Tree Hash では、リーフに 0x00、内部ノードに 0x01 を使用し、同じバイト列が 2 つの役割で解釈されるのを防ぎます。ドメイン分離なしで leaf || sibling をハッシュ化したり、呼び出し元がプレフィックスを勝手に置き換えたりできないようにしてください。

2. 境界およびリソースチェックの先行実行

leaf_index >= tree_size は失敗しなければなりません。空のツリーには有効なリーフが存在しません。パスに上限（例：ceil(log2(tree_size)) + 1）を設定し、各ハッシュに固定のバイト長を要求します。悪意のある証明が無制限にリソースを消費しないよう、整数オーバーフロー、負のエンコーディング、重複パース、過大なパスを拒否します。短いパスが自動的に有効になるわけではありません。最終状態が 1 つのルートに収束する必要があります。

3. レベルごとのルート再構築

RFC 9162 の可変サイズツリーでは、パリティだけでは不十分です。境界条件 fn == sn によって連結方向が変わります。現在のノードをその親にマッピングするために、各レベルの後に fn と sn の両方をシフトします。擬似コード：

text

verify(leaf, leafIndex, treeSize, path, expectedRoot):
  if treeSize <= 0 or leafIndex < 0 or leafIndex >= treeSize: return false
  r = HASH(0x00 || leaf)
  fn = leafIndex
  sn = treeSize - 1
  for sibling in path:
    if sn == 0: return false
    if (fn & 1) == 1 or fn == sn:
      r = HASH(0x01 || sibling || r)
    else:
      r = HASH(0x01 || r || sibling)
    fn = fn >> 1
    sn = sn >> 1
  return sn == 0 and r == expectedRoot

4. パスとツリーサイズの一致確認

証明の tree_size は方向の計算に関与しており、単なる装飾的なログのメタデータではありません。パスを使い切ったとき、sn はゼロでなければなりません。正の値のままであれば証明がルートに到達していません。sn がすでにゼロなのに兄弟ノードが残っている場合は証明を拒否します。固定ツリーの実装では異なるルールを使用する場合がありますが、その生成器と検証器は RFC 9162 のパスと混用せず、同一のツリー規約を共有する必要があります。

5. 計算量、通信、および信頼

平衡ツリーは通常 O(log n) 個の兄弟ハッシュを持ちます。検証には O(log n) 回のハッシュ操作とパス以外の O(1) の状態が必要で、通信量は O(log n * hashSize) です。証明はリーフを提供されたルートに束縛するだけです。ルートが信頼できないレスポンスから取得された場合、攻撃者はルートと証明の両方を置き換えることができます。本番のプロトコルでは、署名、信頼できるログヘッド、または認証されたトランスポートを使用してルートとツリーサイズを保護します。

模範解答

私なら検証器をバージョン管理されたツリー仕様にバインドします。まず tree_size > 0、0 <= leaf_index < tree_size、ハッシュ長、およびパスの許容量をチェックし、次に r = HASH(0x00 || leaf) を計算します。fn = leaf_index と sn = tree_size - 1 を保持し、各レベルで fn が奇数または fn == sn の場合は兄弟ノードを左に、それ以外の場合は右に配置し、HASH(0x01 || left || right) で更新します。両方のインデックスをシフトします。最後は sn == 0 であり、信頼できるルートと一致する場合にのみ成功とします。証明サイズと検証コストは O(log n) であり、プロトコルはルート、ツリーサイズ、およびパス順序を認証する必要があります。

よくある間違い

インデックスの偶奇のみから方向を選択し、可変ツリーの境界 fn == sn を無視する。
リーフと内部ノードに同一のハッシュプレフィックスを使用し、ドメイン分離を失う。
リーフの境界、パス長、または sn の収束をチェックせずに、再構築されたルートのみを比較する。
信頼できないレスポンスのルートを認証のアンカーとして扱う。
あるツリー規約で構築し、別の完全二分木ルールで検証する。
バージョン管理された規約からパス順序、ハッシュのバイト順、またはリーフの正規化を省略する。

フォローアップ質問

append-only な一貫性証明はどのように検証しますか？

包含証明は 1 つのリーフが 1 つのルートに属しているかどうかを答えます。一貫性証明は新旧両方のルートを再構築し、古いツリーが新しいツリーのプレフィックスであることを証明します。入力には新旧のサイズ、パス、および両方の信頼できるルートが含まれます。状態遷移が異なるため、Boolean のみを返す包含関数の中に隠蔽すべきではありません。

パスだけでなく tree_size を送信するのはなぜですか？

可変サイズツリーでは、最後のノードがそのレベルで右の兄弟を持たない場合があります。方向は現在のサブツリーの境界に依存します。tree_size は検証器にどのノードが存在するかを伝え、余分なハッシュが偽のルートパスに不正混入するのを防ぎます。

ハッシュアルゴリズムのダウングレードをどのように防ぎますか？

アルゴリズム識別子、出力長、リーフ/内部プレフィックス、および正規化をバージョン管理します。許可リストのみを受け入れ、未知または脆弱なアルゴリズムを拒否します。マイグレーションによって新しいルート名前空間が作成されるため、異なるアルゴリズムのダイジェストが同一ツリーを共有してはなりません。

重複するリーフは証明にどのように影響しますか？

包含証明はバイト列を特定の位置に束縛するものであり、その値が一度しか出現しないことを証明するものではありません。一意性を保証するには、別のキーインデックスや集合証明が必要です。単一の Merkle ルートでは、別の同一値が存在しないことを証明できません。

ツリー全体を保存せずに生成器をインクリメンタルにするにはどうすればよいですか？

各レベルで最新の右側サブツリーダイジェストをプレフィックスアキュムレータとして保持し、二進数の繰り上がりのように新しいリーフをマージします。古いリーフを証明するには、依然として必要な兄弟ノードを保持するか外部ストレージが必要であり、ルート単体からパスを再作成することはできません。

検証器は過大なパスをどのように処理すべきですか？

パース前にツリーサイズとハッシュ長から上限を計算し、それより長いパスを拒否し、乗算オーバーフローを避けるために各要素の固定長をチェックします。不正な証明が無限ループや大量のメモリ割り当てを引き起こさないよう、ハッシュ計算の前にリソースバジェットを確認してください。