Develop with pleasure!

福岡でCloudとかBlockchainとか。

Schnorrベースのマルチシグネチャスキーム「MuSig」

先日、Gregory MaxwellとAndrew Poelstra、Yannick SeurinとPieter Wuilleらによって、Schnorr署名を使ったマルチシグスキームのホワイトペーパーが発表された↓

https://eprint.iacr.org/2018/068.pdf

これに関する記事をPeiter WuilleがBlockstreamのブログにポストしていたので↓

blockstream.com

まずは↑読んで理解した範囲でMuSigについて書いてみる↓

既存のマルチシグ

Bitcoinにおけるマルチシグはよくm-of-nのように記載されn個の公開鍵の内m個の公開鍵に対応する秘密鍵で署名された署名データがあればコインのロックを解除できるといったもので、以下のようなscriptPubkeyと、アンロックする際のscriptSigが用いられる。

scriptPubkey

2-of-3のマルチシグのscriptPubkey↓

2 <公開鍵1> <公開鍵2> <公開鍵3> 3 OP_CHECKMULTISIG
scriptSig

↑の2-of-3のscriptPubkeyにロックされたコインを使用する際に必要なscriptSig

0 <公開鍵1の秘密鍵による署名> <公開鍵3の秘密鍵による署名>

トランザクションにはn個分の公開鍵と、m個分の署名データが含まれm-of-nの個数が増えるほどこのデータサイズも増えることになる。

鍵と署名の集約

既存のマルチシグは署名にECDSAを採用しているが、MuSigではこの部分をSchnorr署名をベースにした仕組みでサイズの削減とプライバシーを向上させようとしている。MuSigは鍵の集約をサポートする新しいマルチシグの方式で、マルチシグを構成する複数の公開鍵を1つの鍵に集約することができる。既存のマルチシグのscriptPubkeyは複数の公開鍵への支払いとみなすことができるのに対し、MuSigでは集約された公開鍵への支払いとみなすことができる。署名検証時も集約された鍵があれば良いので、個々の公開鍵の値が何なのか検証者に知られることはなく、サイズの削減とプライバシーの向上が見込める。

マルチシグの仕組みをMuSigにすることで、

  • トランザクションの各インプットに複数セットしていた署名の数を1つに減らせる
  • すべての公開鍵を含むスクリプトを1つの集約された公開鍵に減らせる

といった既存のマルチシグへのメリットが考えられる。

またそれ以上に複数のインプットを持つトランザクションの署名を1つに集約するということも可能になる。前者のマルチシグが複数の署名者が同じメッセージ(sighash)に対して署名するのに対し、後者の場合は各署名者は異なるメッセージ(インプット毎にsighashは異なる)に署名することになる。

具体的にどういう署名方式なのか見てみよう。

表記

  •  {x,x_1,x_2,...}を公開鍵 {X,X_1,X_2,...}に対応する秘密鍵とする(ジェネレータGと合わせ、 {X_i = x_{i}G})。
  • 署名されているメッセージはm
  • H()は暗号学的ハッシュ関数

Schnorr署名

Schnorr署名の式は以下のように定義されている。

  • 署名は {(R, s) = (rG, r + H(X, R, m)x)}。rは署名者が選択したランダムなナンス。
  • 検証は {sG = R + H(X, R, m)X}が成立するか。

構成要素はECDSAよりシンプルだ。

※ 他のサイトのSchnorrの式みると {H(R, m)}でXが含まれてないんだけど、どういう違いから来てるのか? Xがあると(R, s)から公開鍵を復元することもできない気がする。

Schnorrベースのマルチシグ

Schnorrベースのマルチシグの署名と検証は以下のように行う。

  • Xを各署名者が持つ公開鍵=点 {X_i}の合計とする。
  • 各署名者はランダムなナンス {r_i}を選択し、他の署名者と {R_i = r_{i}G}を共有する。
  • Rを点 {R_i}の合計とする。
  • 各署名者は {s_i = r_i + H(X, R, m)x_i}を計算する。
  • 最終的な署名データは(R, s)で、sは {s_i}の値の合計。
  • 検証は {sG = R + H(X, R, m)X}が成立するか確認する。ここでXは個々の公開鍵の合計。

署名 {(R, s)}及び検証式 {sG = R + H(X, R, m)X}が↑のSchnorr署名の式を満たす形でマルチシグを構成しているのが分かる。

各署名者がの秘密鍵とナンスから {s_i}を加算して求めた点と、各署名者の公開鍵と {R_i}を加算して出来た点の検証になってるので、楕円曲線の準同型性を利用した仕組みみたいだなー。

rogue-key攻撃の問題

↑のSchnorrベースのマルチシグで問題になるのがrogue-key攻撃。例えばアリス(公開鍵 {X_A})とボブ(公開鍵 {X_B})がマルチシグを構成する場合、お互いに公開鍵を教える必要がある。例えばアリスが公開鍵を教えた後に、ボブがアリスの公開鍵を使って {X'_B = X_B - X_A}を計算して、 {X_B^{'}}を自分の公開鍵として教えることが考えられる。この場合鍵を集約すると {X_A + X'B = X_A + X_B - X_A = X_B}となり、ボブの公開鍵 {X_B}秘密鍵だけで署名ができてしまう。

この問題を回避する方法の1つは、アリスとボブの公開鍵に加えて、それぞれがその公開鍵に対応する秘密鍵を本当に所有しているという証明を最初にするというもの。ボブは {X'_B}秘密鍵を持っていないので証明できず不正を働けない。ただ必ずそういった証明を事前に行えるという保証をプロトコルレベルで保証するものではないので、こういった攻撃ができない仕組みが求められる。

Bellare-Nevenのマルチシグネチャ方式

rogue-key攻撃に対して安全なのがBellare-Nevenのマルチシグネチャで、以下の手順で署名の作成と検証を行う。

  •  {L = H(X_1,X_2,...)}とする。
  • 各署名者はランダムなナンス {r_i}を選択し、他の署名者と {R_i = r_{i}G}を共有する。
  • Rを {R_i}ポイントの合計とする。
  • 各署名者は {s_i = r_i + H(L, X_i, R, m)x_i}を計算する。
  • 最終的な署名データは(R, s)で、sは {s_i}の値の合計。
  • 検証は {sG = R + H(L, X_1, R, m)X_1 +H(L, X_2, R, m)X_2 + ... }が成立するか確認する。

さらに、各署名者は {R_i}を公開する前に、 {H(R_i)}を公開する事前のコミットメントラウンドを設けるケースもある。

検証式を見れば明らかだが、この方式だと↑の通常のSchnorrの式を満たさない。署名の {s_i}を計算する際に、公開鍵に乗算する {H(L, X_i, R, m)}に各公開鍵が含まれており、 {x_i}に乗算する値が署名毎に異なるため、 {sG = R + H(X, R, m)X}のような集約はできない。確かにrogue-key攻撃を防ぐことはできるが、反面、検証には各公開鍵が必要となり、鍵の集約特性が失われてしまう。

MuSig

rogue-key攻撃に対して安全でありつつ、鍵の集約特性を備えたマルチシグネチャ方式が、今回提案されたMuSigで、以下の手順で署名の作成と検証を行う。

  •  {L = H(X_1,X_2,...)}とする。
  •  {H(L, X_i)X_i}の合計をXとする。
  • 各署名者はランダムなナンス {r_i}を選択し、他の署名者と {R_i = r_{i}G}を共有する。
  • Rを {R_i}ポイントの合計とする。
  • 各署名者は {s_i = r_i + H(X, R, m)H(L, X_i)x_i}を計算する。
  • 最終的な署名データは(R, s)で、sは {s_i}の値の合計。
  • 検証は {sG = R + H(X, R, m)X}が成立するか確認する。

ポイントはSchnorrベースのマルチシグのXを、単純な各公開鍵の和でなく、全公開鍵をハッシュした要素に公開鍵を乗算した和にしている点だ。

BNと異なるのは、各署名作成時に署名毎に異なるハッシュ値 {H(L, X_i)}を持つものの、それに対応する点 {H(L, X_i)X_i}を加算してXを作り共有することで、鍵の集約を可能にしている。署名 {(R, s)}及び検証式 {sG = R + H(X, R, m)X}が標準のSchnorrの式と同じになりっており、集約特性があることが分かる。

また各 {s_i}の計算時に署名毎に異なる {H(L, X_i)}秘密鍵 {x_i}に掛けているため、標準的なSchnorrベースのマルチシグに比べてrogue-key攻撃への耐性がある。

というのがMuSigの仕組みみたい。

↑の式だと1つのメッセージへの多重署名なのでマルチシグの置き換えは可能だけど、トランザクションの署名を1つに集約する場合、メッセージはインプット毎に異なるため、 {H(X, R, m)}のmは署名毎に変わるからmを {H(L, X_i, m)}側に移動するのかな?この辺はホワイトペーパー見てみないと分からない。

これがどういう形でBitcoinに適用されるかは、多分またBIPとして出てくるだろう。