DorChain：利用休眠币提高交易验证效率

潘森杉，徐腊梅

(1.江苏省工业网络安全技术重点实验室，江苏 镇江 212013；2.江苏大学 计算机科学与通信工程学院，江苏 镇江 212013)

自中本聪[1](Satoshi Nakamoto)在2008年提出区块链的概念以来，以其去中心化和分布式存储等特点吸引了许多专家和研究人员。由于其验证程序可以保留所有分类账数据的安全性，它在许多领域也具有广阔的应用前景，包括物联网环境中的数据共享[2]、车辆社交网络[3]、医疗[4-5]、教育[6]、边缘计算[7]和数据验证搜索[8-9]等。但是，每个验证者都需要保留所有分类账数据，这对于普通用户节点而言，存储负担非常大。从2008年到2020年，区块链上新生产数据的日增长率达到0.135 3 GB。如果根据比特币链中数据的增长率进行估算，在过去的两年中，整个比特币网络的数据量将超过6 TB。针对这种不断增长的数据情况以及所带来的验证负担，许多研究人员提出了相关验证方法[10]。

Boneh方案[11]：提出了两种解决方案。一种是基于UTXO的无状态区块链技术，另一种是应用于IOP(交互式oracle证明)的矢量承诺技术。主要讨论无状态区块链。Boneh主要使用未知阶群构造RSA累加器，然后在此基础上实现成员证明和非成员证明的批处理技术。未知阶群的使用在证明大小和证明传输方面具有明显的优势，尤其是批量更新和聚合成员证明技术。

Edrax方案[12]：主要提出两个示例。一种是基于UTXO的比特币的货币类型，另一种是基于账户的以太坊的货币类型。仍然基于UTXO模型介绍比特币。作者主要使用稀疏Merkle树的技术来实现它，其中每个UTXO都采用[键，值]的形式。主要原理可以概括如下：整个树中都有最新的证明，用过的TXO(交易输出)在树中用null表示。当UTXO处于事务流通中时，可以将此事务添加到最新事务的右侧，然后计算和更新最新证明。可以理解为以这种方式，最右边的交易证明是最新证明，可用于更新或验证。

MiniChain方案[13]：使用STXO(已花费的交易输出)代替UTXO，从另一个角度看问题，将用过的TXO放在一个集合中以形成STXO承诺。作者主要提出了两种方案：一种是MiniChain +同时包含STXO和TXO承诺，另一种是仅STXO承诺的MiniChain-方案。另一方面，作者还提出了STXO缓存机制，该机制可有效减少状态更改引起的重新计算量。 STXO承诺使用RSA累加器技术将大量STXO映射到质数，然后形成一个简短的承诺过程，并且没有删除操作的计算量。TXO的承诺主要是使用MMR技术进行构造。与Boneh的工作相比，作者将累加器更新的复杂性从O(m2)降低到O(m)，其中m是区块中的事务数。

Ethanos方案[14]：主要讨论定期清理不活动账户节点的方案。Ethanos解决方案主要基于以太坊账户模型设计。如果账户节点状态更改，则运行恢复事务以恢复其状态。建议定期清理不活动的账户节点，而不下载旧的事务以节省启动成本。因此，该账户节点可以完成在其自己的设备上验证数据的任务。此解决方案可以将账户状态的大小减少一半。

1 系统细节

在DorChain中，小于18个月活跃的UTXO称为ATXO，大于18个月活跃的UTXO称为DTXO。首先，将区块链中的所有UTXO初始化为休眠状态(新开采的硬币设置为活跃状态)，存储在集合DTXO中，称为D。如果UTXO处于活跃状态，从集合D中删除UTXO存储在集合ATXO中，称为A。其次，使用MMR技术实例化A中的UTXO。同时构造休眠证明，使用变量DT来判断休眠时间。最后，D中的UTXO使用RSA累加器技术来实例化。该种设计方式的优势在于将休眠UTXO独立，仅利用MMR技术对活跃UTXO实例化，在引入最低区块头数据的同时，只需要提供存在性证明，即可达到验证币真伪的目的，降低计算开销，大大提高验证效率。接下来介绍DorChain的主要构成：DTXO承诺，AMR (ActiveMerkleRoot)，休眠证明的构造，验证，更新以及存储等方法。

1.1 在RSA累加器中实例化的DTXO承诺

将区块链中的所有UTXO初始化为休眠状态，即DTXO。首先使用HashToPrime[15-16]函数将DTXO集合中的元素映射到质数，然后使用RSA累加器[15]将集合DTXO哈希化为简洁且恒定的承诺(DTXO承诺)。在使用累加器计算承诺之前，利用哈希函数将集合中的DTXO映射到素数再计算，主要是为了避免冲突。基本结构如图1所示。

图1 DTXO承诺构造过程

算法2DUpdate：在检查点更新DTXO_C。如果参数DT为18个月，则需要将DTXO添加到DTXO集合中。如果在该时期内硬币从休眠状态变为活跃状态，则可以通过删除操作将其从集合D中删除。更新的DTXO_C记录在标记的DTXO上。然后可以使用算法1来更新DTXO_C。具体算法如图2所示。

1.2 在MMR中实例化的AMR

在该解决方案中，区块链中的所有UTXO被视为处于休眠状态(新开采的硬币除外)。因此，当UTXO即将变为活跃状态时，将此UTXO视为集合D中的删除操作。已删除的DTXO被标记为“活跃”，并且用户在UTXO上记录了最新删除后的DTXO_C，将删除的DTXO存储在代表活跃UTXO集合A中。在A集合中，主要使用MMR[17-18]技术来构造AMR。

笔者以m块到n块为例，详细描述其构造方案。Bm记录为区块m，此块中有t个ATXO，然后使用这t个ATXO作为叶子来构造MMR，最终可以得到root0(此时记录root0的高度)，并记录为Rm和存储在区块Bm中。区块m+1表示为Bm+1，该块中的q个ATXO继续将数据追加到前一个区块的山中的右边。当该区块的哈希值的高度与前一个区块root0记录的高度一致时，与root0一起进行哈希，然后后续的ATXO继续以仅追加的形式向后哈希。如果该区块的哈希值的高度与前一个块root0记录的高度不一致，则使用装袋方法输入哈希以获取root1，其记录为Rm+1。当它是最新的块时，AMR反映最新的ATXO的状态。AMR可用作ATXO的验证基础。

1.3 状态转换

在这一部分中，主要介绍UTXO在休眠状态和活跃状态之间切换的详细操作流程。

休眠到活跃状态：在DorChain中，无论是正常区块还是检查点，UTXO都可以随时从休眠状态更改为活跃状态。可以在提供UTXO的AMP的前提下随时执行Delete操作，将已删除的UTXO标记为“活跃”，最新的DTXO_C也记录在UTXO上并在整个网络上广播以进行验证。在检查点时，最新标记“活跃” UTXO携带的DTXO_C是删除操作的最新状态。对于这种状态的验证方法，在DorChain中设计了矿工，以比较基于标记的UTXO在Boneh方案中使用BatchDelete算法计算的结果，如果它们一致，则是正确的。

活跃到休眠状态：在DorChain中，仅在检查点对DT为18个月的UTXO执行加法操作。添加操作发生后，UTXO被标记为“休眠”状态，Boneh方案中的BatchAdd算法用于添加最新的“活跃”状态的 UTXO，且该UTXO携带最新的状态DTXO_C，此时更新的DTXO_C是最新状态。具体操作如图3所示。

1.4 休眠证明的创建、验证、更新以及存储

假设ATXO需要在一个时期内从活跃状态再次变为休眠状态，则单个UTXO的休眠证明构造参数为：休眠硬币(DTXO)，DTXO_C(DTXO承诺)，AMP(ActiveMerkleProof)和DT(休眠时间)，其中AMP是A集合中ATXO利用MMR构造的Merkle证明记录，而DT是记录硬币的休眠时间。AMP可以帮助证明硬币是真实的而不是伪造的，并且当DT达到18个月时，认为该硬币再次进入休眠状态，并且可以使用添加操作将其添加到下一个检查点设置的DTXO集合中。因此，休眠证明不仅可以证明硬币的存在，而且是可以确定UTXO再次进入休眠状态的条件。休眠证明的功能如图4所示。

图4 休眠证明的功能图

在详细介绍休眠证明之前，首先给出一个例子来解释AMP的构造方法。以下面的图5为例来构造ATXO 15的Merkle证明。

图5 AMP示例图(最底层数字表示叶子节点，依次往上数字为哈希结果在示例中有4个小的山峰，峰点分别为14、21、24、25)

具体创建方法如下：① 创建从叶子节点15到山21的Merkle证明，证明为{16，20}。② 袋装右边的山峰，右边只有24和25。结果为hash (25，24)并添加证明，证明为 {16，20，hash (25，24)}。③ 从左到右，将左侧的山峰插入到证明中。左边只有14个，因此证明为 {16，20，hash (25，24)，14}。因此，最终证明是ATXO 15的Merkle证明。

1.4.1 休眠证明的创建

函数1DormantWitCreate←(Xt，Dt+1，AMP，DT )：为了有效判断在检查点进入休眠状态的UTXO，以DT为18个月(通过调研数据发现在18个月的时候，休眠与活跃的比例接近1∶1)为准则构造了休眠证明。当DT为18个月时，AMP是活跃UTXO的Merkle证明路径，并且AMP还可以确保进入休眠状态的UTXO不会被伪造。所以休眠证明为DormantProof←(Xn，Dt+1，AMP，DT )。

1.4.2 休眠证明的验证

定义1DormantWitVerification：在最新区块中使用AMR进行验证。根据休眠证明中包含的参数AMP，如果重新计算AMR与最新的块一致，则验证成功；否则，验证将失败并且ATXO被认为是伪造的。

1.4.3 休眠证明的更新

定义2DormantWitUpdate：当UTXO从休眠状态变为活跃状态时，将休眠证明中的DT置零，并清除之前存储的AMP。当UTXO从活跃状态变为休眠状态时，DT开始计时直到DT为18个月，并且用户节点开始记录UTXO所在的路径AMP。如果在某个时期发生删除操作，则参数Dt也将实时更新为最新状态。

1.4.4 休眠证明的存储

笔者为每个用户设计存储自己的UTXO休眠证明，当用户想要使用休眠UTXO，需提供休眠证明说明该笔交易的真实性，并将自身存储的证明数据进行广播，以便其他用户节点使用该用户广播休眠证明中的AMP进行验证。如果一致，则验证成功；如果不一致，则验证失败。

2 分 析

本节将从多个参数中讨论该提议方案与其他相关方案的比较研究。详细信息显示在表1中。令n为UTXO大小，m为每个区块中的事务，L为区块链的长度，NA表示未有相关数据。

2.1 交易证明大小的分析

Minichain-方案包括存在性证明和未花费证明，因此总数为810字节。在Minichain+方案中，比Minichain-方案多一个TXO_C参数，并且存在性证明也多一个，因此它是1 450字节。在Boneh方案中，只有436个字节的未花费证明。在Edrax方案中，使用SparseMerkleTree的结构证明字节为371字节。Ethanos方案中使用MerklePatriciaTries结构证明字节为3 kB。在DorChain的解决方案中，仅需要AMP证明(只有320字节)，这是最小的同步证明长度，可有效节省节点的存储空间。

表1 DorChain与其他工作的比较

2.2 区块头大小的分析

在Minichain +解决方案中，区块头包括3部分：TXO_C，STXO_C和TMR。首先，该区块中的所有事务都使用Merkle树[15]技术来形成每个TMR；然后，使用MMR技术实例化每个TMR来形成峰值，并对所有峰值使用普通的Merkle树来获得TXO_C；最后，使用RSA累加器技术将每个区块中的STXO存储在区块头中，以形成STXO_C。在该解决方案中，检查点的参数为DTXO_C及AMR，普通块的参数仅为AMR，大小为32字节。DorChian基于UTXO，将UTXO分为两种状态，使用RSA累加器将休眠的UTXO实例化为DTXO_C，MMR技术将活跃的UTXO实例化为AMR并将其存储在区块头中。因此，与Minichain +解决方案相比，该方案少引入了一个参数TXO_C，即少引入了384个字节。如表1中所示，比较特定的数据大小。Flyclient中的每个区块记录Merkle Mountain Root和8个字节来存储难度，因此它是40字节，而Ethanos在每个块头中引入Bloom Fliter，因此增加了10 MB。

2.3 验证时间的分析

在Minichain方案中，作者首先将区块链中的所有STXO集映射到素数，然后计算STXO_C，将该值存储在区块头中。其次，作者使用区块链中的所有交易以普通Merkle树的形式在每个区块中形成一个TMR。MMR技术用于实例化为每个块形成的TMR，然后形成实例化的峰值。TXO_C以普通的Merkle树的形式形成，并存储在块头中。但是，每个块的更新需要4轮计算。在第1轮中，每个STXO都映射到素数以计算STXO_C。在第2轮中，计算当前块中的所有事务以获取TMR。在第3轮中，使用MMR技术基于TMR计算峰值。在第4轮中，使用普通的Merkle树技术计算峰值以获取TXO_C。因此，计算开销很高。证明验证(在1 000个事务验证的情况下)包括存在性证明(100 ms)和未花费证明(20 000 ms)。由于Minichain+比Minichain-方案具有更多的TMR包含证明，因此验证时间要长200 ms。在Boneh方案中，由于不仅需要验证成员资格证明，而且还需要验证非成员证明，因此验证时间大约是Minichain中非成员证明的验证时间的两倍(40 000 ms)。在Edrax方案中，验证时间为264 ms。在Ethanos方案中，选择了100个普通事务，并在检查点执行恢复事务。第5个检查点的恢复时间为150 ms，因此1 000个事务大约需要 1 500 ms。

验证程序使用NI-POE协议检查累加器是否正确更新。验证器的最大负担是映射要添加到每个块中的块头的元素，然后计算乘积。在DorChain的方案中，每个检查点仅使用BachAdd进行计算。另一方面，Boneh解决方案需要两轮NI-POE验证，而Minichain解决方案只需要一轮NI-POE验证。具体证明开销如表2所示。

在笔者提出的解决方案中，由于不需要验证成员资格和非成员资格证明，因此仅需要MMP(Merkle Mountain Proof)验证，而无须进行NI-POE验证。尽管从表1可以看出，DorChain方案中的证明大小和验证复杂性稍微增加了通信开销，但在该方案的验证过程中，用户只需要提供一个存在性证明，且方案中使用的MMR是树形结构，复杂度为对数级。在Windows系统中的VSCode平台上利用Python做实验，得到的存在性证明验证时间约为100 ms。验证时间大大减少了。

表2 DorChain方案与Minichain和Boneh的证明成本比较

2.4 其他方面的分析

在DorChain的方案中，使用RSA累加器实例化休眠的UTXO，而MMR实例化活动的UTXO。首先，区块链中的所有UTXO都被初始化为休眠状态，除了新挖矿产生的UTXO之外，因此该方案没有扫描休眠账户的开销。如果它从睡眠状态变为活跃状态，则使用删除算法进行操作；如果状态从活跃状态变为睡眠状态，则使用添加算法进行操作。另一方面，在状态更改过程中需要提供AMP，以证明UTXO是真实的而不是伪造的。因此，用户只需要存储其自己拥有币的AMP即可。在文献[11]的方案中，提出了Ethanos技术来定期清理不活动的账户。首先，需要建立一个空状态来扫描休眠账户。当闲置的帐户想要调用交易时，它需要提供一个Merkle证明，一个无效证明以及先前存储在其中的值。通过向每个区块引入布隆过滤器，它解决了由于过多的睡眠时间而导致的大量存储和验证问题。因此，每个区块增加了10 MB。具体信息如表3所示。

表3 与Ethanos方案的激活条件比较

2.5 特例

在区块链中，所有UTXO都是实时变化的。笔者通过对近一年内的所有数据进行统计分析，发现有22%的比特币在大于5年的时间里都没有移动过。此数据仅是当前的实时状态，以后可能会稍有变化。即使如此，笔者仍假定由于区块链中持有人的行为而没有UTXO休眠，但是由于早期阶段的密钥管理不当，私钥的丢失是真实的，并且这部分产生了不可移动的UTXO(根据调查结果)，丢失的硬币约占所有已发行硬币的21%，并且永久丢失了400万个比特币，这也适用于DorChain的方案。

3 结束语

在这项工作中，笔者提出了基于UTXO的休眠比特币DorChain的概念，以解决区块链中的验证问题。基本思想是将区块链中的所有UTXO划分为活动状态和休眠状态。使用RSA累加器实例化DTXO，并使用MMR实例化ATXO。笔者提出的方案只需要验证休眠证明，可以提高验证效率。同时，在该方案中，也可以很好地控制证明大小和区块头引入的数据。

未来，关于最新状态的验证，每次休眠的UTXO被删除时，最新的DTXO_C都会记录在UTXO中。该验证工作将移交给DorChain中的矿工通过BatchDel进行验证。为了使DorChain的方案长期稳定发展，可以建立相应的激励机制，以鼓励矿工进行验证并获得奖励。