はじめに

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

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

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

Schnorr Signatures

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

詳細を独立しました。
Schnorr Signatures（楕円曲線：EC）

MuSig

ここでは、以下を参考としています。
Simple Schnorr Multi-Signatures with Applications to Bitcoin

準備

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

\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を交換するようにします。
これを行わない場合、秘密鍵が相手に知れてしまう危険性があります。

\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を計算しこれらを使って、最後の等式が成り立てば、署名が正当となります。

\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を積算することで、署名と検証が成り立ちます。

\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（ローグキー？攻撃）」を防ぐ為となっています。
詳しくは、ここを参考にしてください。

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

さいごに

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

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