FROSTの署名作成時の最適化 - Develop with pleasure!

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

techmedia-think.hatenablog.com

GBECの解説動画はこちら。

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

最適化のポイント

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（2⁵ - 2³ - 2⁰）となる。

スカラー乗算ではビットが非ゼロの部分で点の加算が発生するが、バイナリ法だと平均して全ビットの半分が非ゼロになり計算対象となるけど、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と言える。