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

ブロックチェーンベースの分散型合意形成アルゴリズムの一部であるノードを実装してみました.
プログラムは, 入力されるトランザクションとブロックを受信し, 更新されたブロックチェーンを維持するよう実装します.
これは 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 クラスの仕様 (概要)

ここでは, 次のように 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