http://www.umut.cn

区块链协议中的随机性

我们今天发表的一篇短论文介绍了 NEAR 协议所采用的随机信标。佐餐食用的本博文将着重讨论随机性的重要意义、实现难度以及其它协议的实现路径。

包括 NEAR 在内的诸多新型区块链协议都高度依赖于随机性,以抉择由哪些成员执行协议中的特定操作。如果恶意攻击者能影响随机源,他们就有机会增加自己被选中的概率,最终威胁协议的安全性。

分布式随机性同样也是众多区块链应用的重要基石。举例来说,假如某个智能合约接受用户的赌约,规则为无偏倚地产生一个随机数,据此以 49% 的概率返还两倍押注,51% 的概率没收赌资。如果恶意攻击者可以影响或者预测该随机数,他们就能旱涝保收,并很快搬完合约中所有的资金。

在设计分布式随机性算法时,我们希望它具备以下属性:

1. 算法必须公正无偏(unbiasable)。换言之,不允许有任何参与者能丝毫影响随机数生成器的结果。
2. 算法无法被预测。即在随机数生成之前,所有的参与者都不知道会生成什么样的结果(也不能预测到其属性)。
3. 协议需要具备在某些节点掉线时仍保持正常运行的容错能力,即使有节点故意阻碍协议,也可以继续运行。

本文将介绍分布式随机信标的基础知识,说明为何朴素的技术方案无法达成效果。在最后,我们将介绍 DFinity 、Ethereum Serenity 以及 NEAR 协议所采用的随机信标方案,并逐一剖析其优越性与不足之处。

RANDAO

RANDAO 非常简单,因此也是一个十分常见的随机性实现方案。其大致思想是网络中的所有人首先各自私下选定某个随机数,然后向 RANDAO 提交该随机数的承诺,接着所有人根据一定的共识算法从所有的承诺中选定一组;在参与者揭示这组承诺背后的随机数之后,大家对该组随机数达成共识;最后这组随机数进行异或操作得到的结果就是一轮 RANDO 协议产生的随机数。

RANDO 的做法的确让随机数难以预测,并且随机数享有与底层共识协议一样的活性,但仍有可以钻空子的地方。比方说,恶意攻击者看到网络中所有其他人揭露各自所选取的随机数之后,可以根据自身随机数先执行异或运算,并根据结果对自己的利弊来决定是否要揭露自己的随机数。这种设计使得单个攻击者就能对输出造成一定的影响,同时随着攻击方所控制的参与者数目增多,他们的破坏性也随之增强。

区块链协议中的随机性

RANDAO + VDFs

要增强 RANDAO 的公平性,其中一种办法是替换掉最后的那个异或计算,将其改变为执行时间必定长于各方随机数揭露等待期的操作。如果计算最终结果的时间比随机数揭露等待期要长,那么恶意攻击者就无法预先知道自身随机数揭露与否能给自己带来好处,因此理论上就无法影响最终结果的属性了。

虽然需要有一个函数来拖延参与者生成最终结果的时间,但不能因此让随机数用户也耗费巨大的开销去验证所生成的随机数。因此,理想函数应该能让用户轻易验证系统生成的随机数,而无需重复之前的计算开销。

上述既需要长时间来计算,同时能轻易验证计算结果,并且对每一个输入都有着独一无二输出的函数正是可验证延迟函数(verifiable delay function ,可缩写作 VDF ),设计一个这样函数的工作委实艰巨。近来这一领域已经有所突破,比如这个和这个已经可以应用,当前以太坊就计划应用 RANDAO 和 VDF 来作为其随机性信标。除此之外,由于这种策略所具备的不可预测性和无偏见性,使得系统甚至能在仅有两个参与者在线的情况下依然具备活性(假设底层共识协议的在参与者如此稀少时仍能具备活性)。

VDF 虽好,但目前的最大挑战在于函数需要足够健壮,即使某些别有用心者花大价钱配置定制化硬件设备,也无法在揭露等待期结束之前计算出最终结果,理想情况是函数具备有足够威慑力的安全边际,例如延迟时间较揭露等待期拖长 10 倍。下图展示了系统中参与者采用定制化 ASIC 设备所发起的一次攻击,攻击者能够在各方揭露 RANDAO 承诺之前计算出最终会输出的随机数。攻击者依然能根据计算得到的随机数结果,以及最终结果对自身收益的利害关系,自主决定是否要揭露所掌握的随机数。

区块链协议中的随机性

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。