Proof of Importanceを読み解いてみた

本記事の目的

Proof of Importanceで用いられている数学的計算の読解

基本的にNEMのホワイトペーパーの内容に沿って説明します。有志による日本語訳も出ているため、原文(7. Proof of Importance（重要度の証明） · GitBook)を読んで理解できる人は読む必要はありません。よく見かける「数学的な計算によってネットワークに貢献したノードの重要度を上げる」というふわっとした部分を掘り下げていきます。効率的にインポータンスを上げる方法といった話ではないので悪しからず。
なるべく誰でも理解できるよう、前提知識としては高校数学程度を想定します。行列について知らない方は、いくつかのベクトルを並べてまとめて扱うものくらいの認識で結構です。

1.スコアの計算方法
2.アウトリンク行列
3.NCDawareRank
4.クラスタリング
5.まとめ

1.スコアの計算方法

先に結論から。重要度スコアは次式によって求められます。

$\psi=(normalize1(\max(0,v+\sigma\omega_0))+\hat{\pi}\omega_i)\chi$

normalizeは正規化するという操作で、ここではベクトルの大きさ(ノルム)を1にします。

$normalize1(v)=\frac{v}{\|v\|}$

ここでは、 ${\max(0,v+\sigma\omega_0)}$ というベクトルを正規化します。 ${\max(a,b)}$ は ${a}$ か ${b}$ の大きい方を表します。(ex. ${\max(0,5)=5}$ )
${v}$ は権利確定済みのXEMの量(残高)です。(参照：2.1 アカウントの状態 · GitBook)
${\sigma}$ は重み付きの正味のアウトリンク(2.アウトリンク行列参照)です。おそらくですが重み付きトランザクションの総和だと思われます。
正規化する意味としては、 ${v+\sigma\omega_0}$ が1万を超える大きな数になりスコアが無駄に大きくなるのを防いでいるのと、スコア後半部分のNCDawareRankのノルムも1なのでそれに揃えるという意味があるのかと思われます。
${\hat{\pi}}$ はNCDawareRankのスコア(3.NCDawareRank 参照)です。重要度に応じてアカウントに点数(Rank)をつけたものです。
${\chi}$ はグラフの構造的トポロジー(形状・性質)を考慮するための重みベクトルです。アカウントがクラスタのメンバーであれば1、クラスタに属さない外れ値・ハブは0.9倍のスコアとなります。(クラスタ：性質の似たアカウントをグループ化し、まとめたもの)
${\omega_0}$ と ${\omega_i}$ は定数で、それぞれ1.25、0.1337です。
本筋とは逸れますが少し見やすくすると

${\psi=\{(v+1.25\sigma)_{normalize}+0.1337\hat{\pi}\}\chi}$

イメージとしては、(残高 + 送金量 + Rank)×(補正)　といった感じでしょうか。
さて、とりあえず計算に必要なものはすべて出揃いました。

2.アウトリンク行列

アウトリンク(outlink)とは外へのリンク、つまりXEMの送金のことを指します。どのアカウントがどのアカウントへどれだけのXEMを送金したのかを表す行列がアウトリンク行列です。といっても全てのトランザクションが対象となるわけではなく、いくつかの条件があります。①送金元、送金先のアカウントは共に、権利確定したXEMを10000XEM以上保有している ②1000XEM以上の送金である ③最新ブロックから過去43200ブロック以内(約30日分)　の三つの条件を満たすトランザクションが、この行列の要素を計算するための対象となります。
最初に生成されたブロックから何番目のブロックであるかを示すものとしてブロック高を定義し、現在のブロック高を ${h}$ とします。アカウント ${A_i}$ からアカウント ${A_j}$ へ ${\mu}$ XEM送金したトランザクションを ${T_k}$ とし、 ${T_k}$ が含まれるブロックのブロック高を ${h_{ijk}}$ とすると、重みを付けた送金トランザクションは次式で表されます。

${w_{ijk}=amount*\exp(\lfloor\frac{h-h_{ijk}}{1440}\rfloor*\ln0.9)}$
( ${=amount*\mathrm{e}^{\lfloor\frac{h-h_{ijk}}{1440}\rfloor*\log{e}(0.9)}}$ )

${\lfloor x \rfloor}$ は床関数というもので、 ${x}$ を超えない最大の整数を表します。(ex. ${\lfloor 2.5 \rfloor=2}$ , ${\lfloor 3 \rfloor=3}$ )
(おそらく ${amount=\mu}$ ですが、手数料も含めた量かは不明)
${h-h_{ijk}}$ は最新ブロックからの深さを表し、1分あたり1ブロック生成されるとすると1日で1440ブロック生成(60×24)されるので、 ${\lfloor \frac{h-h_{ijk}}{1440}\rfloor}$ はトランザクション ${T_k}$ が何日前に生成されたかを表します。
例えば6日前( ${h_{ijk}=h-10079}$ ～ ${h-8640}$ )に生成された10000XEMの送金に重みを付けると、

${w_{ijk}=10000*\mathrm{e}^{6*\ln0.9}=5314.41}$

となります。過去30日分のトランザクションを追いますよ、古いものほど価値は下がっていきますよ、ということです。さらに送金のアカウントペア ${(i,j)}$ が同じであるトランザクションは合算します。

$\tilde{w}_{ij}=\sum_{k}^{} w_{ijk}$ (30日分の ${A_i}$ → ${A_j}$ のトランザクションを足す)

ここで、

${\tilde{o}_{ij}=\begin{cases}\tilde{w}_{ij}-\tilde{w}_{ji} & (\tilde{w}_{ij}-\tilde{w}_{ji}>0) \\ 0 & (otherwise) \end{cases}}$

とおきます。(原文は減算が逆になっていますがおそらく誤植) otherwiseはその他の意。同じアカウント間の送金、入金はキャンセルし合います。最終的にアウトリンク行列 ${O}$ の要素 ${o_{ij}}$ は以下のように表されます。

$o_{ij}=\begin{cases}\frac{\tilde{o}_{ij}}{\sum_{i} \tilde{o}_{ij}} & (\sum_{i}^{} \tilde{o}_{ij}>0) \\ 0 & (otherwise) \end{cases}$

各要素を各行の総和で割っているのは、各行の総和を1に揃えるためです。行列の第 ${i}$ 行をみると、アカウント ${A_i}$ がどのような割合(確率)で別のアカウントに送金しているかが分かります。
スコアの計算でのアウトリンクは総和を揃えては意味がないので、アカウント ${A_i}$ のアウトリンクは

$\sigma_i=\sum_{j}^{} \tilde{o}_{ij}$

でしょうか。(記載なし)
同じアカウント間の送金、入金は相殺され、30日間で総合したものが行列の要素となります。要素 ${o_{ij}}$ はアカウント ${A_i}$ から ${A_j}$ へ送金されたXEMの重み付き総フロー量であり、 ${o_{ij}}$ が正の値ならば、 ${o_{ji}}$ の値は0となります。

3.NCDawareRank

NCDawareRank(Nearly Completely Decomposable：ほぼ完全に分解可能な)とは、ノードの重要度を測る一つの指標です。ランク、つまりアカウントに点数をつけて順位付けを行います。アカウントをいくつかのグループに分類し、グループごとの結びつき、関係を考慮してランクを決定します。もっと正確に言うと、XEMの移動に注目して、どのような確率で、どのアカウントをXEMが移動していくかを計算します。おそらくこの計算が一番わかりにくいかと思います。
さて、ここで少しグラフ理論について触れておきます。さすがに前提知識ゼロでは厳しいので、マルコフ連鎖のイメージや推移確率行列(遷移確率行列)について簡単に把握しておいてください。
(参考：マルコフ連鎖の基本とコルモゴロフ方程式 | 高校数学の美しい物語)

ここでいう天気はアカウントに対応します。この章での数学的計算の目標は、遷移確率行列のすべての固有値の中で最大の固有値を探し、その最大固有値に対応する固有ベクトルを求めることです。この固有ベクトルの各要素が各アカウントのRankとなります。NCDawareRankを計算する上での遷移確率行列は

${O\eta+M\mu+E(1-\eta-\mu)}$

です。 ${O}$ はアウトリンク行列、 ${M}$ はレベル間近似度行列、 ${E}$ はテレポーテーション行列です。 ${\pi}$ をNCDawareRankとすると、

${\hat{\pi}=O\eta\pi+M\mu\pi+E(1-\eta-\mu)\pi}$
( ${=(0.7O+0.1M+0.2E)\pi}$ )

として、べき乗法で固有ベクトル(NCDawareRank)を計算することができます。(参考：べき乗法 - Wikipedia)　 ${\eta}$ , ${\mu}$ はRankへの寄与率を表すもので定数なので代入してあります。つまりアカウントに到達したXEMには三つの移動の方法があり、①通常の送金 ②性質の似たアカウントへの送金 ③ランダムな送金で、それぞれの確率は70％、10％、20％となっています。

${M}$ と ${E}$ の求め方について説明していきます。
${W}$ を権利確定済みのXEM残高10000以上の全アカウントの集合とします。あるアカウント ${u}$ に対して、 ${u}$ から受け取ったXEMの方が多いアカウントの集合を ${G_u}$ とします。( ${O}$ の第u行で値 ${>0}$ の列)
${W}$ を互いにほぼ分離可能(NCD)な部分集合として ${A_1,A_2,...,A_N}$ に分割します。(4.クラスタリング参照)　任意の ${u\in W}$ に対して、 ${u\in A_K}$ となる ${K}$ がただ一つ存在します。(部分集合は共通部分を持たない＝NCD)
このとき、 ${u}$ の近接アカウントの集合 ${\chi_u}$ は

$\chi_u=\bigcup_{w\in (u\cup G_u)}^{} A_{(w)}$

と定義できます。少しわかりにくいでしょうか。 ${u}$ 自身を含んでいるNCDブロック( ${A_{w1}}$ )と、 ${u}$ が送金(トータルで正の値)したアカウント( ${G_u}$ )を含むNCDブロック( ${A_{w2},A_{w3},...}$ )の和集合として、近接アカウント集合を定義しています。 ${\chi_u}$ に含まれるNCDブロック( ${A_K}$ )の数を ${N_u}$ とします。
このときレベル間近似度行列 ${M}$ の要素 $M_{v,u}$ を

${M_{v,u}=\begin{cases}\frac{1}{N_u|A_{(v)}|} & (v\in \chi_u) \\ 0 & (otherwise) \end{cases}}$

として定義します。アカウント ${v}$ が ${u}$ の近接アカウント集合に属しているとき、近似度は近接アカウント集合に含まれるNCDブロック数と ${v}$ が含まれるNCDブロック内のアカウント数を掛けたものの逆数になります。

べき乗法で最大固有値の固有ベクトルを求める際、要素に0を含む非負の行列であるときの必要条件は、行列が既約である(任意のアカウントから任意のアカウントへXEMが移動できる)ことです。(ペロン＝フロベニウスの定理)
PoIの計算に参加できる資格はあるが一度も送金をしていなかったり(もしくは入金のほうが多い)、いくつかのアカウントで送金ループを形成していたりした場合、XEMが任意のアカウントへと移動できません。これを解消するために最後にテレポーテーション行列を導入します。テレポーテーション行列 ${E}$ を以下で定義します。

${E=ev^{T}}$

${e}$ は全要素が1のベクトル、 ${v^{T}}$ はテレポーテーション確率のベクトルです。簡単にいうと一定の確率で任意のアカウントへの移動を許します。全アカウント数が1万なら1万分の1の確率で任意のアカウントへ移動します。これにより ${O\eta+M\mu+E(1-\eta-\mu)}$ は既約行列という条件を満たせました。

べき乗法による収束が保証されたため、あとはプログラムで計算することができます。

4.クラスタリング

レベル間近似度行列 ${M}$ を計算する際に、どのように全アカウントをNCDブロックに分類(クラスタリング)するかについて説明します。さらに複雑になるので興味のない方は飛ばしてしまっても大丈夫です。

アカウント集合 ${V}$ をノード、1000XEM以上の重み付き送金トランザクションの集合 ${E}$ をエッジとし、 ${V}$ と ${E}$ からなるグラフ ${G}$ を考えます。
自身を含む構造的隣接アカウント集合 ${\Gamma(u)}$ を

${\Gamma(u)=\{v\in V|\{u,v\}\in E \}\cup\{u\} }$

とします。 ${\{u,v\}}$ はアカウント ${u,v}$ 間のエッジを表しています。つまり送金が行われているアカウント群は隣接しているとみなします。アカウント ${u}$ と ${v}$ の類似度 ${\sigma(u,v)}$ は隣接アカウント集合を用いて

${\sigma(u,v)=\frac{|\Gamma(u)\cap\Gamma(v)|}{\sqrt{|\Gamma(u)||\Gamma(v)|}}}$

と表されます。 ${|.|}$ は集合の濃度(大きさ)を表しており、有限集合の場合は要素数を指します。共通部分が多いほど類似度は高くなり、それぞれの要素数が多くなるほど類似度は低くなります。隣接集合 ${\Gamma(u)}$ の中でも、類似度の閾値を ${\epsilon}$ とした構造的隣接アカウント集合を ${N_\epsilon}$ ( ${\epsilon}$ -近傍アカウント集合)とします。

${N_\epsilon(u)=\{v\in \Gamma(u)|\sigma(u,v)\ge \epsilon\}}$

${N_\epsilon(u)}$ は ${\Gamma(u)}$ の部分集合で、「 ${u}$ と送金関係がありその中でも構造的に似ているアカウント群を集めた」集合です。次にクラスタを拡張する際の中心となるコアノードを以下のように定義します。

${K_{\epsilon,\mu}(u)\Leftrightarrow |N_\epsilon(u)|\ge \mu}$

つまり、 ${\epsilon}$ -近傍アカウント集合の濃度(要素数)が ${\mu}$ 以上のアカウント ${u}$ がコアとなりえます。 ${\mu}$ はクラスタの最小サイズをコントロールするものです。NEMでは ${\mu=4}$ 、類似度の閾値 ${\epsilon=0.3}$ となっています。コアノードを中心にクラスタを形成し、 ${N_\epsilon}$ がクラスタの最初のメンバーとなります。 ${u}$ がコア、 ${v}$ が ${N_\epsilon(u)}$ のメンバーであるとき、アカウント ${v}$ は「構造的直接到達性をもつ」といい、

${u\mapsto_{\epsilon,\mu} v}$

で表します。
アカウント ${u}$ から二次の距離にあるアカウント集合 ${H(u)}$ は次のように表されます。

${H(u)=\{v\in V|(u,v)\notin E\wedge (v,w)\in E \}}$

${w}$ は ${N_\epsilon(u)}$ のメンバーです。( ${u}$ を除く)　つまり二次の距離とは、 ${u}$ と直接送金の関係はないが、 ${w}$ 経由でつながっている関係です。最初の起点となるアカウントから二次の距離にあるアカウントの中から、コアノードとなれるアカウント( ${|N_\epsilon(v)|\ge \mu)}$ が新たなクラスタを形成します。同様の手順で ${\Gamma(v)}$ のメンバーの類似度を計算し、直接到達性のある ${\epsilon}$ -近傍アカウントをクラスタに加えていくわけですが、このとき、最初の起点とした ${u}$ から直接到達可能な、すなわち ${N_\epsilon(u)}$ は計算から除外します。二次の距離にあるアカウントを拡大していくとき、以下の手順で進められます。

$H(u_n)=\{v\in V|(u,v)\notin E \wedge (v,w)\in E \wedge v\notin \bigcup_{i=0}^{n-1} N_\epsilon(u_i)\cup H(u_i) \}$

ややこしいですが、上記の文章を数式化しただけです。全ノードの計算が終わると、全ノードについて以下をチェックします。

1.複数のクラスタに属しているノードがある場合、そのクラスタを結合する。
2.どのクラスタにも属さないノードは、2つ以上のクラスタとつながっていればハブ、そうでなければ外れ値とみなす。

クラスタに属していないのにクラスタとつながっていると聞くと不思議に思うかもしれませんが、類似度が閾値を超えているものだけをクラスタのメンバーに加えていくので、送金の関係があったとしてもクラスタには属さないという状況が起こりえます。以上で「ほぼ」完全に分離可能なブロック(NCDブロック)が形成されました。

5.まとめ

最後にもう一度スコアの計算方法を見てみましょう。

${\psi=\{(v+1.25\sigma)_{normalize}+0.1337\hat{\pi}\}\chi}$

あるアカウントのインポータンスを計算するとき、まず権利確定済みの残高をみます。
次にそのアカウントの過去30日間の重み付き送金トランザクションの総和を計算します。
次にそのアカウントのNCDawareRankを計算します。
最後にそのアカウントがハブまたは外れ値に該当していないか判定します。
以上の数値を用いてスコアが導かれます。

・数値例
3アカウントa,b,cの残高 ${v=(10000,15000,20000)}$ 、アウトリンク ${\sigma=(0,2000,4000)}$ 、NCDawareRank ${\hat{\pi}=(0.1,0.4,0.5)}$ とし、aとbはクラスタに属するアカウント、cはハブとします。このとき

${v+\sigma\omega_0=\left(\begin{array}{ccc}10000\\15000\\20000\end{array}\right) +1.25\left(\begin{array}{ccc}0\\2000\\4000\end{array}\right) =\left(\begin{array}{ccc}10000\\17500\\25000\end{array}\right) }$
より、
${\psi=\{\frac{1}{10000+17500+25000} \left(\begin{array}{ccc}10000\\17500\\25000\end{array}\right)+0.1337\left(\begin{array}{ccc}0.1\\0.4\\0.5\end{array}\right) \}\left(\begin{array}{ccc}1\\1\\0.9\end{array}\right)\simeq\left(\begin{array}{ccc}0.20\\0.39\\0.49\end{array}\right)}$

となり、各アカウントのスコアは ${(0.20,0.39,0.49)}$ となりました。(数値設定はかなりいい加減に選んだのでご容赦ください。正規化に関しては表記がなかったので1-ノルムで計算しました。)

いかがでしたでしょうか。
Proof of Stakeの課題を解決している？富めるものが更に富む仕組みは変わっていない？改善の余地は？といった議論に花を咲かせてみるのもよいのではないでしょうか。
ほとんどのものはトレードオフの関係にあり、何がベストとは一概に言えない部分もあります。 ${w_0,w_i}$ の値が小さいため、スコアの大部分を残高が占めているところが個人的には懸念点だと思っています。PoSの改良版という位置づけにもかかわらず結果的に残高重視なのはいかがなものかとは思いますが、残高の少ない弱者にも「それなりに」有利なアルゴリズムなのかなと。
勝手な解釈や不明な点も多々あるので、誤りがあればコメントしていただけると修正致します。

最後に。
富めるものが更に富む仕組みというのはいわば資本主義の原則のようなもので、これ自体に私は否定的ではありません。むしろ努力の如何に関わらず皆同列の社会主義的考え方は不平等とすら思います。PoWもPoIも例外ではなく富めるものが有利な仕組みです。しかし「有利」であるだけで、維持し続ける努力は必要となります。大企業がその財力をもって幅広く市場シェアを獲得するのに有利である一方、努力を怠ればやがて衰退し倒産するでしょう。この点はPoWもPoIも同様です。つまり富めるものが更に富む仕組みが問題ではなく、必要とされる改善・維持努力の程度が重要なのではないかと。このハードルの高さはそのまま「無駄の大きさ」につながり、逆にあまりに低いとそれはやはり「不平等」なのでしょう・・・。