Computer Science

分散ネットワークシステムで合意形成 (コンセンサス) を得るためには, 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 (ビザンチン) 将軍問題というものがあります.

これは分散ネットワークシステム上の合意形成にかかる問題で, 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 取引の理論を Java で実装してみます.
これは Princeton 大学の講義 “Bitcoin and Cryptocurrency Technologies” のプログラミング課題の1つです.

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

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

File	Description
Crypto.java	電子署名の有効性を確認する verifySignature() メソッドを含んだ Crypto クラス.
Transaction.java	Scrooge Coin の取引を表す Transaction クラス. 内部クラスに Transaction.Outputと Transaction.Input がある.
TxHandler.java	取引の有効性を確認する isValidTx() メソッドと, 各取引の有効性を確認し受け入れた取引について 現在の UTXO プールを更新する handleTxs() メソッドを含んだ TxHandler クラス.
UTXO.java	Unspent Transaction Output を表す UTXO クラス. フィールドとして, UTXO が発生した取引のハッシュ値と, その取引内の対応するインデックスが含まれる.
UTXOPool.java	UTXO たちの現在のコレクションを表し, 各 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;
    }
}