基于刚性内存的区块链协议改进

程穗，林宪正，俞能海

（1.中国科学技术大学网络空间安全学院，安徽 合肥 230001；2.中国科学院电磁空间信息重点实验室，安徽 合肥 230001）

1 引言

比特币是一种去中心化的电子加密“货币”[1]。作为一个账单系统，比特币不依赖于中央机构发行新币和维持交易，而是依赖分布式系统来维护交易列表，这个交易列表即区块链[2]。区块链是通过密码学方法生成的一串相关数据块。新区块始终链接到其前一个区块。因此，区块链是一种协议，当新区块被挖掘出来时，区块链的数据发生变化[3]。

在比特币系统中，所有用户都可以参与由工作量证明（PoW）协议维护的区块链[4-6]。PoW协议要求有效块的哈希值小于预定的阈值[7]。每个矿工通过调整哈希函数的输入值（在区块中称为nonce）进行有效区块的计算[8]。获取有效区块后，矿工将广播该区块到整个网络，其他矿工在验证该区块的有效性后停止当前高度的区块挖掘[9]。

在传统区块链中，除了创世区块外，每个区块的区块头均包含其父区块的哈希值。每个新区块的生成方式都是通过更改随机数，并不断计算其区块头的哈希值，直到其小于当前难度。因此，挖掘只是一个纯粹的计算过程。计算速度越快，挖掘出新区块的可能性越大。

普通的采矿设备经历了从PC到GPU和FPGA的多种变化，直到ASIC矿机出现。当前，比特币采矿市场已经被ASIC矿机所主导，并且无法通过使用其他采矿设备来营利[10]。ASIC矿机是致力于挖矿过程。但是，早期使用ASIC矿机存在一系列问题：

1)随着网络的计算能力持续迅速地提高，ASIC矿机芯片的寿命变得非常短（约6个月）；

2)投资ASIC采矿设备会增加成本（电力成本和冷却成本）；

3)由于行业的不成熟，采矿设备的延迟交付导致芯片被淘汰。

尽管使用ASIC矿机进行挖矿已经相当成熟，并且挖矿设备的寿命更长，但挖矿业已经从个人领域转移到了大型的专业挖矿中心。因此，挖矿行业对个体矿工非常不友好。此外，整个网络中的大部分计算能力集中在少数人手中，这不仅增加了资源浪费，而且增加了51%攻击的可能性。这与比特币[11]最初的设计目的背道而驰。

为了打破挖矿行业中ASIC矿机的垄断，已经有多种方法被提出，如具有刚性内存的函数。刚性内存函数是一类很难并行处理的哈希函数。在此功能中，完成给定计算问题所需的时间主要取决于从内存中读取数据的时间，这可以减少总时间成本上的计算能力部分。因此，通过增加从内存中读取数据的次数，I/O所占的时间将控制新区块挖掘的时间，从而达到抵抗ASIC矿机的目的。

现在已经有与刚性内存相关的算法被提出，如Scrypt和Primecoin[12]。这些算法可以分为两个步骤：第一步是从一个随机数种子生成一个伪随机数数组，该数组存储在主存储器中；第二步是计算新区块的哈希值，哈希函数的输入是相关区块区块头的串联，这些区块是从伪随机数数组中随机选择的。

由于必须读取几个伪随机数，数据读取将影响哈希计算的时间。然而，在Scrypt函数中，每个伪随机数都是通过前一个伪随机数计算出来的，ASIC矿工可以通过仅存储具有奇数索引[13]的伪随机数来将主存储器中使用的空间减少一半。如果哈希函数需要带有偶数索引的伪随机数，则可以从前一个随机数计算出该值。因此，对于这些刚性内存函数，计算的时间和内存属性是可以进行调节的。时间和内存的折中可以减小哈希计算中数据读取的影响，使ASIC矿机和通用CPU之间的性能差距仍然很大。

为了解决此问题，需要一种新的哈希函数，该函数不具有时间内存折中的功能。也就是说，如果存储器的大小小于阈值，则挖矿性能将显著下降，并且没有有效的方法来设计一种具有时间/内存权衡的方法。此外，希望协议中的数据读取时间是可控的，因此，本文提出一种新的区块链协议，在该协议中，每个区块除了与其父区块相关联之外，还与之前的多个区块相关联。该协议决定了主导挖矿时间的是I/O，而不是计算速率。

2 基于刚性内存的协议模型

2.1 协议模型

本节将详细描述所提出的协议。该协议具有两个参数（n,m），其中，n表示在区块挖掘过程中可能被使用的区块的数量，m表示在内存中选择的哈希值的数量。为了提高协议的性能，应将这n个哈希值存储在缓存或内存中，否则处理器必须花费大量时间在区块挖掘过程中访问这些值。在提出的协议中，区块链中最后n个区块的哈希值依次表示为{Ni|i=0,…,n-1}，其中N0表示最新区块。n个哈希值中的m个（包含N0）将用于新区块的哈希计算。给定随机数的值，以下是选择m个哈希值的步骤。

1)令t0=nonce和i=1，计算t=hash0(t0)。

2)令ti=Ni，计算t=hash0(ti)。如果i=m，输出(t0,t1,…,tm)，否则i=i+1并重复步骤2)。

可以看到，hash0的共域是{0,…,n-1}，那么有 hash0(x)=x(modn)。哈希值可以通过R=hash(t0||t1,Y||…||tm,Y||N0)进行计算。如果哈希值R满足目标难度，则挖掘过程结束，否则选择新的nonce并重复该过程以找出新的m个哈希值。在实现中，这n个哈希值存储在循环队列中，如图1所示，避免数据移动。

图1 环队列存储方式Figure 1 Circular Queue

2.2 协议分析

2.2.1 时间/内存属性权衡

作为内存依赖型的PoW算法，Scrypt算法包含两个步骤。第一步，依次生成n个伪随机数，其中每个随机数都是由其前一个随机数计算而来。第二步，通过使用伪随机顺序选择的多个伪随机数来生成哈希值。通过在存储器中存储偶数位索引的个伪随机数，可以进行时间内存的权衡。由于在哈希运算中，ASIC矿机的计算速率比通用CPU快得多，ASIC矿机可以牺牲部分计算能力来减少所需的内存。因此，这种刚性内存算法无法达到较好的抗ASIC效果。

在本文提出的协议中，每个哈希值不能直接通过其前一个哈希值计算出来，因此该协议不具有时间/内存权衡的属性，这个属性被称为Memory-hard。因此，如果n个哈希值不能完全存储在内存中，那么应当存储在辅助存储设备（如硬盘）中。当哈希计算过程需要使用对应的哈希值时，处理器必须访问硬盘读取数据，这将减慢整个挖掘速度。

2.2.2 加载时间分析

在本文提出的协议中，对内存是有限制的，因此当内存大小小于n时，区块的挖掘速度将显著降低。s表示存储在内存中的哈希值的数量，当s

当s≥n时，哈希计算所需数据的平均读取时间为mt0。当s＜n时，哈希计算所需数据的平均读取时间为。通常，t1是t0的数万倍，因此，合适的n值可以限制ASIC矿机在挖矿哈希计算过程中的优势。

3 安全性分析

本节将通过对区块链交易进行篡改攻击来分析区块链的安全性。在每个区块的区块头，令Y表示区块中交易的哈希值，令X表示区块的其余部分。本文将从单个区块的篡改攻击和连续两个区块的篡改攻击来分析协议的安全性。

（1）单个区块篡改攻击

首先分析对区块链中一个区块进行篡改的难度。对于如图2所示的传统区块链，区块A是区块B的父区块。攻击者篡改了区块A中的交易，这将改变区块A中Y的值。区块A′表示被篡改后的区块，Y′表示篡改后交易的哈希值。如果修改了区块A中的交易，则区块A′必须满足

假设找到合适的A′Y′满足式(1)的概率为P。

图2 对传统区块链的攻击Figure 2 Attackon traditional blockchain

对于本文提出的协议，如图3所示，每个区块都与其父区块以外的m个区块相关联，当区块N0被篡改时，应满足

其中，每个di由2.1节中的算法计算。也就是说，对于i=0,…,m，有d1=hash0(Anonce)和di=hash0(Ndi-1)。假设找到合适的N0,Y′满足式(2)的概率表示为q。在最坏的情况下，如果di≠0，则对于i=0,…,m，在式(1)和式(2)中更改的长度是相同的。由生日攻击[14]可知，有q=p。

图3 新的区块链结构Figure 3 New blockchain structure

攻击者将用于区块A的哈希计算中使用到的区块N0篡改为。此外，N0用于其他t个表示为G1,G2,…,Gt的区块的哈希计算中。令Ui表示用于区块iG哈希计算中使用的m+1个哈希值，令U0表示用于区块A哈希计算中使用的m+1个哈希值的集合。对于i=0,…,t，hash (N0)∈Ui，有

其中，每个ui,j∈Ui，j=0,…,m。值得注意的是，对于i=0,…,t,ui,k=hash(N0,Y)∈Ui和ui′,k=hash(N0,Y′)表示替换后的哈希值。

这t+1个方程是独立的。在最坏的情况下，只有ui,k=hash(N0)∈Ui，因此概率为qt+1=pt+1≤p。这表明，当t≥1时，所提出的协议比传统的区块链协议更安全。

（2）连续两个区块篡改攻击

如图4所示，如果将区块A篡改为A′，并且将区块B篡改为，则在传统区块链协议中，当区块A被篡改为区块A′时，成功的攻击必须满足

图4 对新区块链的相邻篡改攻击Figure 4 Adjacent tamper attack on new blockchain

当区块B被篡改为区块B′时，成功的攻击必须满足

假设满足式(5)的概率表示为p1。

在本文提出的协议中，区块B和区块C都与m+1个之前的区块相关联。对于i=0,…,m，令表示区块B哈希计算过程中使用的m+1个哈希值组成的向量，令表示区块C哈希计算过程中使用的m+1个哈希值组成的向量。值得注意的是，有B0=hash(A)和C0=hash(B)。那么必须满足

如果区块B的哈希计算过程使用了区块A的哈希值，则将其他ta个区块定义为GA1,GA2,…,GAta。同样地，如果区块C的哈希计算过程使用了区块B的哈希值，则将其他tb个区块定义为GB1,GB2,…,。

对于i=1,2,…,ta，令UAi表示参与区块GAi的哈希计算的m+1个哈希值组成的向量，令UBi表示参与区块GBi的哈希计算的m+1个哈希值组成的向量。特别地，UA0对应区块B哈希计算的m+1个哈希值向量，UB0对应区块C哈希计算的m+1个哈希值向量。对于i=0,1,…,ta，有hash(A)∈UAi。对于i=0,1,…,tb，有hash(B)∈UBi，那么可以得到

其中，当j=0,…,m时，有。式(8)中的，并且当i=0,…,t时，将定义为篡改后的哈希值。同样地，必须满足

其中，当j=0,…,m时，有ubi,j∈UBi。式(9)中的ubi,k=hash(BY)∈UBi，并且当i=0,…,t时，将ub′i,k=hash(BY′)定义为篡改后的哈希值。

可以看出，这ta+1和tb+1个方程都是独立的。因此，当ta≥0时，将区块A篡改为区块A′并满足式(8)的概率为；当t≥0时，将b区块B篡改为区块B′并满足式(9)的概率为。因此，攻击成功的概率为P=P1P2=。可以看出，P比在传统的区块链协议中攻击成功的概率低。

4 协议改进

为了提高协议实现的效率与稳固该协议的刚性属性，本节从相关联的区块数m的确定与新区块计算使用的哈希函数的输入两方面进行分析。

（1）相关联的区块数的确定

由2.1节中的协议步骤可知，本文提出的协议在新区块的挖掘过程中，每选择一个随机值nonce，就需要重新从内存中读取m个区块的哈希值。令x表示比特币网络中计算一个新区块平均所需的计算次数，t2表示ASIC矿机进行一次哈希计算所需的时间，t3表示普通CPU进行一次哈希计算所需的时间。由2.2.2节可知，当s≥n时，ASIC矿机进行一轮挖矿计算所需的时间为t2+mt0，CPU矿机进行一轮挖矿计算所需的时间为t3+mt0；当s＜n时，ASIC矿机进行一轮挖矿计算所需的时间为，CPU矿机进行一轮挖矿计算所需的时间为t3+mt0。可以看出，哈希计算的时间在ASIC矿机和CPU矿机进行一轮挖矿计算的时间中所占的比例可忽略不计。因此，为了达到抗ASIC矿机的效果，应增大n的取值，而m的取值大小在抗ASIC方面没有突出的作用。增大m的值仅仅增强了区块链稳定性，但同时导致节点在进行区块验证时面临更大的压力，新区块的验证过程也变得更加烦琐。因此，为了减轻验证节点的负担，取m=1。

（2）哈希函数的输入

在传统区块链的区块挖掘过程中，新区块仅仅与其前一个区块相关联，因此其哈希计算过程中，哈希函数的输入仅包含其前一个区块的哈希值。在本文提出的协议中，新区块除了与其前一个区块相关，还与m个之前的区块相关。假设m=2，令T0表示当前区块，T1、T2和T3表示T0的父区块。T1为T0的前一个区块，T2和T3为随机选择的父区块，T3的区块高度小于T2。按照区块的形成时间，区块T3和T2比区块T1更早出现。因此，在对区块T0进行哈希计算的过程中，需要用到其3个父区块的哈希值 hash。然而，当按照区块高度由低到高对区块哈希值进行串联作为哈希函数的输入时，ASIC矿机可能不需要对所有n个区块进行存储，这种情况是由某些哈希函数是线性输入导致的。因此，顺序串联可能导致本协议不是完全刚性的，这与本文提出的完全刚性的属性不符，对哈希函数输入的串联方式进行了更改。本文将新区块的前一个区块的哈希值放在首位，然后按照区块高度由低到高进行串联。对于T1、T2和T3，计算新区块T0时使用的哈希函数输入的串联方式为hash。

5 结束语

本文提出了一种在区块链上的完全刚性内存的协议。该协议是一种无记忆功能，没有时间/内存折中的协议。因此，内存中必须存储区块链的最后n个区块的哈希值。然后，随机选择n个哈希值中的m个和最新的哈希值串联来计算新区块的哈希值。因此，每个区块不仅与其父区块相关联，而且与n个先前的区块中的m个相关联。分析表明，本文提出的协议是一种完全刚性的存储协议，并且证明了所提出协议的安全性优于常规区块链协议。