Develop with pleasure!

福岡でCloudとかBlockchainとか。

FROSTの署名作成時の最適化

FROSTは、Schnorrベースの閾値署名方式↓

techmedia-think.hatenablog.com

GBECの解説動画はこちら

最近、Zcash Foundationから、FROSTの署名生成時のスカラー乗算処理を最適化した記事が公開されてたので見てみる↓

zfnd.org

最適化のポイント

FROSTでは、署名ラウンドで各参加者が署名を生成する際に、Schnorr署名の集約Public nonce(グループコミットメント)  {R = \sum^{t}_{k=1}D_{kj} + p_iE_{kj}}を計算する処理がある(最後に、SAが部分署名を集約する際にも計算される)。

tは署名処理の参加者の数(閾値)なので、この数が増ええれば、その分この計算コストも線形増加していくので、閾値が大きくなるほど、ここの計算効率が上がるとメリットになる。

この計算は、楕円曲線上の点のスカラー乗算 {p_iE_{kj}}と、点の加算 {D_{kj} + p_iE_{kj}}処理になっており、この内、複数のスカラー乗算の計算を最適化した模様(なのでプロトコルレベルの最適化ではなく実装の最適化)。

点のスカラー乗算

スカラー値xを楕円曲線上の点Gに乗算するスカラー乗算は、単純に計算するとGをx回加算する処理だけど、秘密鍵のような巨大な範囲の数値で、このような計算をするととてもコスト高な計算になるので、効率的な計算方法がいくつかある。簡単で有名なのはバイナリ法とか。

今回使用されてるのはwNAFみたい。

NAF(Non-Adjacent Form)

バイナリ法が0と1でスカラー値を表現するのに対して、NAFは0と±1で値を表現し、その際に0以外の数値が隣接しないようにする。

例えば23という数値は、バイナリ表現だと1 0 1 1 1だけど、NAF表現だと1 0 -1 0 0 -1(25 - 23 - 20)となる。

スカラー乗算ではビットが非ゼロの部分で点の加算が発生するが、バイナリ法だと平均して全ビットの半分が非ゼロになり計算対象となるけど、NAFだとそれが1/3程度に減少するので加算の回数が少なくなる、かつ点の減算も簡単であるため、乗算の計算が効率的になる。

wNAF

wNAFというのは表現するNAFの値を、3値固定ではなくサイズwのウィンドウで表す。具体的には、 {0, 1, 3, 5, ..., 2^{w-1} - 1}とそのマイナス値を使ってNAFに変換する(たとえば、w = 3の3NAFだと-7, -5, -1, 0, 1, 3, 5, 7)。※ NAFはw = 2のwNAFと言える。

最適化処理

Zcash Foundationが提供してるfrost-coreで最適化されたコミットメントの計算処理を見てみると↓

グループコミットメント計算時に、これまで各 {D_{kj} + p_iE_{kj}}をそのまま計算して合算していたのを、 {D_{kj}}の合算と {p_iE_{kj}}の合算処理を分離し、後者の合算処理で、

  1. スカラー {p_i}をそれぞれwNAFに変換(w = 5)
  2. 乗算対象の各点 {E_{kj}}について、ルックアップテーブルを作成
  3. 1,2を元に、各スカラー値について、各NAFのビット毎に点の加算/減算処理を行い、それを累積していく。

という計算をするようになってる。

閾値が小さいとそんなに効果は分からないと思うけど、667/1000の閾値で約50%の高速化がされてるみたい。