一种随机并联的区块链安全共识算法
2018-11-09杜江天
◆杜江天
一种随机并联的区块链安全共识算法
◆杜江天
(武汉市第二中学 湖北 430010)
为防止区块链系统因ASIC芯片的引入而削弱其中心化特性,提升区块链共识算法的抗ASIC能力显得至关重要。本文提出的RPCA16共识算法引入了动态随机特性,且采用多散列算法并联,极大提升了算法的抗ASIC能力。与X16R算法相比,具备抗ASIC的效率高、安全性强等优势。
区块链;共识算法;抗ASIC;安全性
0 引言
在基于工作量证明机制(POW机制)的区块链系统中,其共识算法对于保障区块链的安全性和去中心化的特性具有重要作用。原始的区块链系统例如比特币系统使用计算机的CPU或GPU来实现共识算法的计算,从而使系统中算力得到平均分布,保障了去中心化的特性。但随着区块链系统的发展和流行,部分硬件厂商开发出专用的ASIC设备来进行挖矿计算,由于ASIC在计算能力和耗电量上具有巨大优势,从而占据了区块链系统的大部分算力,导致系统出现中心化的危险,从而带来“51%攻击”的隐患,严重影响系统安全和正常运行。因此,共识算法的抗ASIC能力成为当前研究的重要方向。
1 POW共识算法概述
在传统的比特币区块链计算模型中,其工作量证明机制使用的共识算法为SHA256散列算法,该共识算法保证了区块链的安全性和不可篡改性[1]。但是,这种保障依赖于一个前提条件,即单一节点无法控制全系统中超过51%的算力。但随着专用的进行SHA256散列计算的ASIC芯片的研发和应用,单台机器的算力相较于通用计算机得到了数十万倍的提升,导致算力越来越集中,几个大型矿池的机器联合起来就可能超过全网51%的算力,从而危及区块链系统的安全。为解决这一问题,后续的区块链开发者设计了各类共识算法,试图抵抗ASIC专用芯片带来的算力集中问题。例如以太坊区块链设计了ETHASH算法,该算法依赖于计算机的内存性能,且能有效提高区块链的事务处理能力[2]。达世区块链提出了X11算法,该算法使用11种散列算法进行串联,从而提高了制造专用ASIC芯片的成本。其后还发展出X13、X15等算法。门罗区块链提出了Cryptonight算法,该算法依赖于CPU中的特定指令集和高速缓存,从而使通用计算机的CPU具备了独特的计算优势。
上述算法虽然从指令集、内存依赖、多算法串联等不同角度增加了开发相应ASIC芯片的难度,但是都未能成功地阻止相应ASIC机器的出现。其原因在于这些算法虽然设置了一定障碍,但如果开发相应ASIC芯片的收益高于成本,设计者依然可以通过在芯片上堆积更多的逻辑电路和专用存储器来开发出相应的算法功能。因此,为增加算法的ASIC抗性,不能简单地只增加算法复杂度和资源消耗量,而是需要增加算法的随机性,从而使其难以固化为专用的ASIC电路。布莱克等人提出的X16R算法引入了随机性[3],但该算法仍然是一种串联算法,串联方式虽然增加了算法复杂度,但也降低了安全性。因为其中任一串联的散列算法被破解都会影响该算法的总体安全性,所以应采用并联方式来联接多个算法。
2 随机并联算法RPCA16
为提升区块链共识算法的抗ASIC能力,保障算法的安全性,本文提出一种随机并联共识算法RPCA16(Random Parallel Consensus Algorithm 16)。RPCA16算法的主要思路是构建散列算法池,然后随机从算法池中挑选算法进行并联计算,从而最终求得符合难度条件的本区块随机数(none值)。
为构建RPCA16随机算法,首先应构建散列算法池。散列算法池是一个包含16种散列算法的有序集合,其包含元素见表1,其中序号以16进制数字表示,所选择的散列算法包含了X15算法中的15种标准散列算法,另外加上SHA512算法。
表1 RPCA16算法池
基于以上算法池,构建RPCA16算法如下:
(1)从算法池的16个算法里面随机挑选4个算法:截取上一区块的区块头散列值的最后4位(16进制位),以该四位为序号依次从算法池中挑选4个算法,形成一个新的包含4种算法的有序集合。
例如,假设上一区块头散列值为:
0000000000000000008c9a29e053bc2970145ac3870210f18da00189b8e83e2c
以其最后四位3e2c为序号依次挑选算法池中对应的算法,得到jh、whirlpool、groestl、fugue,形成有序集合A,见表2。
表2 有序集合A
(2)数据预处理:对当前正在进行试算的区块头数据D进行处理,删掉none字段,得到数据D1。对数据D1使用SHA256和HEFTY1算法依次计算,得到散列值H1。即:
H1=HEFTY1(SHA256(D1))
(3)映射排序:截取H1的最后4位(16进制位),对该4位上的数字进行大小比较,得出其从小到大排序的序号(排序序号以0开始),把每一位上的数字替换为其排序序号,则映射得到一个新的数字序列L。随后根据L中数字的顺序依次从有序集合A中挑选算法,形成新的有序集合A1。
例如,假设H1的后4位是9d2a,则这4个数字从小到大进行排序,9排序序号为1,d排序序号为3,2排序序号为0,a排序序号为2,则9d2a中的每一位替换为排序序号后,得到1302。以1302中的每一位为序号,依次从有序集合A中挑选算法,得到新的有序集合A1,见表3。
表3 有序集合A1
(4)计算散列值:对当前区块的区块头数据D依次用有序集合A1中的4种散列算法进行计算,得到散列值h1、h2、h3、h4。即
h1=whirlpool(A1)
h2=fugue(h1)
h3=jh(h2)
h4=groestl(h3)
(5)混淆排列:分别取h1、h2、h3、h4各散列值前64位(2进制位),得到p1、p2、p3、p4。将每个数按32位(2进制位)长度平分为前后两段,得到p1a、p1b、p2a、p2b、p3a、p3b、p4a、p4b。将这八段数字按以下顺序混淆排列:p1a、p2a、p3a、p4a、p1b、p2b、p3b、p4b,得到最后的区块头散列值L。具体排列方法见图1。
图1 通过混淆排列方式得到区块头散列值L
(6)迭代:将L与当前区块链系统中的难度值N相比较,如果L RPCA16算法与传统的共识算法相比,通过增加随机性,使得ASIC芯片流水线无法满负荷运行,从而提升了其抵抗ASIC的性能。与同样具有随机性的算法X16R相比,具备以下优势: (1)RPCA16从16个标准散列算法中选4个进行并联计算,而X16R使用固定的16个算法。因此当ASIC芯片进行RPCA16算法计算时,将有75%的电路空置,从而大大降低了ASIC相对于CPU或GPU的优势。 (2)RPCA16对挑选出来的4个标准算法进行随机排序,从而进一步降低ASIC电路的流水线效率。同时由于是在区块头数据构造的过程中引入的动态随机,因此RPCA16对FPGA芯片也须有一定的抵抗能力。 (3)RPCA16在数据预处理过程中引入了HEFTY1散列算法,该算法难以通过ASIC来实现,进一步增强了抗ASIC的特性。 (4)X16R使用多算法串联,其中任一算法被破解都会影响系统安全。而RPCA16是并联类型的算法,只有所有的算法都被破解,才会影响最终算法的安全性,因此RPCA16算法抗哈希碰撞的能力强,其安全性较串联算法大大增强。 区块链技术具有高可用性和去中心化、去中介化等特性,目前在信息系统中的应用方兴未艾。但由于区块链的数据是分布式的,网络是开放式的,因此其安全性显得尤为重要。通过增强区块链共识算法的抗ASIC和抗哈希碰撞特性,可以大大增强区块链系统抵抗51%攻击和穷举攻击的能力,从而可以开发出高安全性的区块链公链体系。 [1]袁勇,王飞跃.区块链技术发展现状与展望[J].自动化学报,2016. [2]邵奇峰,金澈清等.区块链技术:架构及进展[J].计算机学报,2018. [3] Tron Black,Joel Weight.X16R ASIC Resistant by Design. https://ravencoin.org/wp-content/uploads/2018/03/X16R-Whitepaper.pdf.3 RPCA16算法抗ASIC性及安全性分析
4 结语