科普:区块链协议中的随机性_ARKS:BTCC价格

编者按:本文来自以太坊爱好者,作者:AlexanderSkidanov,翻译&校对:闵敏&阿剑,Odaily星球日报经授权转载。我们今天发表的一篇短论文介绍了NEAR协议所采用的随机信标。佐餐食用的本文将着重讨论随机性的重要意义、实现难度以及其它协议的实现路径。包括NEAR在内的诸多新型区块链协议都高度依赖于随机性,以抉择由哪些成员执行协议中的特定操作。如果恶意攻击者能影响随机源,他们就有机会增加自己被选中的概率,最终威胁协议的安全性。分布式随机性同样也是众多区块链应用的重要基石。举例来说,假如某个智能合约接受用户的约,规则为无偏倚地产生一个随机数,据此以49%的概率返还两倍押注,51%的概率没收资。如果恶意攻击者可以影响或者预测该随机数,他们就能旱涝保收,并很快搬完合约中所有的资金。在设计分布式随机性算法时,我们希望它具备以下属性:算法必须公正无偏。换言之,不允许有任何参与者能丝毫影响随机数生成器的结果。算法无法被预测。即在随机数生成之前,所有的参与者都不知道会生成什么样的结果。协议需要具备在某些节点掉线时仍保持正常运行的容错能力,即使有节点故意阻碍协议,也可以继续运行。本文将介绍分布式随机信标的基础知识,说明为何朴素的技术方案无法达成效果。在最后,我们将介绍DFinity、EthereumSerenity以及NEAR协议所采用的随机信标方案,并逐一剖析其优越性与不足之处。RANDAO

RANDAO非常简单,因此也是一个十分常见的随机性实现方案。其大致思想是网络中的所有人首先各自私下选定某个随机数,然后向RANDAO提交该随机数的承诺,接着所有人根据一定的共识算法从所有的承诺中选定一组;在参与者揭示这组承诺背后的随机数之后,大家对该组随机数达成共识;最后这组随机数进行异或操作得到的结果就是一轮RANDO协议产生的随机数。RANDO的做法的确让随机数难以预测,并且随机数享有与底层共识协议一样的活性,但仍有可以钻空子的地方。比方说,恶意攻击者看到网络中所有其他人揭露各自所选取的随机数之后,可以根据自身随机数先执行异或运算,并根据结果对自己的利弊来决定是否要揭露自己的随机数。这种设计使得单个攻击者就能对输出造成一定的影响,同时随着攻击方所控制的参与者数目增多,他们的破坏性也随之增强。RANDAO+VDFs

要增强RANDAO的公平性,其中一种办法是替换掉最后的那个异或计算,将其改变为执行时间必定长于各方随机数揭露等待期的操作。如果计算最终结果的时间比随机数揭露等待期要长,那么恶意攻击者就无法预先知道自身随机数揭露与否能给自己带来好处,因此理论上就无法影响最终结果的属性了。虽然需要有一个函数来拖延参与者生成最终结果的时间,但不能因此让随机数用户也耗费巨大的开销去验证所生成的随机数。因此,理想函数应该能让用户轻易验证系统生成的随机数,而无需重复之前的计算开销。上述既需要长时间来计算,同时能轻易验证计算结果,并且对每一个输入都有着独一无二输出的函数正是可验证延迟函数,设计一个这样函数的工作委实艰巨。近来这一领域已经有所突破,比如这个和这个已经可以应用,当前以太坊就计划应用RANDAO和VDF来作为其随机性信标。除此之外,由于这种策略所具备的不可预测性和无偏见性,使得系统甚至能在仅有两个参与者在线的情况下依然具备活性。VDF虽好,但目前的最大挑战在于函数需要足够健壮,即使某些别有用心者花大价钱配置定制化硬件设备,也无法在揭露等待期结束之前计算出最终结果,理想情况是函数具备有足够威慑力的安全边际,例如延迟时间较揭露等待期拖长10倍。下图展示了系统中参与者采用定制化ASIC设备所发起的一次攻击,攻击者能够在各方揭露RANDAO承诺之前计算出最终会输出的随机数。攻击者依然能根据计算得到的随机数结果,以及最终结果对自身收益的利害关系,自主决定是否要揭露所掌握的随机数。和VDF家族关联的特制ASIC设备会比传统硬件的计算速度快100倍。因此,如果揭露等待期耗时10秒,同时为了达成理想的10倍安全边际,需要保证ASIC设备至少花100秒才计算出最终结果,由此换算到普通硬件设备上则需100x100秒,即约3个小时来得到输出结果。针对这一问题,以太坊基金会的做法是设计自己的ASIC设备并开源。一旦上述设想落地,以太坊之外的其它协议也能把真正的随机数用起来了。不给过在那个时刻到来之前,无力投资研发自己ASIC设备的协议们还是没法应用RANDAO+VDF的解决方案。这个网站收录了许多关于VDF的文章、视频以及其它资讯。门限签名

Dfinity团队正倡导并研究的的门限BLS签名是随机性的又一实现方案。BLS签名用于多方对一则消息构建一条聚合签名,由于无需额外的签名通信,因此常用于节省空间和带宽。在区块链里,BFT共识协议的区块签名通常就使用BLS签名。例如在一个有100个节点的区块链系统中,当其中的67个节点都对某个区块进行了签名时,就可以认定这个区块已经上链。每一个节点都可以提交自己那片BLS签名,系统根据某些共识算法选出其中67片签名来聚合成一条BLS签名。虽然任意67片签名都能组成一条聚合签名,但不同的签名输入不会聚合成相同的BLS签名。其实如果系统中参与者持有的私钥是通过某种特殊方式生成的,那无论选择哪67片签名,都能输出一样的聚合签名。这种特性可以用来产生随机性:系统中参与者首先对某则他们未来会进行签名的信息达成一致,然后就此产生一个聚合签名。在67个参与者揭露自身签名之前,没有人能预测输出结果,同时由于大家在第一片签名披露之前就认定完了输出结果,因此任何参与者都无法再对输出产生影响。上述随机性实现方案具备无偏见性和不可预测性,只要网络中有2/3参与者在线就能维持运行。即使1/3的节点掉线或篡谋发起攻击,他们也只能让系统停滞,因为要想对最终结果产生影响,需要至少2/3的节点。看起来一切都很完美,但是,依然有一个但是。前文我曾提及私钥需要按某种特殊方式生成,这种被称为分布式密钥生成的技术事实上十分复杂并且仍处于探索阶段。在最近的一些公开演讲中,Dfinity提出了使用zk-SNARKs来实现DKG,但是zk-SNARKs十分复杂,并且这种构造方法还没有经过时间检验。总的来说,门限签名和DKG技术尚未发展到能落地应用的阶段。RandShare

目前为止,NEAR受到的最大影响来自于另一种算法:RandShare。RandShare是一个无偏见且不可预测的协议,支持1/3恶意节点容错。其速度相对较慢,在对应论文中虽然提到了RandHound和RandHerd两种加速方法,然而和RandShare本身相比还是太过复杂,我们想要的理想协议应该简洁优美。除了较大的通信压力,RandShare面临的另一个问题在于虽然1/3的容错门限能保证协议在应用中的活性,但这个门限难以震慑别有用心者对输出结果发起攻击。具体原因有以下几点:攻击输出结果所带来的收益要远远大于拖滞随机数生成带来的收益。如果某一方控制了RandShare中超过1/3的节点并试图操纵输出结果,这种攻击甚至不会留下任何痕迹。与光天化日之下拖滞随机数生成相比,操纵输出结果根本就是闷声发大财。从现实考量,某势力操纵超过1/3的哈希算力/权益并非天方夜谭,而且根据两点,具备实力的攻击者基本不会选择拖滞随机数生成,而是倾向于暗地操纵输出结果。NEAR方案

我们最近发表的一篇论文介绍了NEAR方案。这是一个无偏见且不可预测的协议,其活性具备1/3节点的容错能力,即攻击方只有控制了全局1/3及以上的节点才能阻塞协议。然而和RandShare不同,NEAR能保证2/3恶意节点的容错。这个门限对实际应用来说显然更为优越。NEAR协议的核心思想如下:每一个节点首先提出自己的输出片,将其分成67份,再用纠删码将其编码为100份,这一过程需要保证任意67份数据都可以恢复输出片,然后使用其它各节点的公钥对每一份数据签名并转发,这样一来,各节点互相持有加密片。系统中各节点使用某种共识算法选出特定67个节点所生成的加密片。一旦达成共识,各个节点根据步骤(2)的结果,从本地取出被自身公钥签名过的加密片,解码揭露数据后立即广播。一旦有67个节点完成了步骤(3),系统就有了足够的信息解码重构出原始数据,最终结果可以由(1)中各节点输出片的简单异或操作得到。上述协议具备无偏见性和不可预测性的道理和RandShare以及门限签名都类似:一旦达成共识,输出已经被确定了,只不过要等到至少2/3的节点用各自公钥将加密的那部分揭露,大家才能看到输出结果。如果要考虑一些特殊情况以及可能的恶意攻击,协议可能变得稍稍复杂中有节点生成无效的纠删码,系统需要有能力应对),但总的来说整个协议还是十分清爽,涵盖了所有证明和相关密码学原语和引用的论文篇幅仅7页长。如果你想了解算法更为规范的描述,或是对其活性和防御性的分析,请务必阅读我们的论文。当前NEAR协议架构已经应用了类似的纠删码思想,系统中区块生产者会在特定时期内创建一些分块,其中包含了对于某一特定分片的所有交易,然后将分块进行纠删码编码后的版本附带默尔克证明发送给其它区块生产者,以保证数据可用性。结语

我们正在努力编写一组主题为区块链协议及相关内容的高质量技术文章,本文是其中一篇。除此之外,我们还制作了一系列面向其它协议创始人和核心开发者的视频,目前已经录制了针对包括EthereumSerenity、Cosmos、Polkadot、Ontology、QuarkChain在内多个项目的视频。为了便于查看,所有视频都已经被打包进了这个播放列表。如果你对NEAR协议背后的技术感兴趣,请务必研读上文提到的那篇分片论文。NEAR是少数几个在分片中解决状态验证和数据可用性矛盾的协议,并且该论文在给出我们的解决方案之外,还提供了一个针对分片的更为开阔、通用的视角。今时今日,虽然扩容是区块链中的大挑战,但可用性难题或许更值得大家关注。我们团队对此倾注了大量资源,努力构建更可用的区块链系统。最近我们发表了一篇概览,介绍了当今区块链协议面临的种种可用性挑战,以及对应的探索路线。Twitter关注,不迷路!也欢迎来我们的Discord频道畅所欲言,无论是技术、经济、治理或是协议设计中的其它方方面面,我们都会进行热烈而精彩的讨论。

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

金智博客

火必99%的币都是垃圾?_数字货币:KBTC

一、前言 前两天看了闪电黄世亮的文章,文章写的很有意思,标题叫做《为什么要研究“山寨”币》,其中提到了一个事迹,就是他花了1万块钱买了100种山寨币,每个山寨币买了100元.

[0:0ms0-3:351ms