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