Develop with pleasure!

福岡でCloudとかBlockchainとか。

通信ラウンドの効率性を重視したSchnorrベースの閾値署名スキームFROST

Cryptography Schnorr 秘密分散

TaprootのアクティベートによりBitcoinでもSchnorr署名が利用可能になったけど、Schnorr署名をメリットの1つはマルチシグの署名を単一の署名に集約できる集約特性があることで、この恩恵を受けるためにはこのようなマルチシグを扱うウォレットの開発が必要になる。

マルチシグの集約について、簡単なのはn-of-nのケースで、このようなマルチシグをトラストレスに安全に構成する（Rogue-Key攻撃に対して安全）プロトコルとしてMuSig2などが発表され開発が進んでいる↓

techmedia-think.hatenablog.com

n-of-nのマルチシグはSchnorr署名の線形特性をそのまま利用するためシンプルだが、一方、m-of-nのような閾値設定のマルチシグのプロトコルは、秘密分散法を利用して、集約された秘密鍵の情報を漏らすことなく、閾値m個の有向な部分署名が集まった場合に有効な署名を完成できる必要があり、難易度はぐんと上がる。有名なのはPedersenの検証可能な秘密分散法（VSS）を用いた閾値署名スキームなど↓

techmedia-think.hatenablog.com

FROST

そんな閾値署名スキームの提案の1つがFROST: Flexible Round-Optimized Schnorr Threshold Signatures。堅牢性よりも効率性を採ったプロトコルになる。

これまでの閾値署名スキームは、ある参加者が不正をして、不正なシェアを提供した場合、残りの正直な参加者は、その不正を検出し、残りの正直な参加者の数が閾値tいる限りプロトコルを完了できるという堅牢性を備えている。

ただ、ある程度信頼できる参加者の中では、つまり全参加者が正直にプロトコルに従っているという楽観的なケースでは、プロトコルを中断し、不正を行ったユーザーを除外してプロトコルを再実行することで、署名プロセスで必要になる通信ラウンド数を減らすというのがFROSTの採るアプローチ。

https://eprint.iacr.org/2020/852.pdf

今回は、このFROSTの署名スキームについて詳しくみていく。

前提として、n人の参加者がいて、この内、t人の協力があれば集約鍵に対して有効なSchnorr署名を構成できるものとする。

多項式補間

具体的なプロセスの前に、重要な構成要素である多項式補間について。

↑の記事にも書いたシャミアの秘密分散法は、閾値tにおいてf(0) = シークレットとなるようなt-1次の多項式を構築し、そのシェア（i, f(i)）を配布し、それがt個集まったら多項式f(x)が再構築できf(0)のシークレットが分かるという仕組み。

多項式の復元には、ラグランジュ補間を使用できる：

{\displaystyle f(x) = \sum_{j=1}^{t}f(j) \Pi_{i \neq j}\frac{x - x_i}{x_j - x_i}}

そして復元した多項式からf(0)のシークレットを求めるには、

{\displaystyle f(0) = \sum_{i=1}^t}f(i)\lambda_i

を計算する。ここで {\lambda_i}は、x = 0つまりf(0)における {\displaystyle \lambda_i = \Pi^{t}_{j=1, j \neq i} \frac{j}{j-i}}となるiに対するラグランジュ係数。

後の署名処理の際に登場するけど、ここでのポイントは、シークレットを求める際に使用するラグランジュ係数は、閾値の数とiの値が分かれば定数値として求まるという点。

分散鍵生成

まず最初に、分散鍵生成（Distributed Key Generation＝DKG）プロセスを実行して、集約鍵を生成する。ここではPedersenの検証可能な秘密分散法（VSS）のDKGをベースにしている。*1

n人の参加者は、それぞれ1〜nまでの一意の識別番号を持っていることとする。各参加者は以下を行う。

  1. t個のランダムシークレット {a_0,..., a_{t-1}}を生成する。
  2. 1のシークレットを使ってt-1次の多項式を作成する。 {f(x) = a_{t-1}x^{t-1} + a_{t-2}x^{t-2} + ... + a_0}
  3. {a_0}の知識の証明をするため、以下の手順でSchnorr署名を作成する。
    1. ランダムなnonce kを選択。
    2. 自身のIDと {a_0G, kG}およびリプレイ攻撃を防ぐための文字列の値のハッシュ値を計算しチャレンジcとする。
    3. {a_0}を秘密鍵としてSchnorr署名 {sig = (kG, k + ca_0)}を生成する。
  4. 各係数に対するコミットメントとして、1で生成した多項式の各係数に対応する公開鍵 {(a_0G, ..., a_{t-1}G)}を計算する。
  5. 3で生成したSchnorr署名と4の多項式の係数に対応した公開鍵のリストを他の参加者に送信する。
  6. 他の参加者から受信した5のデータから、署名の有効性（署名が {a_0G}に対して有効か）を検証する。

ここまでで、第一ラウンドの通信が終了。

続いて第二ラウンドでは、以下を行う。

  1. 参加者は生成した多項式を使って、他の参加者に {(i, f(i))}のシェアを送信する。ここでiは他の参加者のID。
  2. 1のシェアを受け取ったユーザーは、第一ラウンドで受け取った公開鍵のリストを使って、そのシェアが正しく計算されたものか検証する。多項式の係数自体は不明だが係数に対応する公開鍵を持っているので、検証は可能。
  3. 他のすべての参加者からシェアを受け取ったら、それらのシェアを合算して、集約鍵のシェアを導出する。IDがiの参加者は、 {s_i = f_1(i) + f_2(i) + ... + f_n(i)}を持つことになる。
  4. 自分の公開シェア {P_i = s_iG}とし、集約公開鍵 {P = \sum^{n}_{i=1} a_{i0}G}を計算する。
  5. また他の参加者の公開シェアも、多項式の係数に対応する公開鍵のリストから算出できる。

つまり、この第二ラウンドが終わった時点で、第一ラウンドで各参加者がそれぞれランダムに生成した多項式を合算した多項式に対するシェア（ {s_i}）を各参加者が持っている状態になる。

そして、各参加者の {a_0G}を合算した {P = \sum^{n}_{i=1} a_{i0}G}が集約公開鍵となる。署名生成フェーズでは、この集約公開鍵に対して有効な署名をt人で協力して生成することになる。

FROSTのDKGプロトコルは以上の2ラウンドの通信で完了する。

署名生成

前処理ラウンド

署名生成は、前処理ラウンドから始まる。前処理ラウンドでは各参加者iは以下を実行する。

  1. 一度だけ使用するnonceのペア {(d_i, e_i)}生成する。
  2. 1のシークレットに対応する公開鍵のペア {(D_i = d_iG, E_i = e_iG)}を生成する。

↑を {\pi}個作成し、 {\pi}個の公開鍵のペアのリストを他の参加者に公開する。各署名プロセスではこのnonceの値のペアを１つ使用するため、 {\pi}個使い切ったらまたこの前処理ラウンドを実行する。つまり、署名の度にこの前処理ラウンドが必要という訳ではない。初回の前処理ラウンドは、↑のDKGと一緒にやっても良い。

署名ラウンド

DKGで集約鍵が決定し、前処理ラウンドが終わると、メッセージmに対して署名をする準備が完了する。

署名プロセスでは参加者の1人がSignature Aggregator ＝ SA（署名の集約を行う人）の役割の担う。SAは参加者の中から、自身を含めてt人をピックアップし、このt人の未使用のnonceのペア {(D_{ij}, E_{ij})}（iは参加者のID、jは前処理ラウンドで生成した {\pi}個中のインデックス）をピックアップする。そして、SAは選択した {(D_{ij}, E_{ij})}のリストとメッセージmをt人の参加者に送信する。

t人の参加者は、

  1. SAから送られた署名対象のメッセージmを確認する。
  2. SAから送られてきた {(D_{ij}, E_{ij})}のリストのコミットメントが、前処理ラウンドで自分が受け取ったリストの中にあるか確認する。
  3. IDと {(D_{ij}, E_{ij})}のリストとメッセージをハッシュしたバインディング値 {p_i = H(i, m, リスト)}を署名参加者全員分計算する。このバインディングを行うことで既知の偽造攻撃を回避する。
  4. 署名に使用する集約nonce {R = \sum^{t}_{k=1}D_{kj} + p_iE_{kj}}を計算する。
  5. 続いて署名のチャレンジ {c = H(P, R, m)}を計算する。
  6. DKGで導出された自身の秘密鍵に関するシェア {s_i}を使って部分署名 {z_i = d_{ij} + p_i e_{ij} + H(P, R, m)s_i \lambda_i}を計算し、SAに送信する。

↑の部分署名を見てみると、 {d_{ij} + p_ie_{ij}}をnonceとした秘密鍵 {s_i \lambda_i}のSchnorr署名の形式になっていることが分かる。 {\lambda_i}は、前述した多項式f(x)についてf(0)を求める際のラグランジュ係数。

ここで、 {s_i \lambda_i}というのは、多項式補間で求める秘密鍵の {\displaystyle f(0) = \sum_{i=1}^t}f(i)\lambda_iの一部で、それによってSchnorrの部分署名を作成していることが分かる。つまり、これを閾値分合算すれば、集約秘密鍵で署名したのと同じ結果のSchnorr署名の値になるということ。

SAはすべての部分署名を受信し、

  1. 集約nonce Rとチャレンジcを計算する。
  2. すべての部分署名が正しいものか、 {z_iG = R_i + c \cdot \lambda_i \cdot P_i}が成立するか検証する。成立しなかった場合、その部分署名を作った参加者が不正をしていることになる。前述したように、参加者のセットが決まれば {\lambda_i}はどの参加者も計算できるため、この検証が可能になる。
  3. 部分署名を合算して、最終的な署名 {z = z_1 + ... + z_t}を計算する。
  4. (R, z)がメッセージmに対して有効なSchnorr署名となる。

また、各参加者は署名を行ったら、 {(D_{ij}, E_{ij})}のリストから署名に使用したデータを削除する必要がある。

上記のプロセスから、FROSTの署名プロセスはSAと各署名者の１ラウンドの通信で完了することが分かる。

参考

*1:ちなみにVSSとは、秘密分散法でシェアを配布する際に、参加者のシェアがすべて正しいことを検証するための仕組み。FledmanのVSSでは中央のディーラーを必要としたのに対し、PedersenのVSSは各参加者がディーラーとして機能するようになっている。