zk-STARKでBIP-32シードの知識を証明して量子脆弱なコインを救済する仕組み

将来、既存の楕円曲線ベースの鍵など量子脆弱な鍵を用いた支払いが禁止された場合に、そこにロックされた資金を量子脆弱な鍵を導出したBIP-32（HDウォレット）の知識の証明を提供することでリカバリーできるようにする提案を、先日Olaoluwa Osuntokun（Roasbeef）が実際に実証した↓

https://groups.google.com/g/bitcoindev/c/Q06piCEJhkI

背景となる問題

量子コンピュータが secp256k1 の離散対数問題を解けるようになった場合、公開鍵が露出している UTXO はすべて危険にさらされる。

Taprootのアウトプットは、ロックスクリプトがそのまま公開鍵なのでこれに該当し、将来的にはソフトフォークでTaprootのkey-pathを無効化してscript-pathのみをサポートすることが考えられる。

一方、↓のようにBIP-32のシードからTaproot用の鍵導出をして、script-pathは使用しない（スクリプトツリーが空）パターンのUTXOの場合、上記のソフトフォークが行われるとこれらのアウトプットにロックされたコインはすべてロックされてしまう。

techmedia-think.hatenablog.com

※ もちろん、script-pathを使っていたとしても、そこに量子耐性のあるデジタル署名スキームがなければ、高速な量子コンピューターに侵害される可能性は残る。

zk-STARKでシードの知識を証明するリカバリーアプローチ

Roasbeefが提案するアプローチは、以下の関係を証明するもの。

${\mathcal{R} = \left\{\, (K, C;\, s, \mathbf{p}) \;\middle|\; \begin{aligned} K &= \text{BIP86Taproot}(\text{BIP32Derive}(s, \mathbf{p})) \\ C &= \text{SHA256}(\texttt{"bip32-pq-zkp:path:v1"} \,\|\, \mathbf{p}) \end{aligned} \,\right\}}$

ここで、

Kは、Taprootのアウトプットの公開鍵で誰でもオンチェーンで確認できる公開情報
Cは、導出パスpへのコミットメント（先頭の"bip32-pq-zkp:path:v1"はドメイン分離のためのタグ付きハッシュ）
sは、BIP32のシード
pは、BIP-86の導出パス（例：m/86'/0'/0'/0/5）

証明者はオンチェーンのTaprootアウトプットKに対して、それが自分のBIP-32シードからBIP-86導出経由で生成されたものであることを、zk-STARKを用いてsとpを明かすことなく証明する。そしてその有効な証明がある場合のみ、量子脆弱なコインのリカバリーを許可するソフトフォークを行おうという提案。

どうして量子安全なのか？

量子攻撃者がこのリカバリースキームを攻撃するためには、上記の有効な証明を作成する必要がある。量子コンピューターで公開鍵Kの秘密鍵を導出することができたとしても、BIP-32の導出ロジックがネックになる。

まず、攻撃者は公開鍵Kの秘密鍵を知れても、HDウォレットのシードは知らず、秘密鍵から逆算することはできない。そのため、証明を偽造する必要がある。BIP-32では、128〜512 bitのシードsについてHMAC-SHA512("Bitcoin seed", s)を実行してマスター拡張秘密鍵を導出する。証明の偽造のためには別のシードs'を使って同じマスター鍵を導出する必要がある。つまり、HMAC-SHA512の衝突を見つける必要があり、これは量子コンピューターでも効率的に解くことはできない。

このアプローチでは、BIP-32でウォレットを生成した事実が、量子攻撃者でも再構成できない秘密として機能する。

なお、アプローチではBIP-86が取り上げられているけど、BIP-32経由で導出された任意の鍵で同じ理屈が成立する。再利用済みのP2(W)PKHや、スクリプト内に公開鍵が埋めこまれたP2(W)SHでも、内部で同様の関係を証明する回路を組めば救済自体は可能だろう。

一方で、BIP-32以前に単純な乱数から生成した鍵については、上記のような構造上の秘密が存在しないので救済できない。

zk-STARK

このアプローチで採用されているのはzk-STARK。実証では、以下のスタックを使用している模様：

tinygo-zkvm：TinyGoをforkして、risc0が要求するrv32im(32-bit RISC-V + 整数乗除算)ターゲットriscv32-unknown-noneを追加
risc0：STARKベースのzkVM。RISC-V ELFを実行し、その実行トレースに対してSTARK proofを生成。
go-zkvm：RISC-V ELFを risc0のR0BF形式にパッケージし、Rust製のホストとC FFI経由で連携して証明を生成
bip32-pq-zkp：BIP-32+BIP-86の関係Rを判定するゲストプログラム本体

ゲストプログラムは秘密の入力としてsとpを受け取り、HMAC-SHA512でマスター鍵を導出し、パスpに従ってCKDpriv/CKDpubを実行し、最後にBIP-86のQ = P + SHA256("TapTweak" || P) · G を計算してQのx座標をジャーナルに書き出す。同時にCも計算してジャーナルに書き出す。risc0はこのプログラムが正常終了したという事実そのものをSTARKで証明するので、ジャーナルに書かれた(K, C)に対応する witness (s, p) が存在することが暗号的に保証される。