「1つの種から千の葉へ」――Merkleの認証ツリーがデジタル署名を変えた

From One Seed to a Thousand Leaves – Merkle's Authentication Tree

1979年、Ralph Merkleは博士論文で、Lamport-Diffieのワンタイム署名を改良した「ツリー認証」を提案した。この方式では、公開鍵をツリー構造にまとめ、ルート値だけを共有することで、署名の検証に必要なデータを大幅に削減できる。本稿では、AliceとBobの例を用いて、デジタル署名の基本からMerkleツリーの仕組みまでを解説し、従来方式と比較した際のストレージ効率の劇的な改善を示す。