はじめに

Pieter Wuille（sipa）が出した、Bitcoinで使われるであろうSchnorr Signatureについて書かれたものです。
まだ、BIPにも登録されていないsipa個人のリポジトリにあるものについて記述します。

※：個人的な解釈を含んでいるので、詳しく知りたい人は原文を読んでください。
※：ご意見、ご感想を頂けると有り難いです。

サンプルコードを作成しました
https://github.com/tnakagawa/bipschnorr

動機（Motivation）

全部で５つのMotivationをあげています。
上記３つに関しては、従来のECDSA（Elliptic Curve Digital Signature Algorithm）との比較について記してあります。
最後の２つに関しては、Schnorr Signatureにした時の利点について記してあります。

安全性（Security proof）

Schnorr Signatureでは、楕円曲線離散対数問題(elliptic curve discrete logarithm problem / ECDLP)での仮定の元で安全であると言えますが、
ECDSAには無いとの事・・・（知らなかった）

非展性（Non-malleability）

ECDSAには展性（malleability）があり、秘密鍵を知らない第三者であっても署名値から、別の有効な署名値に変更する事が可能だそうです。
この問題は、BIP-62で論議されているようです。
（筆者は原理を知りません）
Schnorr Signatureでは、そのような事はないそうです。

線形性（Linearity）

Schnorr Signatureは、複数の人が協力して公開鍵の合計に対し有効な署名を生成する事が出来る特性を持っています。
これによって、マルチ署名の効率化やプライバシーの向上が可能となります。

署名エンコード（Signature encoding）

署名をDERエンコードで表しています、これは可変サイズで最大72byteですが、
これを単純な64byte固定長フォーマットにする事が出来ます。

バッチ検証（Batch validation）

ECDSAの場合は個別に検証する必要があります。
これをバッチ検証で効率的に検証可能にします。

デザイン（Design）

Schnorr signature 改良（Schnorr signature variant）

楕円曲線Schnorr署名（Elliptic Curve Schnorr signatures）では以下の式が成り立つことで検証を行います。

\begin{align*}
& m\text{ : message} \\
& P\text{ : public key} \\
& R\text{ : random point} \\
& e = H(R\ ||\ m) \\
& sG = R + eP
\end{align*}

1.(e,s)を署名とする場合
Rの変換が楽になります。

\begin{align*}
& (e,s)\text{ : signatures} \\
& e = H(sG-eP\ ||\ m)
\end{align*}

2.(R,s)を署名とする場合
ハッシュ関数の中に楕円曲線演算が入らないので、バッチ検証が可能となります。

\begin{align*}
& (R,s)\text{ : signatures} \\
& sG = R + H(R\ ||\ m)P
\end{align*}

バッチ検証をサポートする為、(R,s)を採用する

キープレフィックス（Key prefixing）

通常の検証ルールを使用した場合、以下のように変換可能です。

\begin{align*}
& (R,s)\text{ : signatures} \\
& sG = R + H(R\ ||\ m)P \\
& P' = P + aG \\
& (R,s+aH(R\ ||\ m))\text{ : signatures} \\
\end{align*}

Bitcoinでは事前に、公開鍵Pをコミットするので問題はありませんが
今後、他の目的で利用された場合を考慮します。

Schnorr Signatureのキープレフィックスを以下の式に変更します。

\begin{align*}
& sG = R + H(R\ ||\ P\ ||\ m)P \\
\end{align*}

点Rエンコーディング（Encoding the sign of R）

1.RのX座標とY座標を完全にエンコードして、96バイトの署名を生成します。
(X座標32byte ＋ Y座標32byte ＋署名値32byte = 合計 96byte）

2.完全なX座標をエンコードしますが、Yが偶数であるか奇数であるか（圧縮された公開鍵）のみです。
　これにより、65バイトの署名が作成されます。
(Y座標判定1byte ＋ X座標32byte ＋署名値32byte = 合計 65byte）

3.X座標のみエンコードして、64byteとします。
(X座標32byte ＋署名値32byte = 合計 64byte）

1.の場合、検証がやや効率的になります（約5%）が、サイズを優先して3.を選択します。

ただ、このままだとY座標が曖昧になってしまいます。
（すべての有効なX座標には2つの可能なY座標があります。）
切り分ける為にいくつかの中から決めます。

1.半分以下のY座標を暗黙的に選択します。

2.偶数であるY座標を暗黙的に選択します。

3.平方剰余（quadratic residue）であるY座標を暗黙的に選択します。
（剰余平方根をもつ）

Y座標の平方剰余は、ヤコビアン座標（Jacobian coordinates）で表される点に対して直接計算が出来るので、署名時間は遅くなりますが、検証は少し早くなります。
（筆者はなんとなく理解できましたが、教える事ができません。）

3.を選択します。

最終的に以下のようになります。
rは、RのY座標が平方剰余となるX座標です。

\begin{align*}
(r,s)&\text{ : signatures} \\
r&\text{ : the X coordinate of a point R} \\
sG &= R + H(r\ ||\ P\ ||\ m)P \\
\end{align*}

仕様（Specification）

詳しくは、原文：Specification参照

※筆者の推測
平方剰余のY座標を選択する事により、検証が少し早くなると書いてあった部分についてですが、
以下の式で求められるからだと思います。

\begin{align*}
& r\text{ : the X coordinate of a point R} \\
& c = r^3 + 7\pmod{p} \\
& y = c^{\frac{p+1}{4}}\pmod{p} \\
\end{align*}

アプリケーション（Applications）

Schnorr Signatureによりいくつかのアプリケーションが可能となります。

マルチ署名と閾値署名（Multisignatures and Threshold Signatures）

アダプター署名（Adaptor Signatures）

ブラインド署名（Blind Signatures）

さいごに

これが実装されると、署名、検証の効率化はもちろん
様々な用途に流用される事が出来るので、よりBitcoinの利用方法に幅が出ると思います。