前回までにOTSとFTSを見てきました。 次は，ハッシュ関数に基づいた実用的な署名体系はどのようにして構築されるかを見ていきたいと思います。 多くの回数使うことが出来て，理想的には何回も使うことができる署名方式です。

Dumb木

最初に考えられるのはOTSを束にして使うことです（OTSは自分が使いたいもの）。 初めて署名する場合は，最初のOTS鍵ペアを使用し，二度とと使ってはいけません。二回目に何かに署名したい場合は，二番目のOTS鍵ペアを使用し，それもまた二度と使ってはいけません。これを繰り返すと最終的にどうなるかはよくわかると思います。公開鍵はすべてのOTS公開鍵で構成されるため，とても悪いことになるでしょう（その署名方式をたくさん使用することにしたい場合，かなり多くのOTS公開鍵を持つことになります）。

秘密鍵の記憶量を減らす一つの方法は，秘密鍵を生成するための疑似乱数生成器でシードをしようすることです。この方法では，秘密鍵を保存する必要はなく，必要なのはシードのみです。

しかしこれでも，公開鍵が大きくなりすぎるので実用的ではありません。

Merkle木

OTS公開鍵すべてを，一つのメインの公開鍵にリンクする非常に簡単な方法が一つあります。それはMerkle木を利用することです。これはMerkleによって1979年に考案された解決策で，発表はその10年後でした。

簡単に定義すると次のようになります。 Merkle木は，すべてのノードがその子ノードのハッシュであり，ルートが公開鍵であり，葉がOTS公開鍵のハッシュである基本的な２分木です。

最初にこの木を使って何かに署名するとしましょう。 最初のOTS公開鍵(A)を使用し，それを二度と使いません。次にBのOTS公開鍵，次にCの，最後にDのOTS公開鍵を使用します。したがってこの木では，合計4つのメッセージに署名することができます。木が大きければ，より多くのメッセージに署名することができるのがわかりますね。

これの良いところは，公開鍵が木のルートのみで構成されていて，何かに署名するたびにその署名が少数のハッシュで構成されていることです。これが認証パスとなります。

この例では，OTS鍵(A)による署名は（\(1\)，署名，公開鍵A，認証パス）となります。

  • 1は署名の葉の\({\it 番号}\)です。繰り返して覚えておかなければいけないことは，葉のOTSを二度と使ってはいけないことです。このことが署名方式をステーフルにします。
  • \({\it 署名}\)はOTSの公開された秘密鍵です。
  • \({\it 公開鍵}\)は，署名を検証するためのOTS公開鍵です。
  • \({\it 認証パス}\)は，ルート（主となる公開鍵）を再計算することを可能にするノードのリスト（ハッシュのリスト）です。

認証パスについて考えてみます。 前の例を取り上げると，最初のOTS鍵(A)で何かを署名した後の認証パスがハイライトされています。

OTS公開鍵と二つのハッシュ（Aの葉からルートまでの経路にあるすべての隣接ノード）とで，主となる公開鍵を計算できることが分かります。したがって，これが実際に，その主となる公開鍵に由来する署名であることを検証することができます。

このテクニックのおかげで，私たちは，主となる公開鍵を検証するために全てのOTS公開鍵を知る必要はありません。これにより，空間も時間も節約されることになります。

以上がMerkleの署名方式の簡単なイメージです。