APP下载

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

2022-05-28潘森杉徐腊梅

西安电子科技大学学报 2022年2期
关键词:检查点字节实例

潘森杉,徐腊梅

(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的方案长期稳定发展,可以建立相应的激励机制,以鼓励矿工进行验证并获得奖励。

猜你喜欢

检查点字节实例
No.11 字节跳动计划自研芯片:仅供内部使用
Spark效用感知的检查点缓存并行清理策略①
No.8 字节跳动将推出独立出口电商APP
SQL Server数据库备份与恢复的研究与实践
完形填空Ⅱ
完形填空Ⅰ
人类进入“泽它时代”