こんにちは。AndGoの代表をしております @ToshihideHara です。
本日より技術ブログをはじめてみようと思います。
さてさて、初回は超マニアックどころの閾値ECDSAについてとりあげたいと思います。
閾値ECDSAといえば、FireblocksのMPCウォレットが有名ですね。
ということで、本日はそのへんの深堀りです。
CGGMP21方式について
Fireblocksのウォレットは、CGGMP21で提案された閾値ECDSAを実装し、サービスとしては3-of-3 にパラメータを固定したものを提供しています。
CGGMP21: https://eprint.iacr.org/2021/060
３プレイヤーがそれぞれ保有する３つのシェアにて部分署名を行う事で、最終的な署名ができあがるよ、というスキームになります。イーサリアムのようにオンチェーンレベルでマルチシグに対応していないチェーンであっても、複数プレイヤーによる署名でもってブロックチェーンの認識する署名付トランザクションをつくれます。チェーンを問わずに多者による認可、というワークフローを実現できるのは魅力的ですね。
なお、元論文では閾値、シェア数を3-of-3とは固定してませんので、なにかしらサービスレイヤ側での事情の結果としてこうなっているんだと思います。
では、実際の実装ではどうなっているか気になるなあ、ということで調べてみました。
実装系について
CGGMP21 の実装系は、Fireblocksを含め、複数の会社がオープンソースとして提供しています。
自分の知っているところとしては、主要どころとしてつぎの２つがあります。
Fireblocks-MPC
提供者: Fireblocks
リポジトリ: https://github.com/fireblocks/mpc-lib
ライセンス: GPL-3.0
主な特徴
- 閾値ECDSAを実装している
- 元論文にあるオンライン、オフライン手法の両方が実装されている
- Key-Refreshが実装されている
- 閾値パラメータが3-of-3 に固定されている
- 閾値EdDSAも実装されている
- 監査を受けている
- C++言語製
multi-party-sig
提供者: Adrian Hamelink and Taurus SA
リポジトリ: https://github.com/taurusgroup/multi-party-sig
ライセンス: Apache-2.0
主な特徴
- 閾値ECDSAを実装している
- BIP32鍵導出への対応を正式にうたっている
- Key-Refreshが実装されている
- 閾値シュノア署名（FROST プロトコル）も実装されている（ビットコインのTaproot用！）
- 定数時間演算
- フォーク実装が監査を受けている
- Go言語製
TaurusのほうはApacheライセンスなので使い勝手がよさそうですが、コード監査を受けていないのは気になりますね。
補足しておきますと、multisig-labsによるフォーク実装がKudelski Securityにより監査を受けているようです。
https://github.com/taurusgroup/multi-party-sig/issues/103
気になる方はこちらを参照のこと。
Key-Refreshについて
さて、いきなりマニアックな話題となりますが、CGGMP21の特徴のひとつとして、Key-Refresh という機構を搭載していることがあげられます。
Key-Refreshの特徴
1.シェアセットをもとに、おなじ公開鍵に紐付く新しいシェアセットを安全に生成する
2.元シェアセットと新シェアセットとは独立しており、混ぜることはできない
特徴1について
この特徴から、予めシェアセットを複数用意しておくことで、シェアを保有する署名器の故障、紛失時にダウンタイムを最小とする運用を行えそうです。
一方、新シェアセットの作成には、元とするシェアセットが必要になります。そのため、"予め用意する"という、タイミング的な制約があります。
特徴2について
元シェアセット(1A,1B,1C)から新シェアセット(2A,2B,2C)を作成した場合、
例えば(1A,1B,2C)の組合わせは機能しない、ということになります。
そのため、元シェアセットの一部の紛失に気付いた場合であっても、まるごと新セットに移行させる必要があります。
Key-RefreshとBIP32鍵導出との関係について
さてさて、ウォレットの実装に関わったことがある方からすると、HDウォレットにおける鍵導出とKey-Refreshとの関係が気になりますね（えっ、そんなことない？）。
ビットコインを筆頭に、ニーモニック（リカバリーフレーズ）を扱っているウォレットは基本的にはBIP32/BIP44規格に従った鍵導出でもって秘密鍵・公開鍵を生成しています。
BIP32における鍵導出とは、(シード, 導出パス) から秘密鍵を階層決定的に生成する手法を標準化したものです [https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki]。
木の根元がシード（元とする乱数）であり、そこから枝が分岐していって、節にあたる部分と葉にあたる部分とが秘密鍵になる、といった手法になります。
これの何がうれしいかというと、たくさんの秘密鍵を１つのシードだけで管理できちゃう点です。シードをニーモニックという単語リストにてバックアップしちゃえばよい分けです。運用が圧倒的に楽になりますね。
閾値ECDSAはここ数年の最新テクニックであることから、このBIP32規格が策定されたときには閾値署名のことなんてまったく考えられていませんでした。
この導出の際には、SHA512ハッシュ関数を利用したHMACを利用しています。
そのため、同様の方法をシェアに適用してしまうと、いかにも準同型性が破綻して閾値署名なんかできないのでは、という気がします。
というのも、CGGMP21では加法準同型暗号を用いているからです。
加法準同型暗号とは、次の性質を満たすものです [https://eprint.iacr.org/2020/1390]。
元データをそれぞれ暗号化してから加算すると、元データを加算してから暗号化した結果と一致するという魔法のようなことが実現できます。
CGGMP21では、この性質をうまく利用することで高効率なMPCによる閾値署名を実現しています。
Enc(SHA512(m)) != SHA512(Enc(m))
なのは自明ですので、ハッシュ関数とこうした準同型暗号とはいかにも相性が悪そうです。
そこで、改めてBIP32規格を丁寧に読んでみますと、じつはSHA512ハッシュ関数は関係ないことが分かります（正確にはhardenedな操作はやはり厳しい）。
まず、ECDSAの鍵ペア(k, K)は次のように表されます。
K = kG: 楕円曲線上の点 (公開鍵)
ここで、Gは楕円曲線のベースポイント(generator)です。
加法的鍵導出(AKD)では、新しい鍵ペア(k', K')を次のように導出します。
j: ランダムなスカラー値
J = jG: 楕円曲線上の点
k' = k + j
K' = K + J = kG + jG = (k+j)G
ここで線形代数の基本概念が登場します。楕円曲線上の点に対するスカラー倍算は、線形性を持っています。つまり、
(a + b)G = aG + bG
が成り立ちます。この性質により、K' = (k+j)Gが導かれます。
閾値ECDSAでは、秘密鍵kが複数のパーティに分散されています。各パーティはkの一部分([k])のみを知っています。AKDを適用する際も、各パーティが自身の分散鍵[k]に対してランダムなスカラー値[j]を加えることで、新しい分散鍵[k']を得ることができます。
[k'] = [k] + [j]
[K'] = [K] + [J] = [k]G + [j]G = ([k]+[j])G
各パーティは[k']を用いて部分署名を生成し、それらを集約することで、新しい鍵ペア(k', K')に対する有効な署名を得ることができます。
以上のように、楕円曲線上のスカラー倍算の線形性を利用することで、閾値ECDSAにおいても加法的鍵導出が可能になっています。各パーティが秘密鍵全体を知ることなく、新しい鍵ペアを協調して導出できるということですね。
さてさて、BIP32はAKDの一種です。
BIP32では、親鍵から子鍵を導出する際に、親秘密鍵に対してチェーンコードから計算されるスカラー値を加算することで、子秘密鍵を得ています。
具体的には、以下のようなステップで子鍵が導出されます。
1. 親秘密鍵(k_par)とチェーンコード(c_par)から、HMACを用いて子鍵のためのスカラー値(j)を計算
2. 子秘密鍵を k_child = k_par + j として導出
3. 子公開鍵を K_child = K_par + jG として導出
ここで、親公開鍵(K_par)は親秘密鍵(k_par)のスカラー倍算で得られます。
これは、先に説明したAKDの一般的な形式とほぼ同じです。唯一の違いは、AKDではランダムなスカラー値(j)を使うのに対し、BIP32ではチェーンコードから決定論的にjを導出している点です。
以上より、実はハッシュ関数はスカラー値の計算に用いているだけであることが分かりました。
また、子秘密鍵、子公開鍵は加算で導出しています。おお、加法準同型性が生きるぞ！
ということで、Key-RefreshはBIP32鍵導出と組合わせることもできそうです。
