0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@sen-ltd

Merkle tree のインタラクティブ可視化ツールを作った — 1 byte 書き換えると root が O(log n) で別物になる図

0
Posted at

「Merkle tree は 100 万個のトランザクションをひとつの root hash にコミットでき、特定の 1 件が含まれることは ~20 個のハッシュだけで証明できる」 — 説明はだいたいここで止まる。この記事は、その図そのもの をブラウザで動かせるようにした話。

leaf を編集すると、その leaf から root までのハッシュが連鎖的に赤く変わる。inclusion proof（特定の leaf が含まれていることを root だけしか持たない検証者に証明する道具）も画面右にリアルタイムで生成され、検証結果が ✓ / ✗ で切り替わる。

merkle-viz UI: 4 leaves の Merkle tree を SVG で描画。leaf 2 を tamper（"carol→dave 3" → "carol→dave 3!"）したことで、leaf 2 のハッシュ・level 1 の親ノード・root の 3 ノードが赤枠で示されている。改ざんされていない sibling 側（leaf 0, leaf 1, level-1 左ノード）はグレーのまま。右側パネルには inclusion proof の sibling ハッシュ 2 件と、緑色の "✓ matches root — leaf is included" 検証結果が表示されている。

🌳 デモ: https://sen.ltd/portfolio/merkle-viz/
📦 GitHub: https://github.com/sen-ltd/merkle-viz

純粋ロジック ~200 行 + DOM/SVG ~150 行。ビルド不要、依存なし。ハッシュは crypto.subtle.digest("SHA-256", …) を使うので、同じ merkle.js がブラウザでも Node 18+ でも動く。node --test で 17 ケースのユニットテスト付き。

Merkle tree が解いている問題

リスト（トランザクション・ログ・ファイル等、何でもいい）に対して、ひとつの短い指紋（fingerprint）を作る。ただし以下の性質を満たす:

  1. 任意の項目を 1 個でも書き換えると、指紋が変わる
  2. 任意の項目について、「これがリストに含まれていた」ことを 指紋しか持たない検証者 に証明できる。リスト全体を送る必要なし
  3. 証明の生成・検証はどちらも O(log n) で済む

素朴な「全部連結して sha256 する」では (1) は満たせるが (2) で詰む（検証者にリスト全体が必要）。Merkle tree は 3 つ全部を満たす。

構成は機械的:

level 0:  H(L0)  H(L1)  H(L2)  H(L3)        ← 各 leaf のハッシュ
level 1:    H(H(L0)||H(L1))     H(H(L2)||H(L3))  ← 2 つずつまとめてハッシュ
level 2:        H( level1_left || level1_right )
                       =
                     ROOT

H は SHA-256、|| は byte 連結（hex 文字列の連結ではない、これは罠）。leaf 数が奇数の level では、本実装は最後のノードを 複製してそれ自身とペアにする（Bitcoin の合意ルールが採用している規約）。Certificate Transparency は奇数残りをそのまま上に上げる別規約を使う、Ethereum の Patricia trie は更に別物 — 規約はどれかひとつ選んで明文化して使い続ければいい。

inclusion proof は単純に「leaf から root まで上っていく途中で、各 level の sibling のハッシュ」を集めたもの。leaf 4 個なら proof は 2 個、1024 個なら 10 個、100 万個なら 20 個。

純粋ロジック側

merkle.js は検証者が必要とする 4 関数 + 可視化用の補助 3 関数を export する。すべて async（crypto.subtle.digest が async なので）。

const enc = new TextEncoder();

export async function sha256Hex(bytes) {
  const buf = bytes instanceof Uint8Array ? bytes : enc.encode(bytes);
  const digest = await crypto.subtle.digest("SHA-256", buf);
  return bytesToHex(new Uint8Array(digest));
}

export async function hashLeaf(text) {
  return sha256Hex(text);
}

export async function hashPair(leftHex, rightHex) {
  const buf = new Uint8Array(64);
  buf.set(hexToBytes(leftHex), 0);
  buf.set(hexToBytes(rightHex), 32);
  return sha256Hex(buf);
}

hashPair で間違えやすいのが「子ハッシュを byte で連結 する」点。hex 文字列のまま + で繋ぐと別物の root になり、別実装で作った proof は通らなくなる。テストで明示的に固定:

test("hashPair concatenates child bytes (not hex strings)", async () => {
  const left = await hashLeaf("L");
  const right = await hashLeaf("R");
  const got = await hashPair(left, right);

  // 参照実装: byte 列を連結してから sha256
  const concat = Buffer.concat([
    Buffer.from(left, "hex"),
    Buffer.from(right, "hex"),
  ]);
  assert.equal(got, createHash("sha256").update(concat).digest("hex"));
});

ツリー構築は素直なボトムアップ:

export async function buildTree(leaves) {
  if (!leaves.length) return { levels: [[]], root: null };

  const leafHashes = await Promise.all(leaves.map(hashLeaf));
  const levels = [leafHashes];

  while (levels[levels.length - 1].length > 1) {
    const cur = levels[levels.length - 1];
    const next = [];
    for (let i = 0; i < cur.length; i += 2) {
      const left = cur[i];
      const right = i + 1 < cur.length ? cur[i + 1] : cur[i]; // 奇数残りは複製
      next.push(await hashPair(left, right));
    }
    levels.push(next);
  }
  return { levels, root: levels[levels.length - 1][0] };
}

可視化のため全 level を保持しているが、root しか必要ない実装なら各 level を消費後に捨てればよい。

proof の生成と検証

getProof(levels, i) は leaf i から root まで上りながら sibling を集める:

export function getProof(levels, index) {
  if (!levels.length || !levels[0].length) return [];
  const proof = [];
  let i = index;
  for (let lvl = 0; lvl < levels.length - 1; lvl++) {
    const layer = levels[lvl];
    const isRight = i % 2 === 1;
    const sibIdx = isRight ? i - 1 : i + 1;
    const sibling = sibIdx < layer.length ? layer[sibIdx] : layer[i]; // 奇数残りは自分自身
    proof.push({ hash: sibling, side: isRight ? "left" : "right" });
    i = Math.floor(i / 2);
  }
  return proof;
}

非自明なポイントが 2 つ:

  1. side が必須。running hash と sibling を連結する順序が結果を変える。running が左の子なら running || sibling、右の子なら sibling || running。これを忘れると、検証は静かに全部 reject する
  2. 奇数残りの leaf は自分自身を sibling にする。3-leaf tree の level 0 は [H(L0), H(L1), H(L2)]、level 1 は [H(H(L0)||H(L1)), H(H(L2)||H(L2))]。L2 の proof の最初のステップは sibling=L2 自身のハッシュ、になる

検証は逆向き:

export async function verifyProof(leafText, proof, expectedRoot) {
  let running = await hashLeaf(leafText);
  for (const step of proof) {
    if (step.side === "left") {
      running = await hashPair(step.hash, running);
    } else {
      running = await hashPair(running, step.hash);
    }
  }
  return { ok: running === expectedRoot, computedRoot: running };
}

検証者は他の leaf を一切見ない。候補 leaf をハッシュし、与えられた sibling と pair-hash を順に再生し、最終値を信頼している root と比較するだけ。これで O(n) のデータセットへの inclusion を O(log n) のハッシュで証明できる。

改ざん伝播の可視化

Merkle tree のデモで一番効くのは「leaf を 1 byte 変えると root が変わる」を 見える ようにすること。可視化ツールは「baseline tree」と「current tree」をメモリに保持し、描画時に diff を取る:

export function diffLevels(a, b) {
  const changed = new Set();
  for (let lvl = 0; lvl < Math.max(a.length, b.length); lvl++) {
    const la = a[lvl] || [], lb = b[lvl] || [];
    const w = Math.max(la.length, lb.length);
    for (let i = 0; i < w; i++) {
      if (la[i] !== lb[i]) changed.add(`${lvl}:${i}`);
    }
  }
  return changed;
}

leaf を 1 個編集すると、changed set には leaf から root への 1 本道だけ が入る。proof が依存している sibling 側は無傷。テストで形を固定:

test("diffLevels finds exactly the path of changed nodes", async () => {
  const before = await buildTree(["a", "b", "c", "d"]);
  const after  = await buildTree(["a", "b", "c!", "d"]);
  const changed = diffLevels(before.levels, after.levels);
  // 期待: leaf 2, 親 (1,1), root (2,0)
  assert.ok(changed.has("0:2"));
  assert.ok(changed.has("1:1"));
  assert.ok(changed.has("2:0"));
  // sibling 側は無傷
  assert.ok(!changed.has("0:0")); assert.ok(!changed.has("0:1"));
  assert.ok(!changed.has("0:3")); assert.ok(!changed.has("1:0"));
});

これがそのまま「改ざんは O(log n) で root に伝播する」というコード化。SVG 側は changed set を歩いて該当ノードを赤く描く。Merkle tree の解説でみんな描きたいのに描かれない図、になる。

2 ファイル構成にした理由

merkle.js は DOM 参照ゼロ・グローバル使用ゼロ・モジュール状態ゼロ。export はすべて純粋（または async-pure）。これで node --test がそのまま読める:

$ npm test
✔ sha256Hex matches node:crypto for ASCII input
✔ hashLeaf is deterministic and matches sha256(text)
✔ hashPair concatenates child bytes (not hex strings)
✔ buildTree on 4 leaves yields a 3-level tree
✔ buildTree duplicates the last leaf when count is odd (Bitcoin style)
✔ proofs verify against the real root for every leaf
✔ proof verification fails if a single character of the leaf changes
✔ proof verification fails if a sibling hash is swapped
✔ diffLevels finds exactly the path of changed nodes
…
ℹ tests 17  ℹ pass 17  ℹ fail 0

script.js は DOM/SVG だけを担当: leaf エディタ、SVG ツリー描画、proof パネル。ハッシュ計算は持たず、必ず merkle.js 経由。これで本番コードとテスト対象が同じものになる。

crypto.subtle.digest は近代ブラウザと Node 18+ で挙動が同じなので、polyfill も shim も要らない。代償は async-everywhere になることだけ、というのは妥当なトレードオフ。

実世界での Merkle tree

  • Bitcoin のブロックヘッダ は、ブロック内の全トランザクションに対する root hash を持つ。SPV (Simplified Payment Verification) ウォレットはまさにこの inclusion proof で動く: サーバが「トランザクション + Merkle proof」を返し、ウォレット側はすでに持っているブロックヘッダだけで検証する。2008 年の論文の中核設計
  • Git の tree オブジェクト はディレクトリ内の blob と再帰的な sub-tree をハッシュする。完全な balanced binary tree ではない（content-addressable graph）が、性質は同じ: ファイルを 1 byte 変えると root commit のハッシュまで全部変わる
  • Certificate Transparency log は CA が発行した全証明書をコミットする。ブラウザは証明書を信頼する前に、log root に対する Merkle inclusion proof で「ちゃんと log されているか」を検証する。規約は微妙に違う（leaf 複製しない、domain separation あり）が、数学は同じ
  • Content-addressable storage の IPFS や Plan 9 系も Merkle DAG でアドレス指定。同じアイデアの別トポロジー

共通する直感は「ハッシュは合成可能」というだけ。ハッシュのハッシュもまた指紋であり、subtree 全体の指紋を root に持つツリーが作れる。これが見えれば残りは配管作業。

意図的に省いたこと

可視化ツールは小さく保つことを優先した。本番実装が気にする以下は省いている:

  • Domain separation — 本番の Merkle tree は leaf hash と internal-node hash で異なる prefix（0x00 vs 0x01）を使い、検証者を「内部ノードを leaf として騙す」second-preimage 攻撃から守る。CT や最近の Bitcoin 提案はやっている。デモは説明を短くするためにやっていない
  • streaming 構築 — buildTree は全 level をメモリに保持する。1 億エントリの log なら、親 level を on-the-fly に計算しながら子 level を捨てるべき
  • proof のシリアライズ形式 — 実世界の proof は決まった byte レイアウト（CT は RFC 6962、Bitcoin はプロトコルの compact format）に直列化する。この可視化ツールはプレーンな JS object のまま扱う

本番投入するなら RFC 6962 (CT) や Bitcoin developer reference を読むこと。可視化ツールのデフォルトを信用してはいけない。

触ってみる

https://sen.ltd/portfolio/merkle-viz/ は 4 leaves（送金トランザクション風のテキスト）でスタートする。leaf 2 の tamper ボタンを押すと、典型デモが見える: leaf 2 の input が赤くなり、SVG 上で leaf 2・level 1 の親・root が赤枠に変わり、上のヘッダの root hash も切り替わる。右側の inclusion proof は 依然として ✓（current tree 側で sibling も再計算されるので、proof は新しい root に対して通る）。次に "tamper with the leaf I'm verifying" の details パネルを開いて、leaf テキストと違う内容を入力してみる。そこで初めて検証が ✗ になる — 候補 leaf がツリーのどの leaf にも対応していないので。

ソース: https://github.com/sen-ltd/merkle-viz — MIT、合計 ~350 行、17 ユニットテスト、ビルド不要。読むなら merkle.js から。残りは表示。

🛠 本記事は SEN 合同会社 が公開している小さな開発者ツール群の 1 つです。他のツールは portfolio 一覧 から。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?