基于ECDLP 的工作量证明方案设计*

刘志杰, 张方国, 田海博

1. 中山大学 数据科学与计算机学院, 广州510006

2. 广东省信息安全技术重点实验室, 广州510006

1 引言

由于Koblitz[1]和Miller[2]开创性的工作, 使得已被数学家研究了一百多年的椭圆曲线在密码领域中发挥重要的作用. 椭圆曲线密码体制(ECC) 的数学基础是利用椭圆曲线上的点构成的Abelian 加法群中的离散对数的计算困难性. 换而言之, ECC 的安全性依赖于椭圆曲线离散对数问题(ECDLP) 的困难性. 在过去的几十年里, ECC 已经成为一种标准化的工具[3], 应用于各种密码协议和系统. 在求解ECDLP 的算法中, 大家公认的最有效的算法是基于生日悖论的Pollard rho 算法[4], 其实质是在群元素中寻找匹配或者碰撞, 希望能从这种碰撞中得到碰撞点之间的联系进而来求解ECDLP. 后来的密码学家在此基础上提出了各种对Pollard rho 算法的改进和优化方案. Van Oorschot 和Viener[5]等人利用可区分点碰撞检测的办法对Pollard rho 算法进行改进, 证明了该算法在群元素中寻找碰撞的所需要的时间呈线性减少. 同时, 改进的Pollard rho 算法可以利用传统的分布式计算框架进行并行计算, 每个并行节点将计算好的可区分点存入同一个数据库中, 一旦某一个并行节点发现自己存储的可区分点已经在数据库中, 那么碰撞就找了, 最后计算出ECDLP 的最终求解. 目前为止, ECDLP 的求解最高记录是Wenger 和Wolfger[6]等人在2014 年给出的113 bits.

比特币[7]作为区块链技术的一个典型代表, 其共识算法是工作量证明, 矿工们主要是执行哈希算法完成这一项工作. 事实上, 许多分布式计算问题或困难问题, 都可以作为工作量证明的困难问题. 在区块链中, 每个矿工打包区块的计算资源可以视为是一种分布式计算的资源. 例如Primecoin[8]采用数论问题设计一个新的工作量证明方案, 而Chatterjee[9]则是利用NP 完全问题设计了一个新的工作量证明方案. 此外, 在区块链中, 矿工打包区块需要消耗大量的计算资源, 这个过程中造成资源的浪费的问题一直受到人们的诟病[10], 因而将分布式计算问题或困难问题引入到挖矿的过程中, 可以使得挖矿所消耗的能源变的更有意义.

Marcella 和Nadia[11]等人提出了基于离散对数问题(DLP) 的工作量证明方案, 但是该方案中没有给出一个从初始点到满足挑战难度的可区分点的快速有效的验证方法. 本文基于一种改进的并行的Pollard rho 算法, 提出了基于ECDLP 的工作量证明方案. 特别地, 本文提出了一种思路, 解决了一个区块中从初始点到可区分点的有效验证问题. 另一方面, Certicom[12]公司为ECDLP 挑战者设立了丰厚的奖金. 因此, 可以借助区块链中天然的激励机制, 为每位参与挖矿的矿工给予报酬, 从而促使更多的节点参与到挖矿的过程中来. 同时, 可以促进ECDLP 求解算法的软件或硬件实现的优化, 更好的推动ECDLP求解算法的研究与发展.

2 预备知识

2.1 ECC

一般地, 椭圆曲线是指在有限域Fq或F2m上的椭圆曲线. Fq是一个特征q ̸=2,3 的有限域, 椭圆曲线E 定义为满足方程:y2=x3+ax+b, a,b ∈Fq且4a3+27b2̸=0 的点(x,y)∈Fq×Fq和特殊点(无穷远点) 所组成的集合.

定义在有限域F2m上的非超奇异椭圆曲线E 为满足方程:y2+xy = x3+ax2+b, a,b ∈F2m且b ̸=0 的点(x,y)∈F2m×F2m和特殊点(无穷远点) 所组成的集合.

2.2 ECDLP

给定椭圆曲线E 上阶为素数n 的点P, < G > 为P 生成的一个素数阶群. 对于任意Q ∈G, 找一个整数k, 0 ≤k ≤n, 使得Q=kP, 就是椭圆曲线离散对数问题.

2.3 ECCp-131

ECCp-131 是Certicom[12]公司设立的挑战之一, 目前还没有被攻破. 该挑战是定义在有限域Fq上的椭圆曲线, 其中

同时, 给定的素数阶为

对于该挑战ECCp-131, 点P 和点Q 的值分别是

2.4 Pollard rho 算法

随机选取2r 个整数

并且计算r 个元素

定义一个映射函数v, 使得G 中的元素均匀地映射到{1,··· ,r} 中, 即

定义随机游走迭代函数F :G →G 为

随机选取a0,b0∈{0,1,··· ,n −1}, 令Y0=a0P +b0Q 作为起始点. 每一次迭代中ai,bi的表达式如下

一旦发生碰撞, 即Yi=Yj(i ̸=j), 可以得到如下表达式

如果gcd(bi−bj,n)=1 则k =(aj−ai)(bi−bj)−1mod n.

2.5 可区分点碰撞检测

令D 为G 的一个子集合, 给定一个约束条件d, D 中所有的元素都满足如下要求:

(1) 对于任意一个可区分点Yi∈D, 满足Yi的x 轴坐标值小于等于d.

(2) 对于任意一个可区分点Yi∈D, 满足Yi=aiP +biQ, ai,bi∈{0,1,··· ,n −1}.

(3) 一旦发生碰撞, 即Yi=Yj(i ̸=j), 满足aiP +biQ=ajP +bjQ, gcd(bi−bj,n) =1.

2.6 工作量证明

工作量证明[13]早期是为了防止垃圾邮件和Dos 攻击而被提出的, 随后比特币采用工作量证明作为共识机制, 使得比特币在开放的, 去中心的, 互补信任的节点之间可以达成共识. 工作量证明由三个函数组成[14](Gen, Solve, Verify):

(1) c ←Gen(1n): 产生挑战c 的概率性算法.

(2) s ←Solve(c): 解决挑战c ←Gen(1n) 得到解s 的算法.

(3) { 接受, 拒绝}←Verify(c,s): 验证挑战c ←Gen(1n), 是否被s ←Solve(c) 解决的算法.且满足以下几点[14]:

(1) 效率性:

(a) Gen(1n) 的运算时间复杂度是O(n).

(b) 对于任意c ←Gen(1n), Solve(c) 的运算时间复杂度是O(t(n)), 其中t 是一个指数函数.

(c) 对于任意c ←Gen(1n) 和s ←Solve(c), Verify(c,s) 的运算时间复杂度是O(n).

(2) 完备性:

对于任意c ←Gen(1n) 和s ←Solve(c), Pr [Verify(c,s) = 接受] = 1.

(3) 难解性:

l 为任意的多项式, ϵ 为任意常量且 ϵ > 0, 当给定任意多项式时间 l(n) 的挑战{ci←Gen(1n)}i∈l(n), Solve∗l的运算时间复杂度为l(n)t(n)1−ϵ, 有Pr[∀i Verify(ci,si) = 接受 | (s1,··· ,sl(n))←Solve∗l(c1,··· ,cl(n))] <δ(n), 其中δ(n) 是一个可忽略的概率值.

在比特币中, Gen 函数的输出值是前一个区块的哈希值. Solve 是由一个难度值d 控制的函数, 矿工需要找到一个随机值nonce, 使得SHA-256(c,nonce) < 2256−d. SHA-256 可以视为是一个随机数函数,因此矿工寻找一个满足要求的随机值nonce 的概率是2−d. 换言之, Solve 的运算时间复杂度是O(2d).Verify 函数是验证(c,nonce) 是否满足SHA-256(c,nonce) <2256−d, 如果满足该条件就接受, 否则拒绝.

2.7 激励机制

在区块链中, 当每个新区块产生后, 区块链系统都会奖励找到该区块的矿工. 在挖矿的过程中是需要消耗计算资源和电力的, 因此奖励也可以作为交易费用来资助矿工. 同时, 这种激励可能有助于鼓励节点保持诚实. 另一方面, 每个新区块的奖励也不是固定的, 每开采210 000 个区块, 大约需要4 年的时间, 货币发行速率将降低50%. 以比特币为例, 从2008 年开始计算, 在其运行的第一个四年中, 产生区块的矿工将获得50 个比特币. 到了2012 年后, 产生区块的矿工将获得25 个比特币. 依次类推, 产生区块的矿工将获得12.5 个比特币.

3 方案模型

3.1 用户关系模型

本文方案共有3 个参与方, 分别为ECDLP 发布者, 矿工和验证者. 其中ECDLP 发布者可以为任何一个需要发布ECDLP 挑战的区块链用户, 该用户只需要发布一个挑战申明的交易. 挑战申明交易包含了ECDLP 的初始点P, Q, 可区分点单价以及一系列固定参数(mi,ni,Mi, i=1,··· ,r) 等信息, 所有的矿工会将挑战申明的交易信息记录到一张挑战申明表中. 一旦当前的ECDLP 的问题被解决了, 他们会选择下一个ECDLP 挑战重新开始计算. 矿工的主要责任是执行随机游走迭代函数F, 计算符合挑战难度要求的可区分点, 并将该可区分点的x 轴坐标值打包放到区块头中, 然后向全网广播. 验证者的主要责任是验证新区块头中可区分点是否满足要求, 如果满足则接受该新区块, 否则拒绝. 同时, 验证者会验证所有的可区分点在区块链上是否存在碰撞, 一旦发现了碰撞, 会发布一个碰撞的交易.

3.2 区块头结构

矿工产生满足挑战难度的可区分点之后需要将其打包到新区块的区块头中, 因此本文重新设计了区块链中的区块头结构, 如图1所示.

图1 区块链头部结构Figure 1 Head structure of blockchain

(1) VERSION: 记录区块版本号.

(2) PREVIOUS: 记录前一个区块的哈希值.

(3) NONCE: 记录随机数.

(4) TARGET: 记录该区块工作量证明算法的难度阈值.

(5) TIME: 记录时间戳.

(6) POINT: 记录符合挑战难度目标的可区分点x 轴坐标值.

(7) LISTS: 记录存储特殊点的游走路径.

(8) MERKLE ROOT: 记录Merkle 树根节点的哈希值.

上述提及的区块头部中的PREVIOUS 字段用于作为一个挑战c, 并且和NONCE 字段值一起计算出初始点Y0. POINT 字段只需要存储可区分点的x 轴坐标值, 因为在碰撞检测的过程中, 只需要检测两个可区分点是否有相同的x 轴坐标值即可, 同时也减少了头部占用的存储空间. LISTS 字段是一个r 维向量, 由r 个整数组成(s1,··· ,sr), 依次代表着从M1到Mr的累加次数, 区块链中的验证节点可以通过LISTS 字段快速验证特殊点产生所需要的工作量, 为每个新生区块提供工作量证明.

3.3 挑战难度关系模型

为了使得工作量证明中挑战难度容易受控制, 本文方案规定满足当前挑战难度的可区分点的x 轴坐标值小于等于难度阈值TARGET. 难度阈值是矿工打包区块速率的重要参考指标, 它决定了矿工大约需要经过多少次计算才能产生一个合法的区块. 在比特币系统中, 每个区块生成的时间大约为10 分钟. 若要维持新区块的产生速率约为10 分钟一个区块, 难度阈值必须根据全网算力的变化进行调整. 难度阈值的调整是在每个完整节点中独立自动发生的, 每当生成了2016 个区块, 所有的矿工都会按一个规定好的公式进行自动难度调整. 这个公式是由产生最新2016 个区块所花费的时长与期望时长(20 160 分钟) 比较得出的, 具体表达式如下:

其中actual_time 为产生最新2016 个区块所花费的时长, expected_time 为期望时长. 若在区块链系统初始化时, 我们以Certicom[12]公司设立的ECCp-131 作为默认挑战, 同时维持新区块的产生速率约为10 分钟生产一个区块, TARGET 值的初始值应为77766331555005660491798357300000.

3.4 工作量验证模型

虽然验证者需要验证满足挑战难度要求的可区分点YD的x 轴坐标值在二进制编码形式下, 由最高位开始依次d 个二进制位都为零, 但是验证者却无法确定YD是由一个合法的初始点Y0开始计算得到的.于是一个不诚实的矿工可以预先计算好一个满足挑战难度的可区分点, 然后将该点打包到区块头部并发布到网络中去. 为了避免这样的情况发生, 验证者需要记录下矿工提供从Y0到YD的游走路径(s1,··· ,sr),然后验证者沿着该路径一步一步计算到YD, 判断YD是否付出了足够的工作量. 但是这种验证方法并不是有效的, 不满足工作量证明中“难于计算, 易于验证” 的要求.

3.5 激励模型

本方案中的激励方案共分为两个部分, 第一部分是矿工成功打包区块后所获得的奖励, 第二部分是矿工成功计算出已发布问题的可区分点后所获得的奖励. 在区块链中, 为了鼓励节点保持诚实, 当每个新区块的产生后, 区块链系统都会奖励给打包该区块的矿工. 对于第一部分, 本文采用与比特币系统相同的激励方案, 每开采210 000 个区块, 大约需要4 年的时间, 货币发行速率将降低50%, 并且在第一个四年中,产生区块的矿工将获得50 个链上流通的货币.

对于第二部分, 当区块链系统中有已发布的ECDLP 挑战后, 矿工成功计算出符合要求的可区分点后会获得相应的第二部分的奖励, 该奖励金额由ECDLP 发布者决定. ECDLP 发布者在发布挑战交易时,需要指定每个可区分点的金额, 当矿工成功计算出符合要求的可区分点时, 该矿工会获得该金额. 如果当前区块链系统中没有任何节点发布ECDLP 挑战, 矿工将计算默认的ECDLP 挑战, 但是当矿工成功计算出符合要求的可区分点时, 矿工获得第二部分的奖励的金额为0.

4 具体设计

本文中的方案设计主要包括挑战申明交易发布, 矿工挖矿, 区块验证, 碰撞检测和EDCLP 求解五个模块. 本小节将会更为详细的阐述每个模块的具体实现或具体使用的参数.

4.1 挑战申明交易发布

Teske[15]通过大量的实验表明, 在基于adding walks 的Pollard rho 算法中群G 的划分大小为30 是最适合的选择. Teske 的实验结果显示, 当r = 30 时, 找到碰撞所需要计算量是最小的. 因此在ECDLP 发布者需要在挑战申明交易中输入自身的ECDLP 挑战之后, 额外要输入预计算好的30 组固定参数(mi,ni,Mi), i=1,··· ,30, 具体步骤如下:

(1) 随机选取整数α ∈{0,1,··· ,n −1}, 令Q′=αQ 且P ̸=Q′.

(2) 随机选取60 个整数mi,ni∈{0,1,··· ,n −1}, i=1,··· ,30.

(3) 计算Mi=miP +niQ′.

(4) 向挑战申明交易输入ECDLP 参数(Mi,P,Q′) 和单个可区分点金额.

(5) 发布挑战申明交易.

(6) 矿工接收到该交易, 并记录到挑战申明表中.

由于区块链上的信息都是公开透明的, 在发生可区分点碰撞时且网络时延比较大的情况下, 恶意的用户可能可以预先一步将解决ECDLP 的成果占为己有, 恶意用户可以通过碰撞点计算出ECDLP 的挑战结果, 然后去冒领完成该挑战的奖励. 因此为了避免这样的情况发生, ECDLP 发布者在公布自身的ECDLP 挑战之前需要对Q 做盲化处理, 这样即便找到了碰撞, 也只有ECDLP 发布者能获得真正的挑战成果. 当找到碰撞时, ECDLP 发布者进行一次去盲的操作便可以计算出最终的解. 同时, 所有挑战申明表中第一条都是默认的ECDLP 挑战参数, 以保证开始阶段矿工能正常的挖矿. 需要注意的是, 每个矿工维护的挑战申明表中都有一个相同默认挑战, 当矿工收到新的挑战申明时, 会向表中插入该新的挑战申明,并记录相应的时间戳.

4.2 矿工挖矿

矿工主要是计算出满足挑战难度的可区分点, 将计算得到的可区分点打包放入区块头中, 并发布到网络中去. 此外, 区块链上的信息都是公开透明的, 为了避免恶意用户预先计算好满足要的可区分点, 方案规定一个合法的初始点Y0必须从最新区块的区块头中计算获得. 具体步骤如图2 所示.

图2 矿工挖矿流程图Figure 2 Mining procedure process

(1) 选择挑战申明表第一个未被求解的ECDLP 挑战参数. 当申明表中没有未被求解的ECDLP 挑战, 矿工会选择申明表中的默认挑战参数进行挖矿.

(2) 获取当前最新区块的哈希值作为挑战c 和选取随机数n, 令(a0,b0)=Hash(c||n).

(3) 令i=0, 且s1=s2=···=s30=0.

(4) 计算Y0=a0P +b0Q′.

(5) 若Y0满足当前难度下的可区分点要求, 则进入第(7) 步, 否则进入下一步.

(6) 迭代计算: Yi+1=F(Yi)=Yi+Mv(Yi), sv(Yi)=sv(Yi)+1, i=i+1.

(7) 若Yi+1满足当前挑战难度下的可区分点要求, 则进入下一步, 否则返回到第(6) 步.

(8) 将游走轨迹(s1,s2,··· ,s30) 写入LISTS 字段, 随机数n 写入NONCE 字段, 同时打包可区分点Yi+1的x 轴坐标值到区块头中, 打包区块并发布到全网中.

4.3 区块验证

区块链验证节点需要验证矿工发布的区块内容是否满足要求, 具体步骤如图3 所示:

(1) 计算每个Mi,i = 1,··· ,30 的预计算标量乘查找表, 并存储到本地(该步骤为预计算步骤, 对于每一个ECDLP 挑战, 该步骤只需要执行一次).

(2) 验证POINT 字段中的数值是否满足挑战难度值要求, 若满足则进行下一步, 否则直接抛弃, 验证阶段结束.

(3) 获取当前最新一块区块的哈希值, 并验证该值是否与PREVIOUS 字段值相等, 若相等则进行下一步, 否则直接抛弃, 验证阶段结束.

(4) 提取PREVIOUS 字段值作为挑战c 和NONCE 字段值n, 计算Hash(c||n)=(a0,b0).

(5) 计算Y0=a0P +b0Q′.

(6) 通过(s1,s2,··· ,s30) 查表并计算Y′=Y0+s1M1+s2M2+···+s30M30.

(7) 判断Y′的x 轴坐标值是否与POINT 字段中的值相等, 若相等则进行下一步, 否则直接抛弃, 验证阶段结束.

(8) 验证POINT 字段中的数值是否满足挑战难度值的要求, 若满足则接受该区块, 验证阶段结束, 否则直接抛弃, 验证阶段结束.

4.4 碰撞检测

验证者在区块验证结束之后需要将矿工计算的可区分点存储到本地数据库中, 其目的是用于碰撞检测. 如果当前计算的是默认ECDLP 挑战参数, 验证者则不进行碰撞检测, 否则验证者需要对该可区分点做一些预处理, 把处理后的信息存储到本地数据库中. 一旦发现碰撞, 验证者就会发布一个碰撞交易, 通知全网用户该ECDLP 挑战已被求解. 矿工会选择挑战申明表中下一个未被求解的挑战继续挖矿. 需要注意的是, 碰撞检测预处理操作是紧接着在区块验证完成以后进行的, 具体步骤如图4 所示.

(1) 检测是否为默认的ECDLP 挑战, 如果是则直接抛弃, 检测结束, 否则进行下一步.

(2) 计算a′=a0+s1m1+s2m2+···+s30m30(modn).

(3) 计算b′=b0+s1n1+s2n2+···+s30n30(modn).

(4) 计算Y′′=a′P +b′Q′.

(5) 判断Y′′是否与Y′相等, 若相等则进行下一步, 否则直接抛弃, 检测结束.

(6) 存储Y′的x 轴坐标值x′, a′和b′到本地数据库中.

(7) 检测是否存在碰撞, 若碰撞则进行下一步, 否则检测结束.

(8) 提取出碰撞点的信息x′′轴坐标值, a′′和b′′.

(9) 判断x′′是否与x′相等, 若相等则进行下一步, 否则直接抛弃, 检测结束.

(10) 判断等式gcd(b′−b′′,n)=1 是否成立, 若成立则进行下一步, 否则直接抛弃, 检测结束.

(11) 计算k′=(a′′−a′)(b′−b′′)−1mod n.

(12) 判断等式Q′=k′P 是否成立.

(13) 若成立, 输入k′, Q′和P 到碰撞交易中, 然后向全网发布该交易, 否则直接抛弃, 检测结束.

4.5 ECDLP 求解

当ECDLP 发布者接收到碰撞交易时, 他将验证该交易的正确性. 若通过验证, 将进行最后的去盲操作, 进而得到最终的ECDLP 求解值, 具体步骤如下:

(1) 计算Q′′=k′P, 如果Q′′=Q′, 进行下一步, 否则求解结束.

(2) 计算k =α−1k′.

(3) 若Q=kP, 则求解ECDLP 成功, 结束, 否则求解失败, 结束.

5 验证区块效率与安全分析

5.1 验证区块效率分析

验证者接收到矿工新发布的区块时, 需要验证YD=Y0+s1M1+s2M2+···+srMr, 因此验证者需要计算r 次标量乘运算和r+1 次点加运算. 其中r 次标量乘运算是r 个固定点标量乘, 于是可以利用查找表的方式进行加速计算, 为每个固定点Mi,i = 1,··· ,r 建立一个查找表, 当计算siMi的值时, 验证者只需要通过si进行查表即可. 此外, 由于每个标量乘是相互独立的, 因此验证者可以并行查找和计算每个siMi的值, 然后进行一次求和, 进一步提高验证上述等式的速度.

以ECCp-131 作为例子, 在单线程情况下, 平台为Ubuntu 18.04 LTS, 处理器为Intel Core i7-782x(Skylake-X), 3.60 GHz 并且内存为64 GB, 验证等式YD= Y0+s1M1+s2M2+···+srMr所消耗的时间约为81.45 ms. 同时在相同的平台下, 计算一次SHA-256 所消耗的时间约为0.013 ms. 本方案的验证速度与比特币系统的中计算SHA-256 的验证速度相比较还是有较大的差距, 但是该方案具有一定的实用性, 并且从实践中验证了本方案达到“难于计算却易于验证” 的目标.

5.2 验证区块安全分析

定理1 如果存在恶意的矿工把一个预计算好满足挑战难度的可区分点构造一个合法的新区块并发布到网络中, 这个新区块被全网络接收的概率是可以忽略的.

证明: 对于恶意的矿工来说, 他需要找到一条游走路径(s1,s2,··· ,s30) 使得他预计算好的可区分点Y′D满足Y′D= Y0+ s1M1+ s2M2+ ··· + s30M30, 其中初始点Y0是一个合法的初始点, 即矿工选取最新一块区块的哈希值作为挑战c 和随机选取一个nonce 值n, 令Hash(c||n) = (a0,b0) 并计算Y0= a0P +b0Q′. 如果恶意的矿工可以在多项式时间内找到这样的一条游走路径, 那么ECDLP 就被解决.

6 总结

本文基于ECDLP 设计一种工作量证明方案. 其结合并行的Pollard rho 算法提出了一个新的思路,有效解决了一个区块中从初始点到可区分点中有效计算的问题. 本文的方案通过记录区分点的游走路径的和结合固定点标量乘查找表的办法, 实现快速验证区块的功能. 本文设计的方案不仅可以作为一种新的在区块链中的共识算法, 还可以为用户提供一种解决ECDLP 困难问题的工具.