江苏快三开奖结果 > 区块链 > 读懂区块链与数字货币,区块链中的随机数【江

原标题:读懂区块链与数字货币,区块链中的随机数【江

浏览次数:109 时间:2020-01-16

"Randomness is something beyond human beings."—— The Big Qiu随机是不确定性,而依赖确定性是人的天性。程序本是确定的,而引入随机数这个不确定因素之后,带来了更多的可能性。而随机数作为区块链生态中的一部分,应用层面,如各类游戏;协议层面,能解决性能瓶颈。作为区块链中重要的组件之一,随机被应用在各个领域,应用层面,如游戏;协议层面,则能解决性能瓶颈。但在区块链公共可验证的透明之下,随机数的生成机制被彻底暴露;而货币成为原生属性之后,所有人都更有激励希望去操作随机的天平导向自己。2018 年出现最多的事件就是,某 Dapp 随机数出现漏洞,并且愈演愈烈,让我们质疑:区块链上的随机数,能够“随机”吗?或许利用密码学和博弈论,结合激励和惩罚,能出现无限可能的解法。本文从随机数的基本概念讲起,为大家理清楚“区块链上的随机数”。技术的发展总是盘旋而上,区块链带来无限可能性,原本无限美好的“透明”却带来了意想不到的不安全感,然而有新的方式来解决。就像那句话:“而现在,我们生活在一个技术没有天花板的时代,由新技术造成的问题,只能由更新的技术解决。”随机性 (Randomness) 的获取是区块链中非常重要的一个课题。这里的随机性的获取包括但不仅限于:如何在智能合约中引入不可预测的随机数;如何在共识协议中安全地进行随机抽签。显然,上述对于随机性获取的问题描述已经说明了为何这个课题十分重要。而在区块链中获取随机数非常困难,这一方面来自于区块链系统的透明性——从通常意义上来讲,该特性会使得一切算法的输入,输出以及算法本身暴露给所有的系统参与者——因此,在密码学中广泛使用的伪随机数发生器不可以被直接以硬编码的方式或者是智能合约代码的方式应用在区块链系统中来获取安全的随机数,因为透明性,系统参与者能够根据代码预测到随机数甚至操纵随机数,从而让随机源不“随机”。另一方面,随机数获取协议作为区块链系统的一个子协议常常与该系统下的其他协议有紧密的关系,如共识协议,这意味着其他协议很有可能会影响随机数获取协议的安全性。从而使随机数获取协议的设计变得非常复杂,常常需要具体问题具体分析。本篇文章总结了目前主要的应用在区块链的不可预测随机数获取协议,并提炼出它们的设计思想,方法论以及依赖的假设,然后对他们进行比较。本文分为两部分:第一部分介绍基本概念,并从零开始解释构造适用于分布式系统的随机数协议核心;第二部分介绍目前主流的应用在区块链项目中的随机数协议,并分析他们是如何使用第一部分所介绍的某类或者某几类协议核心。本文假设读者已经具有基本的区块链知识,并对以太坊智能合约的基本原理和比特币共识协议的基本原理有大致的了解。随机性的定义在日常生活中,我们经常会听到诸如“随机选择”,“伪随机数”,“随机模型”,“随机序列”之类的词汇,以及“伪随机数”、“真随机数”这样的概念。想要理解这些词汇和概念,必须要搞清楚随机是什么。事实上,与“随机”相对的是“确定”。因此,我们可以将“随机”直观上理解为“不确定”——无论是随机数,还是随机选择,我们都希望这个数或者选择的结果从某种程度上来讲是不确定的。因此,如果直接给出一个数,而不给出这个数的产生方式,它不能被称之为随机数,比如直接给出一个数字 1,我们不能说 1 是随机数,但是如果这个 1 是通过掷骰子决定的,则可以说这个 1 是随机的。当然,这些都是非常直观而宽泛的理解。更精确地讲,“随机”,或者我们说“随机数”、“随机序列”,在不同的领域有不同的定义。在数学上,随机数的定义和概率论相关;在计算复杂性理论中,使用描述随机序列的程序长度来定义(即序列越随机,描述它的程序的长度就越长);密码学会结合统计特性和密码攻击来描述随机数。我们这里先给出随机序列的描述性定义,我们可以称一个序列为随机序列,当它满足:均匀性:该序列服从均匀分布。独立性:该序列的各个元素相互独立。不可预测性:依据该序列的任意片段,不能预测该序列余下的部分。展开来讲,我们可以先考虑如下问题:考虑一个每一项要么取 1 要么取 0 的数列。假设它的每一项均为1,它显然不是随机序列,因为违反了均匀性。均匀性要求0和1出现的概率相同。假设它的每一项都和前一项不相等。比如 “0101010101”,它满足了均匀性,但是仍然不是随机序列,因为违反了独立性。对于一个满足独立性和均匀性的随机序列。比如从常数 e 的小数点后第 10 位开始依次选取数码组成序列。这样的序列在统计上满足独立性和均匀性,但是它的序列是可以被预测的。我们说过,不同的领域对随机性有不同的定义。比如,在仿真当中我们想要模拟顾客到达的间隔时间,用只满足前两条的随机序列是足够的。但是在密码学中,比如生成随机的密钥,仅满足前两条的随机序列是不够的,一个有可能被预测的随机序列用在密钥生成中当然是有安全问题的。比如我们用自然对数的底 e 的数码作为随机序列。e 确实可以被认为在统计上是均匀分布和独立的(尽管没有完全证明),用来做仿真是足够的,但是不能用作密码学中的随机种子。因为对手有可能通过一定长度的已知序列猜测到是在使用 e 。同理,在抽奖、游戏当中使用的随机数也通常是要求不可预测的。鉴于区块链领域中涉及的多是密码学和游戏的场景,接下来的内容都是满足全部三条性质的随机序列。随机序列又可以被分为真随机 (True Random) 序列和伪随机 (Pseudorandom) 序列。伪随机序列,顾名思义,就是“不是真的随机,只是看起来是随机的”。因此,根据图灵奖得主姚期智提出的概念,粗略地讲,伪随机序列就是指一个与真随机序列在计算上不可区分的序列。而真随机序列,指的是不可被重现的随机序列,比如通过抛硬币产生的随机序列。我们可以看出来,在这样的定义下,伪随机序列的统计特性应当和真随机序列无法区分,也就是说,伪随机序列同样是满足全部三条性质的随机序列。当然,这样的定义通常用在计算复杂性理论以及密码学当中,在其他领域,只满足前两条性质的随机序列也可以被称作伪随机序列。产生随机序列的发生器叫做随机数发生器 (Random Number Generator, RNG) 。按照产生的序列的性质,我们可以将其分为真随机数发生器 (True Random Number Generator, TRNG) 和伪随机数发生器 (Pseudorandom Number Generator, PRNG)。此外,还有一种与之正交的分类方法是从随机数发生器的实现方法来分类,可以将随机数发生器分为硬件随机数发生器和软件随机数发生器,它们之间的关系如图 1 所示真随机数发生器通常利用一些非确定现象,通过物理手段将其转换为真随机序列。通常的非确定现象包括混沌效应和量子随机过程。其中混沌效应的特点是目前物理学能够明确解释其因果,但是由于结果对于初始值过于敏感,导致无法精确预测其结果。比如,通过收集大气噪声而产生的随机数就是利用混沌效应产生的随机数的例子。而量子随机过程则是利用微观量子态的不确定性,这个不确定性已经被目前物理学理论承认,它能够保证即使输入值完全相同,输出值也是可能完全不同的。比如利用激光器的相位噪声来生成随机数。硬件真随机数发生器,通常使用芯片实现;而软件真随机数发生器,通常利用系统自带的一些非确定现象,譬如硬盘寻道时间、RAM 中的内容或者是用户的输入,Linux 系统里的 /dev/random 就是一种软件真随机数发生器,它通过采集机器运行过程中的硬件噪音数据来获取足够的随机性来源,并依此生成随机数。而伪随机数发生器是一段程序,是一种确定性的算法,通常以短的真随机数作为输入,进行扩充,生成更长的和真随机序列非常接近的随机数序列。它的输入被称作种子 (Seed)。它同样也有硬件实现和软件实现。如何从区块链上取得随机数上一节中我们给出了随机性的一个定义,这样的定义也将用于本文余下的部分。并且,我们还给出了伪随机性以及伪随机数发生器的概念。在实际应用中,可用于密码学的伪随机数发生器有很多并且也已经很成熟了,那么我们很自然地想到,能否将伪随机数发生器直接用在区块链,在区块链的共识过程或者应用上面加入随机性,使得这样的随机性满足我们上面提到的三条性质?很遗憾的是,答案是否定的。伪随机数发生器产生的随机序列的不可预测性的前提是伪随机数发生器作为一个黑盒,除了它的输出,外界无法得知其他一切信息。但是区块链上的一切都是公开透明的,包括使用的伪随机数发生器及输入到伪随机数发生器里面的种子也是一样公开透明的。在这样的情况下,所有传统的伪随机数发生器都无法在区块链的环境下产出具有不可预测性的随机数序列。而至于真随机数发生器,的确存在将真随机数发生器的结果通过可验证的不可篡改的通道引入区块链系统内部,这样的通道又被称作 Oracle。以太坊现在常用的随机数发生器就是通过 Oracle,引入 random.org(random.org 是一个网站,它声称提供真随机数)提供的随机数。但是这种方法的问题在于,所谓的“真随机数发生器”往往是中心化的,拥有这样的硬件或者软件的人或者组织拥有篡改随机数发生器结果并且不让用户发觉的能力。这对于主打“去中心化”的区块链系统来说,无疑如鲠在喉。除了伪随机数发生器和真随机数发生器,还有一类随机数发生器会直接利用区块链系统中共识过程所天然产生的随机性。比如,使用未来某个块或者之前某个块的 Hash 值来作为种子之一生成随机数(其他的种子可以是用户的地址、用户支付的以太币数量等,但是这些是用户可控的部分,没有增加不可预测性的作用)。这种做法也常见于各种区块链博彩类游戏以及资金盘游戏当中,但是这样的随机数获取过程有着致命的漏洞——用户有可能通过仔细选择交易时间来控制随机数向有利于自己的方向生成;即使用户无法控制,矿工也可以控制随机数的生成,并且这样的攻击成立并不需要太多算力的参与。只要最终随机数牵涉的金额足够,完全可以使用租用算力或者贿赂矿工的方式进行攻击。那么归根结底,在区块链这样的一个系统当中随机性可以来自哪里呢?也就是说,通过上面的分析,我们发现,对于如上做法的随机数发生器,无论规则或者程序设计得如何复杂,它都是确定性的算法。对于一个确定性的算法,算法本身不会对输出的随机性有任何的影响,能够影响最终输出的随机性的,只有算法的输入。因此,在区块链系统当中,我们需要在一个分布式的,公开透明的环境中去仔细选择一个有足够随机性的输入。那么符合要求的输入存在吗?答案是肯定的,这样的输入实际上来源于我们对于区块链系统参与者之间不是一个整体的假设。随机数生成协议模型我们现在从最简单的情况开始去逐步构造一个区块链上可以使用的公平的随机数发生器。下文所涉及到的在分布式的环境下的协议都可以转换为区块链的环境,因此不对“分布式”和“区块链”做区分。“分布式”和“区块链”的区别区块链系统属于分布式系统,但是分布式系统不仅仅是区块链系统,还包括点对点文件传输系统,分布式数据库系统等等。“分布式”只是对网络的拓扑结构进行描述,表明网络不是集中式的,而是分布的多节点控制的。为了更清楚地说明构造分布式随机数协议,也叫分布式随机数信标 Distributed Randomness Beacon, DRB),的方法论,我们首先引入一个随机数协议的抽象模型:(图2)这个模型能够完整地描述一个分布式随机数协议的输入输出与其节点之间的关系。如图 2 所示,假设每个节点地位相同,不做区分,那么每个节点都会运行同样的协议。一个分布式随机数协议包含三部分的输入:每个节点i自己的输入 Iiself,来自其他节点的输入Ijinter,j≠i以及一个公开的预先约定好的公共输入Icommon,这三部分输入每一部分都可以包含多次的输入。作为一个分布式随机协议,其输出随机性的来源只能由输入提供,我们先不考虑这三部分输入进入协议的先后顺序,那么我们可以将协议分为两类,一类是采用Iself与Iinter作为随机性来源的协议,另一类是采用Icommon作为随机性来源的协议。大家可以发现,这两类事实上已经涵盖了所有的随机性来源的可能,其他类别的协议都可以视为这两类协议的组合。文章后面的部分将主要对这两类协议展开分析。使用Iself与Iinter作为随机性来源下面,我们考虑这样的一个场景:Alice 和 Bob 在网上凑钱一起买了一张彩票,结果中了神秘的头奖,令他们吃惊的是,奖品竟然是一只皮卡丘,如图 3 所示。但是皮卡丘不可分割,并且由于两人相隔甚远无法见面猜拳,所以他们俩决定设计一个对两个人都公平的随机数生成协议来确定谁能获得这只皮卡丘。v1.0:最简单的随机数生成协议Alice 设计了如图 4 所示的一个协议,这个协议又被称作 Coin-Tossing Protocol 或是 Coin-Flipping Protocol。协议接收每位参与者的一次输入,在该场景下是ξA和ξB,输入的取值只能是 0 或者 1。协议拥有唯一公共输出ξ,取值也是 0 或者 1,如果最后ξ=0,Alice 获得皮卡丘;若ξ=1, Bob 获得皮卡丘。而从每一位参与者的角度来讲,这个协议接收自己的输入以及其他运行这个协议的节点的输入,经过算法运算之后,输出一个一致的最终结果,其实就是上一节中我们提到的抽象模型中的,利用Iself与Iinter作为随机性来源的协议。那么这样的协议具体是怎么做的呢?为了构造这样的一个协议,我们需要确定这样的协议需要满足什么样的性质。考虑到每个人之间的输入是相互独立的,这样的协议需要保证每个人自己的输入也应当是和输出相互独立的,但是他们又共同对输出做出了一定贡献。只有这样,才能确保每个人都无法光凭借改变自己的选择来改变输出。同时,协议也需要保证只要有一个人的输入是均匀分布的,那么结果就是均匀分布的。现实中满足这些条件的构造方式有很多,其中一种是异或操作,将两人的输入异或之后输出:在给定 Bob 选 1 的情况下(Alice 不知道),Alice 不管选 0 还是 1,输出结果都是 0 和 1 各一半的可能性;给定 Bob 选 0 的情况同理。ξ=ξA⊕ξB另一种方法是利用 mod 加法,将两人的输入进行模 2 加法之后输出,也能得到类似的结果。ξ=ξA+ξB mod 2v2.0:带有承诺的版本v1.0 看似解决了我们的问题,实际上它有非常大的漏洞。这个漏洞在于,我们无法保证 Alice 和 Bob “同时” 输入。假如 Bob 等 Alice 向协议输入她的选择之后再进行选择,那么由于协议的交互对于两人来讲是公开的,Bob 可以根据 Alice 的选择来调整自己的选择。例如,如果 Alice 的选择是 0,那 Bob 就输入 0;如果 Alice 是 1,那他就输入 1。这样,无论 Alice 怎么选择,Bob 都可以使得异或的结果永远是 1,就能拿走这只皮卡丘。(图5)事实上,同时输入是很难保证的,而为了防止这种作弊行为,我们需要保证,协议中的来自其他人的输入对于参与者来讲应该是暂时机密的,不会透露任何他们的选择的信息。与此相应的,应该多出一个去机密化的过程以计算出协议的输出。为了实现这样的需求,我们需要引入新的机制:承诺 (Commitment)。如图 5 所示,该机制包含两个阶段:承诺 (Commit) 阶段和揭示 (Reveal) 阶段。在第一个承诺阶段,协议参与者不再直接输入自己的选择,而是对自己的选择进行数字签名,将签名的结果,我们称之为承诺,输入进协议。例如,Alice 会将她的选择ξA用自己的私钥skA​进行签名,获得结果sigskA(ξA)​输入进协议。当所有参与者的签名结果均输入进协议中后,进入第二个揭示阶段。该阶段所有参与者将第一轮自己的选择输入进协议,例如 Alice 会输入ξ′A​,协议会结合第一个阶段的承诺进行验证,确认输入的ξ′A​和ξA相等。如果所有的验证都通过,则输出最终结果 ξ,最终结果就是我们想要的随机数。这样的协议保证了,在第一个阶段里没有任何人的选择会被除自己以外的其他人获知,并且在第二阶段,即使 Bob 先知道了 Alice 揭示出来的选择值然后在自己揭示之前计算出结果,他也无法改变自己的选择了,因为第一个阶段的签名已经做出了“承诺”。这里,数字签名能够保证消息的不可篡改性,不可否认性以及暂时的机密性。如果该协议是运行于区块链之上,由于通常区块链协议都会对交易内容进行数字签名,那么我们的协议也可以将使用数字签名改为使用 Hash 函数。v3.0a:使用经济惩罚v2.0 的版本在对于两个人的情况的时候看起来非常公平,但是对于两人以上的情况,它仍然是有漏洞的。假设 Alice、Bob、Clare 三个人分一只皮卡丘,其他设定不变,采用 v2.0 协议。这时,Bob 想到了个主意:“在最后的第二阶段,我可以在输入自己的选择进行揭示之前先依据别人的揭示结果计算出输出,如果不是对我有利的输出,我就不进行揭示阶段,假装网线被挖断了。”刚才的协议无法处理这种情况。是重新再来一遍,还是就取剩下两个人的输入呢?这两种方法是都有问题的:如果重新再运行一遍协议,那么攻击者就可以利用这种重新运行的机制在每次自己不利的情况下强行使得协议重新运行;如果只取剩下两个人的输入,攻击者同样可以利用这种机制选择是否放弃输入来趋利避害。因此,我们需要有一种机制来保证参与者不得随意放弃,最简单的方式就是利用经济惩罚。如图 6 所示,当参与者在第一阶段承诺的时候,必须要向协议锁定一个比特币(也可以是其他的数字货币)——如果是在带有智能合约的区块链的环境,这样的操作十分容易。如果 Bob 不按时揭示他的选择ξB ,那么就会没收 Bob 的比特币分给 Alice 和 Clare,然后重启协议。由于皮卡丘的价值(也许)通常并不会超过一个比特币,Bob 不会选择这样的方式进行作弊。这样的一个惩罚机制,就是为了防止这样的拒绝服务攻击。需要注意的是,之所以本节一开始所述的攻击对只有两个参与者的协议不奏效,是因为两个人的情况下,在仅剩一个人的时候,我们可以直接给出有利于剩下的参与者的结果,而在多于两个人的情形下,我们仍旧无法保证在剩下的人当中做出选择。这样的规则是一种天然的对拒绝服务的参与者的惩罚。v3.0b:使用门限机制除了经济惩罚之外,还有另外一种方式,我们称之为门限 (Threshold) 机制。门限机制指的是一种协议的某一个指标达到一定阈值就可以执行特定流程的机制。在这里我们引入门限机制,主要是为了使得在协议参与人数有缺失的时候仍然能够给出正常的输出。门限机制的作用在于增强协议的健壮性,使得它能够容忍一定程度的拒绝服务攻击。我们接下来讨论的门限机制都是(t,n)门限机制,意思就是对于 n 个参与者的协议,只需要 t 个参与者的输入即可完成协议的输出,注意这里的 n 不一定是协议预先规定好的,或者说是协议必须知道的,它也有可能是一个不确定的数字。如果协议必须规定了确切的 n 才能够保证正确性,那么这样的协议只能用于许可环境 (Permissioned Setting) 中;如果不需要规定确切的 n ,那么这样的协议可以被用于非许可环境 (Permissionless Setting) 中。如图 7 和 图 8 所示,我们使用最基本的 v1.0 版本的 Coin-Tossing 协议,将门限机制的输出作为 Coin-Tossing 协议的输入。这样的门限机制总的说来有三种。第一种门限机制是将输入按照某种规则排序之后,简单地取前 t 个输入。但是这种方式不抗女巫攻击 (Sybil Attack)——假如 Bob 是黑客帝国的复制人,他复制了一万个自己,因此 Bob 通过控制这一万个身份有很大的可能占有前 t 个输入,从而控制随机数的结果。因此,这种门限机制是无法用在没有抗女巫攻击机制的环境下——譬如,没有身份验证的非许可环境下,但它的优点在于,这样的机制不需要知道 n 的确切值。女巫攻击简单来讲,指的是一种网络内的少数节点控制多重身份的攻击方式第二种门限机制是无分发者的秘密分享系列的。这一系列协议均需要每产生一个随机数输出都进行一次秘密分享来保证门限机制,属于有状态 (Stateful) 协议。更直观地讲,比如有 n 个人,假设只需要有 t 个人提交了就能输出我们想要的随机数,同时,我们需要 r 个这样的随机数。那么如果采用无分发者的秘密分享系列的门限机制,我们需要这 n 个人相互交互至少 r 轮。另一个局限是,该方案需要在许可环境下实施,也就是说协议必须知道总人数 n ,才能确定合理的门限 t 。这一系列协议包含很多种形式,其中最基本的形式是无分发者的秘密分享 (Secret Sharing)。秘密分享可以将一个秘密字符串分成多个碎片,又称作份额 (Share),只有集齐一定数量的碎片才能将该秘密恢复出来。通常,秘密分享需要有一个可信第三方充当分发者将秘密分成秘密碎片然后分发。而无分发者的含义则是秘密分享的过程不需要这样的分发者,也就是说,更加去中心化了。如图 9 所示,首先是分发阶段,比如说 Bob 把他的选择 ξB 分成三份:sAξB,sBξB,sCξB,这三份中的任意两份都可以恢复出完整的ξB。上角标代表了这个份额发送给的人,例如sCξB表示该份额发送给 Clare。每个人都像 Bob 这样做之后,每个人手上都有 3 份来自包括自己在内的不同的人的份额。例如,Clare 此时手上应该有 sCξA,sCξB,sCξC。此时,每个人再把这些份额拼成份额向量广播给所有人。例如 Clare 会将份额向量sC=[sCξA,sCξB,sCξC]广播给其他两个人。这样每个人只要手里有包括自己在内的两份这样的向量就能恢复出 Alice、Bob 和 Clare 三人的选择,然后就可以算出最终的随机数,例如 Bob 拥有向量sB=[sBξA,sBξB,sBξC]和 sC=[sCξA,sCξB,sCξC]。下角标相同上角标不同的任意两个份额都可以恢复出相应的秘密,例如sBξB和sCξB可以恢复出ξB。由于这一点,我们可以得到 [ξA,ξB,ξC]​,由此算出最终的结果ξ。但是这样的秘密分享方案是有漏洞的,如果秘密分发者——譬如 Bob——在分发份额sAξB,sBξB,sCξB的时候,将其中一份份额sAξB替换为其他的一个任意值,那么收到这个份额的 Alice 在使用该份额进行恢复的时候有可能恢复出错误的 ξB。为了防止这样的攻击,我们需要保证使用的秘密分享方案中包含可以验证秘密份额的步骤。于是,如图 10 所示,我们使用无分发者的公开可验证秘密分享 (Publicly Verifiable Secret Sharing, PVSS)——与第一种相比则是在分发阶段的时候多了一些额外的数据。这些数据就是“证明”,记作 π 。“证明” π 可以被用来检验每个人收到的份额是否和其他人的一致。所有人都会使用这个公开的 π 去验证收到的份额,验证通过就可以说明这个份额确实是和其他发出去的份额是一致的,都是按照正确的规则生成的。第三种方法是分布式密钥生成 (Distributed Key Generation) + 门限签名 (Threshold Signature)。门限签名可以理解为秘密分享应用到了数字签名方案中,但是它又不是单纯将两者相叠加。通常的数字签名方案是,一个人用自己的私钥加密了消息获得签名之后,签名可以被公钥等公开参数验证。而该方案使用的门限签名方案里同样有一对公私钥,但是每个参与者分别只有总私钥的其中一个碎片以及相应的公钥碎片;这些私钥碎片集合起来可以恢复出完整的私钥,公钥碎片同理;每个人可以利用自己的私钥碎片进行签名获得签名碎片,这些签名碎片可以被公钥的相应碎片验证;并且,这些签名碎片中的任意 t 个合起来可以计算出一个总签名,该总签名相当于用总私钥进行签名,因此也能被总公钥验证。故而这样的签名过程并不需要所有人参与,只需要 n 个人中的 t 个人的有效签名即可完成签名过程。而且无论是哪 t 个人参与签名,最后生成的签名是一样的。并且签名过程中涉及到的私钥不会被泄露,每个人分享的只有公钥碎片和自己的签名结果,这使得多轮无交互签名成为可能。当然,这个总的公私钥对以及相应碎片不是任意选取的,它的生成需要所有的 n 个人在协议第一次运行时运行分布式密钥生成协议才能生成有这样的密码学特性的公私钥对及其碎片。因此,这个方案同样存在协议必须要知道总人数 n 的问题。使用Icommon作为随机性来源使用Icommon作为随机性来源,最常见的方法是采用比特币链上未来某一个块的 Hash 值作为Icommon,或者使用当日股票市场上某一支股票的收盘价。但是这个方法的问题在于,输出 O 完全由 Icommon计算得来,攻击者有可能通过操纵 Icommon的值来使得 O 变为他想要的值。如果从Icommon 计算 O 的过程没有那么容易,比如说有可能要耗上一整天,那么攻击者将没有足够的时间去提前预测 O 的值。为了实现这样的需求,我们引入了一个新的密码学工具:可验证延迟函数 (Verifiable Delay Function, VDF)。这样的工具能够使得输出 O 在给定时间 t 内是很难通过输入Icommon 计算出的,即使拥有任意的并行处理器以及多项式级别的提前计算量。同时,输出 O 是唯一的并且可以被公开验证是由 Icommon正确计算得来的。它很像 PoW,但是 PoW 不抗并行处理器及多项式级别的提前计算攻击,也就是说,使用并行处理器能够显著缩小 PoW 的计算时间到远远小于 t。使用 VDF 可以保证在给定时间内全世界没有任何一个人可以预测与给定输入相匹配的输出。以太坊 2.0 已经计划使用 VDF 作为随机数信标。来源:以太坊爱好者

8月1日,Ultrain联合创始人&CEO郭睿、联合创始人&CSO廖志宇做客链得得吐槽大会。在接受群友们的车轮战时,有这么一个问题成为了讨论的核心:超脑链使用的随机可信证明机制(R-POS)中,随机数是如何产生的?是否存在真随机?在密码学中,随机数的概念有着重要的地位,而基于密码学原理的区块链技术中对随机数的应用也在各项目中屡见不鲜。从本质上来说,区块链技术的核心,共识机制就是依托各种方式来选出随机的记账人,以构建一个安全和去中心化的记账体系。以PoW采用的方式来说,所有矿工解一个数学难题,算力高的节点优先解出答案的概率较低算力节点更高。注意,这里是概率更高而已,并不是单纯的对全网所有节点进行算力的比较,低算力节点依然有可能提前算出解,从而获得记账权。这种方式维护了全网中记账权的随机性,让作弊成本变得非常高。PoS中则是将算力竞赛改为了股权竞赛,依然是通过同样的方式来保证记账权的随机分配。DPoS之所以饱受诟病的原因也是如此。在DPoS体系中,为了提高性能,通过超级节点的选举将随机的记账权保持在一个数量极小(往往不超过25)的节点范围内,牺牲了去中心化。那么,在PoW的共识机制中,真的能够做到完全随机吗?根据密码学原理,随机数的随机性检验可以分为三个标准:统计学伪随机性。统计学伪随机性指的是在给定的随机比特流样本中,1的数量大致等于0的数量,同理,“10”“01”“00”“11”四者数量大致相等。类似的标准被称为统计学随机性。满足这类要求的数字在人类“一眼看上去”是随机的。密码学安全伪随机性。其定义为,给定随机样本的一部分和随机算法,不能有效的演算出随机样本的剩余部分,即“不能通过给定的随机序列的一部分而以显著大于二分之一的概率”。真随机性。其定义为随机样本不可重现。实际上只要给定边界条件,真随机数并不存在,可是如果产生一个真随机数样本的边界条件十分复杂且难以捕捉,可以认为用这个方法演算出来了真随机数。相应的,随机数也分为三类:伪随机数:满足第一个条件的随机数。密码学安全的伪随机数:同时满足前两个条件的随机数。可以通过密码学安全伪随机数生成器计算得出。真随机数:同时满足三个条件的随机数。根据真随机性的概念,如果将产生随机数的边界条件变得难以捕捉,这个过程就会更加随机。区块链项目中产生随机数的边界条件包括使用上一个区块的哈希值,上一个区块的时间戳等等。但由此也产生了一些问题:这些信息都是写在上一个区块中的,根据区块中的信息产生一个随机的结果来选出下一个区块,存在循环论证的嫌疑,安全性相对较差。而一般意义上的真随机数发生器往往利用了更加复杂的边界条件来产生随机数。第一个广泛认知上的真随机数发生器是1955年由Rand公司创造的,而在1999年,Intel发布Intel810芯片组时,就配备了硬件随机数发生器,基于IntelRNG的真随机数生成器可以生成满足独立性和分布均匀性的真随机数。目前大部分芯片厂商都集成了硬件随机数发生器,只要安装相应驱动,了解读取寄存器地址,可以直接调用发生器。Intel810RNG的原理大概是:利用热噪声(是由导体中电子的热震动引起的)放大后,影响一个由电压控制的振荡器,通过另一个高频振荡器来收集数据。在区块链世界中,通过复杂的边界条件来获得随机数的案例也有不少。今年1月,加密货币Zcash举行了一个看起来相当惊人的仪式:他们在美国伊利诺伊州和威斯康星州上空的一架小型私人飞机上举行了一个“可信的设置仪式(trusted setup ceremony)”。这个仪式通过在乌克兰切尔诺贝利核设施中心获得的核废料产生辐射,并利用盖革计数器将放射性脉冲转换成了一个“完全随机”的数字,并将其放在了Zcash的代码里。在仪式上,开发人员通过驾驶飞机,确保了恶意参与者不可能在其过程中破坏代码。在上面两个案例当中,随机数都是通过一些难以捕捉的边界条件产生的。纯粹依靠算法是否能够生成真随机数呢?一般认为,由于计算机算法均具备确定的特性,所以真随机数无法由算法来生成。

江苏快三开奖结果 1image

我们生活的环境充满了随机性。一直以来,运气,概率和命运这些概念都与随机性紧紧联系在一起。所有人类无法理解或无法预测的事物往往都被归类为随机事物。从生理上来说,我们也是沉浸在了随机海洋中。从云的运动到粒子和波浪的行为,随机性简直无处不在。

然而,尽管人类接触到了各种各样的随机事物,对随机性很熟悉,但依然难以将它转化为计算机可以使用的东西。当我们谈论计算机系统中的随机性时,我们真正指的是伪随机性,即尽可能模拟出现实世界应有的随机性,使之近乎于“真正的随机性”。以密码学安全伪随机数生成器为例,这是一个非常强大的随机性模拟。

随机数在隐私技术和密码学中发挥着重要作用。令人惊艳的是,通过生成一个随机数来对一条消息进行异或运算,提供了一种简单但十分强大的加密方案。即使是双方之间最简单的私人通信形式(即双方提前共享密钥的对称加密方案)也要求共享的密钥是随机的。如果此共享密钥不是随机的,则加密就毫无用处,因为任何知道密钥生成算法的人都可以确定密钥然后解密该条消息。

随机数的重要性不仅体现在安全通信渠道的建立上,还体现在确认通信对象上。如果多个人试图通过有限带宽的频道来互相通信,则可以利用随机数来确定频道携带消息的合理顺序。

随机数能够有效帮助团体或计算机达成一致协议或共识。随机共识协议就是这样一个例子。本文将探讨随机数在区块链中的作用。

区块链就是一个多方尝试就全局视角的某种更新达成一致的成功案例。更新通常在一轮内完成,也就是在一个周期性离散时间间隔内。

在互联网上,特定时间段内发送的消息数量是有上限的,并且发送消息必将花去一定的时间,这都对共识造成了一定的限制。任何区块链共识协议的目标是在上述限制范围内达成一致协议。在公链上有数千个节点参与了区块链的维护,如果每个节点需要向所有其他节点发送消息并获得其反馈,那么网络的限制会大大增加达成共识的成本。这是因为在一轮时间内通过网络发送的消息数量太大。因此,为了确保共识,则需要通过减少在互联网上发送消息的数量来优化通信方案。

比特币达成此协议的方式是通过使用 工作证明作为随机数源来确定每一轮中哪一个区块将会被添加到区块链中,从而减少消息传递的费用。因为 PoW 设置的题目在算法上非常难解决,只有最先算出来的人才能将他们的区块添加到分类帐中。由于多个人同时解开难题的概率非常低,因此 PoW 可以作为一种限制网络消息传递数量的机制。

理论上,任何试图取代 PoW 的共识机制都需要找到一种方法来限制网络传递消息的数量。大多数权益证明协议用于解决该问题的方法是根据验证者持有的代币数量来选出一组验证者(维护与管理区块链的节点)组成一个小组委员会,然后这组验证者可以在网络限制内相互通信并及时达成一致。

当然,为了公平选举出小组委员会的成员,保证没有人会提前知道成员的身份,算法必须能够融入一些公平、无偏倚的(unbiasable)随机数源。一旦该组验证者在下一个区块上达成了一致,那个区块就会被广播给网络中的每一个人。

在 PoS 协议中用于小组委员会选举的理想随机数源必须是不可支配的(unbiasable),即没有人可以随意改变随机种子。为了实现不可支配性,随机性协议需要确保以下两点:

  • 随机函数总会生成一些随机数;

  • 随机函数生成的随机数没有被操纵

(注意:我们在之后的博客文章中将会探讨 i)与ii) 之间的权衡,以及这种权衡与网络同步模型的关系)

我们在 Mechanism Labs 上分析过的所有小组委员会选举协议都没有满足上面提到的两点。因此,鉴于上述权衡,区块链共识协议应该使用能不断产生随机数的随机数源,而不是使用仅能一次性产生不可支配的随机数的随机数源。因为区块链协议需要确保区块链保持增长、不能让随机数源成为瓶颈。即使是偏好一致性的协议,随机数源也不应该成为区块链停滞的原因。无论如何,随机数源都应该确保协议能够专注于应付其他攻击,比如对验证者组成的小组委员会实施 DoS 攻击使得区块链停滞等等。

如果区块链由于随机函数输出的随机数出现了偏差而完全停止运行,那么社交层就得付出巨大的协调成本来重新启动区块链。这将要求社区通过外部的社交媒体平台就区块链实际上是什么的问题达成一致,而这会是一个非常耗时的讨论,此成本可与当初解决 DAO 黑客攻击的成本相当。社交层的巨额成本也会动摇社区对区块链协议安全性的信心,但只要偏差非常小并且具备从偏差状态恢复的机制,那么几轮的小偏差对区块链安全性的影响就比较微弱,因为公有区块链协议每一轮给予验证者的所有协议奖励是相对较少的。每一轮或每一个时期进行小组委员会选举时,随机函数中的偏差必须非常显著,验证者才能以欺骗协议来牟利并降低区块链协议的安全性。

而在另一个领域内,那些用到随机数的彩票游戏必须保证随机数源绝对不被操纵,因为即使出现一点偏差也会完全改变中奖结果。由于中奖者能够获得大量的即时奖励,所以篡改彩票结果带来的影响是巨大的。因此,这种彩票游戏偏好于一次性生成不可支配随机数的函数,即使这意味着随机函数的输出有时会停止。

本文将探讨基于区块链协议设计的背景下公正无偏的随机数源的重要性。接下来的文章中,当我们考虑不可篡改的协议时,我们是倾向于不会被中止的协议。

理想的委员会选举方案 应该满足 i)不可被支配,ii)只在新一轮开始时显示随机种子。随机函数必须如前文讨论的定义那样做到不可被偏转。如果随机数被操控(并存在协议内奖励分配机制),就会造成不公平的奖励分配。不恰当的奖励分配意味着一些人将获得更丰厚的奖励。由于只有拥有权益的人才能成为验证者,并且投票权与验证者所拥有的权益成正比,那么不公平的分配将导致区块链最终只掌控在少数验证者手里。因此,协议的不可操纵的程度,决定了是否有人可以长期作为验证者维护部分网络。另一方面,种子在新一轮开始之前提前多久显示,决定了谁可以首先成为网络的一部分。由此可见,上述两个属性将决定区块链的去中心化程度。

由于每一轮都会进行小组委员会的选举,因此从公布随机函数输出的随机数到那一轮开始所需的时间是至关重要的。在此时间范围内,攻击者可以利用随机函数输出的随机数得知哪些验证者获选。如果此输出被隐藏,则试图攻击区块链协议的攻击者将无法提前得知获选的验证者。此时间范围的长短决定了协议对攻击的承受能力。较强的攻击者,即具有较多计算能力和资源去攻击网络的人,能够在短时间内计算出获选的验证者。如果攻击者有足够的时间,他们会通过运行选举委员会所用的算法以及该轮给定的随机数种子来确定哪些验证者当选,然后对该轮获选的验证者进行拒绝服务攻击,导致空白区块的产生,令该轮无任何进展。对区块链来说,即使是停止一轮,后果也是毁灭性的。设想一下,如果几小时内世界上没有人可以进行任何交易,比特币会变成什么样!因此,有能力抗 DoS 攻击的节点才应该首先成为验证者。另外,提前显示种子也意味着共识协议只能应对较弱的攻击者,这弱化了区块链的去中心化性质。

基于我们曾在 替代性共识协议的元分析 中剖析的不同区块链协议的使用案例,下面我们会从技术角度详细介绍各种随机数的生成机制。

Tendermint

Tendermint 是使用一种确定的循环协议方案来选出提议者的;该协议不具备随机性。提议者是根据投票权和验证者被选次数的堆排序算法选出的。攻击者只能通过添加或删除权益来干预协议,但这种干预不能立即生效,因为验证者在系统中移除或者添加权益所需的时间很长。尽管如此,攻击者就可以有更长的时间提前计划好如何操纵提议者的选择。

使用确定性的随机算法意味着随机种子会在远早于每一轮之前公布,提议者也能被提前确定。

Algorand

Algorand 的随机数方案如下:被选为提议者的每一位验证者 v 使用公式 < seedr, π > ← VRFskv (seedr−1||r) 来计算 r 轮的种子,其中 skv 是验证者 v 的密钥,seedr-1 是前一轮的随机种子。

VRF 是用来证明 r-1 轮中接受的区块包含了 π 以及 r 轮的种子。如果给定的 VRF 证明未能验证给定的种子,则每个人计算新一轮的种子 H(seedr−1||r),其中 H 是哈希函数。这意味着必须提前选好每位验证者的密钥,确保他们无法干预随机种子。

当网络不能很好地同步时,攻击者完全控制了消息传递链接(校对注:感觉这里像在说“异步”假设),因此可以删除提议的区块并强制用户支持空白的区块,从而计算出未来用于选举的随机种子。因此,Algorand 要求 弱同步 假设,即在每个时间长度为 u 的周期中,必须存在时间长度为 s的强同步来保证协议的不可操纵性。只要 s 值足够大,使得在时间段 b 内至少产生一个诚实的区块,则选择密钥 skv' 的攻击者 v' 就不能操控 r 轮的随机种子。

只有当一个区块被提议之后,才会生成一个新的随机数种子,和一个可用来验证的公开 VRF 证明。这确保了提议者和随机种子没有被提前泄露,同时保证 Algorand 能够抵御针对提议者的 DoS 攻击,即使在节点离线甚至瞬间腐化的模式下都能实现自适应安全。

Dfinity

江苏快三开奖结果,对于大部分协议,攻击者通常会中止协议来调用回退机制,从而操纵随机数。但 Dfinity 使用的门限签名方案(threshold scheme)是不可操纵的,因为选择阈值的原则就是确保攻击者无法通过阻止生成 门限签名 来中止协议(因为随机数种子是从门限签名中推导出来的)。因此阈值 t 必须根据以下公式进行选择:t∈[f + 1,n - f],其中 f 是攻击者控制的签名数,n 是方案中的总签名数,t 是用于生成随机数的签名阈值。选择该阈值是为了确保攻击者既无法预测签名生成的结果,也无法阻止签名的生成。

需要注意的是,在任何 BLS 方案中,只要攻击者拥有 50% 以上 的保证金,他们就能够操控最终的签名与随机数。然而,如果一名攻击者拥有如此大份额的权益,也会出现其它类型的攻击,这种情况就违反了 Dfinity 协议的基本假设。

一旦诚实的验证者进入到第 r 轮,随机种子就会被揭示。虽然从诚实的验证者进入到新一轮正式开始之间的时间差很小,但这个时间差足以让具有大量计算资源的攻击者识别出提议者并对其进行 DoS 攻击。这就是为什么 Dfinity 只能应对温和的攻击者而无法应对瞬时瘫痪的状况。

Thunderella

在哈希函数实例化的随机数预言机方案中,提议者将依据以下公式来确定:H_nonce < Dp,其中 H 是用作随机数预言机的哈希函数,pk 是验证者的公钥, q 是给定的迭代时间,nonce 是哈希函数的熵来源。Nonce 由前一个区块的提议者选择。设置难度参数 D_p 是为了在单个迭代时间内,委员会成员被选为提议者的概率为 w。

如果攻击者提议了一个区块,她可以操控为下一轮哈希函数生成熵的 nonce 值,从而影响下一个区块的提议者的人选。然而,为了降低随机数方案的可篡改性,在哈希函数中相同的 nonce值不仅仅用于选择下一轮的提议者,也会用于选择接下来 r 个轮次的提议者。这使得攻击者在计算上很难通过强制改变 nonce 值来让自己连续成为接下来 r 个轮次的提议者。虽然这种策略仅损失了多项式安全性,但它具有可预测性的弊端。该方案仅能够应对慢速自适应的攻击者。

在上述算法中,当重复使用相同的 nonce 值给哈希函数喂送种子时,就会导致攻击者能够提前预测到谁是提议者。由于在一时期中相同的 nonce 值被重复用作熵,从而导致随机种子在新一轮开始之前被泄露,使得攻击者可以对提议者进行腐化或者实施 DoS 攻击。

Casper FFG

Casper FFG 计划使用的随机数方案是基于以下算法:

一个时期开始时,每个验证者承诺 H (H ))),其中 S 是验证者承诺的种子。 R 赋值为 R 与哈希函数内原象的异或运算(R := R⊕ Pre-image of the inner layer of hash)。在一轮中,验证者可以创建或中止一个区块。

如果在回退机制中没有生成随机数,这可能会造成比可预测或可操纵的随机数更大的问题,因为你将不再需要 1/3 的恶意者来中止协议,1个人就足够了。

作为当前提议者的验证者是知道下一轮的随机种子的。

随机数是密码学和区块链的重要部分。不良的随机数方案会通过以下方式破坏区块链的安全性:i)停止区块链协议;ii)导致中心化。 因此,在理解区块链的安全性时,探究随机性在该区块链协议中的角色乃是重中之重!

内容来源:公众号-以太坊爱好者

原文链接:

作者: Aparna Krishnan

翻译&校对: 哲妹 & 阿剑

江苏快三开奖结果 2image

本文由江苏快三开奖结果发布于区块链,转载请注明出处:读懂区块链与数字货币,区块链中的随机数【江

关键词:

上一篇:江苏快三开奖结果莫让区块链才具变为,区块链

下一篇:没有了