2019-03-04

楕円曲線論はじめの一歩 (9)

今回のおはなし

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

前回、「楕円曲線に交わるように直線を引くと、その直線は必ず 3 箇所で交わります」と書きましたが、
実際には例外があります。

今回はその例外について見ていきましょう。

楕円曲線と接する場合

f:id:y-hoshizuki:20181225193413p:plain

楕円曲線に直線を重ねると、この図のように接線となる場合があります。
その場合は、2 点でしか交わりません。

このような場合は、3 点で交わっている状態から連続的に変化させていき、その極限を考えます。

f:id:y-hoshizuki:20181225193426p:plain

P-P'-Q の直線は 3 点で交わっています。
これを少しずつ、Q の位置を変えずに上にずらしていきます。

すると、P と P' はどんどん近づいていって、あるとき P'' の 1 点に集約されます。

つまり、接線となっている点は、その点で 2 回、交わってる状態と「連続」しているわけです。
要するに、接線の部分で 2 回交わっているとカウントするわけですね。

中学校で二次方程式の解を求める時に、「重解は 2 回交わっているものとみなす」と習いました。
あれと同じです。

数式で考えるともう少し明白です。

前回、2 点 P = ( x1, y1 ) と Q = ( x2, y2 ) から有理点 S を求める式をお見せしました。

$x_3=(\frac{y_2-y_1}{x_2-x_1})^2-x_1-x_2$
$y_3=\frac{y_2-y_1}{x_2-x_1}(x_1-x_3)-y_1$

ここで、 $\lim_{x_2 \to x_1}$ を考えます。
x2 が変化すると y2 もあわせて変化していくことに注意して極限を求めると、

$x_3=(\frac{3x_1^2+a}{2y_1})^2-2x_1$
$y_3=\frac{3x_1^2+a}{2y_1}(x_1-x_3)-y_1$

が得られます。今回も詳細な計算は省略します。

式の形はだいぶ違いますが、傾きを表している

$\frac{y_2-y_1}{x_2-x_1}$

が、

$\frac{3x_1^2+a}{2y_1}$

に変わっているだけです。

直線を連続的に移動させて点 P と点 P' が極限まで近づいて点 P'' になる。
これを数式で考えるとこうなる、というお話です。

接する場合を考えると何ができるか

さて、以上の考え方を逆にすれば、
「楕円曲線上に有理点が 1 個があれば、そこに接線を引くことで別の有理点が見つかる」
ということになります。

P と P' から S を発見できるのであれば、P'' と P'' からも S を発見できるというわけです。

前回は有理点が 2 個から別の点を見つけましたが、実は 1 個でもあれば見つけられる、
というお話です。

まとめ

今回は、楕円曲線と直線が 3 点で交わらないケースについて見てみました。
実はもう 1 パターンあるのですが、それについては次回、触れることにしましょう。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

2019-02-25

楕円曲線論はじめの一歩 (8)

今回のおはなし

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

前回まで、代数論の基礎を簡単になぞりました。
そして今回からみなさんお待ちかね、楕円曲線の話をはじめようと思います。

そもそも楕円曲線とは

楕円曲線って何でしょう？

楕円曲線とは、 $y^2=x^3+ax+b$ こんな形をした方程式のことです。

a, b は係数で、x と y が変数です。
この方程式の解をグラフにするとこんな感じになります。

f:id:y-hoshizuki:20181225193049p:plain

f:id:y-hoshizuki:20181225193102p:plain

え、どのあたりが楕円かって？...名前のことは気にしない方がいいです。
いろいろな歴史的事情でこう呼ばれているだけで、これが楕円曲線なんです。

詳しく知りたい方は、楕円積分について調べるといいですが、
あまりオススメはしません...

天下り的で申し訳ないですが、こればかりは、「こういうもの」として
覚えていただければと思います。

楕円曲線上の有理点

さて、問題です。

ある楕円曲線が与えられたとき、その楕円曲線に含まれる有理点、
つまり x, y 座標それぞれが有理数となる点はどれだけあるでしょうか？

まったく存在しない？それとも有限個？もしくは無限に存在する？

...実はこの問題は未解決問題の 1 つで、未だに回答は出ていません。
残念。

楕円曲線上の有理点を探す問題

未解決の問題について考えても仕方ないので、
とりあえず、さらに条件を加えます。

ある楕円曲線と、「その楕円曲線上の有理点が 2 つ与えられたとき」、
他の有理点を探すことはできるでしょうか？

f:id:y-hoshizuki:20181225193119p:plain

実は、楕円曲線に交わるように直線を引くと、その直線は必ず 3 箇所で交わります。
実際には例外があって 2 箇所になる場合もありますが、とりあえず後回しにします。

この交点を左から順に P, Q, R としましょう。
P と Q が有理点であれば、R も有理点になることは計算すればわかります。

これだけだと、3 つ目を見つけて終了してしまいますので、さらにもう 1 つみつけましょう。

f:id:y-hoshizuki:20181225193205p:plain

R を通る垂直線との交点、つまり、R の y 座標を反転させた点 S も有理点となります。
( x, y ) が有理点なら、 ( x, -y ) も有理点、という話です。

さて、これで 4 つ目が出てきました。ここで、直線 SP や直線 SQ を引くと、
さらにたくさん有理点が見つかりそうですね。

点 S を導き出せるのは非常に重要そうです。

さて、ここで、つまり有理点は無限に存在するんだ！と思ったあなた、残念早とちり。
これを繰り返したときに、既知の点以外である保証がないので、
無限に存在するとは限りません。つまり、どこかでループする可能性があるのです。

ともあれ、2 つの有理点から、別の有理点を見つける方法があることはわかっていただけたと思います。

実際に計算してみる

有理点 P の座標 ( x1, y1 ) と、有理点 Q の座標 ( x2, y2 ) から、新たな有理点 S の座標 ( x3, y3 )
を求めてみましょう。

詳しい計算については他のサイトを参照してもらうことにしてここでは答えだけ。

$x_3=(\frac{y_2-y_1}{x_2-x_1})^2-x_1-x_2$
$y_3=\frac{y_2-y_1}{x_2-x_1}(x_1-x_3)-y_1$

と、なります。x1, x2, y1, y2 すべて有理数ならば、x3, y3 も有理数になることがおわかりでしょうか？

有理点 2 つから、新たな有理点が得られることが、数式からも見て取れます。

まとめ

今回からようやく楕円曲線の話に入りました。
話題の焦点は「楕円曲線上で、x と y がともに有理数となる点」つまり「有理点」です。
これを突き詰めていくと面白いことがたくさんあります。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

2019-02-18

楕円曲線論はじめの一歩 (7)

今回のおはなし

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

前回は「他にどんなものが『体』となるか？」から「有限体」について語りました。
今回はもう 1 つ、「体」となるものを紹介しようと思います。

数直線

みなさん「数直線」って覚えていますか？

f:id:y-hoshizuki:20181225192636p:plain

直線上の点を実数に対応させて図にするアレです。

例えば、3 はここです。

f:id:y-hoshizuki:20181225192649p:plain

これを使うと、数値が視覚的に見れて便利、という優れものです。

数直線上に存在しない点

さて、ここでとある方程式を持ってきます。

$x^2+1=0$

この左辺には、最小多項式、原始多項式という名前がついていますが、
今は覚えなくても大丈夫です。

この方程式の解となる値はどこでしょう？

二次方程式の判別式を覚えている方はすぐにわかると思いますが、
この方程式には実数の解は「存在しません」。

そのため、数直線上の点には対応しません。

でももし仮にそんな値が存在するとしたら？と考えると、いろいろ面白いことがわかります。
それが、「拡大体」という概念への入り口となります。

とりあえず方程式の解が存在するとして、数直線の図に、無理やり点を作りましょう。
数直線上は全部実数に対応しているので、
その外に、対応する点をおきます。0 の真上が都合がいいので、そこにおきます。

f:id:y-hoshizuki:20181225192659p:plain

そんな適当においていいの？と思われそうですが、
重要なのは 0～1 を結ぶ直線と、0～解を結ぶ直線とが
「0 で直交しているところ」がポイントです。

これにより、ユークリッド幾何学の概念を取り込むことができるから便利なのですが、
今はそこに詳しく触れる必要は特にないので、忘れてしまっても大丈夫です。

呼び方がないと不便なので、「虚数単位」「i」と呼びます。
電気回路を扱う人は、電流 i と見分けをつけるためにあえて j と呼んでいるようですが、
ここは数学の人たちの流儀に合わせて i を使っていきます。

数直線から複素平面へ

さて、今、実数と対応付けられた数直線１本と、虚数単位の点があります。

新しく加わった虚数単位 i と、いろいろな実数 x, y を使って
$x+yi$ で表すことのできる値を「複素数」と呼びますが、
その複素数全体のそれぞれに対応する点はどこでしょう？

f:id:y-hoshizuki:20181225192713p:plain

この図の水色で表した「平面」全体が複素数全体のそれぞれに対応付けられる点となります。
これが複素平面、別名、ガウス平面です。

逆に見れば、この平面内のどの点も、虚数単位 i と実数 x, y を使って
$x+yi$ で表すことができる複素数と対応付けられています。

f:id:y-hoshizuki:20181225192732p:plain

例えば、 $3+2i$ はここの点と対応づけられます。

存在しない値を追加して線を面にする

数直線から複素平面を作ったように、元々実数として含まれていなかったはずの点を
追加することで面を作る。ということができます。

実数は元々「体」ですが、こうやって作った $x+yi$ の集合、複素数も、「体」となります。

f:id:y-hoshizuki:20181225192745p:plain

この新しく作った体を「拡大体」と呼び、今回のように、実数に $x^2+1=0$ の解を追加して
作った拡大体を特別に「複素数体」と呼んでいます。

複素数の足し算と複素平面

複素数は実は「体」の用件を満たす、ということは足し算ができます。
$(3+2i)+(2+2i)=5+4i$

これを複素平面で見てみましょう。

f:id:y-hoshizuki:20181225192758p:plain

このように、0 の点（原点）からの矢印をつなげていくことで、
複素数の足し算ができます。

小学校で数直線を習ったとき、数直線での足し算、やりましたよね？
それと同じことができるという話です。

まとめ

解の存在しない方程式を用意して、その解が仮に存在することとして追加することで、
１次元だった数直線を平面に拡大する、というやり方です。

既知の体から、拡大体を作る方法についてお話しました。
そしてその一例が、複素数体となります。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

2019-02-12

楕円曲線論はじめの一歩 (6)

今回のおはなし

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

前回は掛け算（割り算）を抽象化した概念、「体」について説明しました。
そして、「実数」は「体」の条件を満たしてることを確認しました。
今回は、他にどんなものが「体」と呼べるのか、みていこうと思います。

自然数は？

自然数とは、1 2 3 4... のことですね。流派によっては 0 も含みます。
自然数は足し算について、逆元（マイナス元）が存在しないので、
体の条件を満たしていません。

なら整数は？

それでは自然数にマイナスも含めた整数ではどうでしょう？

確かに、足し算は可換群となっています。
しかし、掛け算に対して、逆元が存在しないので、体の条件を満たしていません。

例えば、3 の掛け算に対する逆元は $\frac{1}{3}$ で整数ではありません。

有限巡回群に掛け算を導入する

有限巡回群 $\mathbb{Z}/7\mathbb{Z}$ の足し算はこう定義していました。

$(x + y) \bmod 7$

これと同じように掛け算も定義してみます。

$(x \times y) \bmod 7$

実はこうすると、体の条件を満たすようになります。

確認してみましょう。

まず、足し算が群であることは確認しました。

足し算は可換でしょうか？実は足し算を定義する式を見れば一目瞭然で、
$(x + y) \bmod 7 = (y + x) \bmod 7$
なので、左右を入れ替えても結果は同じことがわかります。
つまり、足し算に対しては可換群であります。

次に、掛け算について、0 以外が可換群であるか確認してみましょう。

掛け算の定義で mod 7 しているので、掛け算の結果は必ず 0 ～ 6 の間に含まれます。
つまり、掛け算に対して“閉じて”います。

結合法則を確認するのは少々手間なので細かいところは省きますが、ざっくりと、
$(((x \times y) \bmod 7) \times z) \bmod 7 = (x \times ( (y \times z) \bmod 7)) \bmod 7$
が成り立つので、結合法則は成り立つといえます。

掛け算に対する単位元は 1 ですね。

逆元ですが、以下のようになっています。

元	逆元	元×逆元	mod 7
1	1	1	1
2	4	8	1
3	5	15	1
4	2	8	1
5	3	15	1
6	6	36	1

全ての元に対して逆元が存在していますね。

掛け算に対して可換かどうか。
$(x \times y) \bmod 7 = (y \times x) \bmod 7$
左右を入れ替えても同じ結果になることがわかると思います。

0 の掛け算についても、結合法則を満たすし、可換なのは明白だと思います。

最後に分配法則。これも細かいとこをまで見るときりがないので、ざっくりと
$(x \times ( (y + z) \bmod 7) = ( ( (x \times y) \bmod 7) + ( (x \times z) \bmod 7)) \bmod 7$
が成り立つので、分配法則も成り立ちます。

以上より、 $\mathbb{Z}/7\mathbb{Z}$ は、掛け算を
$(x \times y) \bmod 7$
と定義することで、「体」と呼べることが確認できました。

実はこれは別の名前がついていまして、有限体、もしくはガロア体と呼ばれています。
$\mathbb{F}_7$ もしくは GF(7) と書いたりもします。

7 以外の数字でも有限体になるのでしょうか？

答えは No。例えば mod 12 の有限巡回群に同じ掛け算を定義しても、
元 6 に対する逆元は存在しないため、「体」の条件を満たしません。

実は、mod の後ろ側、7 にあたる部分が“素数”であれば「体」の条件を満たして「有限体」となる。
ということがわかっています。そのため、素数を使って作った有限体のことを
総称して、素数 prime の頭文字をとって $\mathbb{F}_p$ とか GF(p) と書きます。

暗号の世界ではよく「素数」を使いますが、それは「有限体」を作るために必要なんです。

まとめ

今回は、体の条件を満たすものについて触れました。

メインディッシュの「有限体」は、暗号の世界では非常に重要な概念ですので、
よーく覚えておいてくださいね。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

2019-02-04

楕円曲線論はじめの一歩 (5)

今回のおはなし

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

前回まで、ずっと足し算の話をしてきました。
じゃあ、掛け算と割り算はどうなんでしょう？というのが今回のテーマです。

「掛け算（割り算）」と呼んでもいい条件

掛け算ついても、過去の偉い人たちが散々検討を重ねた結果、
「これを満たせば『掛け算』と呼んで差し支えないだろう」
という条件が決まっています。

「足し算」が存在する

掛け算というのは、それ単体で存在するものではなく、
足し算がある上に、さらに追加の演算として存在するものである。

というわけです。つまり、足し算ができる上で、さらに追加で別の演算ができるときに、
その追加の演算を「掛け算」と呼ぶわけです。

足し算は可換群の性質を持つ

「可換」とは、「左と右を入れ替えても結果が変わらない」という性質のことです。

1 + 2 = 2 + 1

つまり、足し算が群であるだけでなく、
追加で「左と右を入れ替えても同じ結果になる」という性質を備えている必要があります。

掛け算は 0 以外に対して可換群の性質を持つ

ここまでは、要するに「掛け算が存在するためには『足し算』が要る。それは可換群である。」という話でした。

掛け算の本質はここからです。

足し算の可換群の元から 0 を除くと、掛け算に対しても可換群の性質を持ちます。

つまり、こういうことです。

f:id:y-hoshizuki:20181225192008p:plain

「群」とは足し算を抽象化したものである。と説明してきましたが、
実は掛け算も、本質的な性質としては、似たようなものとして説明できてしまうわけです。
これ、結構面白くないですか？

足し算と異なるのは、0 を含まないという点と、つながっている順番（構造）が
異なるというところだけです。

つまり、足し算ができて、足し算とは構造の違う演算がもう一種類定義されたとき、
それを掛け算と呼んでいるわけです。

0 の掛け算は結合法則が成り立って可換である

結合法則が成り立つ。つまり、

$(a * b) * c = a * (b * c)$

このどこに 0 が入っても等号が成立します。また、可換である。つまり

$0 * a = a * 0 = 0$

となります。

「分配法則」が成り立つ

これは小学校で習いましたね。

$3 \times (1+2) = 3 \times 1 + 3 \times 2$

ということです。

具体例で見てみましょう

抽象的に説明してもピンと来ないと思うので、
具体的に、「実数」に対して考えてみましょう。

まず、実数には和と積、２種類の演算ができます。

次に、和については、可換群の要素を満たしています。

実数と実数の和は実数　→　演算について閉じている
和の順序を入れ替えても結果は同じ　→　結合法則を満たす
0 をいくら足しても結果は同じ　→　単位元（零元）は 0
マイナスをつけた数との和は 0　→　逆元（マイナス元）が存在する
和の左右を入れ替えても結果は同じ　→　可換である

なお、掛け算の「単位元」「逆元」と混同しないように、
足し算の群の方は「零元」「マイナス元」と呼んだりします。

さらに、積についても、0 を除けば可換群の性質を満たします。

実数と実数の積は実数　→　演算について閉じている
積の順序を入れ替えても結果は同じ　→　結合法則を満たす
1 をいくらかけても結果は同じ　→　単位元は 1
逆数をかけると 1 になる　→　逆元が存在する
積の左右を入れ替えても結果は同じ　→　可換である

0 の掛け算に関しては、結合法則を満たすし、可換でありますね。

あとは、小学校で習ったとおり、分配法則も満たします。

以上から、実数は全ての条件を満たしていることがわかります。

つまり、これらの条件は、実数に対する和と積から、
極限まで具体性をそぎ落とした、「和と積についての本質的な性質」といえるわけです。

この、「和と積についての本質的な性質」を満たすもののことを「体」と呼びます。

まとめ

掛け算とは、足し算ができる上で、さらに別の演算が定義されている場合に、
それが特定の条件を満たしている場合の呼び名である、というお話でした。

そしてそれは、実数のように、普通に四則演算に使っているものから、
具体性を極限までそぎ落とした、「四則演算の本質」であるということでした。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

2019-01-28

話題の Fake Stake 攻撃についての解説

はじめに

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

今回は普段の連載ではなく、先日、米国研究グループから公表された、
Fake Stake 攻撃に関するレポートについて、解説してみようと思います。

この記事は、脆弱性を周知することでコインノードを運用している方々に指摘があったことを
認知していただくためのものであり、決して DoS 攻撃を推奨するものではありません。
実際に攻撃を行った場合、法律により罰せられますのでご注意ください。

情報元

https://medium.com/@dsl_uiuc/fake-stake-attacks-on-chain-based-proof-of-stake-cryptocurrencies-b8b05723f806

前提知識

昨今の暗号通貨の系譜

暗号通貨っていろいろ種類がありますが、その大半は、bitcoin の実装を元に、
ソースコードを改造して作られたものです。

bitcoin から派生していない暗号通貨といえば、Ethereum が筆頭にあがりますが、
それ以外はほとんどが、bitcoin をベースに開発されたものとなっています。

つまり、bitcoin を改造して作られている以上、bitcoin の性質を色濃く受け継いでいるわけです。

今回、問題になっている「チェーンベース PoS」というのも、
元々は PoW で実装されていた bitcoin を改造して、
PoS を導入した暗号通貨のことを指しています。

bitcoin のシステム構造

bitcoin は、それぞれのノードが自分のデータベースを持っていて、
相互に通信しながらそれを同期する仕組みになっています。

f:id:y-hoshizuki:20190125183135p:plain

そして、誰かがマイニングに成功したら、それをブロードキャストして、
それぞれのノードが自分で新しいブロックを検証してから、自分のデータベースに追記します。

f:id:y-hoshizuki:20190125183152p:plain

bitcoin のブロックの構造

ブロックは、大きく分けて２つのデータから成り立っています。

ブロックヘッダ（ブロックの中身のハッシュ値、タイムスタンプ、Nonce など）
ブロック本体（トランザクションデータ）

PoW と PoS

そもそも PoW, PoS とはなんでしょう。

PoW は、ブロックヘッダに Nonce と呼ばれるフィールドを用意して、
ブロックヘッダのハッシュ値が一定値以下になる Nonce を探し当てるゲームです。

SHA256(ブロックヘッダ) < target (difficulty から算出)

この等式を成り立たせる Nonce を総当りで探します。
difficulty は、ブロック発見頻度が概ね 10 分（bitcoin の場合）になるように、
自動で調整される値です。

一方、PoS は、Stake、つまり今持ってる資産に応じて当選確率が上がる抽選です。

SHA256(ブロックヘッダ) < target * 今持ってる資産

この抽選を一定時間ごとに行い、当選したらマイニング成功というわけです。

PoS にもいくつかバリエーションがありますが、この先、
単純に PoS と書いた場合は PoSv3 のことを指すとお考えください。

PoW の欠点、PoS の欠点

PoW の欠点はもう有名ですが、とにかく大量に電力に消費するところです。

これを解決するのが、PoS ですが、こちらはこちらで、
お金持ち（暗号資産をたくさん持っている人）ほどマイニング報酬を得やすくなり、
経済格差が広がる一方、という問題が既に指摘されています。

とはいえ、PoW だって、現金を持っている人ほどいい ASIC や GPU を買えるので、
どっちもどっちと言えなくはないと思います。

もう１つ、今回の鍵になる PoS の欠点ですが、
各ノードが新規に追加されるブロックを検証するときに、
PoW なら「ブロックヘッダのハッシュ値を求めて比較するだけ」で済むのに対して、
PoS だと、「マイナーの資産を確認する」必要があるという点があります。

つまり、PoS はマイナーの資産を確認する分だけ、検証が重い、という問題があるわけです。
今回の脆弱性はすべて、ここが発端となります。

bitcoin から派生した PoS コインの仕組み

bitcoin には、マイナーが報酬を得るためのトランザクション、
coinbase トランザクションが、各ブロックに 1 つあります。

coinbase トランザクションは、入力を持たず、出力で 50BTC や 25BTC などを、
マイナー宛に送金するトランザクションです。

bitcoin から派生した PoS コインでは、この coinbase トランザクションに加え、
新たに coinstake トランザクションというものを追加しました。

これは、マイニングに成功したか否かを確認するために、
マイナーの未使用資産（UTXO）を入力としているトランザクションで、
PoS でマイニングされたブロックには 1 つあるものです。

また、coinstake トランザクションでは手数料をマイナスの数にすることができます。
これによって実質のマイニング報酬としています。
そのため、coinbase トランザクションは未使用として運用されています。

このあたりに、bitcoin の血を受け継いでいる感じがありますね。

チェーンの分岐

bitcoin はマイナーが複数人いる上、ネットワークの伝播にラグがある関係上、
チェーンが分岐する場合があります。

そのため、同じブロック高で複数種類のブロックを受け取った場合には、
どちらも正当なものとして一旦保存しておきます。
ある程度伸びた時点で、長く伸びたほうにはたくさんの計算量（マイナー）が集まっている
という仮定のもと、短いほうを廃棄する、という仕組みになっています。

それまでは、分岐した両方のチェーンを保持しています。

そしてこの仕組みは、bitcoin から派生した PoS コインにも受け継がれています。

今回の脆弱性

メモリを大量に消費する DoS 攻撃

bitcoin では、ブロックヘッダの伝播と、ブロックデータの伝播は分けて行われます。

それは、まずブロックヘッダだけ受け取って検証してから、
中身であるブロックデータを受け取れば済むからです。

ところが、bitcoin から派生した PoS コインでは、
ブロックヘッダだけでは検証ができません。ブロックデータに含まれる
coinstake トランザクションに検証用のデータが入っているからです。

そのため、新規にブロックを受け取った際には、
ブロック全体をダウンロードしてメモリに載せる必要があります。
つまり、PoW だった bitcoin と比べて、新規ブロック受け取り時の
メモリ消費量が桁違いに多いわけです。

ここを突くのが、1 つめの攻撃方法です。

例えば、ターゲットのノードに複数のプロセスから同時に接続し、
同時に適当なブロックヘッダとブロックデータを流し込むと、
ターゲットのノードは律儀に全部メモリに載せようとします。

これでメモリを大量に消費してクラッシュする場合もあります。

この攻撃は、特に暗号資産を持っている必要がなく実行できます。

ディスクを大量に消費する DoS 攻撃

前述の通り、coinstake の検証には、マイナーの保有資産を確認する必要があるため、
非常に重いという問題があります。

マイナーの保有資産は、UTXO set と呼ばれるデータベースで管理していますが、
これは現在一番長いチェーンの先端時点での情報であり、
分岐したチェーンの状態ではありません。

そのため、分岐したチェーンでは、coinstake が UTXO として指し示す先が、
トランザクションの出力として存在するか、という最低限の検査のみ行い、
実際に未使用か否かの検査は省略してディスクに保存します。

これがこの脆弱性の肝ともいえる部分です。

そのため、実際には使用済みのトランザクション出力を UTXO と偽って
coinstake を作成し、ターゲットのノードに受信させることで、
ディスクをどんどん圧迫することができます。

これが 2 つめの攻撃方法で、メモリの消費に比べて
「ただの再起動じゃ直らない」という点においてより悪質と書かれています。

ただし、この攻撃を実現させるためには、少なくともハッシュ値は十分、
当選に値するものである必要があるため、ある程度多くの暗号資産を持つ必要があります。

攻撃をしやすくする、Stake Amplification

前述の攻撃手法をとるためには、少なくともハッシュ値の計算で
当選した coinstake を量産しなければならないという問題があります。

そのため、ある程度多くの暗号資産を持つ必要があるわけですが、
ここでポイントとなるのは、coinstake の指し示す先が使用済みであってもよい、
という事実です。

そのため、自分への送金を何度も何度も繰り返します。
そうすると、自分宛のトランザクション出力（ただし使用済み）が大量に生まれます。

これを前述の攻撃に使用することが可能、というわけです。

まとめ

一次ソースの情報を斜め読みして、ざっくりと攻撃の仕組みを解説してみました。
攻撃について、まとめると以下の通りです。

攻撃を受ける可能性があるコイン：bitcoin から派生した PoS 型の暗号通貨（おそらく全て）
攻撃を受ける可能性のある人：コインノードを立てている人（マイニングを行っている人とほぼ同義）
攻撃を受けた結果：メモリ使用量が増えてクラッシュ、もしくはディスクを食いつぶしてシステム停止
攻撃では出来ないこと：他人の暗号資産を奪うこと、など

おそらく、近いうちに対策を施したバージョンがリリースされると思いますので、
今回対象となっている暗号通貨のコインノードを立てている人は、
可能な限り、早めのバージョンアップを心がけると良いのではないでしょうか。

もしくは、リスクを少しでも避けるならば、対策バージョンがでるまで、
マイニングをおやすみしてコインノードを止めるのが、もっとも確実かもしれません。

今回の脆弱性の発見についての記事では、既に多くの暗号通貨において、
何らかの緩和策が取られているとのことですので、その場合はあまり問題にならないかも知れません。
しかし、bitcoin から派生した PoS コインでは仕組み上「完全な解決」は不可能なため、
各自で具体的な対応状況や、リスクの大小など、判断していただくよう、お願いいたします。

ご質問、ご意見等ありましたらお気軽にリプライください。

2019-01-28

楕円曲線論はじめの一歩 (4)

今回のおはなし

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

前回は、時計の短針を例に、有限巡回群について語りました。
有限巡回群について、もう少しだけ、お話しておくことがあります。

群の位数、元の位数

群に含まれる要素の数を、「群の位数」と呼びます。
前回触れた時計の短針の場合、群の位数は 12 です。
なぜなら、要素（元、つまり時刻）は 12 種類あるからです。

こちらは簡単ですね。

また、「その元を何回足し合わせると単位元になるか？」という値を、
「元の位数」と呼びます。

こちらは少し難しいので例を挙げましょう。

f:id:y-hoshizuki:20181225191800p:plain

3 は、単位元（0）から 4 回足すと、元の単位元に戻ってきます。

$(0 + 3 + 3 + 3 + 3) \bmod = 12 \bmod 12 = 0$

だから、元 3 の「元の位数」は 4 となります。

f:id:y-hoshizuki:20181225191816p:plain

4 の場合を見ると、3 回足すと単位元に帰ってきます。
だから、4 の「元の位数」は 3 です。

群の位数と元の位数の関係

それぞれの元に対する、元の位数を表にしてみましょう。
単位元 0 は既に単位元に戻っているため、省略します。

元	元の位数
1	12
2	6
3	4
4	3
5	12
6	2
7	12
8	3
9	4
10	6
11	12

すべて 12 の約数であることにお気づきでしょうか？

そう、有限巡回群においては、どの元の位数も、群の位数の約数になるという法則があります。
証明は今回も省略します。

素数位数の群

「元の位数」は「群の位数」の約数であるというお話をしました。
ということは、群の位数が素数、例えば 7 ならばどうでしょう？

f:id:y-hoshizuki:20181225191830p:plain

また表にしてみましょう。

元	元の位数
1	7
2	7
3	7
4	7
5	7
6	7

「群の位数」が素数であるということは、約数は「群の位数」それ自身か、1 しかありえません。
ということは、必然的に全ての元の位数は、群の位数に一致します。

「ラグランジュの定理」と呼ばれる性質です。

まとめ

今回は、群の位数と元の位数についてお話しました。
そして、ラグランジュの定理にも少し触れました。
大事な性質なので、よく覚えておいてください。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。