Hierarchy Deterministic Wallet（階層的決定性ウォレット）。

ビットコインなどの暗号通貨で使用されているアドレスはECDSA（Elliptic Curve Digital Signature Algorithm、楕円曲線電子署名アルゴリズム）の公開鍵である。昔は単にアドレスが必要になる度に乱数を生成して秘密鍵とし、対応する公開鍵を導出していた。コインを受け取るために明示的にアドレスを作成する場合はもちろん、たいていは、プライバシーのために、送金時のお釣りは元のアドレスに戻すのではなく新規にお釣り用アドレスが作成される。生成した秘密鍵はその都度バックアップしておかないとディスクがクラッシュしたらコインが失われる（さすがにそれでは不便なので、Bitcoin Coreではまとめて100個のアドレスを生成する。実際は100個ごとのバックアップで良い）。また、数が増えてくると紙などのアナログな手段でバックアップするのは現実的ではなく、ファイルとして保存することになる。

最近のクライアントではHDウォレットというものが用いられている。1個の乱数からツリー状に多数のアドレスを生成できる。何らかのウォレットを使い始めたときに「この単語をメモしておけ」と12個の単語（mnemonic phrase）が出てくる。これがルートの乱数。これならばバックアップするのはルートの乱数のみで良いし、アナログな手段でもバックアップできる。

ツリー状にアドレスを生成するだけならば、何らかのルールを決めるだけの話である。が、「あるノード以下のアドレス（公開鍵）の生成は他人に任せるけれど、そのアドレスからコインを引き出せる（秘密鍵を知っている）のは自分だけ」ということが、HDウォレットを使うとできると知った。どのようにして実現しているのかが気になってHDウォレットの仕様（BIP）を読んでみたら、ECDSAを上手く使っていて面白かった。普通に考えると、まず秘密鍵を作り秘密鍵から公開鍵を導出するので、そのようなことは不可能に思える。

ECDSA

楕円曲線DSA - Wikipedia

ECDSAにおいて、秘密鍵は整数$k$であり、公開鍵は楕円曲線上の点$K=kG=(x, y)$である。楕円曲線もベースポイント$G$も固定の値。ビットコインが使用しているsecp256k1のそれぞれの値は、ここに載っている。楕円曲線暗号では楕円曲線上の点の加算が定義されている。$k$個の$G$を足し合わせるとして、乗算$kG$も定義される。実際に$k$回足し合わせなくても、バイナリ法で$O(\log k)$で計算できる。一方、$kG$と$G$から現実的な時間で$k$を求めることはできない。

HDウォレット

bips/bip-0032.mediawiki at master · bitcoin/bips

HDウォレットでは、親のノードの秘密鍵や公開鍵と「チェインコード」と呼ばれる整数、子ノードのインデックス（その親の何番目の子か）を元に、子ノードの秘密鍵や公開鍵とチェインコードを作る。親ノードの秘密鍵を$k_{par}$、チェインコードを$c_{par}$、インデックスを$i$とする。親ノードの公開鍵は$k_{par}G$となる。$k_{par}G$、$c_{par}$、$i$をハッシュ関数に通して、整数$l$を得る。$l$を上位ビット$l_L$と$l_R$に分けて、$k_i=l_L+k_{par}$を子ノードの秘密鍵、$c_i=l_R$を子ノードのチェインコードとする。チェインコードは親ノードの公開鍵とチェインコードを知っていれば導出できることが分かる。

問題は公開鍵。親の公開鍵$k_{par}G$しか知らなくても$l_L$は計算できるが、秘密鍵を得るためには親の秘密鍵が必要。公開鍵しか知らない場合、子ノードの公開鍵は$l_LG+k_{par}G$として求める。分配法則が成り立つので、$l_LG+k_{par}G=(l_L+k_{par})G=k_{i}G$となる。面白い。

赤線は逆算できないところ。

一つ問題があって、子の秘密鍵を知っていると$k_i=l_L+k_{par}$から親の秘密鍵が求められてしまう。さらに遡ったり兄弟の秘密鍵を求めることもできる。そこで、強化鍵（hardened key）という仕様もあって、親の公開鍵だけから子の公開鍵を計算できるという特徴を無くす代わりに、親の秘密鍵を求められないようにすることもできる。