fivebythree.netマルチ署名とは？
マルチ署名とは、複数の人数がかかわる一つのトランザクションで、各ユーザーが発行する署名を足しあげてまとめてしまうことです。 このとき、同様に各ユーザーの公開鍵の線形結合を用いて署名の検証ができる場合があり、Schnorr署名のスキームはそれに該当します。
署名を一つにまとめてしまうことで署名の記録容量を削減することができます。 特に、ビットコインの取引のように、一つの売買で複数のユーザーの売り注文・買い注文のマッチングが頻繁に行われる場合、署名の保存スペースを大きく削減することができる事が期待されています。
Schnorr 署名における、公開鍵の足し算・署名の足し算
Schnorr署名はその数学的な構造により、署名の足し算（線形結合）を行うことができます。 足しあげられた署名は、同様に複数の公開鍵を線形結合したもので署名の検証を行うことができます。
例えば…
ナイーブなマルチ署名
- $d_i$ 署名者 i の秘密鍵
- $\mathbf{P}_i = d_i \cdot \mathbf{G}$ 署名者 i の公開鍵
- $k_i$ 署名者 i が署名に用いる nonce
- $\mathbf{R}_i = k_i \cdot \mathbf{G}$ nonce の 楕円曲線上の点
- $\mathbf{R}_i.x = r_i$ 署名者 i の署名
各署名者は $r_i$ を共同証明者に公開する。次に以下を計算する。
- $\mathbf{R} = \sum_i\mathbf{R_i} $
- $\mathbf{P} = \sum_i\mathbf{P_i} $
- $e = int(Hash_{BIP0340/challenge}(byte(\mathbf{R})||byte(\mathbf{P})||msg)) $
- $s_i = r_i + e d_i \mod n$
$s_i$ を 署名ペアのもう一つとして署名者は公開する。 代表署名者は以下を署名として発行する。
- $s = \sum_i s_i \mod n$
- $(r,s)$ を 署名として発行する。
検証は以下の通り。
- $\mathbf{R}_v = s \cdot \mathbf{G} - e \cdot \mathbf{P}$
- $\mathbf{R}_v.x$ と r が等しければ検証OK.
$\mathbf{R}_v$ をもう少し詳しく検証すると以下の通り。
$\mathbf{R}_v = \sum_i \left( s_i \cdot \mathbf{G} - e \cdot \mathbf{P}_i \right) = \sum_i \left( (r_i + e d_i) \cdot \mathbf{G} - e \cdot \mathbf{P}_i \right)$
$d_i\cdot\mathbf{G}=\mathbf{P}_i$ なので結局、
$\mathbf{R}_v=\sum_i(r_i\cdot\mathbf{G}) = \mathbf{R}$ となり、署名の足し算 $(r,s)$ は、公開鍵の足し算 $\mathbf{P} = \mathbf{P}_i$ を使って検証できることが分かります。
MuSig
前節で「ナイーブ」なマルチ署名とあえて書いたのはやはり、上記方法には脆弱性が知られていて、実際には使うことができません。 具体的には “Rogue Key Attack” と言われる方法で、悪意のある署名者が公開鍵を捏造することで署名者を除外できる方法が知られています。
下記記事の解説が分かりやすいです。
https://blog.blockstream.com/en-musig-key-aggregation-schnorr-signatures/
そこで、署名する際に公開鍵に結合係数をかけた線形結合とすることで、Rogue Key Attack を回避する方法が知られています。 具体的には暗号学的ハッシュ関数を使って、
- $l = Hash_{aggregation}(\mathbf{P}_1. \mathbf{P}_2., … \mathbf{P}_N.)$
- $\mu_i = Hash_\mu(l,\mathbf{P}_i) $
- $\mathbf{P} = \sum_i \mu_i \mathbf{P}_i$
のようにして、公開鍵の線形結合 $\mathbf{P}$ を計算します。
更に、署名の和 $e$を計算する際も以下のように、係数$\mu_i$をを用いて計算します。
- $s = \sum_i \left(r_i + e \mu_i k_i \right) \mod n$
検証は ナイーブなマルチ署名と同じです。
- $\mathbf{R}_v = s \cdot G - e \mathbf{P}$ の x座標が $r$ と等しければ検証OK。
確認すると…
$\mathbf{R}_v = s \cdot G - e \mathbf{P} = \sum_i\left( r_i \mathbf{G} - e \mu_i d_i \mathbf{G} - e \mu_i \mathbf{P}_i \right) = \sum_i r_i \cdot \mathbf{G} = \mathbf{R}$
となり、公開鍵の線形結合 $\mathbf{P} = \sum_i \mu_i \mathbf{P}_i$ にて署名の検証が可能なことが分かります。$\mu_i$ はスクランブルの役目を果たしており、Rogue Key Attack をほぼ不可能にしています。
マルチ署名の Nostr への応用は？
正直、Nostrで複数のユーザーが同時に署名しないといけない場合は思いつかないのですが…。 例えば、各ユーザーのプロファイルデータの変更をリレー間で伝搬させて行くときに使えないでしょうか？
- ユーザーは設定変更イベント（例えば Cotanct Change や Event Deletion)を少数のリレーに送る
- リレーは自身の変更を実施したら、マルチ署名のスキームで署名をアップデートし、別のリレーに送る。
- その際に “signee” に リレー自信の公開鍵を追加する
- リレーは変更イベントを受信した場合、過去におなじevent.id を処理していないかチェック。すでに処理済みである場合は無視する。
- signee の数が規定以上の場合は無視
こんな感じです。
これで変更イベントをリレー間で高率的共有しつつ捏造に強いイベント伝搬ができます（ような気がします…）。
結論＋α
- Schnorr 署名は署名の足し算、公開鍵の線形結合をすることで、複数人の署名を一つの署名にまとめることができる
- マルチ署名には様々な脆弱性が知られており、その一つが Rogue Key Attack という特定のユーザーを署名から排除してしまう方法
- Rogue Key Attack を防ぐスキームとして “MuSig” というものがある。公開鍵に係数を乗じることで、Rogue Key Attack を実質不可能にできる
- (＋α) MuSig にも nonce を意図的に操作することによる秘密鍵漏洩の脆弱性が知られており、それを回避する MuSig2 が現在議論中。