Pebble Coding

ソフトウェアエンジニアによるIT技術、数学の備忘録

主要な仮想通貨のネットワークハッシュレート

仮想通貨

いくつかの主要な仮想通貨のネットワークハッシュレートを調べてみました。
値が大きいほど、ある種の攻撃に対して耐性を持ちます。

Hasseの定理から導き出される補題

暗号

楕円曲線に限定した Hasse の定理
F_p 上の任意の楕円曲線の有理点の個数 \#E の範囲は以下となる。
p + 1 - 2 \sqrt{p} \leq \#E \leq p + 1 + 2 \sqrt{p}

補題
楕円曲線 E ( F_p) に含まれる点Pで、
m P = O
となる m が Hasse の定理により定まる曲線の位数の区間
p + 1 - 2 \sqrt{p} \leq m \leq p + 1 + 2 \sqrt{p}
に唯一存在する時、
\#E = mとなる。

この補題は Hasse の定理から導かれます。
m P = Oということは点Pの位数がmということです。
曲線の位数 #E は点の位数の倍数です。
範囲の最小値、最大値を以下のように表現する。
a_{min} = p + 1 - 2 \sqrt{p}
a_{max} = p + 1 + 2 \sqrt{p}

最小値の2倍と最大値の差をとってみる。
2 a_{min} - a_{max}
= 2p + 2 - 4 \sqrt{p} - (p + 1 + 2 \sqrt{p})
= p - 6 \sqrt{p}
これはpが十分大きいと0より大きい。
これは a_{min}, a_{max}の範囲内の値の倍数はこの範囲内にはないということである。
したがって、倍数は1しかありえないため \#E = m だということになる。

この補題はBaby-step giant-step(BSGS)法の根拠の一部になっている。
力任せに総当り法で#Eを求めたい場合は、 4 \sqrt{p}通りの値を総当たりすれば良いということになる。
BSGS法はこれよりももっと効率が良い方法である。

256bitの暗号化はどの程度強固なのか

暗号

256bit(=32バイト)の暗号化はどの程度強固なのかというのを説明したYouTubeの動画が面白かったのでリンクを貼っておきます。

www.youtube.com

内容としては、まず、8つの大きさに分解します。
{2} ^ {256} = {2} ^ {32} \cdot {2} ^ {32} \cdot {2} ^ {32} \cdot {2} ^ {32} \cdot {2} ^ {32} \cdot {2} ^ {32} \cdot {2} ^ {32} \cdot {2} ^ {32}

それぞれ、M1, M2, M3, ..., M8と表すことにします。

そして、
{2} ^ {32} = 4Giga
です。
GPU(Graphical Processing Unit)の処理速度のオーダーは数GHzです。
つまり、マシン１台辺り1秒間に1Giga個のハッシュを生成できます。
これをM1とします。

そしてグーグルが持つサーバーの台数は数Megaのオーダーです。
これをM2とします。
M2=Kilo Google

地球上の人口は7Giga人ですが、仮に、全員が1Kilo Googleの計算力を持つと仮定します。
これをM3とします。
M3= People on Earth

天の川銀河には100から400Gigaの星がありますが、このうちの1%が全て地球だったと仮定します。
これをM4とします。
M4 = Earth

宇宙には銀河が4Giga個存在すると仮定します。
これをM6とします。

4Giga秒は126.8年に相当します。
これをM7とします。

4Giga かける 126.8年は507Giga年に相当します。これは宇宙の年齢の37倍に相当します。

まだM8が残っていますから、
このハイパーコンピューターで計算した場合に、ハッシュが当る確立は4Giga分の1の確立です。

リカバリーIDについて小さな例を用いて実感する

暗号

一つ前の記事では署名のリカバリーIDについて書きました。

Ethereum の署名とBitcoin の署名 - Pebble Coding

が、いまいち分からんと思うので、実感するため、小さい例で考えてみます。
曲線はsecp256k1と同じ、 y^{2} = x^{3} + 7 を使いますが、法素数は31=pを使います。
この時、群の位数は、21=nとなります。つまり、Oを含めて有理点の数が21個あるということです。
有理点(P1, P2, ..., P19, P20, O) のうち位数が21の点はいくつかありますが、
ここではP3をベースポイントGとして選びます。
以下、P3の点はx座標が1, y座標が15で(1,15)と書きます。
P3を2倍,3倍した時の点の座標は以下のようになります。
21倍したところで、Oになっていますね。

P3:(1,15)
2*P3:(7,3)
3*P3:(27,6)
4*P3:(5,15)
5*P3:(25,16)
6*P3:(24,6)
7*P3:(0,21)
8*P3:(4,3)
9*P3:(11,25)
10*P3:(20,28)
11*P3:(20,3)
12*P3:(11,6)
13*P3:(4,28)
14*P3:(0,10)
15*P3:(24,25)
16*P3:(25,15)
17*P3:(5,16)
18*P3:(27,25)
19*P3:(7,28)
20*P3:(1,16)
21*P3:O

ここでECDSAをおさらいしておきます。

http://pebble8888.hatenablog.com/entry/2018/03/03/154115

ベースポイントを何倍するかという値がnonceですが、
nonce * P3 のx座標( R_x = r と書きます。) がn(=21)より大きい場合はオーバーフローですから、除外します。
以下を除外することになります。

P3:(1,15)
2*P3:(7,3)
3*P3:(27,6) <- コレ
4*P3:(5,15)
5*P3:(25,16) <- コレ
6*P3:(24,6) <- コレ
7*P3:(0,21)
8*P3:(4,3)
9*P3:(11,25)
10*P3:(20,28)
11*P3:(20,3)
12*P3:(11,6)
13*P3:(4,28)
14*P3:(0,10)
15*P3:(24,25) <- コレ
16*P3:(25,15) <- コレ
17*P3:(5,16)
18*P3:(27,25) <- コレ
19*P3:(7,28)
20*P3:(1,16)
21*P3:O

ここで除外したのものはリカバリIDが2, 3のものです。
Ethreumではこのように、nonce * Gのx座標がnより大きい場合はnonceを取り直す
ということをやっているのだと思います。(すいません。ソースを確認した訳ではありません。)

※1 F31を使った全ての点の計算結果は以下です。

F31
#EC:21

P1:(0,10)
2*P1:(0,21)
3*P1:O
order:3

P2:(0,21)
2*P2:(0,10)
3*P2:O
order:3

P3:(1,15)
2*P3:(7,3)
3*P3:(27,6)
4*P3:(5,15)
5*P3:(25,16)
6*P3:(24,6)
7*P3:(0,21)
8*P3:(4,3)
9*P3:(11,25)
10*P3:(20,28)
11*P3:(20,3)
12*P3:(11,6)
13*P3:(4,28)
14*P3:(0,10)
15*P3:(24,25)
16*P3:(25,15)
17*P3:(5,16)
18*P3:(27,25)
19*P3:(7,28)
20*P3:(1,16)
21*P3:O
order:21

P4:(1,16)
2*P4:(7,28)
3*P4:(27,25)
4*P4:(5,16)
5*P4:(25,15)
6*P4:(24,25)
7*P4:(0,10)
8*P4:(4,28)
9*P4:(11,6)
10*P4:(20,3)
11*P4:(20,28)
12*P4:(11,25)
13*P4:(4,3)
14*P4:(0,21)
15*P4:(24,6)
16*P4:(25,16)
17*P4:(5,15)
18*P4:(27,6)
19*P4:(7,3)
20*P4:(1,15)
21*P4:O
order:21

P5:(4,3)
2*P5:(25,15)
3*P5:(27,6)
4*P5:(20,3)
5*P5:(7,28)
6*P5:(24,6)
7*P5:(0,10)
8*P5:(1,15)
9*P5:(11,25)
10*P5:(5,16)
11*P5:(5,15)
12*P5:(11,6)
13*P5:(1,16)
14*P5:(0,21)
15*P5:(24,25)
16*P5:(7,3)
17*P5:(20,28)
18*P5:(27,25)
19*P5:(25,16)
20*P5:(4,28)
21*P5:O
order:21

P6:(4,28)
2*P6:(25,16)
3*P6:(27,25)
4*P6:(20,28)
5*P6:(7,3)
6*P6:(24,25)
7*P6:(0,21)
8*P6:(1,16)
9*P6:(11,6)
10*P6:(5,15)
11*P6:(5,16)
12*P6:(11,25)
13*P6:(1,15)
14*P6:(0,10)
15*P6:(24,6)
16*P6:(7,28)
17*P6:(20,3)
18*P6:(27,6)
19*P6:(25,15)
20*P6:(4,3)
21*P6:O
order:21

P7:(5,15)
2*P7:(4,3)
3*P7:(11,6)
4*P7:(25,15)
5*P7:(1,16)
6*P7:(27,6)
7*P7:(0,21)
8*P7:(20,3)
9*P7:(24,25)
10*P7:(7,28)
11*P7:(7,3)
12*P7:(24,6)
13*P7:(20,28)
14*P7:(0,10)
15*P7:(27,25)
16*P7:(1,15)
17*P7:(25,16)
18*P7:(11,25)
19*P7:(4,28)
20*P7:(5,16)
21*P7:O
order:21

P8:(5,16)
2*P8:(4,28)
3*P8:(11,25)
4*P8:(25,16)
5*P8:(1,15)
6*P8:(27,25)
7*P8:(0,10)
8*P8:(20,28)
9*P8:(24,6)
10*P8:(7,3)
11*P8:(7,28)
12*P8:(24,25)
13*P8:(20,3)
14*P8:(0,21)
15*P8:(27,6)
16*P8:(1,16)
17*P8:(25,15)
18*P8:(11,6)
19*P8:(4,3)
20*P8:(5,15)
21*P8:O
order:21

P9:(7,3)
2*P9:(5,15)
3*P9:(24,6)
4*P9:(4,3)
5*P9:(20,28)
6*P9:(11,6)
7*P9:(0,10)
8*P9:(25,15)
9*P9:(27,25)
10*P9:(1,16)
11*P9:(1,15)
12*P9:(27,6)
13*P9:(25,16)
14*P9:(0,21)
15*P9:(11,25)
16*P9:(20,3)
17*P9:(4,28)
18*P9:(24,25)
19*P9:(5,16)
20*P9:(7,28)
21*P9:O
order:21

P10:(7,28)
2*P10:(5,16)
3*P10:(24,25)
4*P10:(4,28)
5*P10:(20,3)
6*P10:(11,25)
7*P10:(0,21)
8*P10:(25,16)
9*P10:(27,6)
10*P10:(1,15)
11*P10:(1,16)
12*P10:(27,25)
13*P10:(25,15)
14*P10:(0,10)
15*P10:(11,6)
16*P10:(20,28)
17*P10:(4,3)
18*P10:(24,6)
19*P10:(5,15)
20*P10:(7,3)
21*P10:O
order:21

P11:(11,6)
2*P11:(27,6)
3*P11:(24,25)
4*P11:(24,6)
5*P11:(27,25)
6*P11:(11,25)
7*P11:O
order:7

P12:(11,25)
2*P12:(27,25)
3*P12:(24,6)
4*P12:(24,25)
5*P12:(27,6)
6*P12:(11,6)
7*P12:O
order:7

P13:(20,3)
2*P13:(1,15)
3*P13:(11,6)
4*P13:(7,3)
5*P13:(4,28)
6*P13:(27,6)
7*P13:(0,10)
8*P13:(5,15)
9*P13:(24,25)
10*P13:(25,16)
11*P13:(25,15)
12*P13:(24,6)
13*P13:(5,16)
14*P13:(0,21)
15*P13:(27,25)
16*P13:(4,3)
17*P13:(7,28)
18*P13:(11,25)
19*P13:(1,16)
20*P13:(20,28)
21*P13:O
order:21

P14:(20,28)
2*P14:(1,16)
3*P14:(11,25)
4*P14:(7,28)
5*P14:(4,3)
6*P14:(27,25)
7*P14:(0,21)
8*P14:(5,16)
9*P14:(24,6)
10*P14:(25,15)
11*P14:(25,16)
12*P14:(24,25)
13*P14:(5,15)
14*P14:(0,10)
15*P14:(27,6)
16*P14:(4,28)
17*P14:(7,3)
18*P14:(11,6)
19*P14:(1,15)
20*P14:(20,3)
21*P14:O
order:21

P15:(24,6)
2*P15:(11,6)
3*P15:(27,25)
4*P15:(27,6)
5*P15:(11,25)
6*P15:(24,25)
7*P15:O
order:7

P16:(24,25)
2*P16:(11,25)
3*P16:(27,6)
4*P16:(27,25)
5*P16:(11,6)
6*P16:(24,6)
7*P16:O
order:7

P17:(25,15)
2*P17:(20,3)
3*P17:(24,6)
4*P17:(1,15)
5*P17:(5,16)
6*P17:(11,6)
7*P17:(0,21)
8*P17:(7,3)
9*P17:(27,25)
10*P17:(4,28)
11*P17:(4,3)
12*P17:(27,6)
13*P17:(7,28)
14*P17:(0,10)
15*P17:(11,25)
16*P17:(5,15)
17*P17:(1,16)
18*P17:(24,25)
19*P17:(20,28)
20*P17:(25,16)
21*P17:O

P18:(25,16)
2*P18:(20,28)
3*P18:(24,25)
4*P18:(1,16)
5*P18:(5,15)
6*P18:(11,25)
7*P18:(0,10)
8*P18:(7,28)
9*P18:(27,6)
10*P18:(4,3)
11*P18:(4,28)
12*P18:(27,25)
13*P18:(7,3)
14*P18:(0,21)
15*P18:(11,6)
16*P18:(5,16)
17*P18:(1,15)
18*P18:(24,6)
19*P18:(20,3)
20*P18:(25,15)
21*P18:O

P19:(27,6)
2*P19:(24,6)
3*P19:(11,25)
4*P19:(11,6)
5*P19:(24,25)
6*P19:(27,25)
7*P19:O
order:7

P20:(27,25)
2*P20:(24,25)
3*P20:(11,6)
4*P20:(11,25)
5*P20:(24,6)
6*P20:(27,6)
7*P20:O
order:7

Ethereum の署名とBitcoin の署名

仮想通貨

Ethereum の署名の仕様はイエローペーパー
https://ethereum.github.io/yellowpaper/paper.pdf
に記載されています。

0 \lt R_x \lt n
0 \lt s \lt n / 2 + 1
v \in {27, 28}
n = 115792089237316195423570985008687907852837564279074904382605163141518161494337

Rは点でx座標とy座標を持ちます。
n は secp256k1 の群位数です。

v=27は R_y の値が奇数、v=28は R_y の値が偶数を表します。
R_y の値は R_x の値から復元可能なので、 R_x の値と v=27, v=28 の値から一意に復元できます。

リカバリーIDとして機能する値vが２種類しかないのは、 R_x の値として、
オーバーフロー値 n \lt {R_{x}} ^ {overflow} \lt p は採用しないようになっているからです。

一方、ビットコイン での署名では、リカバリーIDとして4種類の値を許しています。
R_x の値が 0 \lt R_{x} \lt n の場合、リカバリーIDは0または1、
R_x の値が n \lt {R_{x}} ^ {overflow} \lt p の場合、リカバリーIDは2または3となります。
1, 3 は R_y が奇数, 0, 2 は R_y が偶数となります。

ビットコインの場合もEthereumと同じLowerS形式( 0 \lt s \lt n / 2 + 1 )を採用します。
Rを計算し、そのあとsを計算した時に s が HigherS形式( n / 2 + 1 \lt s \lt n )になった場合は、
Rの値はそのままで s' = n - s を採用します。s' は 0 \lt s' \lt n / 2 + 1を満たします。
s'を採用した場合はリカバリーIDの偶奇を反転させます。
なぜかというとs'を採用するということは'nonce=-nonceを採用した場合と同じで、
R_x の値は変化せず、 R_y の値はマイナスがつき、偶奇が反転しますので、
リカバリーIDを反転させているのです。