分散ネットワークシステムにおける合意形成の1つを実装してみました.
これは Princeton 大学の講義 “Bitcoin and Cryptocurrency Technologies” のプログラミング課題の1つです.
ノード間の「信頼」関係のグラフが与えられたときの, 分散型合意形成アルゴリズムを実装します.
これは, Sybil 攻撃に対抗し*1, 合意形成を得るための代替手段であり,
PoW のように膨大な電力を「浪費」しないという利点があります.
*1 Sybil (シビル) というのは, 解離性同一性障害を患った女性の名に由来します.
ブロックチェーン業界の用語では, 攻撃者が複数のノードを作ってネットワークを支配しようとする攻撃の事を言います.
まず, ネットワーク内のノードには, Compliant (善良) と Malicious (悪意) の2種類があるとします.
「信頼」とは, ネットワークが有向ランダムグラフで表され, 各エッジがノード間の信頼関係を表しているという意味です.
例えば, A → B のエッジがある場合, ノード B はノード A が伝搬したトランザクションをリッスンしていることを意味し,
B は A のフォロワーであり, A は B のフォロイーであると言います.
もちろん善良ノードと悪意のあるノードには信頼関係が成り立たちません.
図1 善良ノード間の信頼関係
ここで, 悪意のあるノードは, 例えば次のような動作をします:
- 機能的に死んでいて, トランザクションを伝搬しない,
- 独自のトランザクションを常に伝搬し, 与えられたトランザクションを決して受け入れない.
次に, 各ノードは, 同じコードを実行している他のノードをピアとするネットワークで合意形成を得ることに
成功しなければなりません.
異なるトランザクションの集合を受け取るノードのネットワークが, 受け入れるべき集合に合意できるように設計します.
また, 一定のシミュレーション回数が設定され, 各回にノードはフォロワーに提案を伝搬し,
全回数の終了時には合意すべき取引について合意に達している必要があります.
各ノードにはフォロイーのリストが与えられ, フォロイーにはフォロワーに伝搬できるトランザクションの
リスト (提案リスト) が与えられます.
ここで, 全てのトランザクションは有効であり, 無効なトランザクションは作成できないものとします.
最後にテストに関してですが, コードを実行しているノードが, 悪意のあるノードに遭遇する可能性があります (最大45％).
ノードは, 可能な限り多くの悪意のあるノードに耐え, かつ合意形成を得ることができなければなりません.
テストは次に基づいて評価されます:
- どのくらいの規模のノードの集合が合意に達したか.
全てのノードが同じトランザクションのリストを出力した場合にのみ合意に達したとカウントされる, - 合意に達した集合の大きさ (トランザクションの合意に達した集合を可能な限り大きくしたい).
下表に, 使用するクラス一覧とその説明を纏めました.
表1 クラスの仕様 (概要)
| File | Description |
|---|---|
| Node.java | CompliantNode クラス, MaliciousNode クラスのインターフェース. フォロイーを設定する setFollowees() メソッド, トランザクションの提案リストを初期化する setPendingTransaction() メソッド, 自分のフォロワーに送る提案リストを返す (return) sendToFollowers() メソッド, 他のノードからトランザクション候補を受信する receiveFromFllowees() メソッド が含まれる. |
| CompliantNode.java | CompliantNode クラス. Node インターフェイスを実装したもの. |
| MaliciousNode.java | 悪意のあるノードのクラス. Node インターフェイスを実装したもの. |
| Candidate.java | ノードが受け取るトランザクション候補を記述するためのクラス. フィールドとして, 提案されているトランザクションの ID, トランザクションを提案しているノードのインデックスが含まれる. |
| Simulation.java | 合意形成のテストをするためのクラス. グラフを生成し, グラフのパラメータを変更してシミュレーションを行い, CompliantNode クラスをテストすることが可能. |
| Transaction.java | トランザクションのクラス. フィールドとして, 一意の ID が含まれる. |
Simulation.java の処理の概要を述べておきましょう:
- ノードたちを生成する. その中で, どれが悪意のあるノードで, どれが善良ノードかを選択する,
- 1 で生成したグラフを, ランダムグラフとして初期化する,
- 全てのノードにそれらのフォロー先 (フォロイー) を通知する,
- ランダムな ID で有効なトランザクションの集合 (例えば 500個のトランザクションを含む) を初期化する,
- 各ノードが聞いたトランザクションの開始状態を初期化するために, ノード全体にトランザクションを分散させる.
配布はトランザクションとノードのペアごとに, 定めた確率でランダムに行う, - 各ノードがフォロワーへ提案するトランザクションのリストを1つに纏める,
- 6 で纏めた提案リストを, 各ノードに配布する (伝搬させる),
- 6 と 7 を一定のシミュレーション回数だけ繰り返す.
以上を踏まえ, 実際にテストしてみた結果は次のようになりました:
Tests for this assignment involve your submitted miner competing with a number of different types of malicious miners
Running test with parameters: numNodes = 100, p_graph = 0.1, p_malicious = 0.3, p_txDistribution = 0.01, numRounds = 10
On average 44 out of 72 of nodes reach consensus
Running test with parameters: numNodes = 100, p_graph = 0.1, p_malicious = 0.3, p_txDistribution = 0.05, numRounds = 10
On average 61 out of 72 of nodes reach consensus
Running test with parameters: numNodes = 100, p_graph = 0.1, p_malicious = 0.45, p_txDistribution = 0.01, numRounds = 10
On average 33 out of 58 of nodes reach consensus
Running test with parameters: numNodes = 100, p_graph = 0.1, p_malicious = 0.45, p_txDistribution = 0.05, numRounds = 10
On average 42 out of 58 of nodes reach consensus
Running test with parameters: numNodes = 100, p_graph = 0.2, p_malicious = 0.3, p_txDistribution = 0.01, numRounds = 10
On average 69 out of 76 of nodes reach consensus
Running test with parameters: numNodes = 100, p_graph = 0.2, p_malicious = 0.3, p_txDistribution = 0.05, numRounds = 10
On average 74 out of 76 of nodes reach consensus
Running test with parameters: numNodes = 100, p_graph = 0.2, p_malicious = 0.45, p_txDistribution = 0.01, numRounds = 10
On average 41 out of 54 of nodes reach consensus
Running test with parameters: numNodes = 100, p_graph = 0.2, p_malicious = 0.45, p_txDistribution = 0.05, numRounds = 10
On average 49 out of 54 of nodes reach consensusここで, numNodes はノード数, p_graph はランダムグラフのパラメータでエッジが存在する確率,
p_malicious はあるノードが悪意のあるノードとして設定される確率,
p_txDistribution は各ノードに初期トランザクションを割り当てる確率,
numRounds はノードが実行するシミュレーション回数です.
