一つの種から千の葉へ – Merkleの認証ツリー

私のGitHubリポジトリには、小さなMerkleツリーの実装があります。 王家の承認の証である、王国の紋章。何世紀にもわたり、王や女王、皇帝や女帝、貴婦人や貴族は、重要な書類に家名を残すために印章を使用してきました。しかし、私たち一般庶民には何が残されたのでしょうか？単純なサインが、私たちの低予算の印章でした。そのユニークさは、ペンの圧力、速度とリズム、文字の傾き、そして間隔の組み合わせから生まれます。しかし、世界は進化しています。コンピューター、携帯電話、インターネットなしで現代生活を送ることは想像しがたいです。そして、普通のサインがこの環境で抱える問題は、まるで fancy なステッカーのように、ある文書から別の文書へと簡単にコピー＆ペーストできてしまうことです。文書を印刷して署名し、スキャンし直す必要がない場合は非常に便利です。なぜなら、タッチパッドやコンピューターマウスで描くことの苦労は皆知っているからです（少なくとも私はいつも奇妙な落書きになってしまいます）。しかし残念ながら、コピー＆ペーストできるということは、他の誰でも同じことができるということです。そして、ある朝目覚めたら、誰かが贈与証書にあなたのサインを偽造したせいで、あなたの株式や投資がすべてなくなっていたとしたら、気分は良くないでしょう。でも心配はいりません。 すでに1979年に、Ralph Charles Merkleは、彼の博士論文「Secrecy, Authentication, and Public Key Systems」で説明したデジタル署名のアイデアを思いつきました。正確に言えば、デジタル署名のアイデアは彼のオリジナルではありませんでした。彼は、Leslie LamportがMicrosoftの研究フォーラムでのレポート論文の説明で自身が述べているように、Rabinの署名を改良した、すでに存在するLamport-Diffieのワンタイム署名を改良しました。 では、そのLamport-Diffieのワンタイム署名とは何でしょうか？Merkleはそれを非常に素晴らしく明確な例で説明しています。2人の人物を想像してください：株式を所有するAliceと、ブローカーのBobです。Aliceは株式を売却したいのですが、Bobは電話やメッセージでの確認を受け入れることができません（最近は声のディープフェイクが非常に容易だからです）。そこで彼らは、Aliceがこの株式を購入した際に、ワンウェイ関数（そのような関数の例は前の投稿で見つかります）を使用して $F(x)=y$ を計算し、それをBobに送ったことを思い出します。彼らは $F$ と $y$ を含む契約書に署名しましたが、$x$ は含んでいませんでした。そして、Aliceが株式を売却したい場合は、$x$ をBobに開示することに合意しました。 $F$ はワンウェイ関数であり、不可逆であるため、Aliceが開示しない限りBobが $x$ を得る他の方法はありません。だからこそ、Aliceが送信する1ビットのメッセージは認証されると主張できます。 では、Aliceがより長いメッセージを送信したい場合はどうでしょうか？一度にすべての株式を売却したい人はめったにいません。もっと頻繁に、人々は一定数の株式を売却します。例えば、Aliceは11株を売却したいとします。そのためには、購入契約書は少し異なるものにする必要があります。Aliceは $j$ 個の秘密鍵 $x$ を選択する必要がありました： そして、それぞれの $j$ に対して $y_j = F(x_j)$ を計算します。これらの $j$ 個の公開鍵値は、公開鍵ベクトル $Y_i$ としてBobと共有されます。値 $j$ は、Aliceが署名できるメッセージのビット長を表す固定数です。この例では $j=100$ を使用します。しばらくして、Aliceは「11株売却」というメッセージ $m$ を送信したいとします。まず、彼女はそのメッセージのバイナリ表現を必要とします：01010011 01100101 01101100 01101100 00100000 00110001 00110001 00100000 01110011 01101000 01100001 01110010 01100101 01110011 このメッセージの長さは112ビットですが、$j=100$ なので、彼女は100個の事前計算された鍵しか持っておらず、したがって100ビットしか署名できません。それは彼女のメッセージを短くする必要があるということでしょうか？もちろん違います。代わりに、別のワンウェイ関数を使用して、すべての112ビットを100ビットにマッピングします。そして、メッセージが短すぎた場合は、ちょうど100ビットになるまでゼロで拡張します。したがって、100ビットのうちの各ビットについて、彼女は秘密鍵 $x_j$ と公開鍵 $y_j$ を持っています。彼女のメッセージ $m$ に署名するために、彼女はメッセージの1であるすべてのビットに対応するすべての $x_j$ をBobに送信します。したがって、文字sの例では、彼女は以下を送信します： 次の文字eについては、彼女は以下を開示します： …といった具合です。このように、Aliceはメッセージの各ビットに署名します。これでメッセージは安全でしょうか？実際には、完全ではありません。Bobがメッセージを変更する方法があります。彼は、Aliceから受け取った秘密鍵 $x_j$ の1つを、受け取らなかったと主張するだけで、メッセージの1を0に変更できます。このようにして、彼は11株ではなく、10株を売却するように依頼したと言うことができます：00110001 00110000 この問題を回避するために、LamportとDiffieは、$m$ の補数である $m'$ をメッセージの末尾に追加することを提案しています。これにより、Bobが11株を10株に変更したい場合、彼は補数 $m'$ の1に対応する $x_j$ を開示する必要があります（以下の例では偽造されたメッセージの最後のビット）、しかしAliceは彼にその秘密鍵を送っていないので、それはできません。例：元の mm' = 00110001 00110001 11001110 11001110 偽造された mm' = 00110001 00110000 11001110 11001111 これで全てうまくいっているように見えます。しかし、問題は、このようなワンタイム署名はストレージスペースが多すぎることです。そこでRalph Merkleはアルゴリズムを改良することを決定し、メッセージに署名する別の方法を提案しました。 MerkleはLamport-Diffieのワンタイム署名をどのように改良したのでしょうか？Merkleの最初の解決策は、保護されるメッセージの実際の長さを短縮することでした。Lamportは、Bobが署名を改ざんするのを防ぐために、$m$ の補数 $m'$ を使用することを提案しましたね？それは良いアイデアでしたが、メッセージの長さも2倍になってしまいました。ストレージスペースを節約するために、Merkleはメッセージ $m$ の末尾に0の数を追加します。そのためには、$ m ext{ceil}( m ext{log}_2 j)$ （またはこの例では $ m ext{ceil}( m ext{log}_2 100) = 7$）ビットの追加で済みます。これはLamportのアイデアよりも大幅に少ないです。なぜ $ m ext{log}_2$ なのでしょうか？ゼロの数はバイナリ数として格納されます。100ビットのメッセージの場合、数は最大100になり、100は $2^6=64$ と $2^7=128$ の間に位置するため、それを格納するには7ビットが必要です。ゼロの数ではなく、1の数を格納することはできますか？いいえ、それは署名が改ざんされるのを防ぐことにはなりません。ご存知のように、Bobは1を0に変更することはできますが、その逆はできません。0を1に変更するには、彼が受け取ったことのない秘密鍵が必要になります。例を見てみましょう。100ビットのメッセージではなく、5つのゼロを持つ8ビットのメッセージを使用します：10001100 101 ^ ^ m ゼロの数 ここでBobは、1ビットを1から0に変更してメッセージを偽造しようとします。メッセージには6つのゼロが含まれるようになりました：10001000 110 ^ ^ m ゼロの数 ご覧のとおり、ある部分で1を0に変更することは、カウントフィールドで0を1に変更することも意味しますが、これはBobにはできません。もしゼロの代わりに1の数を追加していた場合：10001100 11 ^ ^ m 1の数 Bobは、両方の部分で1を0に変更するだけで、問題なく偽造できます：10001000 10 しかし、すべての公開鍵を保存する必要があるのでしょうか？もちろん（Lamport-Diffieのワンタイム署名を使用する場合）。そうでなければ、BobはどうやってAliceが彼に鍵を送っていることを知るのでしょうか？もしそれがAliceの敵であるEvaで、彼女の邪悪なメッセージ「私のすべての株式をEvaに贈与する。Alice」を作成し、それをBobに送る前にすべての公開鍵と秘密鍵を作成したとしたらどうでしょうか？それは、何らかの事前の取り決めがない限り、修正できません。しかし、想像できるように、すべての公開鍵を保存することはBobのストレージを大量に消費します。そこでMerkleは、「ツリー認証」と呼ばれる別の解決策を思いつきました。 ツリー認証はどのように機能しますか？全体の構造は二分木のように見えます。葉は $Y_i$ の値（Lamport-Diffie法を使用して計算された公開鍵）です。内部ノードとルートは、別のワンウェイ関数 $H$ を使用して帰納的に計算されます。葉から始めます： そしてルートに向かって進みます：