随着时间的推移，比特币系统吸引了越来越多的用户，也相应地引发了交易数据的累积。由于现有比特币系统存储机制的可扩展性较低，累积的交易数据将引起节点中状态数据的急剧膨胀，后者进一步导致了区块校验过程的低效率。低效的区块校验可能会从两方面影响区块链系统的安全性。一方面，区块校验的低效率导致了新区块在网络中广播的高时延，从而增大了区块链分叉的风险。另一方面，全节点在加入区块链网络的初始阶段，需要从邻居节点逐个同步和校验每个历史区块。区块校验的低效率导致了该过程的高时间成本，从而打击了用户运行全节点的积极性。全节点用户的减少，导致了区块链网络中去中心化程度的下降。对此，本文提出一种基于状态数据缩减的区块高效校验方法，主要包含以下三点设计思想：（1）将比特币系统中原有的UTXO集合替换为轻量化的位向量集合，以减少区块链中的状态数据量；（2）缩减后的状态数据使得区块校验过程完全在内存中进行，提升了区块校验的效率；（3）修改交易中输入的数据结构，为区块的正确性校验提供证明性数据。实验结果表明，该方法能够极大地降低状态数据的内存需求，从而提升区块校验效率。

该成果“An Efficient Block Validation Mechanism for UTXO-based Blockchains”发表在IPDPS 2022 (The36th IEEE International Parallel & Distributed Processing Symposium），是实验室分布式系统组在区块链领域的研究成果。

• 论文链接：https://ieeexplore.ieee.org/document/9820744

以比特币为代表的大量区块链系统采用了UTXO（Unspent Transaction Output）数据模型。在该模型中，节点接收到新区块后需要对区块的合法性进行检验。区块只有通过了合法性校验，才会被节点存储到本地账本中，并被该节点转发给其他节点。区块校验主要是对区块中的所有交易进行合法性校验，而交易合法性校验中最具有挑战性的部分便是对输入部分的校验。在当前的比特币实现中，输入校验主要包括两个步骤：数据库操作校验和脚本校验。其中，数据库操作校验同时完成了输入的存在性校验和未花费校验两个部分，前者用来判断该输入是否对应于一个已存在的输出，后者判断该输出是否被花费过。脚本校验则用来检查解锁脚本和锁定脚本是否相匹配。

以上的区块校验过程主要依赖于对存储层中状态数据的查询。然而，随着时间的推移，越来越多的状态数据存储在磁盘中，状态数据的膨胀现象日益严重，状态数据的查询延迟越来越高。查询的高延迟将大大降低区块数据的校验效率，进而影响区块链系统的安全性和性能。具体而言，一方面，区块在点对点网络中传播时，需要经过每一个转发节点的校验：低效的区块校验将导致区块在网络中传播时延的增大，从而增大区块链分叉的风险；另一方面，区块的传播时延与区块链系统的吞吐量成负相关关系：较高的传播时延要求设置较小的区块体积，从而限制了系统性能。因此，亟需对状态数据进行优化，进而提升区块链存储机制的可扩展性和区块的校验效率。

针对状态数据膨胀机器导致低效区块校验问题，我们提出一种基于状态数据缩减的区块高效校验方法（Efficient Block Validation, EBV），该方法采用了一种轻量化的状态表示结构。总体而言，EBV方法将区块链系统中原有的UTXO集合替换为位向量集合并对相应的输入结构进行修改。位向量集合形式的状态表示方法极大地降低了区块链系统中状态数据的内存需求，使得区块校验完全在内存中实现，提升了区块校验的效率。输入结构的改变用以辅助进行区块的去中心化校验，从而保证了区块链系统的安全性。

图1展示了EBV方法的总体设计。相比于比特币的原有设计，EBV方法的改进主要包括两方面：节点中的状态数据库存储内容和交易中的输入结构。和比特币系统存储所有的UTXO数据不同，EBV方法在键值对数据库中维护了一个位向量集合。数据库的键是区块的高度，值是对应于该区块中所有输出的位向量。位向量中的每个比特位标识了相应的输出是否被花费。当一个新区块被加入到区块链中时，一个由全部1值组成的位向量被插入到数据库中，向量的长度为该区块中的输出总数。如图1所示，数据库中新增了一个键为m+1、值为 [1, 1, 1, 1, 1] 的记录。与此同时，针对区块中的所有输入，将输入所花费的输出在数据库中对应的比特位复位为0。以图1为例，新区块花费了第1个区块中的第2个输出，因而该输出对应的比特位被设置为0。由于一个位向量的大小最多数KB，所有区块对应的位向量集合大小约为数百MB，该数值远远小于比特币原有系统中的UTXO集合大小。因此，轻量化的状态表示方法有效提升了区块链存储机制的可扩展性。

图2展示了EBV系统中交易的校验流程，其中存在性校验依赖于输入中的默克尔分支和高度两个字段实现，而未花费校验依赖于输入中的高度字段和位置字段以及节点本地维护的位向量集合实现。具体而言，校验节点首先从本地内存中找到对应于高度的区块头数据。然后自底向上计算默克尔分支中的哈希值，并将计算得到的根哈希与区块头中的哈希进行对比，以判断锁定脚本数据的真实性。锁定脚本数据的真实性也说明了所要花费的输出的存在性，即实现了存在性校验。为进行未花费校验，节点首先以高度为键从状态数据库中查找相应的位向量，并根据位置字段检查该位向量中相应位置的比特值。若比特值为1，说明该输入所要花费的输出尚未被使用，即输入通过了未花费校验。

在以上介绍的状态数据库更新流程中，EBV系统对数据库中值为全0向量的记录进行了删除，以缩小数据库的空间占用。然而对于数据库中只有少数比特位为1的记录，无法通过该方法进行优化。如图3（a）所示，第0条记录的位向量中只有第3个比特位值为1。为表明这一个比特的位置，需要保存完整的位向量，从而造成了极大的空间开销。该问题被称为EBV系统中状态数据库的稀疏向量问题。

为解决该问题，EBV方法对稀疏向量采取“索引向量”的表示形式，并在数据库中进行“位向量”和“索引向量”的混合表示。具体而言，一个稀疏的位向量可以表示为{i₀, i₁,...,i_n} ，其中i_k是位向量中第k个值为1的比特位的索引位置，n是位向量中值为1的比特位的个数。对应于图3（a）中第一条记录的稀疏位向量，该向量的“索引向量”表示形式如图3（b）所示。由于位向量中只有第3位比特值为1，索引向量只包含索引3，其二进制表示为112。和需要五个比特位的“位向量”表示相比，“索引向量”表示中只需要两个比特，大大降低了数据表示的空间占用。

由于索引向量在数据库中也是以比特位的形式存取，当包含多个索引值时，需要以某种方案将这些比特位进行正确切分。一种简单的实现方案是规定每个索引向量的比特位长度。通过对比特币系统中所有区块的输出数量进行统计，发现区块中的输出数量远远小于65536，因此16个比特位足以表示任何一个索引值。此外，由于数据库中混合存储了“位向量”和“索引向量”，需要在向量表示之前增加一个标志位。当标志位值为0时，相应的记录表示一个“位向量”，否则表示一个“索引向量”。

为评估EBV方法的可行性和有效性，我们基于比特币系统的Golang版本Btcd实现了采用EBV校验方法的区块链系统。图4以季度为横坐标，展示了比特币节点和EBV节点从2015年初到2020年中的内存占用对比。为验证EBV系统中“位向量”优化方法（包括删除全0向量和采用索引向量）的有效性，图4对未采用“位向量”优化的EBV系统的内存占用开销也进行了衡量。容易看出，EBV方法有效降低了区块链系统的内存开销，且降低幅度随着时间的推移越来越大。以2020年第二季度为例，EBV系统只占用273.76 MB的内存空间，远远小于比特币原有系统的3.8GB（约为比特币原有系统的7.2%）。此外，通过对比“位向量”优化前后的EBV系统内存开销，可以发现“位向量”优化方法有效缩减了对内存的占用，缩减幅度最高可达42.0%。且随着时间的推移，“位向量”优化的效果越来越明显。这是因为区块中越来越多的输出被花费，使得相应的位向量更可能因成为一个稀疏向量而被优化。

图5（a）展示了EBV系统和比特币系统的区块校验时间对比。正如所预料的那样， EBV系统大幅降低了区块校验的时间，平均降低为比特币原有系统的19.6%。特别地，对于高度为590004的区块，EBV方法将区块校验时间减小为原来的6.5%。此外，将EBV系统中区块校验时间划分为四个部分进行分别统计，统计结果如图5（b）所示。容易看到，区块校验时间中的存在性校验和未花费校验部分占比较小，而脚本校验部分占比较大。由此也说明了EBV方法主要实现了对区块校验过程中存在性校验和未花费校验功能的优化。

详细内容请参见：

Xiaohai Dai, Bin Xiao, Jiang Xiao, and Hai Jin, "An Efficient Block Validation Mechanism for UTXO-based Blockchains," in Proceedings of IEEE International Parallel and Distributed Processing Symposium (IPDPS), Lyon, France, 2022, pp. 1250-1260, doi: 10.1109/IPDPS53621.2022.00124.