ecrecoverでpublic keyが一意に定まる理由 - アルゴリズムとかオーダーとか

y-nakajo.hatenablog.com
以前の記事でEthereumの署名検証の仕組みについて書きましたが、この記事を書いてる時にecrecover(hash, v, r, s)で署名と元となるhashデータから公開鍵が求まるのが不思議でid:techmedia-thinkに質問したところブログでまとめてくれました。
techmedia-think.hatenablog.com

なのですが、上記ブログではrが与えられた時には候補となる公開鍵が２（もしくは４）つ求まるとありますが、ecrecover(hash, v, r, s)ではただ１つの公開鍵が求まります。今回はこの理由について調べたことをまとめたいと思います。

公開鍵を一意に決定づけるパラメーター v

前述のブログ記事では、署名データの(r, s)についてのみ触れられていました。ethereumでの署名データはさらにvというパラメータを追加した(r, s, v)で定義されています。(r = 32 byte, s = 32 byte, v = 8bit integer 0 or 1）

このvがpublic keyを一意に定めるための重要な役割を担っています。
Ethereum YellowPaperによると

It is assumed that v is either the ‘recovery identifier’ or ‘chain identifier doubled plus 35 or 36’. The recovery identifier is a 1 byte value specifying the parity and finiteness of the coordinates of the curve point for which r is the x-value; this value is in the range of [27, 30], however we declare the upper two possibilities, representing infinite values,invalid. The value 27 represents an even y value and 28 represents an odd y value.
vは「回復識別子」または「2倍のチェーン識別子35または36」のいずれかであると仮定されています。回復識別子は、rがx値である曲線点の座標のパリティと有限性を指定する1バイトの値です。この値は[27、30]の範囲にありますが、無限の値を表す上位2つの可能性が無効であることを宣言しています。値27は偶数y値を表し、28は奇数y値を表す。

また、yが偶数の時は正の値、奇数の時は負の値をとることから*1、v=27の時はyが正のポイント(x, y)が公開鍵となり、y=28の時は(-y, x)が公開鍵となる　ということだそうです。

まとめ

ethereumではrecovery idを付加することで公開鍵を一意に定められる様にしてます。ちなみになぜbitcoinでは同様に署名から公開鍵を復元しないのか？っていうと、ちょうどポストが出てて、遅いから　っていう理由の様です。（他にも２つほど理由をあげてたみたいですが言われてもピンとこない。。。）

ちなみにrecovery idについてですが、yが正の時に偶数になって、yが負の時に奇数になるっていうのはまだちょっとよくわかってないです。
y + (-y) = 0mod(p)から、対象となるyについて、y mod(p)が偶数なら -y mod(p)が奇数であり(モジュロの結果は常に正になるので）、その逆もありえるというのはわかるのですが、他の説明を見る限りどうも偶数ならyは正の数になるって断定してるっぽい感じみたいなので、そこがよくわかってないのでまだまだ勉強しないといけないですね。

参考

*1:Elliptic Curve Cryptography、2.3.3を参照