先日、Gregory MaxwellとAndrew Poelstra、Yannick SeurinとPieter Wuilleらによって、Schnorr署名を使ったマルチシグスキームのホワイトペーパーが発表された↓
https://eprint.iacr.org/2018/068.pdf
これに関する記事をPeiter WuilleがBlockstreamのブログにポストしていたので↓
まずは↑読んで理解した範囲で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つに集約するということも可能になる。前者のマルチシグが複数の署名者が同じメッセージ(sighash)に対して署名するのに対し、後者の場合は各署名者は異なるメッセージ(インプット毎にsighashは異なる)に署名することになる。
具体的にどういう署名方式なのか見てみよう。
表記
Schnorr署名
Schnorr署名の式は以下のように定義されている。
- 署名は。rは署名者が選択したランダムなナンス。
- 検証はが成立するか。
構成要素はECDSAよりシンプルだ。
※ 他のサイトのSchnorrの式みるとでXが含まれてないんだけど、どういう違いから来てるのか? Xがあると(R, s)から公開鍵を復元することもできない気がする。
Schnorrベースのマルチシグ
Schnorrベースのマルチシグの署名と検証は以下のように行う。
- Xを各署名者が持つ公開鍵=点の合計とする。
- 各署名者はランダムなナンスを選択し、他の署名者とを共有する。
- Rを点の合計とする。
- 各署名者はを計算する。
- 最終的な署名データは(R, s)で、sはの値の合計。
- 検証はが成立するか確認する。ここでXは個々の公開鍵の合計。
署名及び検証式が↑のSchnorr署名の式を満たす形でマルチシグを構成しているのが分かる。
各署名者がの秘密鍵とナンスからを加算して求めた点と、各署名者の公開鍵とを加算して出来た点の検証になってるので、楕円曲線の準同型性を利用した仕組みみたいだなー。
rogue-key攻撃の問題
↑のSchnorrベースのマルチシグで問題になるのがrogue-key攻撃。例えばアリス(公開鍵)とボブ(公開鍵)がマルチシグを構成する場合、お互いに公開鍵を教える必要がある。例えばアリスが公開鍵を教えた後に、ボブがアリスの公開鍵を使ってを計算して、を自分の公開鍵として教えることが考えられる。この場合鍵を集約するととなり、ボブの公開鍵の秘密鍵だけで署名ができてしまう。
この問題を回避する方法の1つは、アリスとボブの公開鍵に加えて、それぞれがその公開鍵に対応する秘密鍵を本当に所有しているという証明を最初にするというもの。ボブはの秘密鍵を持っていないので証明できず不正を働けない。ただ必ずそういった証明を事前に行えるという保証をプロトコルレベルで保証するものではないので、こういった攻撃ができない仕組みが求められる。
Bellare-Nevenのマルチシグネチャ方式
rogue-key攻撃に対して安全なのがBellare-Nevenのマルチシグネチャで、以下の手順で署名の作成と検証を行う。
- とする。
- 各署名者はランダムなナンスを選択し、他の署名者とを共有する。
- Rをポイントの合計とする。
- 各署名者はを計算する。
- 最終的な署名データは(R, s)で、sはの値の合計。
- 検証はが成立するか確認する。
さらに、各署名者はを公開する前に、を公開する事前のコミットメントラウンドを設けるケースもある。
検証式を見れば明らかだが、この方式だと↑の通常のSchnorrの式を満たさない。署名のを計算する際に、公開鍵に乗算するに各公開鍵が含まれており、に乗算する値が署名毎に異なるため、のような集約はできない。確かにrogue-key攻撃を防ぐことはできるが、反面、検証には各公開鍵が必要となり、鍵の集約特性が失われてしまう。
MuSig
rogue-key攻撃に対して安全でありつつ、鍵の集約特性を備えたマルチシグネチャ方式が、今回提案されたMuSigで、以下の手順で署名の作成と検証を行う。
- とする。
- の合計をXとする。
- 各署名者はランダムなナンスを選択し、他の署名者とを共有する。
- Rをポイントの合計とする。
- 各署名者はを計算する。
- 最終的な署名データは(R, s)で、sはの値の合計。
- 検証はが成立するか確認する。
ポイントはSchnorrベースの集約公開鍵Xを、単純な各公開鍵の和でなく、全公開鍵をハッシュした要素に公開鍵を乗算した和にしている点だ。
BNと異なるのは、各署名作成時に署名毎に異なるハッシュ値を持つものの、それに対応する点を加算してXを作り共有することで、鍵の集約を可能にしている。署名及び検証式が標準のSchnorrの式と同じになりっており、集約特性があることが分かる。
また各の計算時に署名毎に異なるを秘密鍵に掛けているため、標準的なSchnorrベースのマルチシグに比べてrogue-key攻撃への耐性がある。
というのがMuSigの仕組みみたい。
↑の式だと1つのメッセージへの多重署名なのでマルチシグの置き換えは可能だけど、トランザクションの署名を1つに集約する場合、メッセージはインプット毎に異なるため、のmは署名毎に変わるからmを側に移動するのかな?この辺はホワイトペーパー見てみないと分からない。
これがどういう形でBitcoinに適用されるかは、多分またBIPとして出てくるだろう。