nemの楕円曲線暗号を基礎から学んでみる(数式)-その1 数学的準備

ブロックチェーンnemにも使われていると言うことで、僕も楕円曲線暗号を一から勉強してみることにしました。

ちなみに、nemのとか書いていますが楕円曲線暗号そのものは広く使われていて、基本的な考え方は全て同じです。

こんなpdfがあったので、大いに参考にしています。

https://written.4403.biz/source/ecc_rev30r.pdf

前提知識として、集合論とかはある程度知っておいた方が理解しやすいと思います。

 

まず、素数\(p\)について、集合

\[\mathbb{F}_p=\{ 0,1,..p-1\} \]

を考えます。

このちょっと変な集合の上では、要素\(n\)は、普通の整数の\( \{…,n-2p,n-p,n,n+p,n+2p,…\}\)と同じと考えます。

ここでは例として、\(p=5\)とします。

\[\mathbb{F}_5=\{ 0,1,2,3,4\} \]

つまり、この集合での足し算は\(3+4=2(=7-5)\)、

引き算は\(1-4=2(=-3+5)\)

掛け算は\(2\times 3=1(=6-5)\)

割り算は\(3\div 4=2(=(3+5)\div 4)\)

のようになります。

自分でいろいろ適当な数で計算して、遊んでみてもいいかもしれません。ここで不思議なのは、なぜ\(p\)を最初から素数にしたのかです。実際、\(p=9\)などの非素数にしてみると、割り算がうまくいきません。

\[1\div 3=(1+9)\div 3=(1+9\times 2)\div 3=… \]

ここまで来ればお気づきでしょう。9が3で割り切れてしまうからです。なぜ\(p\)が素数の時はすべてうまくいくのかは、ちょっと考えてみてください。

数学では、可算減算積算除算のできる集合を体(有理数体、実数体など)と言いますが、特に、ここで挙げた\(\mathbb{F}_p\)を、素体と言います。

 

次に、楕円曲線の定義をします。

\(y^2=x^3+ax+b (a,b\in \mathbb{F}_p,4a^3+27b^2\neq0)\)

なる曲線を、\(\mathbb{F}_p\)上の楕円曲線と言います。

\(4a^3+27b^2\neq0\)は、異なる\(x\)で同じ\(y\)になる(解が重複する)のを防ぐための条件で、二次方程式の場合の\(b^2-4ac\neq 0\)と同じものです。

例えば、\(a=2,b=3\)とした\(y^2=x^3+2x+3\)は、\(\mathbb{F}_5\)上の楕円曲線のひとつです。

そして楕円曲線上で、\((x,y)\)の両方が\(\mathbb{F}_p\)に属する点を、\(\mathbb{F}_p\)-有理点と言います。さらに無限遠点と言う特別な点\(\mathcal{O}\)も、この\(\mathbb{F}_p\)-有理点の仲間に入れてやります。

では、素体\(\mathbb{F}_5=\{0,1,2,3,4\}\)上の楕円曲線\(y^2=x^3+2x+3\)の有理点を列挙してみましょう。

\((1,1),(1,4),(2,0),(3,1),(3,4),(4,0),\mathcal{O}\)

確認してみてください。

(この場合は、\(x=0\)のときは有理点がありません。また、\(x\)座標が同じで\(y\)座標が\(\mathbb{F}_5\)の和に関する逆元同士(つまり足して5)になっている有理点の組がいくつかあります。この理由もちょっと考えてみて下さい。)

次に、この\(\mathbb{F}_p\)-有理点の集合での加法を考えてみます。以下は、このようにするとうまくいくよ~という計算法です。

1.2点\(P,Q\)を通る直線を引く

2.楕円曲線と直線の交点\(R^\prime \)とする。

3.\(R^\prime\)の\(x\)軸に対する対称点(ようは、\(y\)座標をひっくり返したモノ)\(R\)を和\(P+Q\)とする。

 

 

ホントにうまくいくの?と思いますが、例えば、

1.\((1,1),(2,0)\)を通る直線は、\(y=4x+2\)です。

2.\(y=4x+2\)と楕円曲線\(y^2=x^3+2x+3\)の交点は、\((2,0)\)です。

3.対称点は、\((2,0)\)です。

なんと、ちゃんと和の結果が元の仲間に入っている(有理点の集合は和について閉じて)います。

 

一般に、楕円曲線の有理点の集合は加法群(加法、減法について閉じている)になっています。

この方法に、ちゃんとした定義を与えます。

和\(R=P+Q\)に関して、

\(P\ or\ Q=\mathcal{O}\)のとき、それぞれ\(R=P,Q\)とする。

\(y_P=-y_Q\)のとき、\(R=\mathcal{O}\)とする。(\(P\)は\(Q\)の逆元\(-P\))

\(y_P\neq -y_Q\)のとき、\(x_R=\lambda^2-x_P-x_Q,y_R=\lambda(x_P-x_R)-y_P\)

ここで、\(\lambda\)は2点を通る直線(\(P=Q\)のときは接線)の傾きを表す。

\(\lambda= \frac{y_P-y_Q}{x_P-x_Q}\ or\ \frac{3x_P^2+a}{2y_P}\)

適当に素体\(\mathbb{F}_p\)上の楕円曲線上の点を選びます。これをベースポイントと呼びます。適当な整数\(d\)に対し、

\[d\times P=P+P+…+P\]

を求めることを、スカラー倍算と呼びます。

では、素体\(\mathbb{F}_5=\{0,1,2,3,4\}\)上の楕円曲線\(y^2=x^3+2x+3\)の有理点の集合\(\{ (1,1),(1,4),(2,0),(3,1),(3,4),(4,0),\mathcal{O}\} \)において、\((1,1)\)のスカラー倍算を求めてみましょう。

\((1,1)\times 2=(1,1)+(1,1)\)

\(\lambda=\frac{3\cdot 1^2+2}{2\cdot 1}=0\)

よって、\((3,4)\)

 

次に、

\((1,1)\times 3=(3,4)+(1,1)\)

\(1+4=0\)でるから、\(\mathcal{O}\)

このような、楕円曲線上の有理点のなす加法群をMordel-Weil群と呼び、加法群の要素の個数を、群位数と呼びます。この場合は、群位数は7です。

また、楕円曲線上のスカラー倍算はじゅんぐり回っていって、かならず途中で計算結果が無限遠点\(\mathcal{O}\)に等しくなります。この、何倍して無限遠点に等しくなったかを、ベースポイントの点位数と呼ばれます。

例えばこの場合は、ベースポイント\((1,1)\)に対する点位数は、\(3\)です。

また、じゅんぐりになる群を、巡回群と呼びます。よって、楕円曲線上の有理点の集合からじゅんぐりになるものだけ抜き出し集合は、巡回群です。

この場合は、\(\{ \mathcal{O} ,(1,1),(3,4)\} \)は巡回群をなします。

さて、ここらあたりでブロックチェーンNEMのTecnical Reference(リンクは日本語版)をチラッと読んでみると、だいぶん理解が進んだことに気付くのではないでしょうか。

ちなみに、NEMのこの数字がなぜ分数なのか

\[\frac{121655}{121656}\]

も、除算の説明のところを復習すればわかるでしょう。

nemの楕円曲線暗号を基礎から学んでみる(数式)-その2 スカラー倍算の高速化

に続きます。

nemブロックチェーンに使われているEigenTrustの原論文の要約・和訳(数式)

nemブロックチェーンに使われている、EigenTrustというピアの評価、管理アルゴリズムについての原論文を要約・和訳しました。

 

原論文:https://nlp.stanford.edu/pubs/eigentrust.pdf

要約・和訳版:http://enomotokan.com/wp-content/uploads/2019/01/Eigrentrust.pdf

 

この記事では、要約・和訳版をさらにまとめ、論文の概略を示します。

 

1.導入

悪さをするピアがいるため、そいつらを排除したい。そのために、それぞれのピアに固有のグローバルな、全てのピアの経験を反映させた信頼指数を提案する。

 

本論文では、”ローカルな”ピアの信頼度と”グローバルな”ピアの信頼度を明確に区別しています。

この論文でいうローカルとは、一組のピア同士における、あるピアからあるピアに対する相対的な評価のことを指します。グローバルとは、全てのピアに割り当てられた、お互いの大きさの比較によってそのピアの信頼性を絶対的に評価できる指標という意味です。

 

2.設計思想

1.システムは中央権力ではなく、自己防衛する仕組みにしなければならない

論文では、一旦4.4「基本的なEigenTrust」、つまり中央集権的に信頼度を計算するアルゴリズムを説明しますが、4.6で修正を加え、分散環境で計算する方法を説明します。

 

2.システムは匿名でなければならない。

ピアの評価は、例えばピア自身のIPアドレスのような、外部的に関連付けられたものではなく、不透明な識別子に関連付けなければならない。

論文5.1「アルゴリズムの説明」では、あるピアが、他のピアの信頼度を計算するのがどのピアなのか知ることができないようになっていることがわかります。

 

3.システムは、新しい参加者に評価を割り当ててはならない。つまり、評価はいつくかのトランザクションにおける継続したいい行いによって得られるべきであり、低い評価の悪意のあるピアが彼らの不透明な識別子を変え、新しい参加者の地位を得るのに有利であってはならない。

新しい参加者に関しては、評価値が0になるようにしてあります。

 

4.システムは計算や構造、貯蓄、メッセージの複雑性において、最小限のコストでなければならない。

論文4.6「分散EigenTrust」では、ローカル信頼度がほとんど0であり、ほとんどのピア交流がないために、計算するためのメッセージを送る回数を減らせるから、アルゴリズムの実行コストが実際、低くなることが説明されています。

 

5.システムはお互いに知っていて、システムを転覆させようとする集団に対して堅牢でなければならない。

論文5「安全なEIGENTRUST」では、悪意のあるピアがいたとしてもその影響を受けないようにするため、”基本的なアルゴリズム”をさらに修正しています。

 

3.評価システム-概略

論文では、成功している評価システムの例としてオンラインオークションシステムであるeBayを例に挙げ、その評価法を最も基本的なローカル信頼度として採用します。

具体的には、ピア同士がトランザクションごとにお互いに評価します。おのおのの時刻において、ピア\(i\)が\(j\)からファイルをダウンロードするとき、正\((tr(i,j)=+1)\)または負\((tr(i,j)=-1)\)としてトランザクションを評価します。論文でいうローカル信頼度\(tr(i,j)\)とは、端的に言えば、各トランザクションにおけるピア\(i\)の\(j\)に対する信頼度評価をいいか悪いかのみで表したものです。

 

これらを過去から現在まですべて足し合わせたものを、\(s_{ij}\)とします。

\[s_{ij}=\sum{tr(i,j)}\]

 

次に、\(s_{ij}\)を正規化します。正規化とは、出力を確率的に扱いたいときによく使う手法です。

正規化されたローカル信頼度\(c_{ij}\)として、以下の様に定義します。

\[c_{ij}=\frac{max(s_{i,j},0)}{\sum_j{max(s_{ij},0})}\]

式を見て分かるように、\(0\leq c_{ij}\leq 1\)が保証されます。\(j\)に関する和も、もちろん\(1\)になります。

ここからが本論文のキモです。

\(t_{ik}\)を導入します。

\[t_{ik}=\sum_j{c_{ij}c_{jk}}\]

これは、\(i\)が\(j\)に、\(k\)の信頼度を「訊いた」ことに基づいた信頼度を表しています。ある人に関して、信用がある人に信用があると言われれば、そのある人の信用度は高く評価できるでしょう。

これは行列によっても表現できます。\(c_{ij}\)を\(C\)の\(i\)行\(j\)列目として考えます。\(t_{ik}\)も行列として捉え、\(i\)行目を抜き出し、縦ベクトルにしたものを\(t_i\)とします。\(c_i\)も同じようにとらえます。

すると、以下のように書けます。

\[t_i=C^T c_i\]

少し計算すればわかるように、\(t_{ij}\)も\(\sum_j{t_{ij}}=1\)を満たしていますから、正規化されています。

これを繰り返す、つまり

\[t_i=(C^T)^n c_i\]

とします。

この式は、\(i\)が他のピアに訊き、さらに他のピアに訊き…を繰り返しまくったすえ、目的のピアの信頼度を知ったという意味で解釈できます。

これを無限回繰り返すと、実は、\(t_i\)は\(i\)に依らず\(C^T\)の固有ベクトル(これを、\(C\)の左固有ベクトルと言い、論文ではこちらの用語を用いています。)に収束します。(論文7「実験」ではシュミレーションで実際、10回未満の繰り返しで十分に収束することが経験的に示されます。)

ちなみに、これはべき乗法と呼ばれる、計算機を用いた基本的な固有ベクトルの求め方です。この方法では、行列の最大固有値に対応する固有ベクトルが得られることが知られています。

\(t_{i}\)は数学的帰納法により、やはり\(\sum{t_{i}}=1(ベクトルの総和)\)を満たしていますから、正規化されていることがわかります。論文4.1「ローカル信頼度の正規化」には、この性質により、繰り返しループの中で再正規化を行う必要がないから、計算コストの削減が可能になっているとあります。

この\(t_i\)こそまさに、システムのグローバル信頼度です。つまり、これはもはやピア同士ではなく、あるピア固有の評価値の絶対的尺度として捉えることができます。

以上が基本的な考え方です。

別にこの考え方は、ブロックチェーンのみにとらわれません。例えば、会社の人同士で信用度を百点満点で評価してもらい、表にします。これは相対評価の表です。これを行列とみなして固有ベクトルさえ求めれば、これは絶対評価として解釈できる、この論文の前半は、そういうことを主張しています。

(基本的な考え方はGoogleの、ページランクアルゴリズムと本質的に同じです。そもそも、何もBrinとPageが思いついたわけでもなく、昔から考察されてきていた考え方のようです。この基本的な考え方の詳細はグラフ理論に関わってきますので、そちらを参照してください。)

以降の論文後半では、このアルゴリズムを分散環境で計算可能で、ピアの匿名性を保ちつつ、悪意のあるピアに対して堅牢であるように修正します。

 

原論文:https://nlp.stanford.edu/pubs/eigentrust.pdf

要約・和訳版:http://enomotokan.com/wp-content/uploads/2019/01/Eigrentrust.pdf