はじめに
※:”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ではハッシュ関数が1つですが、MuSigでは2つ使っています。
BNでは「Discrete Logarithm(DL) problem」となっているが、これを「One-More Discrete Logarithm (OMDL) problem」
に置き換える事で、BNで発生していたやりとりを1回減らせるというものだそうです。
※:この部分については、理解できませんでした・・・だれか教えてm(_ _)m
さいごに
MuSigはコンセプトなので、Bitcoinに採用されるかどうかはわかりません。
Reportには、セキュリティ証明などが沢山かかれています。私はほとんど理解できませんでした。
実際にコードやこの投稿をしてみて、署名が集約できることは分かりました。
何人もの人がそれぞれの署名を出さず、集約した1つの署名だけで証明できる事に驚きました。