はじめに

BlockstreamのJonas NickがMediumに投稿した記事、「Reducing Bitcoin Transaction Sizes with x-only Pubkeys by Blockstream」について解説していこうと思います。

概要

Bitcoinでは、楕円曲線暗号のsecp256k1を使用しています。
署名については、ECDSAを使用しているのですが、新たに楕円曲線を使用したSchnorr署名(Schnorr Signatures for secp256k1)を採用する事について論議されています。

その仕様策定の中で、公開鍵を$x$座標だけにするといった提案が採用されそうです。

楕円曲線（elliptic curve）

ここでは、簡単に説明します。（既知の方は読み飛ばしてください。）
楕円曲線（secp256k1では、$y^2=x^3+7$）において点の加算を定義します。

例）緑点を$P$、青点を$Q$、$P+Q=R$とした時、**赤点が$R$となり、橙点は$-R$**となります。

ある生成元を$G$とし、生成元を$d$回加算した点を$P$とします。（式で表すと、$P=dG$）
秘密鍵が$d$、公開鍵が$P$となります。
要するに、秘密鍵は生成元を**$d$回加算したという$d$、公開鍵は楕円曲線上の点（座標）**ということです。
例の図は実数の曲線ですが、コンピューターで実数は扱えない為、有限体を使用します。
公開鍵の位数を$p$、秘密鍵の位数$n$は以下のようになります。（どちらも素数）

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

どちらも、32バイト（256ビット）に近い値です。
秘密鍵は、32バイトで表す事ができますが、公開鍵は、$x$座標と$y$座標の2つが必要です。
例えば生成元$G$は次のようになります。

x = 79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
y = 483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

座標を表現するには、32バイト×2=64バイト必要になります。

点の加算で説明したように、ある点を$P:(x,y)$としたとき、$x$軸に対称な点が$-P:(x,-y)$となります。
有限体の定義より、$-y=p-y$となります。$p$は2より大きい素数なので、もちろん奇数となります。
$y$が偶数であれば$-y$は奇数に、$y$が奇数であれば$-y$は偶数になります。
楕円曲線の式$y^2=x^3+7$から、$x$座標がわかれば$y$を求める事が出来ます。
あとは、$y$が偶数なのか奇数なのかを知る事ができれば、$x$から$y$を復元する事ができます。
そこで、$x$座標の先頭に$y$が偶数であれば0x02、奇数であれば0x03を付加することで32バイト+1バイト=33バイトで表すようになりました。
例えば生成元$G$の$y$座標は末尾が0xB8なので、偶数となり$x$座標に0x02を先頭に付加し次のように表す事ができます。

G = 0279BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798

x座標だけの公開鍵

やっと本題です。
「x座標だけの公開鍵」とはどういうことでしょう？
すばり、0x02や0x03の1バイトを削除して、$x$座標だけを使うということです。

それで成り立つの？と思うかもしれません。
$d$を秘密鍵としたとき、$x$座標だけだと、$(x,y)$なのか$(x,-y)$なのか区別がつきません。
そこで、この提案では0x02として扱うという事でこの問題を解決しています。

ただ、以下の点が気になります。

何かメリットあるの？
セキュリティは大丈夫？
ロジックは大丈夫？

何かメリットあるの？

単純に考えると、1バイト減ります。
Bitcoinの場合、Weight Unitという指標があります。
この指標から、約0.7%減るという試算が出ています。

セキュリティは大丈夫？

秘密鍵による離散対数問題（discrete logarithm problem）によりセキュリティが担保されているわけです。
したがって、秘密鍵が漏れてしまわない限りセキュリティは担保されています。

ロジックは大丈夫？

署名時に工夫が必要です。
※最後の章で詳しく説明します。

楕円曲線を使用したSchnorr署名

簡単に署名と検証手順について説明します。
小文字はスカラー、大文字は楕円曲線上の点とします。
$\text{H}(\cdot)$をハッシュ関数とします。スカラーを返します。
秘密鍵を$d$とした時、公開鍵$P$は$P=dG$となります。
署名には、乱数が必要です。乱数を$k$とした時、乱数点$R$は$R=kG$となります。
また、$m$をメッセージとします。

署名

署名値$s$を以下の式で計算します。
$s = k + \text{H}(R,P,m)\cdot d$

署名値は$(s,R)$となります。

検証

検証者は、署名値$(s,R)$と、公開鍵$P$、署名されたメッセージ$m$を知っているので以下の式の両辺を計算して合致するか判定します。

$sG \overset{?}{=} R + \text{H}(R,P,m)\cdot P$

x座標だけのSchnorr署名

メッセージに署名する人は、公開鍵のポイントが偶数であるか奇数であるか知っています。
それによって、署名する方法を切り替える必要があります。

偶数の場合

この場合は通常で問題ありません。
$s = k + \text{H}(R,P,m)\cdot d$
署名値は$(s,R)$となります。

奇数の場合

この場合は、秘密鍵を$d$とすると、$y$座標が偶数の秘密鍵は$-d$と考える事ができます。
したがって、署名値の計算は以下の式となります。
$s = k -\text{H}(R,P,m)\cdot d$
署名値は$(s,R)$となります。

Google Colaboratoryで実装してみたので、興味のある方は参考にしてみてください。

おわりに

Bitcoinに今後採用されていく、BIP-SchnorrやBIP-taprootはまだまだ論議中です。
以前どこかに書いたと思いますが、1バイトを削る為にかなりの労力が必要だと思いました。
署名ロジックの変更は署名ソフトの改変が必要なので、Schnorr署名が本格的に導入される前にいろいろ論議する必要があると思っています。