ビットコインやイーサリアムなどのブロックチェーンネットワークにおいて、不正なく「正しい送信元から正しい相手に正しい送金額」を送るためにECDSAという暗号技術が用いられています。
例えば、アリスがボブに1ETHを送りたいときは、イーサリアムネットワークにアリスがトランザクションを送信しますが、そのトランザクションが間違いなくアリスが生成したものであり、かつその事実を誰もが正しいと検証できる必要があるのです。
そこで、ここではECDSAを使ってブロックチェーンネットワークにおいてどのようにしてこの正しいトランザクション署名の生成および検証が行われているのか解説していきます。
ECDSAとは
ECDSA(Elliptic Curve Digital Signature Algorithm)とは、楕円曲線DSAとも呼ばれビットコインやイーサリアムの文脈では特にトランザクションの署名に使われます。
例えば、アリスがボブに1ETHを送るとき、宛先である「ボブのアドレス」や送金額「1ETH」などがトランザクションデータとして分散ネットワークにブロードキャストされます。このトランザクションが検証されれば最終的にブロックチェーンに記録され、アリスとボブの残高が変化します。
しかし、ブロックチェーンの分散ネットワークにおいて、上記のトランザクションに対して正しく合意形成を行うためには以下の3つの要素が必要になります。
- 間違いなくアリスが生成したトランザクションであること(他の第三者によって生成された偽データではない)
- トランザクション生成後、第三者によってデータが改ざんされていないことが確認できること
- アリスが生成したトランザクションであると誰もが証明できること
ECDSAによるトランザクションの署名はこれらの条件を満たすことができます。つまり、アリスはトランザクションをブロードキャストするときにあらかじめ、トランザクションに署名をしておくことで間違いなくアリスが送ったトランザクションであり、その署名がある限りデータは改ざんされていない、ということがネットワーク上に誰によっても証明されることになります。
このような暗号化技術はRSAなどさまざま種類が存在しますが、現時点では、ビットコインやイーサリアムにおけるトランザクションの署名はECDSAで行われています。なぜ、ECDSAが用いられているのかというと、RSAに比べ暗号化のための鍵が少ないデータサイズでも十分に強力であるからです。
ECDSAによる署名生成・検証の概要
ECDSAの詳しい解説に入る前にまずは署名の生成と検証の概要について見ていきましょう。ECDSAは上述したようなトランザクションからの署名生成に加え、その署名が本当にトランザクション送信者によるものなのか、つまりアリスが本当に署名をしたのかという「検証」も行われます。
この署名生成と検証は秘密鍵とそれに対をなす公開鍵によって行われます。(秘密鍵と公開鍵の内容はこちらの記事を参考にしてください。秘密鍵から公開鍵そしてアドレスが生成されるまでの流れ)
つまり、送信者アリスしか持っていない秘密鍵によってトランザクションから署名が作られ、その署名はネットワークの誰もが持つことができる公開鍵によって検証できます。この秘密鍵と公開鍵は上述の記事で解説している通りペアをなしているので、送信者アリスは自身の秘密鍵を明かすことなく、その秘密鍵による署名はアリス自身のものであるという証明ができるのです。
ECDSAにおいて秘密鍵を使ってトランザクションから生成した署名はイーサリアムでは、r,s,vという3つの値から成り立ちます。(EIP-155によってリプレイアタック対策のためにv値の算出方法が変更しました。)これら(r, s, v)の値と送信者(署名者)の公開鍵を用いることで、トランザクションが正しく署名されていることを確認するための検証作業が行われます。
これらr, s, vの算出方法について見ていく前に、まずは前提知識となる楕円曲線上での演算方法について見ていきましょう。
前提知識:楕円曲線
楕円曲線上の実数体演算
ECDSAを理解するための前提知識としてまずは楕円曲線上の演算を定義していきます。楕円曲線とは一般的に、以下のような方程式で表される曲線です。$$y^2={x^3}+{ax}+b$$
ビットコインやイーサリアムではsecp256k1曲線という形式が用いられているので、a=0, b=7として、以下のように表されます。$$y^2={x^3}+7$$
以下ではこの楕円曲線について考えていきます。
まず、secp256k1曲線上でA+Bの加算をしたいときは以下のように点Aと点Bを通る直線を引き、曲線との交点のx軸に関する対称点がA+Bとなります。これが、楕円曲線上での加算の定義となります。
同じ要領でsecp256k1曲線上の点Gから2Gを求めたいときは、G+Gを行えばいいので以下のように点Gの接線から交点を求め、その交点のx軸に関する対称点が2Gとなります。
このような楕円曲線上の2G+G=3G, 3G+G=4G….とr回繰り返していくと、楕円曲線上にある点rG=(x,y)が得られます。
そして、実はこの値rがイーサリアム等で用いられる秘密鍵になります。そして、secp256k1の形式で定められたベースポイントG(x, y)から秘密鍵rを用いることで算出されたrG(x, y)が公開鍵になっているのです。(secp256k1では、安全性を満たすように考えられたGx=0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f8179、Gy=0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8が用いられています。)
つまり、ベースポイントGが与えられて、自身の秘密鍵rを持っていれば上述のようにGをr回楕円曲線上で加算することで簡単に共通鍵rGを得ることができます。しかし、楕円曲線の性質上、逆に共通鍵rGから値rを求めることは困難です。
どのような楕円曲線か、どのベースポイントGかはsecp256k1により定義されている上で、共通鍵rGから秘密鍵rを求めることがとても難しいのです。(これを楕円曲線上の離散対数問題と呼びます。)要は、ハッシュ関数のような一方向性の性質を持っています。
つまり、楕円曲線暗号ではこの離散対数問題の難しさを利用することで、「秘密鍵から公開鍵を生成するのは簡単だけれども、公開鍵から秘密鍵を求めることは極限に難しい」という状況を生み出していることになります。
楕円曲線上での有限体演算
ここまでは、楕円曲線上の座標(x,y)は実数であると仮定していました。(実数体)しかし、実際の楕円曲線暗号では、実数体ではなく有限体上で楕円曲線を考えることになります。有限体(ガロア体)とは、pを素数とし位数(要素数)pの{0, 1, 2, …. , p-1 }というp個の整数集合を用いて演算を行います。つまり、整数を素数pで除算したときの余りの集合であり、かつ有限集合でその要素に対して四則演算を行うことができます。
例えば、p=11の有限体であれば{0,1,2,3,4,5,6,7,8,9,10}の整数集合で上述の加算などを行なっていきます。
なので、この有限体での演算ではpを法とした時計演算が行われます。つまり、pで割った余りで考え、一般的にmodという演算子で表現します。例えば、P=5のとき19 mod 5 = 4であり、20 mod 5 = 0になる要領です。
よって、実数体上で楕円曲線を考えると上図のような滑らかな曲線を描くことができますが、有限体上の楕円曲線は整数集合なので複数の点の集合となり、曲線にはなりえないことになります。。
そして、上述したように有限体上の楕円曲線上においてpの値が大きくなるほどGとrGから値rを求めることが難しくなる離散対数問題を考慮すると、安全性が高いsecp256k1においてpの値がp=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f(16進数)=2^256-2^32-977 という非常に大きな値で定められている理由になります。
以下では、この楕円曲線上での演算の性質を利用することで署名の生成および検証を行なっていきます。
ECDSAによる署名生成
まず、ECDSAによる署名生成ではR, Sという2つの値を生成し、トランザクションとともにブロードキャストします。
ECDSAによる署名生成はここまで解説したsecp256k1の楕円曲線上での有限体演算を用いて行われます。なので以下の演算は全てsecp256k1で定義された曲線、ベースポイントGでp(=2^256-2^32-977)を法とする時計演算で行われることになります。
トランザクションの生データがそのまま署名生成に用いられるのではなく、トランザクションをRLPエンコードしたもののKeccak256ハッシュ値hが署名生成に用いられます。
また、上述したように署名に用いられる鍵はトランザクション送信者自身の秘密鍵kになります。これらの値を用いて以下のような値Sを算出していきます。
$$S=\frac{h+kR}{q}{(mod p)}$$
- q:署名生成のための一時的な秘密鍵
- h:トランザクションのハッシュ値
- k:送信者の秘密鍵
- R:一時的な公開鍵のx座標(つまり、ベースポイントGから算出したqG=(x, y)のx)
この値Sと点qG(x, y)のx座標(つまりR)が署名となりトランザクションデータと併せてブロックチェーンネットワークに送信されることになるのです。
イーサリアムにおいてはRとS以外にもVという値も送信する必要がありますが、V値については後述します。
ECDSAによる署名検証
ブロックチェーンネットワーク上に送信された署名付きトランザクション(つまり、SとRとトランザクションデータ)は送信者アリスの公開鍵kG(=K)を用いて、「本当にアリスによる署名なのか」ということが検証できます。
まず受け取ったトランザクションデータからハッシュ値hを算出し、以下のQを検証します。
$$Q=\frac{hG}{S}+\frac{RK}{S}{(mod p)}$$
- S, Q:送信者アリスから受け取った署名
- h:トランザクションデータのハッシュ値
- G:secp256k1のベースポイント
- K:送信者アリスの公開鍵(=kG)
このQのx座標が受け取ったRと等しければ、正当な署名であると証明することができます。これは以下のような演算が行われます。
$$Q=\frac{hG}{S}+\frac{RK}{S}{(mod p)}$$
K=kGであり、S値を代入して計算すると、
$$Q=\frac{q(h+kR)}{h+kR}G$$
$$=qG$$
となります。これはRと確かに一致するので、この署名はアリスによるものであると検証することができました。
しかし、イーサリアムにおいては上述のr, sという値に加え、vという値も追加的に用いています。その理由を見ていきましょう。
イーサリアムでの署名に値vが必要な理由
イーサリアムでは、署名を送るとき上記のr,sに加えてvという値も送る必要があります。なぜvを送る必要があるのかというと、以下の2つの理由があげられます。
- リカバリー時に公開鍵を一意に決めるため
- リプレイアタック対策のため(EIP-155)
そもそもトランザクションデータには、宛先のアドレスは含まれていますが送信者のアドレスは含まれていません。これはなぜかというと、ECDSA署名から署名者(送信者)の公開鍵を算出することができるからです。そして、公開鍵を得ることができればそこから簡単にアドレスを復元することができます。
しかし、署名から公開鍵を復元すると2つの公開鍵が生成してしまうことになります。なぜかというと、前図のように楕円曲線はx軸に対して対称であるため、ひとつのx座標Rに対して2つの点が定まってしまい結果的に公開鍵が2つ生成してしまうからです。
そこで、プレフィックスとしてv値を定義することで、署名から公開鍵を復元するときに公開鍵を一意に定めているのです。つまり、後述するv値が偶数であるか奇数かで公開鍵を一意に定めていることになります。
注記
上記について正しくは公開鍵が2つ、あるいは4つ生成することになります。
ご指摘ありがとうございます。secp256k1の場合、x座標はx=r+jn(j=0,1)となり、rとr+nの2パターンが考えられるが、r+nが定義内におさまるケースに公開鍵が4つの候補になり、それ以外の場合に(r, y)、(r, -y)の2つの候補ということなんですね。注記いれておきます!
— Osuke (@zoom_zoomzo) 2018年5月15日
さらに、EIP-155ではv値に対してこの機能に加えて、リプレイアタック対策の機能を設けることになりました。つまり、vにchain_idの要素を加えることでテストネットのETHをメインネットのETHで使えてしまうということをvを検証することで防げるようになったのです。
EIP-155適用後のvの値は以下のように定められます。(EIP-155適用前はv値は27または28でした)
$$v={chainId}\times{2}+8+{(27 or 28)} $$
r, sのフィールドはトランザクション作成時はゼロに固定されています。
そして、送信される署名トランザクションデータの構造は以下のようになります。
- nonce
- gasPrice
- gas limit
- to
- value
- data
- v, r, s
rとsは32bytesであり、vはメインネットやテストネットであれば1byteです。(ただし、プライベートネットワークでchain IDが大きな値になる場合は、vは1byte以上になりえます。)
(v,r,s)フィールドを加えたrawトランザクションデータをRLPエンコードしハッシュ値を算出することで署名生成が行われ、その後、上述の検証が行われます。なので、EIP-155適用後は署名検証時に従来のr,sの検証が行われる前にvを検証することで正しいネットワークであるのかを検証することができるようになったのです。