从零开始搭建一个类似以太坊数字货币的最小化区块链系统。

原文标题：《源代码 : 一个最小化的区块链系统》
撰文：王嘉平，中科院计算所博士，曾带领团队在 NSDI 2019 发表高性能并行分片区块链系统的论文

近期有个国内著名技术协会的约稿，正好向技术圈分享一下我对区块链系统的拙见。我发现一件有趣的事情，即使是有计算机背景，懂编程的同学，都也不怎么清楚区块链到底是怎么回事。今天这里，我打算用计算机语言和大家沟通，争取可以至少让计算机背景的同学，彻底弄明白区块链是咋回事，是怎么工作的。

不过在开始之前，需要明确的一件事情是，同之前的计算机技术不同，区块链技术核心关乎的是一个计算系统的自动化监管和治理，而不是为了让计算更高效或更大规模地发生。需要明确这个期望，才方便我们去理解，为什么区块链是这样设计的，这样工作的。

我们将以最简化的加密数字货币为例介绍区块链的精确工作原理，为了便于理解将省略手续费，大部分优化，互操作性等层面的东西。这里会用到强类型的伪代码，来精确定义其数据结构和执行逻辑。这里我们将从零开始实现一个类似以太坊数字货币那样的区块链系统，为了便于理解，我们将采用以太坊所采用的账户-状态模型来表示账簿，而不是比特币的那种 UTXO。

我们先从一系列基础实体和原语的定义开始 :

基础数据类型

class String;  // 基础字符串数据结构
class Blob;    // 基础二进制数据，用来表示对象序列化之后的线性二进制数据
class CriticalSection; // 临界区，多线程互斥对象
class BigInt; // 区块链中很多地方的数值采用大整数来表示，例如余额，挖矿难度等。
// 例如用一个 32 字节的无符号大整数，表示 0 到 2^256-1 的整数。

数字签名原语

标准的非对称加密系统里面的函数，公私钥对可以在不联网的情况下，任意生成，并且全球唯一。通常为 32 到 64 字节的无结构二进制数据。其中公钥会公开，在区块链系统中用来表明特定身份，供他人验证其对特定账户的控制权。而私钥则用来通过数字签名来证明其对账户的控制。

VerifySignature 原语，用来对于给定数据和签名，验证是不是对应的签名者签署的。

typedef    BYTE PublicKey[32]; // 公钥数据
typedef    BYTE PrivateKey[64];// 私钥数据
typedef    BYTE Signature[64]; // 数字签名数据
void    Sign(Blob data, PrivateKey sk, Signature sigdata); // 数字签名
bool    VerifySignature(Blob data, PublicKey pk, Signature sigdata); // 检查数字签名是否正确

账户地址

在我们这里的例子中，所有哈希函数都采用 SHA256，其将产生一个 32 字节的哈希值。地址是账户的标识符，是一个 32 字节的无结构二进制数据，由公钥的哈希值 SHA256(PublicKey) 得到。那么也就是说每个公钥，对应一个唯一的地址，对应一个唯一的账户。

typedef        BYTE HashValue[32]; //SHA256 的哈希值
typedef        HashValue Address;  // 账户地址
HashValue    SHA256(Blob data); // SHA256 哈希函数

智能合约 (Smart Contract)

这个有点像一个 C++的类，定义了一些状态，以及修改这些状态的函数。一个区块链系统中，可以有多个智能合约同时存在，但是每个仅会有一个实例。这里我们就数字货币给出一个极度简化的智能合约的例子：

class MyCoin
{
    // internal state
    hash_map<Address, BigInt>_Ledger;

    // internal function
    BigInt_GetBalance(Address addr)
    {
        if(_Ledger.has(addr))return_Ledger[addr];
        else return 0;
    }

    // 转账函数
    void Transfer(Address signer, Address from, Address to, BigInt amount)
    {
        if(signer != from)return;
        if(amount > 0 &&_GetBalance(from) >= amount)
        {
           _Ledger[from] -= amount;
            amount +=_GetBalance(to);
           _Ledger[to] = amount;
        }
    }

    // 挖矿奖励函数
    void CoinBase(int height, Address miner)
    {
        BigInt reward = 5000000000; // 这里简化为，每次奖励 50 个币
        if(reward > 0)
        {
            reward +=_GetBalance(miner);
           _Ledger[miner] = reward;
        }
    }
};

交易 (Transaction)

一个交易表示对特定相关账户一次状态修改请求。交易中不携带任何逻辑代码，仅仅是指定这个交易将调用智能合约里面的哪个公开函数及其调用参数。当然在我们这个极度简化的系统中，只有一种交易，即前面的转账 (Transfer)。交易的发起方必须为扣款方 (from)，并且整个交易携带对交易内容的数字签名，以确信该交易由扣款方发起。基于我们这里的例子，一个交易至少含有以下结构 :

struct Transaction
{
    String      InvokeFunctionName;    // 在我们这里 始终为 「Transfer」
    Blob        InvokeArguments; // 序列化之后的调用参数
    PublicKey   Signer; // 发起者的公钥，注意这里不是地址
    Signature   SignData; // 由发起者的私钥对交易的签名
};

区块 (Block)

一个区块表示区块链接力执行中的一步，里面主要包含这一步中确认的一批交易，以及共识机制验证数据和块头元数据。一个最简化的定义可以是这样 :

struct Block
{
    int     Timestamp; // 出块时间
    HashValue   PrevBlock; // 上一个块的哈希值
    Address     Miner; // 矿工地址
    int     TxnCount; // 这个块中包含的交易个数
    Transaction     Txns[TxnCount]; // 完整的交易列表
    BigInt      PowTarget; // 工作量证明的目标 (共识验证数据)
    int     PowNonce; // 工作量证明的 Nonce 值 (共识验证数据)
};

这里我们给出了最简化的工作量证明 (Proof-of-Work) 的验证数据结构，如果采用其他共识算法，这个部分会有变化。从这个结构可以看出，区块链之所以称为链，就是因为区块结构中包含一个指向上一个区块的「 指针 」，PrevBlock。任何一个被确认的区块，同时也意味着承认其全部的前驱区块，以及这些区块所携带的全部交易。一个区块被确认有三个条件 :

1. 这个区块的共识验证要满足其特定共识算法的要求。在工作量证明算法中，PowTarget 必须小于当前挖矿难度的要求，同时 ((BigInt&)SHA256(Block)) < Block::PowTarget。
2. 这个块所包含的交易必须没有被之前的区块包含过，并且每个交易必须能够保证其数字签名能够被其 Signer 的公钥正确验证。至于交易所执行的逻辑是否正确，是否出错则无关紧要。
3. 在所有分叉块中，即具有相同 PrevBlock 的块，只有优先的块会被确认。这一点不同的共识算法有不同的情况。

P2P 通讯原语

区块链的网络层仅用到了 P2P 网络技术中简单的部分，用基于 TCP 长连接的 Gossip 协议实现一个数据块的全网广播 (Flooding)。我们这里将其抽象下面的通讯原语 :

interface BroadcastNetwork
{
    template<typename T>
    void Broadcast(const T& object); // 将对象序列化并广播出去

    function    OnRecvBlock; // 接收到一个区块的回调函数
    function    OnRecvTransaction; // 接收到一个交易的回调函数
};

内存池 (Mempool) 原语

内存池在区块链系统中用来记录尚未被确认的交易，很容易用比如哈希表来实现。

interface Mempool
{
    bool    Has(Transaction txn);
    void    Insert(Transaction new_txn);
    void    Remove(Transaction txns[count]);
    int Collect(Transaction txns[max_count]);
};

其中 Collect 原语用于挖矿时合成新的区块，从 mempool 中挑出一系列交易来填充 Txns 数组，最多挑 TxnMaxCount 个，并返回实际填充的个数。

区块归档数据库原语

区块链系统中的区块以及交易，在被确认之后，将从内存中移除，并写入归档数据库中。这个部分很容易用一个 Key-value storage 系统来实现，当然用 SQL 数据可也是可以的，就是效率低一些。

interface ArchiveDatabase
{
    void    Archive(Transactiontxns[count]);
    void    Archive(Block blk);
    void    Has(Transaction txn);
    void    Has(Block blk);
}

有了这些定义之后，我们可以给出一个不考虑分叉情况下最简单的基于工作量证明的区块链系统的伪代码 :

static const int TARGET_ADJUST_INTERVAL = 256;  // 每隔 256 个块调整一次算力难度
static const int BLOCK_CREATION_INTERVAL = 600*1000; // 每十分钟出一个块
static const int TRANSCATION_PERBLOCK_MAX = 1024; // 每块最多包含 1024 个交易

BroadcastNetwork*    g_pNet = BroadcastNetwork::Create(...);
Mempool*        g_pMempool = Mempool::Create(...);
ArchiveDatabase*    g_pArchiDB = ArchiveDatabase::Create(...);

MyCoin            g_MyLedger;  // 账簿

// 当前区块链的头
Block        g_BlockHead = Block::GenesisBlock(6); // 初始化为创始区块
HashValue    g_BlockHeadHash = SHA256(g_BlockHead);
int        g_BlockNextHeight = 1;
CriticalSection g_BlockHeadCS;

// 下一个块的共识相关信息 (工作量证明)
PowTarget    g_NextPowTarget = Block::InitialPowTarget(); // 初始挖矿难度
int        g_LastTargetAdjustedTime;


// 收到来自网络广播的交易
g_pNet-> OnRecvTransaction = [](Transaction txn) {
    if(g_pMempool->Has(txn) || g_pArchiDB->Has(txn))
        return;   // 忽略已经存在的交易
    if(!VerifySignature(
            txn.InvokeFunctionName + txn.InvokeArguments +txn.Signer,
            txn.Signer,
            txn.Signature
        )
    )return;// 验证签名是否正确

    g_pNet->Broadcast(txn);  // 基本验证合法之后，接力这个交易的广播
    g_pMempool->Insert(txn);
};

// 收到来自网络广播的区块
g_pNet-> OnRecvBlock = [](Block blk) {
    if(blk.PrevBlock != g_BlockHeadHash)
        return;  // 忽略乱序到达的块，忽略分叉块
    if(blk.PowTarget > g_NextPowTarget)
        return;  // 忽略不满足当前算力要求的块
    if(blk.TxnCount > TRANSCATION_PERBLOCK_MAX)
        return;  // 忽略过于大的块

    HashValue h = SHA256(blk);
    if( ((BigInt&)h) >= blk.PowTarget )
        return;  // 忽略未达到当前标称算力要求的块

    //  校验全部块中的交易
    for(Int32 i=0; i; i++)
    {
        auto& txn = blk.Txns[i];
        if( g_pArchiDB->Has(txn) || // 包含之前已经被确认过的交易
            !VerifySignature(
                txn.InvokeFunctionName + txn.InvokeArguments +txn.Signer,
                txn.Signer,
                txn.Signature
             ) // 包含验签失败的交易
        )return;
    }

    // 至此这个区块被确认
    g_pNet->Broadcast(txn);  // 确认之后，尽快接力这个区块的广播

    g_MyLedger.CoinBase(g_BlockNextHeight, Miner); // 执行出块奖励
    for(auto& txn : blk.Txns)   // 执行每一条交易，然后归档
    {
        // 调用交易中指定的函数
        g_MyLedger[txn.InvokeFunctionName](txn.Signer, txn.InvokeArguments…);
        g_pArchiDB->Archive(txn);
        g_pMempool->Remove(txn); // 从内存池中删除，如果存在的话
    }

    g_pArchiDB->Archive(g_BlockHead);  // 归档上一个区块

    // 更新区块链头，这部分代码需要和挖矿过程中构造新的块的步骤互斥
    g_BlockHeadCS.Lock();
    {
        if(g_BlockNextHeight%TARGET_ADJUST_INTERVAL == 1)
        {// 进行算力调整，周期为 TARGET_ADJUST_INTERVAL 个区块
            if(g_BlockNextHeight > 1)
            {   g_NextPowTarget = PowTargetAdjustment(
                    g_NextPowTarget,
                    blk.Timestamp - g_LastTargetAdjustedTime
                );
            }

            g_LastTargetAdjustedTime = blk.Timestamp;
        }

        // 更新区块链头在最新的这个块
        g_BlockHeadHash = h;
        g_BlockHead = blk;
        g_BlockNextHeight++;
    }
    g_BlockHeadCS.Unlock();
};

这里涉及到一个上面没有定义的算法，PowTargetAdjustment 是用来根据近期出块速度来调整出块算力难度要求，从而使得出块的平均间隔的期望可以大体稳定在一个预先设定的值 (BLOCK_CREATION_INTERVAL)。这是一个和工作量证明共识算法有关的算法，并不是所有区块链系统都有。这个算法的一个最简化定义如下 :

算力难度调整

BigInt PowTargetAdjustment(BigInt cur_target, int nth_block_interval)
{
    return cur_target*nth_block_interval/(BLOCK_CREATION_INTERVAL*TARGET_ADJUST_INTERVAL);
}

到这里一个不出块的区块链节点，即全节点就可以工作了。全节点是区块链网络中的大多数节点，是区块链底层 P2P 网络得以稳定鲁棒运行的保障，同时也实现了区块数据和交易数据的高度冗余的全网存储。虽然不出块，全节点不同于互联网架构的客户端。一个全节点不需要信赖其他节点，更不存在一个服务器。全节点能够独立自主地验证区块链完整的历史演进过程，进而重构其上的状态 (例如一个账户的余额)，而不是去向一个需要信赖的服务器查询。

当然，区块链网络计算接力过程是由出块节点完成了，也就是所谓的矿工节点。这些少数节点，和大量的全节点混在一起，大部分节点收到最新的区块是来自于其他全节点的接力广播，而不是直接来自于一个出块节点。当然，作为接受方，也无从判断发送方是中继的全节点，还是刚刚出块的矿工节点。这也有效地保护了真正出块节点的安全性，避免暴露矿工节点的物理 IP 地址。

一个出块节点，首先是一个全节点，除了上面定义的这些行为之外，还需要一个额外的过程，运行在一个或者多个线程上。我们定义最简化的出块过程如下 :

void Mining()
{
    while(g_KeepMining)
    {
        // 构造新的块，这个部分需要和区块链头更新代码互斥
        g_BlockHeadCS.Lock();
        {
            int next_height = g_BlockNextHeight;
            Block new_block;
            new_block.Timestamp = os::GetCurrentTime();
            new_block.PrevBlock = g_BlockHeadHash;   // 指向最新的块
            new_block.Miner = g_MyAddress;
            new_block.TxnCount = g_pMempool->Collect(new_block.Txns[TRANSCATION_PERBLOCK_MAX]);
            new_block.PowTarget = g_NextPowTarget;
            new_block.PowNonce = os::Random<Int64>();  // 随机初始值
        }
        g_BlockHeadCS.Unlock();

        // 开始挖矿
        while(next_height ==  g_BlockNextHeight)
        {
            if( ((BigInt64&)SHA256(new_block)) < new_block.PowTarget )
            {
                // 挖矿成功
                g_pNet->Broadcast(new_block);  // 立即广播出去
                g_pNet->OnRecvBlock(new_block); // 更新本节点的区块链头
                break; // 开始去挖下一个块
            }
            new_block.PowNonce++; // 尝试下一个 Nonce
        }
        // 大多数情况下，其他节点出了新的块，并更新了区块高度
        // 则挖矿被打断，去挖更新之后的下一个块
    }
}