信頼からの合意形成アルゴリズムの実装

分散ネットワークシステムにおける合意形成の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 クラスの仕様 (概要)

FileDescription
Node.javaCompliantNode クラス, MaliciousNode クラスのインターフェース.
フォロイーを設定する setFollowees() メソッド,
トランザクションの提案リストを初期化する setPendingTransaction() メソッド,
自分のフォロワーに送る提案リストを返す (return) sendToFollowers() メソッド,
他のノードからトランザクション候補を受信する receiveFromFllowees() メソッド
が含まれる.
CompliantNode.javaCompliantNode クラス. Node インターフェイスを実装したもの.
MaliciousNode.java悪意のあるノードのクラス. Node インターフェイスを実装したもの.
Candidate.javaノードが受け取るトランザクション候補を記述するためのクラス.
フィールドとして, 提案されているトランザクションの ID,
トランザクションを提案しているノードのインデックスが含まれる.
Simulation.java合意形成のテストをするためのクラス.
グラフを生成し, グラフのパラメータを変更してシミュレーションを行い,
CompliantNode クラスをテストすることが可能.
Transaction.javaトランザクションのクラス. フィールドとして, 一意の ID が含まれる.

Simulation.java の処理の概要を述べておきましょう:

  1. ノードたちを生成する. その中で, どれが悪意のあるノードで, どれが善良ノードかを選択する,
  2. 1 で生成したグラフを, ランダムグラフとして初期化する,
  3. 全てのノードにそれらのフォロー先 (フォロイー) を通知する,
  4. ランダムな ID で有効なトランザクションの集合 (例えば 500個のトランザクションを含む) を初期化する,
  5. 各ノードが聞いたトランザクションの開始状態を初期化するために, ノード全体にトランザクションを分散させる.
    配布はトランザクションとノードのペアごとに, 定めた確率でランダムに行う,
  6. 各ノードがフォロワーへ提案するトランザクションのリストを1つに纏める,
  7. 6 で纏めた提案リストを, 各ノードに配布する (伝搬させる),
  8. 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 はノードが実行するシミュレーション回数です. 

Trust Stock photos by Vecteezy

Bitcoin における合意形成アルゴリズム Part 2

Bitcoin における合意形成アルゴリズム Part 1」の続きです.

ここでは, Bitcoin の合意形成アルゴリズムが実用的には上手く機能している理由について,
攻撃者 (悪意のあるノード) を想定しながら述べます.

Bitcoin のブロックチェーンでは, 悪意のあるマイナー含め, 各マイナーが自主的にチェーンを伸ばしていきます.
このとき, 必然的にチェーンの分岐が起こってしまいますが, その中の最長チェーンだけを有効なものとするという
ルールを定めています*1.
これにより, ブロックの有効性について, マイナーの多数決での合意形成が行われたことになります.

*1 もちろん2つの有効なブロックが同時に作成されても, チェーンに組み込まれるのはそれらのうちどちらか一方となります.
最終的にどちらのブロックが組み込まれるかは, 他のマイナーがどちらのブロックを選択するかによって決まります.

図1 Bitcoin ブロックチェーンの分岐と最長チェーン

不正なブロックを作成する攻撃者は, PoW により大量の計算コストをかけることになりますが,
最長チェーンに組み込まれる確率は非常に低く, さらに報酬を得ることもできません.
そのため, わざわざ高いコストを支払ってまで不正なブロックを作成しようとする動機にならず,
全てのノードがルールに従い続けようというインセンティブが働くのです.

攻撃者の負ける確率が非常に高いという数学的根拠は Bitcoin の原論文に記述があります:
Satoshi Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System, bitcoin.org, 2008.

まず P を善良ノードが次のブロックを見つける確率, Q を攻撃者が次のブロックを見つける確率,
Qz を攻撃者が z ブロックの遅れから追いつく確率とします.

ここで, P > Q と仮定すれば、Qz = (Q/P)z が成り立つため,
追いつく必要のあるブロック数の増加に伴い, 攻撃者が追いつく確率は指数関数的に下がっていきます.
一方, P ≦ Q と仮定すれば Qz = 1 が成り立ち, 攻撃者の勝利となります.

ここで, P ≦ Q のとき, つまり Q が 50% 以上というのは、
攻撃者が全体のハッシュレートのうち半分以上の割合を支配しているという意味で*2,
不正な合意形成が行われてしまいます. これは 51% 攻撃などと呼ばれています.
しかし, 現実的には 50% 以上のハッシュレートを確保するのは非常に高コストであるため,
難しいとされています.

*2 ハッシュレートとは, 1秒あたりに何回ハッシュ計算ができるかという単位 [H/s] です.
ハッシュパワーや採掘速度とも言います.

いま見たように, 51% 攻撃が行われなければ Bitcoin ブロックチェーンは安心, と誰もが信じたいところですが,
実はそれが覆される攻撃手法が存在するのです.
これは 利己的マイニング (selfish mining) と呼ばれる攻撃で, 2013年に Eyal と Sirer により提案されました:
Ittay Eyal, Emin Gun Sirer, Majority is not Enough: Bitcoin Mining is Vulnerable, 2013.

具体的には, 攻撃者はマイニングに成功してもそのブロックを公開せず,
数ブロック分を公開しないままマイニングを進め, ある時点でまとめて数ブロック分を公開することで,
最長チェーンを伸ばす競争を利己的に進めることができるというものです.

Q を攻撃者が次のブロックを見つける確率,
2つの公開 (分岐) チェーンがあったとき, Z を善良ノードが攻撃者のチェーン上にブロックを追加する確率とします.
このとき, Z = 1/2 ならば, Q > 1/4 で攻撃者は通常マイニングよりも利己的マイニングの方が儲かります.
さらに, Q > 1/3 ならば, 任意の Z に対して, 攻撃者は利己的マイニングの方が儲かることになります.

よって, ハッシュレートの 50% 以上を支配していないマイナーがいなければ安全と信じ込むのは危険です.

Network Stock photos by Vecteezy

Bitcoin における合意形成アルゴリズム Part 1

分散ネットワークシステムで合意形成 (コンセンサス) を得るためには, Byzantine 将軍問題があり,
全ノードのうち 1/3 以上が悪意のあるノードならば, 合意形成は不可能であることを
分散型合意形成と Byzantine 将軍問題で見ました.

Byzantine 将軍問題が発生しても, ネットワークが正しい値について合意できるという性質を
BFT (Byzantine Fault Tolerance, ビザンチン障害耐性) と言います.

Bitcoin のような分散型電子通貨システムを構築する上で解決すべき重要な技術的課題の1つは,
分散型合意形成を実現することですが, Bitcoin ブロックチェーンには BFT があるでしょうか.

結論から言うと, Bitcoin ブロックチェーンは Byzantine 将軍問題に対して,
理論的な解を与えていないが, 実用的な解を与えています.
これは従前のモデルにない条件があることで, 実用的には上手く機能しています.

その条件は2つあります.
1つ目は, インセンティブという概念です.
不正取引を防ぎブロックチェーンの維持に貢献した報酬として, ブロックを作成 (マイニング) したノード (マイナー) に
Bitcoin (ブロック作成報酬と取引手数料の合計) が与えられます*1.
Bitcoin が通貨であるため, 参加ノードが誠実に行動しようと思うインセンティブが働くのです.

*1 ブロックチェーンの維持に貢献したという意味は, PoW (Proof of Work, 作業をしたことの証明) という
大量の計算コストをかけた (ハッシュ計算をした) ということです.

2つ目は, 確率的な合意形成です. Bitcoin ブロックチェーンでは, 合意形成のための特定の出発点や終点の概念がありません.
その代わりに, 合意形成に長い時間をかけ, 実際の運用では1時間程度の時間をかけています*2.
しかし, それだけの時間をかけた後も, ノードは特定の取引やブロックがブロックチェーンに書き込まれたかどうかを
確実に知ることができません.
ただし, 時間が経つにつれて, 自分から見える形は最終的に合意が得られた形に一致していき,
2つの形が乖離する確率は指数関数的に下がります.

*2 ブロックが作成される間隔が約10分であるため, ブロックがブロックチェーンに組み込まれた後に,
6個のブロックが追加されればそのブロックは有効だろうと確信できるということです.
ここで, 6個という数に理論的な根拠はなく, あくまでも経験的な答えであることに注意しましょう.

Bitcoin ブロックチェーンが従来の分散型合意形成にかかる Byzantine 将軍問題を回避する上でのポイントは,
モデルのこのような違いです.
Byzantine 将軍問題を「解決」でなく「回避」というのは, 冒頭で申し上げた通り理論的には解が与えられていないからです.

実際、理論的に解が与えられたと言うためには, 合意が覆る可能性がゼロでなければなりませんが,
Bitcoin ブロックチェーンでは, PoW による合意はブロックが作成された時点では確定しておらず,
あくまでも時間の経過とともにその時点の合意が覆る確率がゼロへ収束する, 仕組みとなっています.

Bitcoin における合意形成アルゴリズム Part 2」に続きます.

Network Stock photos by Vecteezy

分散型合意形成と Byzantine 将軍問題

分散ネットワークシステムで昔からよく知られている問題に, Byzantine (ビザンチン) 将軍問題というものがあります.

これは分散ネットワークシステム上の合意形成にかかる問題で, 1982年に Leslie Lamport 氏らによって定式化されました:
Leslie Lamport, Robert Shostak , and Marshall Pease, The Byzantine Generals Problem, SRI International, 1982.

ちなみに Leslie Lamport 氏は, 2013年にコンピューターサイエンス分野における最高の栄誉
と言われる Turing 賞を受賞しています.
賞の名称は, エニグマ暗号機の解読者であった Alan Turing の名に由来します.

分散ネットワークシステム上では, 有限個のノードがあり, それらのノードの一部は故障していたり悪意を持っていたりします.
それらのノード間において合意形成を得るためには, 次の2つが求められます:

  • 全ての善良ノードがメッセージ (値) について合意して終了しなければならない,
  • メッセージ (値) は, 善良ノードによって生成されなければならない.

Byzantine 将軍問題は, 相互に通信し合うノードにおいて, 通信および個々のノードが故障,
または故意にノードが偽の情報を伝達する可能性がある場合に, 全体として合意形成が得られるか, を問う問題です.

さて, Byzantine 将軍問題と呼ばれる由来について述べます.
これは上記で述べたシステム上の問題を, 古代東ローマ帝国 (Byzantine 帝国) の将軍に喩えたものです.

図1 Byzantine 将軍問題

Byzantine 軍は, 部隊に分かれており, それぞれが1人の将軍に率いられています.
各部隊は敵城を包囲しており, 1対1でしか互いに連絡が取れない状況を想定します.
この戦いでは, 全部隊が同時に攻め込まない限り城を落城させることができないようです.
そこで, 将軍たちは共通プランについて合意したいと考えており, 「突撃」あるいは「撤退」の判断を,
伝令を使って他の部隊へ伝えます.

しかし, 一部の将軍は裏切り者であり, 祖国に忠実な将軍たちが共通プランについて合意が形成できないように,
他の将軍から「攻撃」の情報が伝えられると, 意図的に「撤退」の情報に替えて別の将軍に伝える可能性があります.
この裏切り行為により, 一部の将軍は「突撃」と「撤退」の両方を受け取ることも考えられ,
場合によっては合意形成が得られず, 一部の部隊だけが「突撃」してしまい, Byzantine 軍は敗北することになります.

この問題のゴールは, 全ての忠実な将軍が共通プランについて合意が形成できるようにすることです.
このとき, 裏切り者の将軍の妨害により間違ったプランを採用するようなことがあってはなりません.
この問題は, 1/3 以上の将軍が裏切り者なら, 合意形成は不可能だということが証明されています.

Shapes Vectors by Vecteezy
Knight Vectors by Vecteezy
Network Stock photos by Vecteezy

Scrooge Coin 取引の実装

Scrooge Coin 取引の有効性確認」の続きです.

ここでは, 前回まで見てきた Scrooge Coin 取引の理論を Java で実装してみます.
これは Princeton 大学の講義 “Bitcoin and Cryptocurrency Technologies” のプログラミング課題の1つです.

下表に, 使用するクラス一覧とその説明を纏めました.

表1 クラスの仕様 (概要)

FileDescription
Crypto.java電子署名の有効性を確認する verifySignature() メソッドを含んだ Crypto クラス.
Transaction.javaScrooge Coin の取引を表す Transaction クラス.
内部クラスに Transaction.Outputと Transaction.Input がある.
TxHandler.java取引の有効性を確認する isValidTx() メソッドと, 各取引の有効性を確認し受け入れた取引について
現在の UTXO プールを更新する handleTxs() メソッドを含んだ TxHandler クラス.
UTXO.javaUnspent Transaction Output を表す UTXO クラス.
フィールドとして, UTXO が発生した取引のハッシュ値と, その取引内の対応するインデックスが含まれる.
UTXOPool.javaUTXO たちの現在のコレクションを表し,
各 UTXO から対応する取引の出力へのマップを含む UTXOPool クラス.

今回は, 次のような API を実装する TxHandler クラスを作成します.
ただし, ここでは処理の流れを分かりやすく表現するために擬似コードで書きました.

public class TxHandler {

    Declares the field utxoPool;

    public TxHandler(UTXOPool utxoPool) {
        Initializes the field utxoPool with the argument value utxoPool;
    }

    public boolean isValidTx(Transaction tx) {
        Declare the HashSet with UTXO type;
        Initializes the input value is 0.0;
        Initializes the output value is 0.0;

        Loop i = 0, 1, ..., number of elements stored in the input of tx
            Creates a new UTXO corresponding to the output 
            with index outputIndex in the transaction whose hash is prevTxHash;

            if (!all outputs claimed by tx are in the current UTXO pool) {
                return false;
            }

            if (!the signatures on each input of tx are valid) {
                return false;
            }

            if (UTXO is claimed multiple times by tx) {
                return false;
            }
            Adds the UTXO to Set;
            Adds the previous output value to the input value;
        End i Loop

        Loop i = 0, 1, ..., number of elements stored in the output of tx
            if (!all of txs output values are non-negative) {
                return false;
            }
            Adds the value to the output value;
        End i Loop

        if (output value > input value) {
            return false;
        }

        return true;
    }

    public Transaction[] handleTxs(Transaction[] possibleTxs) {
        Declares the HashSet with Transaction type;

        Loop i = 0, 1, ..., number of elements stored in the possibleTxs
            if (transaction is valid) {
                Adds the transaction to Set;

                    Loop i = 0, 1, ..., number of elements stored in the input of transacion
                        Creates a new UTXO corresponding to the output with 
                        index outputIndex in the transaction whose hash is prevTxHash;
                        Removes the UTXO from the utxoPool;
                    End i Loop
                    Loop i = 0, 1, ..., number of elements stored in the output of transacion
                        Creates a new UTXO corresponding to the output with 
                        index i in the transaction;
                        Adds a mapping from UTXO to transaction output to the utxoPool;
                    End i Loop
            }
        End i Loop

        return a valid transaction array;
    }
}