FROST用の分散鍵生成プロトコルChillDKG

少し前に、Schnorrベースの閾値署名スキームFROST用にChillDKGという分散鍵生成スキームのBIPドラフトが発表された↓

https://github.com/BlockstreamResearch/bip-frost-dkg

FROSTはShcnorrベースの閾値（t-of-n）のマルチシグに対応した署名スキームだけど、FROSTでマルチシグをセットアップする際に必要なのが鍵生成処理。単独のユーザーがバックアップ目的で閾値マルチシグをセットアップする場合は単純で、ベースとなる秘密鍵をそのユーザーが知っている状態で鍵を生成し、その秘密鍵を元にシャミアの秘密分散法などを用いてシェアを生成し、それを各ストレージやデバイスに分散バックアップする。TrezorのShamir Backupで使われているのも、このタイプの鍵管理。

一方、マルチパーティで構成されるマルチシグの場合、この鍵生成は、誰も集約された閾値公開鍵の秘密鍵を知り得ない状態で行わなければならない。ちなみに、秘密鍵を知るエンティティがいる閾値署名の場合、ディーラーと呼ばれる秘密鍵を唯一知るエンティティがシェアを配布し、その配布されたシェアが正しいものかどうか検証可能なスキーム=FeldmanのVSS（Verifiable Secret Sharing Scheme）が有名だ。FeldmanのVSSをディーラーレス（誰も秘密鍵を知るエンティティが存在しない）方式にしたのがPedersenのVSSで、ざっくり言うと、マルチシグの参加者全員がそれぞれ個別にFeldmanのVSSを実行し、それらの秘密のシェアを合算したものがマルチシグの秘密のシェアになるよう構成するスキームで、分散鍵生成方式（DKG = Distributed Key Generation）の１つ。

PedersenのDKGの概略は↓

1. 各参加者がランダムなt-1次の多項式を生成し（tは閾値）、
2. 多項式の各係数に楕円曲線のベースポインを乗算したコミットメントと、その内、定数項（シークレットシェア）の値を知っていることを証明するSchnorr署名を計算し*1、コミットメントと署名を他の参加者にブロードキャストする
3. 2を受け取った参加者は、署名が正しいか検証する
4. 各参加者は1で生成した自分の多項式を使って、他の参加者用のシェアを計算し、計算したシェアを各参加者に個別に送信する
5. 4で受け取ったシェアが正しいか、2で受けとったコミットメントを使って検証する
6. 受け取ったシェアが正しいことを全参加者が検証できたら、共通の公開鍵を計算する

上記2と4から、各参加者はそれぞれ2ラウンドの通信を行う。このスキームでは、

• 中間者攻撃を回避し、他の参加者にシェアを配信する際の秘匿性を確保するために認証および暗号化された安全な相互通信チャネルと
• 全参加者に向けて共有した情報について、全参加者が同じ情報を入手していることを保証するブロードキャストの仕組み

を必要とする。これらが保証されないと、暗号通貨の文脈では資金を失うリスクが発生する。

ChillDKG

↑のリスクを排除するために通信チャネルなど安全性の外的要因を排除してスタンドアロンで安全なDKGプロトコルを提案しているのがChillDKG。

ChillDKGは以下の３つのプロトコルで構成されている：

• SimplPedPop：外部の安全な通信チャネルと等価性チェックプロコトルに依存したPedersen DKGの簡易版。ChillDKGでは、他の2つのプロトコルと組み合わせることで外部依存要因を排除する。またSimplPedPopに対して、以下の変更が加えられている：
  • 各参加者はシードから必要なすべてのランダム値を決定論的に導出する
  • 各参加者の公開鍵がDKGの出力に追加され、部分的な署名検証を可能にする
  • VSSのコミットメントを参加者間で直接送信するのではなく、コーディネーターを経由することでコーディネーターによるコミットメントの集約をサポートする（通信コスト削減）
• EncPedPop：参加者間のECDH鍵交換を利用してシェアを暗号化するプロトコル。これにより安全でない通信チャネルでもシェアを安全に送付することができる
• CertEq：すべての参加者がDKGのセッション中に生成された共通データに同意していること、無効なシェアや証明によってセッションを中止した参加者がいないことを保証する

DKGセッションのフロー

BIPドラフトに掲載されているChillDKGセッションの参加者とコーディネーター*2間のフローが↓

APIのフローなので具体的に記載されているけど、ざっくりフローを追ってく↓*3

hostpubkey

DKGセッションを開始する前に各参加者が、自分のシードからホスト公開鍵を計算する。この公開鍵は参加者の長期的なIDで、シードから計算しているので、シードがバックアップされていればいつでも再計算できる。計算したホスト公開鍵はその後コーディネーターに送られる。

セッションパラメーター

コーディネーターが全参加者のホスト公開鍵を集めたら、

• 全参加者のホスト公開鍵のリスト
• 閾値t

がセッションパラメーターとして、コーディネーターから全参加者に送信される*4。

ChillDKGのセッションを開始するにあたり、各参加者はこの公開鍵で識別される共同署名者のセットを決定している必要がある。また、セッションパラメーターのタグ付きハッシュ値がパラメーターIDとなり、セッションを一意に識別するIDとなる。

participant_step1

セッションパラメーターを受け取った各参加者はセッションの最初のステップを実行する。このステップで行うのは、

• ランダムな多項式の生成（多項式の定数項がシークレットシェア）
• 他の参加者用のシェアの生成
• VSSのコミットメントの生成
• シークレットシェアを知っていることを証明するSchnorr署名の生成

ただ、通常のPedersenのDKGと大きく違うのは、

• 他の参加者用のシェアについては、各参加者の公開鍵と自分の秘密鍵でECDHで共通鍵を導出しシェアを暗号化する*5。
  • 相手の公開鍵は、セッションパラメーターとしてコーディネーターから受信したものを使用
  • 自分の秘密鍵は、セッションパラメーターとして提供したものではなく、このステップで新たに生成したランダム値（シークレットnonce）を使用する。そのため、シェアを受けとった参加者が復号できるように、シークレットnonceに対応する公開鍵＝公開nonceを計算し、それをこの後送付する必要がある。
• ランダムな多項式は、自分のシードと上記の公開nonceとセッションパラメーターからセッションシードを導出し、そのセッションシードを使って導出される。つまり、シードと公開nonce、セッションパラメーターがあれば、生成した多項式を復元することができる。
• 生成したVSSコミットメント、Schnorr署名、他の参加者用の暗号化されたシェア、公開nonceをコーディネーターに送信する*6。

coordinator_step1

コーディネーターは、全参加者から受け取った上記のデータを全参加者に配布する。具体的には、

• 全参加者が作成したデータから、参加者j宛のデータについて、定数項のコミットメントを除くすべてのコミットメント値を合算して集約する
• 全参加者分の集約したコミットメント値のリストと定数項のコミットメント値のリストおよびを全参加者から受け取ったSchnorr署名を全参加者に送信する

※ 定数項のコミットメントだけ別にしてるのは、この後署名検証するのに必要になるから。

participant_step2

コーディネーターから上記のデータを受け取った各参加者は、コミットメントと受け取ったシェアが正しいデータであるか検証する。具体的には、

• 他の参加者の公開nonceと自身のシークレットnonceでECDHを行い、受け取った暗号化シェアを復号する
• 他の全参加者の定数項のコミットメントに対して受領したSchnorr署名の検証を行う
• 定数項のコミットメントを集約されたコミットメント値に集約し、VSSのコミットメント値が正しいか復号したシェアを使って検証する

最終的に、全参加者の定数項のコミットメントの合算値が閾値公開鍵（資金をロックするマルチシグ用の公開鍵）となる。この段階で鍵の導出はされるものの、参加者全員が同じデータに対してセットアップできているか保証がないと安心して資金を預け入れられないので、さらに等価性チェックプロトコルCertEqを実行する。

各参加者は以下の要素を連結したトランスクリプトeq_inputを作成する。

• 閾値t
• 全参加者のVSSコミットメントのリスト
• 全参加者のホスト公開鍵のリスト
• 全参加者の公開nonceのリスト
• 全参加者の暗号化シェアのリスト

基本的にすべてコーディネーターを介して全参加者で共有されているデータであるため、eq_inputはセッションを通して全参加者で同じ値になる。

最後に参加者は、ホスト公開鍵に対応する秘密鍵を使ってeq_inputに対してShcnorr署名を生成し、この署名値をコーディネーターに送る。

coordinator_finalize

全参加者から送られてきた↑の署名を各参加者のホスト公開鍵を使って検証する。問題なければ全参加者の署名を連結したデータを全参加者に送信する。

participant_finalize

コーディネーターから受け取った全参加者の署名をそれぞれ検証する。すべての署名の検証が成功したということは、全参加者が同じeq_inputに合意した＝DKGのセッション中に生成された共通データに同意していることが確認できる。

リカバリー

上記のように、ChillDKGのセッションが完了すると全参加者が共通のセッションデータ（eq_input）を保持した状態になる。その結果、participant_finalizeで受領した検証に成功したすべての署名とeq_inputで構成されるデータからリカバリーデータを作成することができる。シェアは暗号化された状態なので、サードパーティのストレージにバックアップするのも可。また、全参加者共通のデータなので、他の参加者から入手できる可能性もある。

このリカバリーデータと自身のシードがあれば、participant_step1のセッションシードも復元できるので、自身が生成した多項式も復元することができる。ただ、ECDHに使用する一時鍵のシークレットnonceは復元できなさそうなので、セッション完了後のリカバリーに対して有用というところかな。

以上がChillDKGの内容。詳細まで理解したい場合はBIPドラフトや参照実装のコードを参照。

*1:Rogue-Key攻撃対策

*2:決まったコーディネーターが存在しない場合は、参加者の誰かがコーディネーターに。誰がコーディネーターになったとしてもコーディネーターを信頼する必要はなく、悪意あるコーディネーターはDKGを強制的に失敗させることはできても、DKGにセキュリティに悪影響を与えることはできない。

*3:ざっくりとしか書いてないので、事前に従来の鍵生成ロジックについて知っておいた方が理解しやすいかも。参考：GBECの解説動画

*4:ホスト公開鍵のリストは同じ順序で全参加者に送信される必要がある

*5:サンプルコード見た感じ、ECDHした値とシェアを加算してるだけっぽい。

*6:各参加者に送信するのではなく、全員コーディネーターに送信