Ethereumでトランザクションに署名をしたり, その検証をしたり, 署名から公開鍵(EOAアドレス)を導出する方法を整理しておきます.

以下ができます.

1. 秘密鍵の所有者が, トランザクションの実行を許可したことを署名によって確認する
2. 1自体(トランザクションの実行を許可したこと)を否定できないことを保証する
   秘密鍵の所有者でないと, 有効な署名は作れないので, 当然ですね.
3. 署名されて以来, トランザクションが改ざんされていないことを証明する
   トランザクションの内容が書き換わると, トランザクションのハッシュ値も変わるので, 署名が無効になります.
4. 署名から, トランザクションを作成したアカウントの特定(EOAアドレス=公開鍵を導出する)
   トランザクションにはfromアドレスが記載されていないので, 署名から送信元アドレスを計算する必要があります.

署名のデータ

署名には, $(r, s, v)$という3つのデータが入っています. このうち, $v$はチェーン識別子です.

$m$がトランザクション(nonce, gasPrice, gasLimit, to, value, data, vを適切に設定し, rとsにはゼロを入れたもの)を, RLPでエンコードしたものとします.

$k$は, 秘密鍵とします.

署名は,

$(r, s) = F_{sig}(m, k) $

という感じで生成します.

署名をやってくれる$F_{sig}$の中身はどうなっとるんじゃいという話ですが, Ethereumで採用されている署名アルゴリズムはECDSA(楕円曲線デジタル署名アルゴリズム)です.

一応その手順を以下に記しておきます. 楕円曲線暗号よくわかっとらんので, 間違ってたりとかしたら教えてください.

1. 一時的な秘密鍵として, 乱数$q$を生成する.
2. $q$に対応する一時的な公開鍵$Q$を, 秘密鍵$q$から生成する.
   署名作成のときに一時的に使う公開鍵を, 楕円曲線生成元$G$から生成します.
3. $r$は, 一時公開鍵$Q$のx座標になる
   

   まあ楕円曲線ってこんな感じのやつで, 一時公開鍵$Q$は楕円曲線上の点だったと思いますので, そのx座標を$r$とするわけですね.

4. $s = q^{-1}(keccak256(m) + r cdot k) (mathrm{mod} p )$
   $s$はこのように求めるそうです(ハナホジ).
   $p$は楕円曲線の素数次数.

はい, これで無事に$(r, s)$がそれぞれ求まったかと思います. これ+チェーン識別子$v$が署名になるわけですね.

署名の検証は署名の作成と逆で, 署名$(r, s)$から一時的な公開鍵$Q’$を計算する処理をやります(ハナホジ2).

1. $w = s^{-1} mathrm{mod} p$
2. $u_1 = keccak256(m) cdot w mathrm{mod} p$
3. $u_2 = r cdot w mathrm{mod} p$
4. $Q’ = u_1 cdot G + u_2 cdot K (mathrm{mod} p) $

そして, これで$Q’$のx座標と$r$が等しければ, 署名が有効だねということになります.

「署名でできること」の4でも触れましたが, トランザクションには送信元アドレスは含まれていません. なのでトランザクションの送信者を把握したいときは, 署名の$r$から対応する公開鍵(これは先程出てきた一時的な公開鍵$Q$ではなくて, EOAの公開鍵)を計算してあげる必要があります.

以下の手順で, EOAの公開鍵を計算します.

1. $r$って楕円曲線上の点のx座標でしたよね. そこで, $r$から対応する一時的な公開鍵$Q$の候補$R$と$R’$を求めます.
   

   ここで, 楕円曲線はx軸で対称なので, 対応する点は2つ考えられますね. そこで, チェーン識別子$v$が偶数のときは$R$を, 奇数のときは$R’$を採用します.
   なんでかは知らん. 誰か教えてください.
   ↑Twitterで親切な方々に教えていただきました.

   蛇足ながら。ECDSAの署名計算では、r=(kGのx座標) ( kは秘密の乱数 ) があり、公開鍵の逆算 ( recover ) では kG の値が必要ですが、ただ x 座標1つに対して y座標は2つの候補(偶奇)があります。なので、recover 可能なように、署名の際に kG のy座標の偶奇情報を v として残す、と認識しています。

   — angel (as ㌵㌤の猫) (@angel_p_57) December 19, 2021

   すべて、奇素数pで割ったあまりの世界を考えたうえで、

   任意のp未満の整数yについて、次が成り立ちます。

   -y ≡ y – p (mod p)

   さらにいうと
   ・yが奇数のとき、-yは偶数
   ・yが偶数のとき、-yは奇数

   — あっかこー (@_nxnxbh) December 19, 2021

   なので、計算して得た公開鍵（Px, Py）が以下の条件であれば、正しい公開鍵として使うことができます。

   ・vが奇数かつ、Pyが奇数
   ・vが偶数かつ、Pyが偶数

   逆にいかの公開鍵は棄却します。

   ・vが奇数かつ、Pyが偶数
   ・vが偶数かつ、Pyが奇数

   — あっかこー (@_nxnxbh) December 19, 2021

2. 公開鍵$K$ = $r^{-1}(sQ-zG)$

これで, 送信者の公開鍵を求めることが出来ました.

公開鍵からアドレスを求めるには, $keccak256(K)$の最後の20byteを切り出せばOKです.