HN 日本語サマリー

← 一覧へ戻る
プログラミング

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

From One Seed to a Thousand Leaves – Merkle's Authentication Tree (0xkrt26.github.io)

36 pointsby denismenace3 コメント

要約

この記事は、デジタル署名の進化とMerkle認証ツリーの概念を解説しています。従来の署名の限界を乗り越えるため、Lamport-Diffieのワンタイム署名方式が紹介され、その仕組みとストレージの課題が説明されます。最終的に、Merkleが提案したツリー構造による認証方法が、効率的な署名検証の解決策として提示されます。

全文翻訳

1つの種から千の葉へ - Merkleの認証ツリー

王家の承認の証である「王国の紋章」。何世紀にもわたり、王や女王、皇帝や皇后、貴婦人や貴族は、重要な書類に家名を残すために印章を用いてきました。しかし、私たち一般庶民に残されたものは何でしょうか?単純なサイン(自筆署名)が、私たちの低予算の印章でした。そのユニークさは、ペンの圧力、速度、リズム、文字の傾き、そして間隔の組み合わせから生まれます。

しかし、世界は進化しています。コンピューター、携帯電話、インターネットなしで現代生活を送ることを想像するのは難しいでしょう。そして、この状況における通常のサインの欠点は、まるで装飾的なステッカーのように、ある文書から別の文書へと簡単にコピー&ペーストできてしまうことです。文書を印刷して署名し、スキャンし直す必要がない場合は非常に便利です。なぜなら、タッチパッドやコンピューターマウスで署名を描くのがどれほど大変か、私たちは皆知っているからです(少なくとも私はいつも、署名の代わりに奇妙な落書きをしてしまいます)。しかし残念ながら、コピー&ペーストできるということは、他の誰でも同じことができるということです。そして、ある朝目覚めたら、あなたのサインが贈与証書に偽造されたせいで、すべての株式や投資がなくなっていたとしたら、気分は良くないでしょう。

しかし、心配はいりません。すでに1979年に、Ralph Charles Merkleは、彼の博士論文「Secrecy, Authentication, and Public Key Systems」で説明されたデジタル署名のアイデアを思いつきました。正確に言えば、デジタル署名のアイデアは彼のものではありませんでした。彼は、Leslie LamportがMicrosoft Research Forumでのレポート論文の説明で自身が述べているように、Rabinの署名を改良した、既存のLamport-Diffieの1回限りの署名を改良しました。

Lamport-Diffieの1回限りの署名とは何でしょうか?

Merkleは、それを非常に素晴らしく明確な例で説明しています。2人の人物を想像してください:株式を持つAliceと、ブローカーのBobです。Aliceは株式を売却したいのですが、Bobは電話やメッセージを証拠として受け入れることができません(最近は誰かの声をディープフェイクするのが非常に簡単だからです)。そこで彼らは、Aliceがこの株式を購入したときに、1方向関数(そのような関数の例は、以前の投稿で見つけることができます)を使用して $F(x)=y$ を計算し、それをBobに送ったことを覚えています。彼らは、$x$ ではなく $F$ と $y$ を含む契約に署名し、Aliceが株式を売却したい場合は、彼女の $x$ をBobに開示することに合意しました。

$F$ は不可逆な1方向関数であることに注意してください。つまり、Aliceがそれを開示しない限り、Bobが $x$ を取得する他の方法はありません。だからこそ、Aliceが送信する1ビットのメッセージは認証されていると主張できるのです。

Aliceがより長いメッセージを送信したい場合はどうなりますか?

一度にすべての株式を売却したい人はまれです。もっと頻繁に、人々は一定数の株式を売却します。たとえば、Aliceは11株を売却したいとします。そのためには、購入契約は少し異なるものにする必要があります。

Aliceは $j$ 個の秘密鍵 $x$ を選択する必要がありました。

\[\begin{matrix} x_1 \ x_2 \ x_3 \ \vdots \ x_j \end{matrix}\]

そして、各 $j$ について $y_j = F(x_j)$ を計算します。これらの $j$ 個の公開鍵値は、公開鍵ベクトル $Y_i$ としてBobと共有されます。

値 $j$ は、Aliceが署名できるメッセージのビット長を表す固定数です。この例では $j=100$ を使用します。

しばらくして、Aliceはメッセージ $m$:「11株を売却する」を送信したいとします。

まず、彼女はメッセージのバイナリ表現を必要とします。

01010011 01100101 01101100 01101100 00100000 00110001 00110001 00100000 01110011 01101000 01100001 01110010 01100101 01110011

このメッセージの長さは112ビットですが、$j=100$ なので、彼女は100個の事前計算された鍵しか持っておらず、したがって100ビットしか署名できません。

それは彼女がメッセージを短くしなければならないという意味でしょうか?

もちろん違います。代わりに、別の1方向関数を使用して、すべての112ビットを100ビットにマッピングします。そして、メッセージが短すぎた場合は、正確に100ビットになるまでゼロで拡張します。

したがって、100ビットの各ビットについて、彼女は秘密鍵 $x_j$ と公開鍵 $y_j$ を持っています。メッセージ $m$ に署名するために、彼女はメッセージのビットが1であるすべてのビットに対応するすべての $x_j$ をBobに送信します。したがって、文字 's' の例では、彼女は以下を送信します。

\[\begin{array}{l} \texttt{01010011} \\[1ex] x_2 \ x_4 \ x_7 \ x_8 \end{array}\]

次の文字 'e' のために、彼女は以下を開示します。

\[\begin{array}{l} \texttt{01100101} \\[1ex] x_2 \ x_3 \ x_6 \ x_8 \end{array}\]

…といった具合です。このようにして、Aliceはメッセージの各ビットに署名します。

メッセージは保護されていますか?

実際には、完全ではありません。Bobがメッセージを変更する方法があります。彼は単に、Aliceから秘密鍵 $x_j$ の1つを決して受け取らなかったと主張するだけで、メッセージの1を0に変更できます。このようにして、彼は11株ではなく、以下のように10株を売却するように要求されたと言うことができます。

00110001 00110001

Aliceは彼に10株を売却するように要求しました。

00110001 00110000

これを避けるために、LamportとDiffieは、$m$ の補数である $m'$ をメッセージの末尾に追加することを提案しています。これにより、Bobが11株を10株に変更したい場合、偽造されたメッセージの最後のビット(以下の例)に対応する $m'$ の1を開示する必要がありますが、Aliceは決してその秘密鍵を彼に送らなかったため、これはできません。

例:

Original mm' = 00110001 00110001 11001110 11001110
Forged   mm' = 00110001 00110000 11001110 11001111

これで全てうまくいくように見えます。しかし問題は、このような1回限りの署名はストレージスペースが多すぎることです。そのため、Ralph Merkleはアルゴリズムを改良することを決定し、別のメッセージ署名方法を提案しました。

MerkleはLamport-Diffieの1回限りの署名をどのように改良したのでしょうか?

Merkleの最初の解決策は、保護されるメッセージの実際の長さを短縮することでした。Lamportは、Bobが署名を改ざんするのを防ぐために、$m$ の補数 $m'$ を使用することを提案しましたよね?それは良いアイデアでしたが、メッセージの長さも2倍になりました。

ストレージスペースを節約するために、Merkleはメッセージ $m$ の末尾に0の数を追加します。そのためには、$\lceil \log_2 j \rceil$(またはこの例では $\lceil \log_2 100 \rceil = 7$)ビットの追加で済みます。これはLamportのアイデアよりも大幅に少ないです。

なぜ $\log_2$ なのでしょうか?

ゼロの数はバイナリ数として格納されます。100ビットのメッセージの場合、カウントは最大100になり、100は $2^6=64$ と $2^7=128$ の間にあるため、それを格納するには7ビットが必要です。

1の数ではなく0の数を格納する必要がありますか?

いいえ、それは署名の改ざんを防ぐことができません。

Bobは1を0に変更することはできますが、その逆はできません。0を1に変更するには、彼が受け取ったことのない秘密鍵が必要になります。

例を見てみましょう。100ビットのメッセージではなく、5つのゼロを持つ8ビットのメッセージを使用します。

10001100 101
^         ^
m         count of 0s

ここでBobは、1ビットを1から0に変更してメッセージを偽造したいと考えています。メッセージには6つのゼロが含まれています。

10001000 110
^         ^
m         count of 0s

ご覧のとおり、一方の部分で1を0に変更することは、カウントフィールドの0を1に変更することも意味します。これはBobにはできません。

ここで、0の代わりに1の数を追加していた場合を考えます。

10001100 11
^         ^
m         count of 1s

Bobは、両方の部分で1を0に変更するだけで、問題なく偽造できます。

10001000 10
しかし、すべての公開鍵を保存しなければならないのでしょうか?それらは多くのスペースを占有しますが。

もちろん(Lamport-Diffieの1回限りの署名を使用する場合)。そうでなければ、BobはどうやってそれがAliceから鍵を送っていることを知るのでしょうか?もしそれがAliceの敵であるEvaで、彼女が悪意のあるメッセージ「すべての私の株式をEvaに贈与する。Alice」を作成し、それをBobに送る前にすべての公開鍵と秘密鍵を作成したとしたらどうでしょうか?これは、何らかの事前の取り決めがないと修正できません。しかし、想像できるように、すべての公開鍵を保存するにはBobのストレージの多くが必要です。そこでMerkleは「ツリー認証」と呼ばれる別の解決策を思いつきました。

ツリー認証はどのように機能しますか?

全体の構造は二分木のように見えます。葉は $Y_i$ の値(Lamport-Diffie方式で計算された公開鍵)です。内部ノードとルートは、別の1方向関数 $H$ を使用して帰納的に計算されます。葉から始めます。

\[H(i, i, Y) = F(Y_i)\]

そして、以下を使用してルートまで進みます。

\[H(i, j, Y) = F!\left( H!\left(i,, \frac{i+j}{2},, Y\right),; H!\left(\frac{i+j}{2} + 1,, j,, Y\right) \right)\]

これは最初は複雑に見えるかもしれませんが、例を見て、署名プロセスが正確にどのように機能するかを理解してみましょう。

例:

AliceがBobに8通の署名済みメッセージを送信できると仮定します。まず、Lamport-Diffie署名を使用して8つのベクトル $Y_1, Y_2, \ldots, Y_8$ を計算します。次に、Aliceは葉ノードを計算します。

\[\begin{aligned} H(1, 1, Y_1) &= F(Y_1) \ H(2, 2, Y_2) &= F(Y_2) \ &;;\vdots \ H(8, 8, Y_8) &= F(Y_8) \end{aligned}\]

次に、葉ノードのペアを取り、内部ノードを作成します。

\[\begin{aligned} H(1, 2, Y_{1,2}) &= F!\big( H(1, 1, Y_1),; H(2, 2, Y_2) \big) \ H(3, 4, Y_{3,4}) &= F!\big( H(3, 3, Y_3),; H(4, 4, Y_4) \big) \ H(5, 6, Y_{5,6}) &= F!\big( H(5, 5, Y_5),; H(6, 6, Y_6) \big) \ H(7, 8, Y_{7,8}) &= F!\big( H(7, 7, Y_7),; H(8, 8, Y_8) \big) \end{aligned}\]

次に、新しいノードを再度ペアにします。

\[\begin{aligned} H(1, 4, Y_{1,4}) &= F!\big( H(1, 2, Y_{1,2}),; H(3, 4, Y_{3,4}) \big) \ H(5, 8, Y_{5,8}) &= F!\big( H(5, 6, Y_{5,6}),; H(7, 8, Y_{7,8}) \big) \end{aligned}\]

そしてもう一度。

\[H(1, 8, Y_{1,8}) = F!\big( H(1, 4, Y_{1,4}),; H(5, 8, Y_{5,8}) \big)\]

Aliceが得る値 $H(1, 8, Y_{1,8})$ はルート値 $R$ です。これは、BobとAliceが署名する前に合意しなければならない唯一の値であり、したがってBobが保存する必要のある唯一の公開鍵です。

結果のツリーは次のようになります。

graph TD R["H(1,8) = Root R"] --> H14["H(1,4)"] R --> H58["H(5,8)"] H14 --> H12["H(1,2)"] H14 --> H34["H(3,4)"] H58 --> H56["H(5,6)"] H58 --> H78["H(7,8)"] H12 --> H11["H(1,1) = F(Y₁)"] H12 --> H22["H(2,2) = F(Y₂)"] H34 --> H33["H(3,3) = F(Y₃)"] H34 --> H44["H(4,4) = F(Y₄)"] H56 --> H55["H(5,5) = F(Y₅)"] H56 --> H66["H(6,6) = F(Y₆)"] H78 --> H77["H(7,7) = F(Y₇)"] H78 --> H88["H(8,8) = F(Y₈)"]

Aliceは実際にどのようにメッセージに署名するのでしょうか?

AliceとBobの対話形式で、最初のメッセージ $m_1$ が8つの利用可能なメッセージのうちどのように署名されるかを想像してみましょう。

Alice:

\[H(5, 8, Y_{5,8})\] \[H(1, 4, Y_{1,4})\]

Bob: (契約から $H(1, 8, Y_{1,8}) = R$ を取得)

\[H(1, 8, Y_{1,8}) = F!\big( H(1, 4, Y_{1,4}),; H(5, 8, Y_{5,8}) \big);?\]

もしそうなら、続行します。

Alice:

\[H(1, 2, Y_{1,2})\] \[H(3, 4, Y_{3,4})\]

Bob:

\[H(1, 4, Y_{1,4}) = F!\big( H(1, 2, Y_{1,2}),; H(3, 4, Y_{3,4}) \big);?\]

もしそうなら、続行します。

Alice:

\[H(1, 1, Y_1)\] \[H(2, 2, Y_2)\]

Bob:

\[H(1, 2, Y_{1,2}) = F!\big( H(1, 1, Y_1),; H(2, 2, Y_2) \big);?\]

もしそうなら、続行します。

Alice:

\[Y_1\]

Bob:

\[F(Y_1) = H(1, 1, Y_1);?\]

もしそうなら、メッセージは確かにAliceからのものであり、Lamport-Diffie方式に従って秘密鍵を開示できます。

Aliceが8つの利用可能な署名をすべて使用した後、ルート値 $R$ を変更し、二分木を再度計算する必要があります。

ツリー認証は本当に過剰なストレージの問題を解決しますか?

確かに。計算してみましょう。

Lamport-Diffieの1回限りの署名の例では、圧縮と署名に使用される両方のハッシュ関数は100ビットの出力を生成します。

\[\begin{aligned} 2 \cdot j \cdot s &= 2 \cdot 100 \cdot 100 = 20,000 \text{ ビット} \\[1ex] \text{ここで:}\quad 2j &= \text{メッセージあたりの合計鍵数 } (j \text{ 個の秘密鍵 } x_j \text{ と } j \text{ 個の公開鍵 } y_j) \ s &= \text{1つの鍵の長さ(100ビット)}
\end{aligned}\]

ここで、BobがAliceから1通だけでなく1000通のメッセージを受け取った場合、すべての公開鍵を保存するために必要なストレージ量は次のようになります。

\[20,000 \times 1000 = 20,000,000 \text{ ビット} = 2.5 \text{ MB}\]

そして、Bobが他のクライアント(例えば1000)を持っている場合、必要なストレージスペースは約2.5 GBになります。

もちろん、この量のデータを保存することは可能ですが、ユーザー数やメッセージ数がさらに多い場合はどうでしょうか?

Merkleの改良により、Bobはルート値 $R$ のみしか保存しません。これは、他のすべての値と同様に、固定長の100ビットの値です。

2.5 GB 対 100 ビット。違いは大きいですよね?

しかし、Aliceは結局、すべての認証パスを保存しなければならないのではないでしょうか?

正確にはそうではありません。例のツリーの認証パスを見てみましょう。

\[\begin{aligned} Y_1 &: H(2,2),; H(3,4),; H(5,8),; H(1,8) \ Y_2 &: H(1,1),; H(3,4),; H(5,8),; H(1,8) \ Y_3 &: H(4,4),; H(1,2),; H(5,8),; H(1,8) \ Y_4 &: H(3,3),; H(1,2),; H(5,8),; H(1,8) \ Y_5 &: H(6,6),; H(7,8),; H(1,4),; H(1,8) \ Y_6 &: H(5,5),; H(7,8),; H(1,4),; H(1,8) \ Y_7 &: H(8,8),; H(5,6),; H(1,4),; H(1,8) \ Y_8 &: H(7,7),; H(5,6),; H(1,4),; H(1,8) \end{aligned}\]

何か興味深いことに気づきましたか?もし気づかなければ、この修正版を見てください。

\[\begin{aligned} Y_1 &: H(2,2),; H(3,4),; H(5,8),; H(1,8) \ Y_2 &: H(1,1) \ Y_3 &: H(4,4),; H(1,2) \ Y_4 &: H(3,3) \ Y_5 &: H(6,6),; H(7,8),; H(1,4) \ Y_6 &: H(5,5) \ Y_7 &: H(8,8),; H(5,6) \ Y_8 &: H(7,7) \end{aligned}\]

重複をすべて削除した後のテーブルです。すでに保存する量が大幅に減りましたよね?

さらに、修正版はMerkleツリー自体ですが、内部ノードが反転しています。認証パスとツリー図を比較してください。

認証パスの内部ノードは、ルートへの直接パス上のノードではなく、兄弟ノードです。これは、関数 $F$ と $H$ の両方がBobに知られているため、$Y_1$ から $H(1,1)$ を計算できますが、$H(1,2)$ を計算して認証するためにAliceから $H(2,2)$ が必要だからです。

さらに良いのは、Aliceが次のルート変更までほとんどの値すべてを保存する必要がないことです。彼女は認証に再度使用されないノードを削除できます。たとえば、メッセージ $m_1$, $m_2$, $m_3$ に署名した後、4つの内部ノード $H(1,1)$, $H(2,2)$, $H(3,4)$, $H(4,4)$ を削除できます。

更新されたツリーは次のようになります。グレー表示されたノードは削除されました。

graph TD R["H(1,8) = Root R"] --> H14["H(1,4)"] R --> H58["H(5,8)"] H14 --> H12["H(1,2)"] H14 --> H34["H(3,4) ✕"] H58 --> H56["H(5,6)"] H58 --> H78["H(7,8)"] H12 --> H11["H(1,1) ✕"] H12 --> H22["H(2,2) ✕"] H34 --> H33["H(3,3)"] H34 --> H44["H(4,4) ✕"] H56 --> H55["H(5,5) = F(Y₅)"] H56 --> H66["H(6,6) = F(Y₆)"] H78 --> H77["H(7,7) = F(Y₇)"] H78 --> H88["H(8,8) = F(Y₈)"] style H11 fill:#ccc,stroke:#999,color:#999 style H22 fill:#ccc,stroke:#999,color:#999 style H34 fill:#ccc,stroke:#999,color:#999 style H44 fill:#ccc,stroke:#999,color:#999

しかし、Aliceはおそらく未使用のすべての秘密鍵 $X_i$ と公開鍵 $Y_i$ をとにかく保存しなければならないのではないでしょうか?

いいえ。このためにもMerkleは解決策を見つけました。

Aliceが保存する必要があるのは、単一の200ビットのシードキーのみです。これは、一度生成されたランダムな200ビットのデータです。このシードキーだけで、8つの10700ビット長の秘密鍵ベクトル $X_1$ から $X_8$ までを復元できます。それを機能させるために、最初に秘密鍵 $x_j$ のために $8 \times 107$ 個のランダムな値を選択する代わりに、Aliceはこの1つの秘密シードキー(200ビット長)を選択し、以下を生成します。

\[x extbackslash{i,j} = C(\text{seedkey},; \langle i,, j \rangle)\]

ここで秘密鍵 $x$ は2つのインデックス $i$ と $j$ を持ちます。$i$ はメッセージ番号を示し、$j$ はメッセージ内のビットの位置を示します。

$C$ は暗号を表し、暗号化関数として機能します。ハッシュの歴史をカバーし終えたら、暗号と暗号化についてもっと詳しく書きます。今のところ、ランダムに見えるが実際には特別な公開アルゴリズムによって決定される数値のジェネレーターだと想像してください。

シードキーなしでは、どの $x{i,j}$ 値も生成不可能であることに注意してください。これは、Aliceだけが彼女のメッセージの有効な秘密鍵を生成できることを意味します。

したがって、Aliceは200ビットのシードキーからすべての秘密鍵を復元できるので、$Y_i$ を保存する理由は何でしょうか?私たちは、それらが $F(x)$ を通して簡単に計算できることも知っています。Merkleは、すべての鍵をシードキーから計算することは、すべての鍵を保持するために必要なストレージ量と比較して、時間とエネルギーをそれほど多く消費しないと計算しました。今日では、そのような計算時間はさらに短くなっているので、間違いなく価値があります。

Merkleの認証ツリーは今日でも使用されているということですか?

そうです。実際、Merkleツリーはブロックチェーンの基本的な部分です。メッセージの代わりに、葉ノードにはトランザクションのハッシュが含まれています。

ブロックチェーンとは何かを簡単に見てみましょう。名前がすべてを物語っています:それはブロックの連鎖です。各ブロックは前のブロックへの接続と、数千のトランザクションを葉とするMerkleツリーを含んでいます。

ブロックチェーンの最も一般的な例はビットコインでしょう。「Bitcoin: A Peer-to-Peer Electronic Cash System」という論文は、簡略化された支払い検証の解決策としてMerkleツリーを明確に挙げています。これは、あなたがビットコインを購入していて、それが詐欺ではないことを最初に確認したい場合、ブロックチェーン全体をダウンロードせずに単一のトランザクションを検証できることを意味します。必要なのは関連する認証パスだけです。これはまさに、Bobがツリー全体を保存せずに単一のメッセージを検証するために必要としたものです。

さて、この構造全体が、現在カバーしているハッシュの歴史とどのように関連しているのか疑問に思うかもしれません。問題は、これらの1方向関数 $H$ と $F$ がハッシュ関数であるということです。したがって、Merkleツリーの各ノードは基本的に何らかの値のハッシュを格納しています。これは、ハッシュ関数がパスワードを保護するだけでなく、ストレージを圧倒したり高価になったりすることなく、巨大な構造を認証できることを証明しており、Merkleツリーを暗号化における重要なステップの1つにしています。

私の情報源とさらなる資料:

Ralph Charles Merkleの博士論文「Secrecy, Authentication, and Public Key Systems」
Leslie Lamportによる「Constructing Digital Signatures from a One Way Function」
「Bitcoin: A Peer-to-Peer Electronic Cash System」