分散型合意形成と 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;
    }
}

Scrooge Coin 取引の有効性確認

Scrooge Coin の取引形態」の続きです.

まず, Scrooge Coin 取引のデータ構造について説明します.

全ての取引は, 複数の入出力から構成されます.
取引の出力は, 金額とそれが支払われる受信者のアドレス (公開鍵) で構成されます.
取引の入力は, 対応する出力を含む前の取引のハッシュ値, その取引におけるこの出力のインデックス (0から始まる整数),
およびコインの所有者の電子署名で構成されます.

入力が有効であるためには, それに含まれる署名が本取引に対する有効な署名でなければなりません.
コインの所有者が自分のコインを消費することに同意していなければ, 取引は無効となります.


図1 Scrooge Coin 取引のデータ構造

ここで, 取引1は, CreateCoins 取引であり, 新規コインを作成するものであるため, 入力を持ちません.
そして, 最初の所有者にコインを出力します.
また, これは新規コインを作成する取引のため, 署名は不要です.
取引2および3は, PayCoins 取引であり, 入出力から構成されています.

次に, Scrooge Coin 取引が有効であるためには, どの様なことを確認すれば良いか見てみましょう.
以下5つの条件が満たされれば, PayCoins 取引は有効であると宣言されます:

  1. 取引が要求する全ての出力は, 現在の UTXO プールにある,
  2. 取引の各入力の署名は有効である,
  3. 取引によって複数回要求された UTXO はない,
  4. 取引のすべての出力金額は非負である,
  5. 取引の入力金額合計は, 出力金額合計以上であり, それ以外は偽である.

ここで, UTXO (Unspent Transaction Output) とはブロックチェーンに記録された未消費コインを意味し,
その集まりを UTXO プールと呼びます.
つまり一連の取引の流れにおいて, 取引の出力 (Transaction Output) は,
誰も消費していない (Unspent) コインと捉えることができます.
そして, その出力は次の受信者にとっては入力となります.
その取引が入力として消費されると, UTXO プールから削除されます.

有効な取引を Scrooge がブロックに追加してブロックチェーンに連結することで,
この取引が行われたことを誰でも知ることができるようになります.

Scrooge Coin 取引の実装」に続きます.

Scrooge Coin の取引形態

単純な仮想通貨 Scrooge Coin のブロックチェーン」の続きになります.

ここでは, Scrooge Coin の取引形態について説明します.
Scrooge Coin には2種類の取引があります.

1. CreateCoins 取引
この取引では, 1度の取引で複数のコインを作成することができます.
全てのコインには, シリアル番号, 金額, 受信者 (最初の所有者の公開鍵) の情報があります.
つまり, この取引形態では, 複数の新規コインを作成し, それを最初の所有者に与えることができます*1.

*1 CreateCoins 取引は, Bitcoin で言うところの Coinbase 取引に似ています.

各コインのシリアル番号は, 例えば coinID12(0) で表し, 取引12で作成された1番目のコインを意味します.
Scrooge Coin の定義により, CreateCoins 取引は, Scrooge が署名する限り, 常に有効です.

図1 CreateCoins 取引

2. PayCoins 取引
この取引では, 幾つかのコインを消費して破棄し, 同じ金額の新規コインを作ります.
そのコインは別の人 (公開鍵) のものになる可能性もあります.

各新規コインには, CreateCoins 取引と同様にシリアル番号, 金額, 受信者の情報があります.

さらにこの取引では, コインを支払う全員が署名しなければならず,
コインの消費を許可するために, 消費されるコインの所有者の全ての署名が必要となります.

図2 PayCoins 取引

ここで, PayCoins 取引で見たように, Scrooge Coin 自体は不変であることに注意しましょう.
つまり分割や結合されることはなく, 各コインは1取引の中で1度だけ作成され, 将来の別の取引で消費されます.

しかし, PayCoins 取引を使えば, コインの分割や結合ができるのと同じ効果が得られます.
例えば, 自分が所有している2コインを結合するためには,
その2コインを消費すると共に消費合計金額と同じ新規コインを1つ作るような取引を作成します.
この場合, その新規コインの受信者を自分自身に指定すれば良いことになります.

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

単純な仮想通貨 Scrooge Coin のブロックチェーン

Scrooge Coin の説明に入る前に, まず Scrooge について説明しましょう.
Scrooge (スクルージ) とは, 辞書を引くと「けちん坊」や「守銭奴」という和訳が出てきます.

語源は, 英国の文豪 Charles Dickens (チャールズ・ディケンズ) が1843年のクリスマスに発表した小説
A Christmas Carol (クリスマス・キャロル)』の主人公 Ebenezer Scrooge (エベネーザ・スクルージ) です.
小説に登場する Scrooge は, ロンドンの下町近くでスクルージ & マーレイ商会を営んでいる初老の商人で,
冷酷無慈悲, 強欲, エゴイスト, 守銭奴な人物として描かれています.

Scrooge Coin のアイデアは, 名前のもとである Scrooge が中央機関となって,
全ての取引の履歴を記録するブロックチェーンを公開し,それに電子署名することです.

ここで, ブロックチェーンの一連のブロックには, それぞれ1つの取引を格納しているとし*1,
各ブロックは, 取引の一意のID, 取引の内容, 前のブロックを指すハッシュポインタから構成されています.
尚, ハッシュポインタとは, データの格納場所を指し示すもので, そのデータのハッシュ値が付随しています.

そして Scrooge は, 最新のブロックを指すハッシュポインタに署名し*2, ブロックチェーンと共に公開します.

*1 実際には, 最適化のために, Bitcoin のように同じブロックに複数の取引を格納します.
*2 このハッシュポインタは, 一連のブロック全体に含まれる全てのデータを1つに纏めています.

図1 Scrooge Coin のブロックチェーン

Scrooge Coin では, 取引を記録するブロックに Scrooge の有効な署名があることを, 彼の公開鍵を使って誰もが検証できます.
さらにブロックチェーンをずっと遡って, 全ての取引履歴を閲覧することも可能です.

もし誰かが使用済 Coin を2重支払しようと企む取引を作成すれば,
Scrooge がそれを検出しブロックチェーンに記録することを拒否するでしょう.

Scrooge Coin の取引形態」に続きます.