読者です 読者をやめる 読者になる 読者になる

Develop with pleasure!

福岡でCloudとかBlockchainとか。

HDウォレット(BIP-32)

長編のBIPで斜め読みしてたので、ちゃんと読んでみる。

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

概要

このBIPでは階層的決定性ウォレット(HDウォレット)について説明する。

この仕様では、異なるクライアント間で交換可能な決定性ウォレットの標準化を目的としている。ここで説明するウォレットにはたくさんの機能があるが、クライアントに全ての機能のサポートを要求するものではない。

仕様は2つのパートで構成される。最初のパートで、単一のシードからキーペアのツリーを導出するためのシステムについて説明する。続くパートで、その構造を使ってウォレットを構築する方法を説明する。

動機

Bitcoin Core(Bitcoinの参照クライアント)は、ランダム生成されたキーを使用する*1トランザクションのブロードキャスト後に毎回鍵のバックアップをするのを避けるため、キーは都度生成されるのではなく、デフォルトで100個のキーが予約キーのプールにキャッシュされるようになっている。そのためこれらを複数のシステムで同時に共有・使用することはできない。またBitcoin Coreではウォレットの暗号化機能を利用しパスワードを共有しないことで秘密鍵を隠すことができるが、こういったウォレットでは公開鍵を生成する機能もない。

決定性ウォレットは、頻繁なバックアップを必要とせず、楕円曲線の特性を利用して秘密鍵を明かすことなく公開鍵を計算することができるスキームを可能にする。このため例えばECサイトを運用する場合、ECサイトのサーバが秘密鍵にアクセスすることなく、決済や顧客毎に新しい支払い用のアドレス(公開鍵のハッシュ)を生成することができるようになる。

ただ決定性ウォレットは、単一のキーペアのチェーンから構成される。チェーンが1つしかないということは、ウォレットを共有することがオール・オア・ナッシングになる。ユースケースによっては、一部の公開鍵だけ共有したいケースもある。ECサイトの場合、サーバはEC事業者のウォレットの全ての公開鍵にアクセスする必然性はなく、顧客の支払いを受け取るために使われるアドレスにのみ適用されればいい。階層的決定性ウォレットは、単一のルートから派生した複数のキーペアチェーンをサポートすることで、このような選択的な鍵の共有を可能にする。

鍵導出の仕様

表記

このBIPで扱うのは、Bitcoinで使われる公開鍵暗号であるsecp256k1を使った楕円曲線暗号をベースとする。またこれから扱う変数は以下のいずれかである。

  • 曲線の位数(nとする)を法とする整数
  • 曲線上の点の座標
  • バイトシーケンス

2つの座標ペアの加算(+)は、ECグループの操作として定義される。連結(||)はバイトシーケンスを別のバイトシーケンスに追加する操作を表す。

スタンダードな変換関数を、以下のように表記する。

  • point(p)
    secp256k1のベースポイントに、整数pを使ってECポイントの乗算をした結果を返す
  • ser32(i)
    32bitのunsigned integer iをシリアライズした先頭4バイトのシーケンス
  • ser256(p)
    整数pをシリアライズした先頭32バイトのシーケンス
  • serP(P)
    SEC1の圧縮形式 (0x02 or 0x03) || ser256(x)を使って座標ペアP=(x, y)をシリアライズしたバイトシーケンス
  • parse256(p)
    32バイトのシーケンスを256bitの数字として解釈する

拡張鍵

↓で親キーからいくつかの子キーを派生させる関数を定義する。その際、キーのみに依存することを避けるため、最初に余分な256 bitのエントロピーを追加して公開鍵と秘密鍵両方を拡張する。chain codeと呼ばれるこの拡張は、秘密鍵と公開鍵のペアに同一のものが使用され、32バイトで構成される。

ここでは拡張した秘密鍵(k, c)と表記する。kは元の秘密鍵で、cchain codeを表す。
拡張した公開鍵も同様に(K, c)と表記し、Kpoint(k)cchain codeを表す。

各拡張鍵は、231個の通常の子キーと231個の強化鍵を持ち、これらの子キーにはそれぞれインデックスがある。通常の子キーはインデックスとして0〜231-1を使用し、強化された子キーは231〜232-1のインデックスを使用する。強化鍵のインデックスの表記を簡単にするため数値iHを使ってi+231と表す。

子キー導出(CKD)関数

親の拡張鍵とインデックスiが与えられると、対応する子拡張鍵を計算することができる。この計算アルゴリズムは、子が強化鍵かどうか(iが231以上かどうか)、対象が秘密鍵か公開鍵によって決まる。

秘密鍵→子秘密鍵の計算

関数 CKDpriv( (kpar, cpar), i) → (ki, ci) で、親拡張秘密鍵から子拡張秘密鍵を計算する。

  • i ≥ 231かどうかチェックする(子が強化鍵かどうかチェックする)
    • 強化鍵の場合は、I = HMAC-SHA512(Key = cpar, Data = 0x00 || ser256(kpar) || ser32(i))を計算する。(0x00は秘密鍵を33バイトの長さにするためのパディング)
    • 通常の子の場合は、I = HMAC-SHA512(Key = cpar, Data = serP(point(kpar)) || ser32(i))を計算する。
  • 計算した I を2つの32バイトのシーケンスに分割する(分割したのをlLとlRとする)
  • parse256(IL) + kpar (mod n)が子鍵 kiとなる。
  • chain code ciは、lRとなる。
  • parse256(IL) ≥ n もしくは ki = 0 となる場合は、その鍵は無効で i を次の値を使って処理を進める必要がある。

HMAC-SHA512関数はRFC 4231で定義されている。

親公開鍵→子公開鍵の計算

関数 CKDpub( (Kpar, cpar), i) → (Ki, ci) で、親拡張公開鍵から子拡張公開鍵を計算する。この関数は強化されていない子キーに対してのみ有効な関数である。

  • i ≥ 231かどうかチェックする(子が強化鍵かどうかチェックする)
    • 強化鍵の場合はfailureを返す
    • 通常の子の場合は、I = HMAC-SHA512(Key = cpar, Data = serP(Kpar) || ser32(i)) を計算する
  • 計算した I を2つの32バイトのシーケンスに分割する(分割したのをlLとlRとする)
  • point(parse256(IL)) + Kparが子鍵Kiとなる。
  • chain code ciは、lRとなる。
  • parse256(IL) ≥ n もしくはKi無限遠点である場合は、その鍵は無効で i を次の値を使って処理を進める必要がある。
秘密鍵→子公開鍵の計算

関数 N( (k, c)) → (K, c)で、拡張秘密鍵に対応する拡張公開鍵を計算する。

  • 返却されるKはpoint(k)
  • 返却されるchain codeは渡されたchain code

秘密鍵から子公開鍵を計算するには↓の2つの方法がある

  • N(CKDpriv( (kpar, cpar), i) )
    秘密鍵から子秘密鍵を生成し、そこから子公開鍵を生成する方法で、常に動作する。
  • CKDpub( N(kpar, cpar), i )
    秘密鍵から親公開鍵を生成し、そこから子公開鍵を生成する方法で、強化されていない子鍵の場合のみ動作する。
親公開鍵→子秘密鍵の計算

この計算は不可能。

鍵ツリー

次のステップでは、いくつかのCKD構成をカスケードしてツリーを構築する。まず1つのルートとなるマスター拡張鍵mを取る。いくつかのi の値についてCKDpriv(m,i)を計算すると、レベル1の派生ノードがいくつかできる。生成されたものは拡張鍵なので、それらについてもCKDprivを適用できる。

表記を簡略化するためCKDpriv(CKDpriv(CKDpriv(m,3H),2),5)をm/3H/2/5と表記する。公開鍵も同様にCKDpub(CKDpub(CKDpub(M,3),2),5)をM/3/2/5と表記する。結果以下は同一のものを指す。

  • N(m/a/b/c) = N(m/a/b)/c = N(m/a)/b/c = N(m)/a/b/c = M/a/b/c
  • N(m/aH/b/c) = N(m/aH/b)/c = N(m/aH)/b/c

ただし、N(m/aH)はN(m)/aHとは書けない。(後者は不可能なので)

ツリーの各リーフノードは、実際の鍵に対応し、内部ノードはツリーの下にある鍵の集合に対応する。リーフノードのchain codeは無視され、埋め込まれた秘密鍵と公開鍵のみが関連を持つ。この構成のため、拡張された秘密鍵を知っていれば、その全ての子・孫秘密鍵とそれに対応する公開鍵を再構成でき、拡張された公開鍵を知っていれば、その全ての強化されていない子・孫公開鍵を再構成できる。

鍵識別子

拡張鍵は、シリアライズされたECDSAの公開鍵KのHash160(SHA256してRIPEMD160した値)によって識別できる。これは従来のBitcoinアドレスで使用されているデータと全く同じである。そのためアドレスとして解釈される可能性があるので、このデータをBase58で表現することは避けた方がいい。

この識別子の最初の32 bitをkey fingerprintと呼ぶ。

リアライゼーションフォーマット

拡張公開鍵と秘密鍵は以下のフォーマットでシリアライズされる。

バイト数 内容
4 version bytes。mainnetの場合は公開鍵が0x0488B21E秘密鍵0x0488ADE4、 testnetの場合は公開鍵が0x043587CF秘密鍵0x04358394
1 ツリーの深さ。マスターノードが0x00で、レベル1の派生鍵は0x01
4 親鍵のfingerprint(マスター鍵の場合は0x00000000を使用)
4 子の番号で、xi = xpar/iにおけるiのser32(i)。xiはキーがシリアライズされたもの。(マスター鍵の場合は0x00000000を使用)
32 chain code
33 公開鍵または秘密鍵のデータ(公開鍵の場合はserP(K)、秘密鍵の場合は 0x00 || ser256(k))

この78バイトの構造に32bitのチェックサムを追加し、その後Base58でエンコードされ、最大112文字のデータが生成される。選択したversion bytesによってBase58エンコードした値はmainnetの場合はxpubもしくはxprvで始まり、testnetの場合はtpubもしくはtprvで始まる。

親のfingerprintはソフトウェア内で親ノードと子ノードを高速に検出するためのものなので、衝突についてはソフトウェア側で考慮する必要がある。内部的には完全な160 bitの識別子を使用可能。

シリアライズされた公開鍵をインポートする際は、公開鍵データ内のX座標が楕円曲線上のポイントとして存在するかどうか検証する必要がある。もし楕円曲線上のポイントではない場合、その拡張公開鍵は無効である。

マスター鍵の生成

生成可能な拡張鍵ペアの総数は2512だが、生成される鍵は256bit長で、セキュリティの観点から約半分になっている。そのためマスター鍵は直接生成されるのではなく、短いシード値から生成される。

  1. (P)RNGから選択された長さ(128 bit から512 bitの間で、256 bitが推奨される)のシードのバイトシーケンスSを生成する。
  2. I = HMAC-SHA512(Key = “Bitcoin seed”, Data = S)を計算する。
  3. 計算した I を2つの32バイトのシーケンスに分割する(分割したのをlLとlRとする)
  4. parse256(IL)がマスター秘密鍵で、IRmaster chain codeとなる。

IL=0、もしくはIL ≥ n の場合、そのマスター鍵は無効。

https://github.com/bitcoin/bips/raw/master/bip-0032/derivation.png

ウォレットの構造の仕様

↑のセクションでは、鍵ツリーとそのノードについて定義したので、次のステップではウォレットにこのツリー構造を取り込む。このセクションで定義されているレイアウトはデフォルトであり、クライアントは互換性のためこのレイアウトを模倣することが推奨されるが、全ての機能がサポートされるわけではない。

デフォルトのウォレットレイアウト

HDW(HDウォレット)はいくつかのアカウントで編成されている。アカウントにはそれぞれ番号が付けられており、デフォルトアカウント"“の番号は0になる。クライアントは必ずしも複数のアカウントをサポートする必要はなく、その場合デフォルトアカウントのみを使う。

各アカウントはinternalとexternalの2つのキーペアチェーンで構成されている。externalキーチェーンは(Bitcoinの受け取り用に)新しい公開アドレスを生成するために使われ、internalキーチェーンはその他の全ての操作(おつり用アドレスや、世代アドレスなど生成)で使われる。こういった分離されたキーチェーンをサポートしていないクライアントは、externalキーチェーンのみを使用して全ての操作をする必要がある。

  • m/iH/0/kはマスター鍵mから派生したHDWのアカウント番号 i のexternalチェーンのk番目のキーペアを表す。
  • m/iH/1/kはスター鍵mから派生したHDWのアカウント番号 i のinternalチェーンのk番目のキーペアを表す。

ユースケース

完全ウォレット共有:m

2つのシステムが単一の共有ウォレットにアクセスする必要があり、どちらのシステムもBitcoinの支払いが行える必要がある場合は、マスター拡張秘密鍵を共有する必要がある。

ノードは入金を監視するため、externalチェーン用にキャッシュされたN個のlook-ahead keysを保持することができる。このユースケースでは予想されるギャップは無いので、internalチェーンのlook-aheadは非常に小さくすることができる。新しいアカウントの作成時に、未使用のアカウントチェーンに対し確保されているlook-aheadが有効になる。なお、アカウント名はブロックチェーンを介して同期できないので、手動で入力する必要がある。

監査: N(m/*)

監査ノードが入金と出金のリストにフルアクセスする必要がある場合は、全てアカウントの拡張公開鍵を共有する。これにより監査ノードは全てのアカウントの入りと出のトランザクションを参照できる。ただし、秘密鍵は参照できない。

オフィス毎の残高:m/iH

複数の独立したオフィスがある場合は、単一のマスターから派生したウォレットを使用する。これにより本社は、全てのオフィスの全ての入りと出のトランザクションを参照でき、オフィス間の資金移動も可能なスーパーウォレットを保持することになる。

定期的なB2B取引: N(m/iH/0)

取引先間において頻繁に資金を送ることがある場合は、一方の特定のアカウント(M/i h/0)のexternalチェーンの拡張公開鍵をスーパーアドレスの一種として利用することで、支払い毎に支払先の新しいアドレスを要求することなく頻繁に取引することができる。このような仕組みは、可変支払いアドレスとしてマイニングプールのオペレータが使うこともできる。

セキュリティに依存しない資金の受け取り: N(m/iH/0)

Webサーバ上でECサイトを運営している場合、支払いを受け取るための公開アドレスを知る必要がある。(セキュリティに気をつけていても脆弱性のリスクなどはあるので)Webサーバには単一のアカウントのexternalチェーンの拡張公開鍵のみを配置する。これによりWebサーバの脆弱性をついて誰かが侵入したとしても、全ての入金を見ることはできるが資金を盗むことはできないし、サーバが複数台ある場合他のWebサーバが受け取った支払いを見ることもできない。

互換性

この標準に準拠するには、クライアントは少なくとも拡張公開鍵もしくは拡張秘密鍵をインポートできなければならない。仕様の第2部に記載しているウォレットの構造(master/account/chain/subchain)についてはアドバイザリーという位置付けではあるが、(クライアントの機能としてアカウントが分離されていなかったり、internalとexternalチェーンに区別が無かったとしても)互換性のための最小限の構成として推奨する。しかし実際の実装では特定のニーズに合わせて逸脱することがある。より複雑なアプリケーションでは、より複雑なツリー構造が必要になることもある。

セキュリティ

↓の楕円曲線公開鍵暗号自体の特性に加え

  • 公開鍵Kが与えられたとして、攻撃者は楕円曲線の離散対数問題を解く以外に効率的に対応する秘密鍵を見つけることはできない。

この規格の意図するセキュリティ特性は以下の通り

  • 子の拡張秘密鍵(Ki, ci)と整数 i が与えられたとして、攻撃者は2256のHMAC-SHA512のブルートフォースよりも効率的に親の秘密鍵kparを見つけることはできない。
  • インデックスと拡張秘密鍵からなるタプル(ij,(kij,cij))の任意の数(2 ≤ N ≤ 232-1)が与えられたとして、ijが異なる際、それらが共通の親拡張秘密鍵から派生したものか判定するには、2256のHMAC-SHA512のブルートフォースより効率的な方法はない。

しかし、以下のような特性もある。

  • 親の拡張公開鍵(Kpar,cpar)と子の公開鍵(Ki)が与えられると、i を見つけるのは困難ではない。
  • 親の拡張公開鍵(Kpar,cpar)と強化されていない子の秘密鍵(ki)が与えられると、親の秘密鍵kparを見つけるのは困難ではない。

注意事項

秘密鍵と公開鍵は今までと同様、安全に保持する必要がある。秘密鍵の漏洩はコインへのアクセスを意味し、公開鍵の漏洩はプライバシーの喪失を意味する。

拡張鍵については、そのサブツリーの鍵に対応するためいくつか注意する必要がある。

1つの弱点は、親の拡張公開鍵と強化されていない子の秘密鍵が分かれば、親の拡張秘密鍵を知ることができるという点である(親の拡張秘密鍵が知られるということは、そのサブツリーの公開鍵及び秘密鍵が全て知られてしまうことになる)。これは拡張公開鍵は通常の公開鍵より慎重に扱わなければならないことを意味する。またこれは強化鍵が存在しツリーのアカウントレベルで使用される理由でもある。強化鍵を使うとアカウント固有の秘密鍵の漏洩が、マスターまたは他のアカウントに及ぶことはない。

Test Vectors

BIP参照

実装

Pythonの実装

Javaの実装

C++の実装

Objective-Cの実装

Rubyの実装

Goの実装

JavaScriptの実装

PHPの実装

C#の実装

Haskellの実装

bitcoin-rubyに実装してみた

github.com

プルリク出した後に、実は以前実装中ものがあったらしく、↑が取り込まれるかどうかは不明。

*1:Bitcoin Coreも0.13.0からHDウォレットをサポートした