Ed25519で決定論的な鍵導出をサポートするBIP32-Ed25519

Bitcoinのウォレットなどが、単一のマスターシードから多数の鍵ペアを決定論的に導出する仕様を定義したのがBIP-32↓

techmedia-think.hatenablog.com

これは、Bitcoinが採用している楕円曲線secp256k1とECDSAを前提に作られた仕様になる。

これに対して、EdDSA（Edwards-Curveデジタル署名アルゴリズム）の一種であるEd25519においても、BIP32と同様の決定論的な鍵導出を可能にする提案の１つがBIP32-Ed25519↓

https://raw.githubusercontent.com/LedgerHQ/orakolo/master/papers/Ed25519_BIP%20Final.pdf

Ed25519

Ed25519は鍵の導出方法がsecp256k1と異なり、これがBIP-32をそのまま利用できない原因でもある。

鍵生成

Ed25519は以下の手順で秘密鍵と公開鍵を生成する。

秘密鍵は、32バイトのランダム値で、これをxとする。公開鍵はこの秘密鍵を使って以下のように計算される。Gを曲線のベースポイント、nを曲線の位数とする。

SHA-512を使って秘密鍵をハッシュし、その値を ${k = H_{512}(x)}$ とする。
kの下位32バイトを ${k_L}$ とし、上位32バイトを ${k_R}$ とする。公開鍵の導出に使用するのは、 ${k_L}$ のみ。
のデータに対して以下を行う。
- 先頭バイトの下位3 bitをクリアする。
- 最終バイトの最上位bitをクリアする。
- 最終バイトの最上位から２つめのbitをセットする。
3のデータをリトルエンディアンで整数として解釈してスカラー値sとする。
Gに対してスカラー値sをスカラー倍算する（sG）。
公開鍵Pは点sGをエンコードしたもの。sGのy座標を32バイトのリトルエンディアンのバイト列としてエンコードする。最終バイトの最上位bitは常に0で、x座標の最下位bitを最終バイトの最上位bitにコピーする。

こうして生成されたのが公開鍵になる。

秘密鍵からSHA-512で64バイトのハッシュしたけど、半分の ${k_R}$ 使ってないじゃん？って思うけど、これは署名生成の際に使用される。

署名生成

メッセージMと公開鍵Pに対する署名は以下のように作成される。Schnorr署名の一種なので、基本的にはSchnorr署名の計算。

${H_{512}(k_R || M)}$ を計算し、結果をリトルエンディアンの整数rとして解釈する（なお、 ${ r = r \mod n}$ ）。
R = rGを計算する。
${h = H_{512}(R || P ||M)}$ を計算し、64バイトのダイジェストをリトルエンディアンの整数として解釈する。
${s = (r + h \cdot k_L) \mod n}$ を計算する。
R || sが署名データ

Schnorr署名と違うのは、Schnorrがnonceの選択に乱数を使うのに対し、Ed25519は、 ${k_L}$ とメッセージMのハッシュからnonceを生成している。そのため署名生成に乱数を必要としない。

署名検証

R || sおよび、P、Mが与えられた検証者は、以下の検証を行うことで署名の有効性をチェックする。

${h = H_{512}(R || P ||M)}$ を計算し、64バイトのダイジェストをリトルエンディアンの整数として解釈する。
${8sG = 8R + 8h \cdot A}$ が成立するか検証する（Ed25519のco-factorが8であるため）。

BIP32採用の問題

secp256k1のECDSAの場合、秘密鍵xに対応する公開鍵は、単純にベースポイントに対してスカラー倍算したP = xG。公開鍵Pに対してQ = yGを加算した公開鍵Z = P + Qを導出すると、Zに対応する秘密鍵は x + yになるという特性がある。

そのため、公開鍵から新しい公開鍵を導出することができ、元の公開鍵に対応する秘密鍵を知っていれば、導出した公開鍵の秘密鍵を知ることができる。なので、オンラインのECサイトには公開鍵だけ置いといて、支払いの度に新しい支払いアドレスを導出し、秘密鍵はオフラインで管理し、必要な場合に対象の秘密鍵を計算して利用するといったユースケースが可能になる。

これに対し、Ed25519の場合、公開鍵は秘密鍵のSHA-512ハッシュ値の下位32バイトを細工して出来た値をスカラー倍算した値になるため、↑のような特性がない。これがEd25519にBIP-32をそのまま採用できない理由。

BIP32-Ed25519

ただ、Bitcoinみたいに1人のユーザーやシステムが多数の公開鍵を使用するようなケースなど、同じシードから鍵やIDを多数生成したい場合、BIP-32のような決定論的な鍵導出スキームの需要がある。Ed25519でもBIP-32を少し変更することで、これに対応したのがBIP32-Ed25519。

ルート鍵

まず、ランダムに選択した32バイトのマスターシークレットをxとする。

SHA-512を使ってマスターシークレットをハッシュし、その値を ${k = H_{512}(x)}$ とする。
kの下位32バイトを ${k_L}$ とし、上位32バイトを ${k_R}$ とする。 ${k_L}$ の最終バイトの最上位３つめのbitがゼロでない場合、マスターシークレットを廃棄してやり直す。
のデータに対して以下を行う。
- 先頭バイトの下位3 bitをクリアする。
- 最終バイトの最上位bitをクリアする。
- 最終バイトの最上位から２つめのbitをセットする。
得られた ${(k_L, k_R)}$ のペアを拡張ルート秘密鍵とし、 ${P = k_LG}$ をルート公開鍵とする。

鍵の導出手順から分かるように、拡張ルート秘密鍵とルート公開鍵は、Ed25519と鍵としても使えるもの。

そしてBIP-32のルートチェーンコードを ${c = H_{256}(0x01 || k)}$ とする。

子鍵

ルート鍵は、 ${2^{32}}$ 個の子鍵（インデックス $i \in 0..{2^{32} - 1}$ ）を持つ。

子秘密鍵の導出

親のチェーンコードを ${c^{P}}$ 、拡張秘密鍵を ${k^{P} = (k^{P}_L, k^{P}_R)}$ 、公開鍵を ${P^{P}}$ とした場合、i番目の拡張秘密鍵は以下のように計算される。

インデックスに応じて、チェーンコードをHMACの鍵として、以下の計算を行う：
- ${i \lt 2^{31}}$ の場合
  ${Z = HMAC(0x02 || P^{P} || i, c^{P})}$
- ${i \ge 2^{31}}$ の場合
  ${Z = HMAC(0x00 || k^{P} || i, c^{P})}$
Zの左28バイトを ${Z_L}$ 、右32バイトを ${Z_R}$ とする。
子の拡張秘密鍵を ${k_L = 8Z_L + k^{P}_L}$ とし、 ${k_R = (Z_R + k_R^{P}) \mod 2^{256}}$ とする。 ${k_L}$ が位数nで割り切れる場合、その子は破棄する。
子のチェーンコードは、
- ${i \lt 2^{31}}$ の場合
  ${c_i = HMAC_{512}(0x03 || P^{P} ||i, c^{P})}$
- ${i \ge 2^{31}}$ の場合
  ${c_i = HMAC(0x01 || k^{P} || i, c^{P})}$

そして、対応する子どもの公開鍵は ${P_i = k_LG}$ 。

※ ${Z_L}$ だけ28バイトにトリムしているのは、子の ${k_L}$ の最終バイトの最上位2 bitめが常に1であることを保証するためらしい。

子公開鍵の導出

↑の子秘密鍵の場合と同じようにZを計算する。そのため、BIP32と同様、 ${i \ge 2^{31}}$ の強化導出の場合、親の拡張秘密鍵を知らないと導出できない。
${P_i = P^{P} + 8Z_LG}$ を計算する。
↑の子秘密鍵と同様に子のチェーンコードを算出する。

↑からBIP32-Ed25519では、本来の鍵xではなく、拡張秘密鍵 ${k = (k_L, k_R)}$ を使って鍵導出をしている。公開鍵を親の ${k_L}$ に対して加算処理をすることで、親密鍵→子秘密鍵（子公開鍵）、親公開鍵→子公開鍵（親の公開鍵は ${k_LG}$ で既知であるため）の導出をできるようにしていることが分かる。