NEMホワイトペーパーその２
NEMの流出事件からおよそ3か月が経過しました。仮想通貨は下落の一途をたどるばかりですが、開発者の方々は日々技術革新に勤しんでいることかと思います。たとえ一時経済的価値が薄れていったとしても、技術が後退することはありません。ということで、今更感はありますがNEMのホワイトペーパー（テクニカルリファレンス）翻訳第二弾をご紹介いたします。
ちなみに、現在日本の取引所でNEMを扱っているのは「Zaif」と「DMM Bitcoin」、「CoinCheck」となっております。
ZaifでNEMを始める方はこちら
※口座開設方法も詳しくご説明しております 簡単口座開設【Zaif編】
ちなみに、今回紹介するNEMのホワイトペーパーはの原文はこちら↓
https://nem.io/wp-content/themes/nem/files/NEM_techRef.pdf
第一弾の記事はこちら↓です
http://bittrader.jp/2018/03/05/introduce_whitepaper05_01/
「Catapult（カタパルト）」の要約までは先が長いですが、コツコツと頑張っていきたいと思いますので、興味がある方は是非ご一読ください
NEM Technical Reference翻訳２
7 Proof-of-Importance（PoI）
Proof-of-Importance (PoI)は、NEMで使用されるブロックチェーンの合意形成アルゴリズムです（ビットコインでいうProof-of-work(PoW)のこと）。各アカウントには、NEMエコノミーに対する重要性を示す重要度（Importance Score）が割り振られます。
重要度が高いアカウントは、ブロックをHarvest (ハーベスト：収穫)する確率が高くなります（セクション５参照）。NEMでは、全てのトランザクションが公開されているため、NEMエコノミーでのトランザクションのグラフは、正確に計算することができます。
トランザクションのグラフは、アカウントの重要度への入力に利用できます。トランザクションのグラフをアカウントの重要性を解明するために使用できることがPoIの核となる技術革新です。
NEMのブロックチェーンプラットフォームでは、全てのトランザクションを見ることができます。アカウント間でのトランザクションの情報は、アカウントの重要度を格付けすることに利用できます。
グラフ内の全てのノードが同じ特性や重要度を持つわけではないことは、今にわかったことではありません。グラフ理論コミュニティの文献では、「検索」、「ソーシャルネットワーク」「ストリートネットワーク」「神経科学」などの分野において、ノードの重要性を計算することが十分に確立されています。
これを踏まえた上で、ブロックチェーンの合意形成にグラフ理論を基本的な入力値として取り入れることが、NEMの核となる技術革新の一つです。トランザクショングラフを定義するアウトリンク行列は、非常に重要でPoIの計算に用いられます。
7.1 Eligibility for Entering the Importance Calculation（重要度計算への参加条件）
重要度計算へ参加するための資格を得るには、アカウントは確定済みのXEMを最低でも10,000保有している必要があります。確定済みのXEMを10,000以上持つ全てのアカウントは、ゼロ以上の重要度を持つことになります。
8,999,999,999XEM（XEMの発行上限。既に全て発行済み）では、理論上ゼロ以上の重要度を持つアカウントの最大数は、8,999,999となります。実際には、重要度ゼロ以上の実際のアカウント数は、保持されているXEMの不均衡や権利確定に関する一時的なコストによって理論上の最大値に近づくことはないと予想されます。
NEMが非常に一般的になったとしたら、確定済み10,000XEMという閾値は望ましくないかもしれません。必要に応じて、ハードフォークを介して将来この数を見直すことも可能です。これは、取引手数料やハーベスト（収穫）に関する他のパラメーターと同様です。
7.2 The outlink matrix
仮にPoIの計算を行うブロック高がhであるとします。ブロック高hにおいて10,000XEM以上の残高を持つアカウントは、PoIの計算に参加する資格があります。これらのアカウントに対して、NEMは以下の条件を満たす全ての送金トランザクションを収集します。
- 1,000XEM以上の金額を送金したもの。
- 最後（最新）の43,200ブロック以内（約30日分）に発生したもの。
- 受信者もPoIの計算に参加する資格があること。（セクション1参照）
アカウントAiからアカウントAjに、金額 μ XEMを送金し、ブロック高がhijkとなるようなトランザクションTkとすると、重みは以下の計算式により
ここで、[x]は床関数を表します。図８のグラフでは、時間の経過とともにどのように重み付けされるかを示しています。10,000 XEMの持つ重みが減少していくことがわかります
この値は集約され
設定は
最後に、アウトリンク行列0は、要素Oijとして構成されます。
したがって、アウトリンク行列の要素oijは、最後（最新）の約30日間でにAiからAjへと送金されたXEMの重み付き正味流動量（負の値の場合はゼロ）を示します。これは、正味送金量のみがアカウントの重要度に寄与するということを意味します。
図8；10000 XEMの減衰量
図9：2015年4月29日現在、1,456の収穫アカウントを含むNEM取引グラフ（アウトリンク行列）のプロット。
7.3 NCDawareRank（NCD認知度ランク）
ネットワーク内のノードの特異性を判断するには多くの方法があり、PageRankはその1つです。
NCD認知度ランクは、エルゴード的マルコフ連鎖の定常確率分布が計算される[9,11]という点ではPageRankに類似しています。NCD認知度ランクはさらに、レベル間近似行列Mを追加することで、情報の流れを表す大規模なグラフをほぼ完全に分解した構造を利用することができます。
レベル間近似行列は、ノードのグループが相互作用するクラスタを形成するように密接にリンクされているという事実をモデル化しています。
これにより、NCD認知度ランクは、PageRankよりも速く収束すると同時に、同じレベル内のノードのランクが制限されるため、スコア操作に対する耐性が向上します。
行列の形で表記される場合、NCD認知度ランクは次のように計算されます。
そして
- Oはアウトリンク行列
- Mはレベル間近似行列
- Eはテレポーテーション行列
- πはNCD認知度ランク
- ηはアウトリンク行列の寄与率
- μは近似アカウント(proximal account)の重要度の割合
この定義は、Mとμを追加するだけでPageRankの場合と同じです。NEMでは、ηは0.7、μは0.1とし、これらの各変数の詳細は次の様に計算されます。
収穫（ハーベスト）可能なすべてのアカウントの集合をWとします。u ∈ Wについて、Guは、uに送信したものよりもアカウントuから送られてきた値をより多く受け取ったアカウントの集合です。
Wをほぼ完全に分解可能な（NCD）境界は、すべてのu ∈ Wに対して、u ∈ AKとなるような一意のKが存在するように、{A1、A2、…、AN}として定義されます。 したがって、各u、χuの近似アカウントは次のように定義されます。
Nuはχu内のNCDブロックの数を示します。
アウトリンク行列Oの定義は、セクション7.2で説明しています。収束を保証するためには、Oη+Mμ+ E（1 – η – μ）は確率分布としての行列でなければなりません。これは、すべてのアカウントがゼロ以外の確率でテレポートするように、紐付いているアカウントのランクを分散することによって完了します。
レベル間近似行列Mは、各NCDブロックANを定義しトランザクション・グラフをクラスタリング（セクション7.4）することと、M内の各セルvuの近位アカウントを決定することによって計算されます。
テレポーテーション行列Eは次のように計算されます。
ここで v は、テレポーテーション確率ベクトルであり、eはすべての成分が1となるベクトルです。
実際には、NCD認知度ランクは、次のようにべき乗法によって計算されます。
ここで、okiはOのk行i列を表し、mkiはMのk行i列を表します。
このアルゴリズムは、繰り返し間にNCD認知度ランクの変化がε未満になるまで続きます。
アウトリンク行列とレベル間近似行列のテレポーテーションは、アカウント間の遷移確率行列が確率的、既約的、および原始的であるため、アルゴリズムは収束することが保証されます。
スパースなレベル間近似行列Mを2つの行列RとAに分解することによって、計算数を減らし、NCD認知度ランクの計算を高速化することが可能です。
e|Ak| は、すべての要素が１である|Ak| を持つ行列です。
ここで、R’i∗ は 行列Rのi行のことを指し、
となります。
NEMの実装ではMをAとRに分解します。この分解により記憶領域と計算量が節約されることについては、章末で議論されていますので参照ください。
7.4 Clustering the transaction graph（トランザクショングラフのクラスタリング）
クラスタリングは、SCANクラスタリングアルゴリズムの高性能な機能を使用してトランザクショングラフ上で行われます。
高性能の実装では、コアとなるノードを見つけることによってクラスタが作成されます。その後、クラスタを拡張し、相互に２つ飛びで離れたノードのグループ間の構造的類似性を計算します。以下はアルゴリズムの詳細です。
アカウントVのグラフGを仮定します。アカウント間のエッジEは、アカウント間での送金の合計（セクション7.2を参照）が事前に決められた閾値1,000XEMを超えた場合にエッジが作成されるように定義されます。トランザクショングラフGにおけるアカウントのクラスタリングは、グラフ内のクラスタ、ハブ、およびアウトラインを解明する構造的類似性に基づくクラスタリングを実行することによって行われます。トランザクショングラフuとvの2つのアカウント間の構造類似性σ（u、v）は、次のように計算されます。
ここで | . | は、集合基数を示し、Γは構造的に接続（自己を含む）された集合であり、以下のように定義されます。
Nは、あらかじめ決められた閾値“ε”を超えるアカウントとの構造的類似性を有する構造的に接続されたアカウントの集合です。
コアノードは、クラスターの基軸として拡大に使用され、以下のように定義されます。
ここでμは、アカウントがコアとみなされなければならない閾値イプシロン周辺のアカウントの最小数です。クラスタリング中、クラスタはコアアカウントを中心にセンタリング（ピボット）されます。クラスタの最初のメンバーはNεのメンバーです。これは、μがクラスタを最小サイズに制御していることを意味しています。NEMでは、μは4であり、εは0.3です。アカウントvは、uがコアであり、vがN（u）のメンバーである場合、与えられたμについてアカウントuを持つ構造的に直接到達できる可能性u →ε,μ vを有します。
SCANアルゴリズムでは、コアとなるアカウントを軸として構造的に直接到達できる可能性を持つアカウントを含めることでクラスタが拡張されていきます。これは、隣接および２つ隣のアカウントとの構造類似性を計算する必要があります。
SCANの改良版では、基軸アカウントから2つ離れた位置にあるアカウントとアカウントだけが表示されます。アカウントuから2つ離れたアカウントH（u）は、次のように定義されます。
ここで、アカウントwは w∈N（u）＼｛u｝となるアカウントです。基軸から2つ離れたコアアカウントごとに、新しいクラスタが生成され、その周りにピボットされていきます。閾値εの隣接する全てのコアアカウントの（N）が新しいクラスターに追加されます。2つ離れたアカウントを計算する場合、ピボットされたノードから構造的に直接到達できる可能性を持つアカウントは計算対象として除外されます。
グラフ内のすべてのアカウントが処理された後、すべてのノードが分析されます。あるアカウントが複数のクラスタに属している場合、それらのクラスタは結合されます。その後、クラスタ内に無いアカウントは、2つ以上のクラスタを接続する場合はハブとして、そうでない場合は外れ値としてマークされます。
クラスタを拡張するために2つ離れたノードを使用することで、クラスタリングアルゴリズム中で最も時間がかかる部分である構造類似性σの計算計算コストを削減します。
計算されたクラスタは、NCD認知度ランクのレベル間近似行列を決定するためにも使用され、トランザクショングラフがほぼ完全に分解可能な性質を表しています。
7.5 Calculating Importance Scores
重要度スコアΨは、次のように計算されます。
ここで、
νは、権利確定されたXEMの量
σは、重み付けされた正味XEM
πは、NCD認知度
χは、グラフの構造トポロジーを考慮する重み付けベクトル
wo、wiは適当な定数
χは、グラフのトポロジーを考慮し、外れ値やハブではなく、クラスターのメンバーであるノードに高い重みを割り当てます。外れ値とハブは0.9で重み付けされますが、クラスタにあるノードは1.0で重み付けされます。NEMでは、woは1.25、wiは0.1337です。
まとめると、権利確定された残高、送金されたXEM、トランザクショングラフのトポロジーに関する情報は、NEM経済圏におけるアカウントの重要度を形成するのに役立つ評価の基礎となります。さらに、重要度は意図的に操作されたり遊ばれることがないため（セクション7.6参照）、重要度のスコアは単なるブロックチェーンコンセンサス以外の目的にも役立ちます。たとえば、それらは評価１形態としても解釈できます。すべての重要度スコアは有限の値として統一されるため、投票やスパムの防止などの目的に使用できます。
これにより、匿名アカウントを大量に作成しても意図的に操作することができないため、匿名の関係者であっても相互にやり取りすることができます。
7.6 Resistance to Manipulation（操作に対する耐性）
NCD認知度ランク、権利獲得した残高、重みづけされたアウトリンク、そして重要度スコアの計算の中で合算されていることで、意図的な操作に対して耐性を持つことになります。
7.6.1 Sybil Attack（シビルアタック）
ピアツーピアシステムでは、障害のあるモノや悪意のあるモノがシステムの制御権を乗っ取るために、複数のアカウントを作り出すことがあります。 これはシビルアタックと呼ばれます。
NEMでは、ハーベスター（収穫者）がブロックを収穫するために手数料を受け取るというインセンティブ（セクション5.3参照）があります。また、重要度の高いアカウントでは、ブロックを収穫する確率が高くなります。その結果、攻撃者がシビル攻撃を試みることに強いモチベーションを持つことが予想されます。PoIアルゴリズムでは設計時に、シビルスタイルの攻撃を考慮しています。NCD認知度ランクの使用、権利確定された残高、および重みづけされた正味アウトリンクが、重要度スコアの計算においてシビルアタックに対する耐性を作りだします。
重要度スコアの計算に関して、シビルアタッカーが持つ趣向のいくつかは次のとおりです。
- NCD認知度スコアを引き上げるために、アカウントを分割して分割されたアカウント間での取引を行う。
- アカウントを分割して、ランダムなアカウントとの取引を行う。
- アカウント間でXEMを繰り返し送金して、アウトリンクスコアを上げる（セクション7.6.2参照）
シビルアタックに対抗するために、次の対策があります。
- PageRankではなく、グラフ理論を重要度の指標としたNCD認知度ランクを使用。
NCD認知度ランクアルゴリズムにおけるレベル間近似行列Mは、PageRankよりもスパムへの耐性を強くします。Webページの場合、メインサイトにリンクする多くのダミーサイトを作成するスパムが、メインサイトのPageRankを拡大させます。NEMでは、アカウントの残高の一部を他のアカウントに送り、すべてのXEMをメインアカウントに送り返します。
- 一定のスケジュールでアカウントの残高を権利確定するため遅い（即時性が無い）。
アカウントの権利確定を完全にチェックするのに数週間を必要とすることが、大量のXEMを取得してすぐにネットワークを攻撃することを不可能にします。
- アウトリンクスコアの計算に正味アウトリンクXEMを使用。
正味アウトリンクXEMは、重要度スコアの計算に使用されます。一度送ったXEMを再度送り直しても、送り直したXEMはキャンセルされるため、多くのアカウントにXEMを送信するメリットはありません。
- アウトリンク送金への重みを減少させる。
アウトリンクへの転送は、時間が経つにつれて減衰します。XEMを別のアカウントに送信すると、重要度スコアは一時的に向上します。
- 重要度スコアを統一するために標準化する。
全てのスコアを統一するため、他人の行動が自分の重要度スコアに影響します。
- ハーベスト（収穫）の為には、最低10,000 XEMが必要とする。
収集されるXEMを最低10,000必要とすることで、シビルアタックに関与する可能性のあるアカウント数が理論的に制限されます。
- woとwiの値に比較的小さいものを選択。
これにより、重要度な最も大きな要素は権利確定したXEMの量となる為、悪用できません。
まとめると、これらの対策はPoIのSybil-style攻撃に対する耐性を作り出します。これをテストするために、シビルアカウントを1〜10,000個使用してシミュレーションを行いました。以下の図に3条件のシミュレーション結果を示します。
図10：8億XEMと0.4億XEMを持つ二つのアカウントが外部へ向けてXEMを送金した際の重要度を表すグラフ。善意のアカウントはNEMを１つのアカウントに保持しますが、Sybilアカウントは複数のアカウントを管理しているとします。そして、
- 結託したアカウントがお互いに繰り返しXEMを送りあう。
- 結託したアカウントが全ての共通結託アカウントにXEMを送信する。
- 結託したアカウントがランダムなアカウントにXEMを送信する。
重要度はy軸に、Sybilアカウントが管理するアカウントの数でx軸にプロットされます。
上述の図からわかるように、少数のアカウントを追加した後、数千のアカウントを追加してもSybilアタッカーはあまり多くの重要度を得ることはできません。シビルアタッカーは善意な参加者よりも重要性を増しますが、利益は限られており、PoIの計算によって制限されています。何人かの参加者は、アカウントを分割したり他のアカウントにトランザクションを送信して経済活動のフリをすることで、重要性を高めることができますが、PoIのスコアは統合されるので他の合理的な参加者も同じ行動をとるでしょう。これにより、期待される利益は消失します。
PoWマイニングと比較して、PoIによって得られる利点は最小限である。PoWでは、特殊なマイニングハードウェアを購入する採掘者は、一般的に入手できるビデオカードを使用する人よりも大きな優位性を持っています。
この記事の執筆時点では、同じ金額で（1）800 M hash / sのマイニングパワーを持つビデオカード２つか（2）800,000 Mhash / sの特殊なマイニングパワーを持つASICのいずれかを購入することができます。（1）と（2）のマイニングパワーの差は約1000倍です。PoIでは、アルゴリズムの制約のためにマイニングパワーに全力を賭ける参加者でも得られる利益ははるかに低くなります。言い換えれば、PoIでは何もしない同じ残高を持つ参加者に比べて、質的な優位性を持ちません。
制御されたアカウントが共通のマスターアカウントに全額送金するケースでは、上述の図（b）は、より多くのノードが攻撃に関与している場合に重要性が実際に低下することを示しています。上述の図（b）で、重要度はアカウントの閾値がこの攻撃に組み入れられた後に減少しています。なぜなら、グラフのトポロジが変更され、攻撃ノードが同じクラスタに存在しなくなったためです。アカウントのしきい値を組み合わせた後の利益が減少しました。
7.6.2 Loop Attack（繰り返し攻撃）
同じ主体によって制御されるアカウントが、お互いに繰り返し送金トランザクションでXEMを送信しあい、重要度スコアを上げようとする。あるアカウントから外部へのXEMを送金は、重要度スコア計算の大部分ですが、外部へのXEMは正味量としてで計算される為、内部向けのNEMが、外部向けのNEMを相殺します。したがって、1000 XEMを何百万回繰り返し送金しても、1回だけ送金するよりも高い評価を得ることはできません。
（前述の図を参照）
7.7 Nothing-at-Stake Problem（無関心問題）
理論的には、外部リソースを必要としない確率論的ビザンチンコンセンサスのためのアルゴリズムは、nothing-at-stake問題6の題材とされています。
ブロックを作成する機会費用がごくわずかである場合、理論上はnothing-at-stake問題が存在します。 言い換えると、ブロック生成のコストが非常に小さかった場合、ブロックチェーン上のわかっている全てのフォークにたいしてブロックを生成することが簡単にできてしまいます。対照的に、Proof of Workのようなコンセンサスメカニズムの場合、リソースを大量に消費する為このような問題は起きません。
NEMでは、ブロックを作成するコストはごくわずかです。Nothing-at-stake問題を緩和するために、NEMはブロック生成難度の変化を抑制し、フォーク分解時に巻き戻せるチェーンの長さも制限しています
セクション5.1：ブロック生成難度で説明したように、ブロック生成難度の変化率は最大5％に制限されています。もし、攻撃者のネットワークに存在する収穫力の50％よりかなり低い場合、攻撃者が持つ隠されたチェーンのブロック生成時間はメインチェーンよりもかなり長くなります。このような大きな時間差があるとため、攻撃者のチェーンがより受け入れられないようになります。さらに、ブロックチェーンアンワインド制限は360ブロックで、複数のチェーンで作業するハーベスタからの長距離フォークを防止します。さらに、ブロックチェーンは360ブロックを制限としている為、複数のチェーンで働くハーベスターからの長いフォークの生成を防いでいます。
7.8 Comparing importance to stake（ステークとの重要性の比較）
7.5節の重要度の計算にてしめしたように、アカウントの持つ権利確定した残高は、重要度において大きな構成要素です。Proof-of-Stake (PoS)アルゴリズムを用いた仮想通貨内で権利が確定した残高を”stake”とすると、PoSとPoLを似たものとして捉えることができますPoSとPoIで似ている点と異なる点を比較するために、NEMとBitcoinのトランザクショングラフを分析しました。Bitcoinを選択したのは比較的大きなユーザー数とトランザクショングラフが見込まれるからです。
2015年4月29日の時点で、NEMのトランザクショングラフにはハーベスト(収穫)に参加できるアカウント（7.1節参照）が1,456アカウント存在しました。このデータは、2014年10月にビットコインネットワークからおよそ1ヶ月分のデータをダウンロードして分析しました。BTCの量にNEMを合わせると、54,683アカウントがハーベストへの参加資格を持っていました。金額を合わせるには、BTCの量に時価総額率を乗じて行いました。したがって、0.0177 BTCがハーベストに参加できるとアカウントが見なされる、権利確定した残高の最低額でした。ブロック高は、NEMに10を乗じて正規化しています。
図11（a）は、NEMのトランザクショングラフ内で1,456のハーベスト参加資格を持つアカウントそれぞれの重要度と権利確定した残高を対数目盛を用いてプロットしたものです(権利確定した残高は昇順)。そして（b）は、Bitcoinトランザクショングラフにおける54,683のハーベストに参加資格を持つアカウントを示します。見てわかるように、権利確定した残高が単調増加しても、重要度は単調には増加しません。権利確定した残高の低いアカウントの場合、２つのトランザクショングラフのうちPoSよりPoIの方が高い重要性を得ることが出来ます。
図11：ハーベストへの参加資格を持つアカウントの重要度と権利確定した残高を（a）NEMと（b）Bitcoinトランザクショングラフの一部にプロットしたもの。重要度と権利確定残高は合計が一定(1.0)になるよう標準化されており、アカウントは昇順にソートされています。 グラフには、STAKEとIMPORTANCEを明確に比較できるようにy軸上にプロットされ、対数スケールで表示されています。アカウントはx軸に表示されます。
図12は、PoIとPoSとの間の質的差の概要を示すために、正規化された重要度と権利確定した残高の両方をプロットしたNEMトランザクションネットワークグラフを示します。正規化は、低い値と高い値の差をより目立たせるために行われ、重要度と権利確定した残高の合計を一定にしてスケーリングし、その対数の絶対値をとり、それを指数関数にマッピングし、そして合計を一定に再度スケーリングすることによって求めました。 グラフに見られるように、権利確定残高はより少数のノードに大きな重みを与え、重要度スコアではそれほど顕著に大きなノードにはなりません。
図12：NEMのトランザクショングラフ。各ノードは以下でノーマライズされている。ノーマライズの詳細は上記を参照
(a) 重要度スコア
(b) 権利確定済の（vested）残高
アカウントの差異を数値化するため、NEMとBitcoinのすべてのアカウントは、権利確定した残高と重要度に基づいてランク付けされ（同じスコア/残高のアカウントは同じランクが与えられています）、２つの指標間のランクの違いを調べました。
表1:重要度 対 権利確定した残高でのNEMアカウント間での順位の差。NEMトランザクショングラフ内のアカウントの結果を示す。
重要度(Importance)と残高(Stake)での平均ランク上昇数(下位50%)：‐232.4
重要度(Importance)と残高(Stake)での平均ランク上昇数(上位50%)：‐443.8
差分：‐338.1
表2:重要度 対 権利確定して残高でのBitcoinアカウント間での順位の差。Bitcoinアカウントの順位の結果を示す。
重要度(Importance)と残高(Stake)での平均ランク上昇数(下位50%)：2814.6
重要度(Importance)と残高(Stake)での平均ランク上昇数(上位50%)：-2949.6
差分：-67.5
全体として、重要度でランク付けされたNEMアカウントは、権利確定した残高でランク付けされた場合より約338ランク下がっています。上位半数のアカウントは平均で443ランク減少するのに対し、下位半数は平均232ランク減少した。Bitcoinアカウントは、権利確定した残高でランク付けされた場合よりも、重要度でランク付けされた方が平均67.5ランク下がりました。下位半分のアカウントが平均2,814ランクが上がり、上位半分は平均2950ランク下がりました。 これは、PoIの場合PoSよりも裕福なアカウントの影響が小さいことを示唆しています。
7章は長かったですので今回はここまでとして、その3に続きます。PoIはNEMにおける中心的な技術なので、しっかりと理解しておいて次の章に向かいましょう！！
それでは、長文にお付き合いいただきありがとうございました。
