Ethereumの署名のRecovery ID

Recovery ID?

Ethereum の署名には、通常の ECDSA の署名で出てくる $r$ , $s$ に加えて $v$ が必要になる。
EIP-155 に従う場合、$v$ の計算は、

v = recoveryId + chainId *2 + 35

となる。chainId は、Mainnet なら 1 、Ropsten なら 3 等、すぐわかるが、 recoveryId はわかりにくい。recoveryId は署名の検証で使う。

署名の検証

署名の検証では、以下の式を使って計算された公開鍵が、署名に使われた秘密鍵に対応した公開鍵であるかをチェックする。

公開鍵 = (署名s・署名で使われた点 - メッセージハッシュ・加法巡回群の生成元) / 署名r

署名r , 署名s 、メッセージハッシュ、生成元はわかっているので、署名で使われた点を、署名r から復元することで、署名の正しさを確認することができる。ここで Recovery ID が必要になる。

n と p と r

ECDSA の加法は、$\bmod p$ の世界で定義されているので、楕円曲線上の点は $p$ 未満の整数になる。
また $r$ は、楕円曲線上の点の x 座標を、加法巡回群の生成元の位数 $n$ で $mod$ したものなので、$\bmod n$ の世界の数で、$n$ 未満の整数になる。
また加法巡回群は、$\bmod p$の世界の中で定義されていているので、$n < p$ になる。

r から点

x 座標

x 座標から作られる $r$ は、$\bmod p$ の世界から、$\bmod n$ の世界に変換されているので、変換前と後で値が変わっている可能性がある。
変わっている場合は、Ethereumで使われている secp256k1 では、$2n > p$ なので、$n + r$ になる。（ $2n$ 以上になると $p$ を超える）
なので、x 座標の値は、$r$ か $r+n$ のどちらかになる。

y 座標

楕円曲線は、x 軸を中心として上下に対称になっていて、一つの点の x 座標に対して、対になる点が、反対側の象限に必ず存在する。y 座標はこのどちらかの点の y 座標になる。

楕円曲線の加法では、ある曲線上の点と同じ x 座標をもっていて、反対側の象限にある曲線上の点は、加法逆元として定義されているので、対になる点同士を足すと単位元になる。

$y$ を求める計算は $\bmod p$ の世界での計算になるので、仮に片方の点の y 座標が $y$ だとすると、その加法逆元の $p-y$ がもう片方の点の y 座標になる。($y + p - y \equiv p \equiv 0 \bmod p$)。 $p$ は素数で奇数なので、$y$ が偶数なら、$p-y$ は奇数、$y$ が奇数なら、$p-y$ は偶数というように、$y$ は奇数か偶数かのどちらかになる。

ECDSA 署名としては正しくて、Ethereum 署名としては正しくない署名

Ethereum の Yellow Paper に $r$ は $\bmod n$ の世界の数でないといけないと書いてあるので、
ECDSAの署名としては正しくても、署名の点の x 座標が $r+n$ だった場合は Ethereum の署名として不正になる。
この記事を書いた時点では、24 ページの (300) にその記載がある。
$n$ が $p$ に対してかなり大きいため、$r+n$ になる確率は $1/2^{128}$ 位で相当低いので、引っかかることはまずない。（暗号学的にはありえないとかどこかに書いてあった。）
あとは、$s$ が $n$ の半分以下でないといけないという制限もある（Yellow Paperの (301) ）。こちらは理屈はわかってない。
ECDSA の署名をこのあたりの制限がない環境で作ると、たぶん $s$ で引っかかっているのか、5 回に 1 回くらいは Ethereum で不正な署名になる。（細かく見てない）

r が紐づく可能性のある点と Recovery ID

Ethereum で不正とされている範囲を除くと、$r$ が紐づく可能性がある楕円曲線上の点は、点のx座標が $r$ で、$y$ が 奇数のものと偶数のものの 2 通りになる。それぞれに Recovery ID が紐づいている。

Recovery ID=0 -> yがEven
Recovery ID=1 -> yがOdd

署名の検証での Recovery ID の役割

署名の検証時に Recovery ID を渡すことで、署名で使われた楕円曲線上の点が特定できるようになり、署名に紐づく公開鍵も計算できるようになる。