MuSig（解説）


# はじめに

※：”20 May 2018”に内容が更新されましたので、一部修正しました。

~~[以前の投稿](https://qiita.com/tnakagawa/items/40862bc07da63c4f7e80)で下記のReportを楕円曲線（EC）で[コード化(golang)](https://github.com/tnakagawa/musig)してみました。~~（修正中）
作成した当初は内容をあまり理解していませんでしたが、最近いろいろな人から意見やアドバイスを頂き
なんとなくですが理解してきたので、解説していこうと思います。
※：間違いや意見などがありましたら、コメントを頂けると有り難いです。m(_ _)m

[Simple Schnorr Multi-Signatures with Applications to Bitcoin](https://eprint.iacr.org/2018/068)
https://eprint.iacr.org/2018/068


# Schnorr Signatures

すでに内容を知っている方は、特に必要ありません。

詳細を独立しました。
[Schnorr Signatures（楕円曲線：EC）](https://qiita.com/tnakagawa/items/a68606f005630cd09415)

# MuSig

ここでは、以下を参考としています。
[Simple Schnorr Multi-Signatures with Applications to Bitcoin](https://eprint.iacr.org/2018/068)

### 準備
`n`人の署名を集約します。
以下を準備します。

```math
\begin{align*}
G &\text{ : 生成元(generator/EC point)}\\
1 \le n &\\
x_i\ (1\le i \le n)\ &\text{ : 秘密鍵(private key/scalar)}\\
X_i=x_iG\ (1\le i \le n)\  &\text{ : 公開鍵(public key/EC point)}\\
L=\{X_1,...,X_n\}&\\
H_{\text{com}}(\cdot) &\text{ : ハッシュ関数(hash function/return scalar)}\\
H_{\text{agg}}(\cdot) &\text{ : ハッシュ関数(hash function/return scalar)}\\
H_{\text{sig}}(\cdot) &\text{ : ハッシュ関数(hash function/return scalar)}\\
m &\text{ : メッセージ(message)}\\
\end{align*}
```

※：秘密鍵は、各々のユーザしか知りません。
※：`H_com`はユーザ間の間のみ知っている必要があります。
※：他のパラメータは署名者達や検証者は知っているものとします。

### 署名（Sign）
署名は、`n`人なので、乱数`r`（毎回異なる値）も`n`個必要となります。
`n`個の`R`を求め、各`R`を集約します、また各公開鍵`X_i`から`X~`を求めます。
`X~`から`c`を計算し、これらなどから、各署名`s_i`を求めます。
署名を集約し`s`を求めます。

___変更箇所___
署名するユーザどうしが`R`を交換する場合に、先に`H_com`で`R`のハッシュ値を求め
各ユーザに渡します、全員のハッシュ値を取得してから、`R`を交換するようにします。
これを行わない場合、秘密鍵が相手に知れてしまう危険性があります。

```math
\begin{align*}
r_i\ (1\le i \le n)\ &\text{ : 各乱数(random number/scalar)}\\
R_i =r_iG\ (1\le i \le n)\ &\text{ : (EC point)}\\
R=R_1+...+R_n=\sum_{i=1}^{n}R_i &\text{ : (EC point)}\\
a_i = H_{\text{agg}}(L,X_i)\ (1\le i \le n)\ &\text{ : (scalar)}\\
\tilde{X}=a_1X_1+...+a_nX_n=\sum_{i=1}^{n}a_iX_i&\text{ : (EC Point)}\\
c = H_{\text{sig}}(\tilde{X},R,m)&\text{ : (scalar)}\\
s_i = r_i + ca_ix_i &\text{ : 各署名(scalar)}\\
s=s_1+...+s_n=\sum_{i=1}^{n}s_i &\text{ : 署名(scalar)}\\
(R,s) &\text{ : 署名値(signature value)}\\
\end{align*}
```

### 検証（Verify）
検証ですが、署名値`(R,s)`と、準備の秘密鍵`x_i`以外は知る事が出来ます。
まず、各公開鍵`X_i`から`X~`を求めます。
`X~`から`c`を計算しこれらを使って、最後の等式が成り立てば、署名が正当となります。

```math
\begin{align*}
a_i = H_{\text{agg}}(L,X_i)\ (1\le i \le n)\ &\text{ : (scalar)}\\
\tilde{X}=a_1X_1+...+a_nX_n=\sum_{i=1}^{n}a_iX_i&\text{ : (EC Point)}\\
c = H_{\text{sig}}(\tilde{X},R,m)&\text{ : (scalar)}\\
sG \overset{?}{=} R + c\tilde{X} &\\
\end{align*}
```

### 証明（Proof）
署名の計算式に生成元`G`を積算することで、署名と検証が成り立ちます。

```math
\begin{align*}
 a_i &= H_{\text{agg}}(L,X_i)\ (1\le i \le n)\\
 \tilde{X}&=a_1X_1+...+a_nX_n=\sum_{i=1}^{n}a_iX_i\\
 c&= H_{\text{sig}}(\tilde{X},R,m)\\
 s&=\sum_{i=1}^{n}s_i=\sum_{i=1}^{n}\left\{r_i + ca_ix_i\right\} \\
&=\sum_{i=1}^{n}r_i + c\sum_{i=1}^{n}a_ix_i \\
sG&=\sum_{i=1}^{n}r_iG + c\sum_{i=1}^{n}a_ix_iG \\
&=\sum_{i=1}^{n}R_i + c\sum_{i=1}^{n}a_iX_i \\
&=R + c\tilde{X} \\
\end{align*}
```

### まとめ

Reportでは、楕円曲線（EC）で記述されていません。
ただ、元々BitcoinにおけるScalingの問題に対して出てきた案でしたので、冪乗のまま使うことはないと思います。
Bitcoinで使われている楕円曲線（EC）を使って表してみました。

ハッシュ関数の引数に、公開鍵（`X~,X_i,etc`）や集約乱数（`R`）などを入れています。
これは、「rogue-key attack（ローグキー？攻撃）」を防ぐ為となっています。
詳しくは、[ここ](https://blockstream.com/2018/01/23/musig-key-aggregation-schnorr-signatures.html)を参考にしてください。

また、[Bellare-Neven](https://cseweb.ucsd.edu/~mihir/papers/multisignatures-ccs.pdf)(以下、BN)による「Plain Public-Key Model」を元にして考えられているそうです。
大きな違いは、BNではハッシュ関数が１つですが、MuSigでは２つ使っています。
BNでは「Discrete Logarithm(DL) problem」となっているが、これを「One-More Discrete Logarithm (OMDL) problem」
に置き換える事で、BNで発生していたやりとりを１回減らせるというものだそうです。
**※：この部分については、理解できませんでした・・・だれか教えてm(_ _)m**

# さいごに

MuSigはコンセプトなので、Bitcoinに採用されるかどうかはわかりません。
Reportには、セキュリティ証明などが沢山かかれています。私はほとんど理解できませんでした。

実際にコードやこの投稿をしてみて、署名が集約できることは分かりました。
何人もの人がそれぞれの署名を出さず、集約した１つの署名だけで証明できる事に驚きました。