簡単なブロックチェーンの実装

ブロックチェーンベースの分散型合意形成アルゴリズムの一部であるノードを実装してみました.
プログラムは, 入力されるトランザクションとブロックを受信し, 更新されたブロックチェーンを維持するよう実装します.
これは Princeton 大学の講義 “Bitcoin and Cryptocurrency Technologies” のプログラミング課題の1つです.

ブロックチェーンでは, (複数の) フォークが存在する可能性があるため, ブロックはリストではなくツリーを形成します.
また, 新しいブロックが作成される可能性のある全てのブロックに対応する UTXO プールを維持する必要があります.

以下, 実装における前提です:

  • ブロックチェーン全体は巨大なサイズになる可能性があるため, 最新ブロックだけを維持するものとします.
    保存する数は, API の機能を全て実装できていれば, 自由に決められます,
  • 新しい Genesis block は採掘されません. Genesis block を名乗るブロック (親は NULL ハッシュ) を受信した場合,
    BlockChain クラスの addBlock(Block b) メソッドで false を返すことが出来ます,
  • 同じ高さのブロックが複数ある場合は, getMaxHeightBlock() メソッドで最も古いブロックを返します,
  • 簡単のために, あるブロックの coinbase トランザクションは,
    その上に採掘された次のブロックで使うことが出来ると仮定します.
    これは, 実際の Bitcoin プロトコルでは, 使用可能になるまでに 100 回の承認が必要な「満期」期間がある事と異なります,
  • ブロックチェーンのグローバルトランザクションプールを 1 つだけ維持し,
    トランザクションを受信したらそこにトランザクションを追加し,
    新しいブロックを受信または作成したらそこからトランザクションを削除します.
    ブロックチェーンの再編成, つまり分岐チェーンが新たな最長チェーンになったときに,
    一部のトランザクションが削除されても構いません.
    具体的には, 元のメインブランチに存在する (つまりトランザクションプールから削除される) が,
    分岐ブランチには存在しないトランザクションが失われる可能性があります,
  • coinbase の値は 25 コインで一定とします*1, 
  • ノードが新しく受信したブロックの有効性を確認する場合,
    取引が有効な集合を形成しているかどうかを確認するだけで十分です.
    その集合は, 可能な限り最大のトランザクションの集合である必要はありません.
    また, PoW (Proof of Work) のチェックも必要ありません.

*1 coinbase はいわゆる採掘報酬を意味します. Bitcoin では, 25 BTC からスタートし, 約4年ごとに半分になり,
2021年5月現在は 6.25 BTC です.ちなみに最後のブロックの発掘は 2140 年頃です.

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

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

FileDescription
Block.javaブロックのデータ構造を格納するための Block クラス.
フィールドとして, ブロックのハッシュ値, 直前のブロックのハッシュ値,
トランザクションデータが含まれる.
BlockChain.javaブロックチェーンの管理を行うための BlockChain クラス.
フィールドとして, ブロックチェーン, 最大高さのブロックノード,
トランザクションプールが含まれる.
さらに, 内部クラスに BlockNode がある. そのフィールドとして, ブロック, 親ノード, 子ノード,
ブロックの高さ, ブロックの上に新ブロックを作成するための UTXO プールが含まれる.
BlockHandler.javaBlockChain クラス を使用して, 新しく受信したブロックの処理, 新しいブロックの作成,
または新しく受信したトランザクションの処理を行うための BlockHandler クラス.
ByteArrayWrapper.javaHashMap のキーとして使用できるように, バイト配列のラッパーを作成するための ByteArrayWrapper クラス. TransactionPool クラスを参照.
Crypto.java電子署名の有効性を確認する verifySignature() メソッドを含んだ Crypto クラス.
Transaction.javaScrooge Coin 取引の実装」の Transaction クラスと似ているが,
coinbase トランザクションを作成する機能を追加している.
coinbase トランザクションの作成方法は, Block クラスのコンストラクタで実装する.
TransactionPool.java新しいブロックを作成する際に必要なトランザクションプールを実装するための
TransactionPool クラス.
TxHandler.javaScrooge Coin 取引の実装」の TxHandler クラスに, getUTXOPool() メソッドを追加している.
UTXO.javaScrooge Coin 取引の実装」の UTXO クラスと同じ.
UTXOPool.javaScrooge Coin 取引の実装」の UTXOPool クラスと同じ.

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

public class BlockChain {

    private class BlockNode {
        
        Declares fields b, parent, children, height, uPool;
        
        public BlockNode(Block b, BlockNode parent, UTXOPool uPool) {
            Assign b to the b field of own instance;
            Assign parent to the parent field of own instance;
            Create a children instance;
            Assign uPool to the uPool field of own instance;
            
            if (!parent is null) {
                Assign parent.height + 1 to the height;
                Add own instance to the end of parent.children;
            } else {
                Assign 1 to the height;
            }

        }

        public UTXOPool getUTXOPoolCopy() {
            return new instance with the argument value uPool;
        }
    }

    Declares fields blockChain, maxHeightNode, txPool;
    
    Initializes the class constant CUT_OFF_AGE is 10;

    /** create an empty block chain with just a genesis block. Assume {@code genesisBlock} is a valid block */
    public BlockChain(Block genesisBlock) {    
        Create a blockChain instance;
        Create a utxoPool instance;
        Add a coinbase transaction to the UTXO pool;
        Initializes the field genesisNode with the argument values genesisBlock, null utxoPool;
        Store the pair of genesisBlock hash and genesisNode in the blockchain;
        Create a txPool instance;        
        Assign genesisNode to the maxHeightNode;
    }

    /** Get the maximum height block */
    public Block getMaxHeightBlock() {
        return the block of maxHeightNode;
    }

    /** Get the UTXOPool for mining a new block on top of max height block */
    public UTXOPool getMaxHeightUTXOPool() {
        return the UTXO pool of maxHeightNode;
    }

    /** Get the transaction pool to mine a new block */
    public TransactionPool getTransactionPool() {
        return the transaction pool;
    }

    /** Add {@code block} to the block chain if it is valid */
    /** Return true if block is successfully added */
    public boolean addBlock(Block block) {
        Initializes the prevBlockHash is getPrevBlockHash() of block;

        if (prevBlockHash is null)
            return false;

        Initializes the field parentBlockNode is BlockNode corresponding to the prevBlockHash of blockChain;

        if (parentBlockNode is null) {
            return false;
        }

        /** Transaction validity check */
        Initializes the field handler with the argument value UTXO pool of parentBlockNode;
        Initializes the field txs is the transaction of block;
        Initializes the field validTxs is the valid transaction set in txs;

        if (!validTxs.length is txs.length) {
            return false;
        }

        /** Block validity check*/
        Initializes the field proposedHeight is parentBlockNode.height + 1;         

        if (proposedHeight <= maxHeightNode.height - CUT_OFF_AGE) {
            return false;
        }

        Initializes the field utxoPool is the UTXO pool of handler;
        Add a coinbase transaction to the UTXO pool;
        Initializes the field node with the argument values block, parentBlockNode, utxoPool;
        Store the pair of block hash and node in the blockchain;

        if (proposedHeight > maxHeightNode.height) {
            Assign node to the maxHeightNode;
        }

        return true;
    }

    /** Add a transaction to the transaction pool */
    public void addTransaction(Transaction tx) {
        Add a tx to the transaction pool;
    }

}

Web Stock photos by Vecteezy

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

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