本篇文章是上一篇文章《区块链上的随机性概述与构造》的延续。本文会介绍以下四个项目：Algorand、Cardano，Dfinity和Randao分别是如何利用三种基本的方案构建随机数生成协议的。注意本文并不会专门详细解释这四个项目的共识算法，只会介绍最基本的框架以帮助读者理解共识协议和随机数算法之间的联系。
原文标题：《区块链上的随机性项目分析》文章来源：公众号NPC源计划作者：邱飞旸
Algorand
Algorand项目使用了基于PoS的混合共识协议，其共识过程利用了随机抽签。它的随机抽签所依赖的种子，从本质上讲，是通过取前t(t=1)个输入来生成的，对应v3.0b版本的第一种方式。如图1所示，Algorand的共识过程要求节点先在本地抽签，即通过一个可验证随机函数(VerifabaleRandomFunction,VRF)在节点的本地算出来一个可验证的确定的随机数。VRF可以被看作是一种特殊的伪随机数发生器。需要补充的一点是，这里的“确定”指的是，这样的随机数是无法被用户操纵的，因为输入是被唯一确定不受用户控制的。这是由于，其输入是根据上一轮随机数生成过程的公共信息以及每个节点自己的私钥。其中私钥是可以被公钥验证的；公共信息是每个人都可以看到，是唯一确定的，并且可被其他人验证。本地抽签得到本地随机数之后，每个人会立马知道自己是否被选中。之后，被选中的人广播抽签结果、证明和候选区块到全网节点，根据区块的quality大小，选出来候选区块，而确定哪个区块的quality更大是需要做拜占庭共识的。这个时候，就需要再进行一轮本地抽签，所有的节点会自己知道是否被选中去做BA*，即投票选自己认为的quality最高的候选区块，投票会进行很多轮，每一轮都要重新进行一次本地抽签，以增加安全性。可以看出，Algorand共识的本质就是我们每个人都生成一个确定的随机数。但是我们最终只想要一个随机数，这样我们才能根据最后确定的唯一的随机数去决定哪个块会被全网接受。这个时候的方案就是根据某种确定的规则从众多备选结果中取一个，方法是通过拜占庭共识达成一致。
图1：Algorand的共识协议
图2：VRF
Cardano
Cardano是基于Ouroboros的一个项目，采用了基于PoS的共识协议。Ouroboros这篇论文给出了一个可证明安全的PoS协议框架，但是并没有给出具体的实现，实现由Cardano完成。因此这里主要讲解Cardano在工程上采用的一个具体的方案。Cardano所采用的方案也在第一篇所讲的三种方式之中。如图4所示，它的方案其实就是就是无分发者的秘密分享承诺。图3简单描述了它的共识协议，在它的GenesisBlock里面会初始化一个随机数，这样就可以利用确定的抽签算法以这个随机数作为随机信标来确定谁的区块会在之后的某个slot里被接受。slot的数量是固定的，因此，有可能有的slot中会有不止一个节点被抽中，也有可能没有节点被抽中，具体解决方案不在本文讨论范围内。那么，初始化的随机数是怎么生成的呢？Cardano协议首先采用了标准的承诺-揭示方案，不过在之后多了一个将随机数做一次无分发者的公开可验证秘密分享(PubliclyVerifiableSecretSharing,PVSS)的步骤。即分发碎片并且广播证明之后揭示随机数。这时也许有参与者会跑路，没有揭示随机数，但是没有关系，这个时候剩下的参与者可以通过广播碎片把跑路的参与者的随机数恢复了。因此，这是一个有一定冗余度的随机数生成机制，但是同时带来了一定的健壮性。通过这个机制，只要恶意节点不超过一半，一定可以生成一个随机数。
图3：Cardano的共识协议
图4：Cardano的DRB模型
Dfinity
Dfinity的共识算法和Algorand很像，如图5所示，协议里同样需要选举一个委员会，委员会会运行分布式随机信标(DistributedRandomnessBeacon,DRB)协议得到随机数种子。至于这个协议我们后文会讲，为了理清共识协议的基本步骤，我们先假设DRB协议可以达成这些功能。通过这个随机数种子，加上每个节点自己的私钥，每个节点通过运行可验证随机函数(VRF)就可以算出自己的排名。同时，由于所有节点都会被分组，那么每一个节点应该被分配到哪一个组也是由随机数种子决定的。在所有的组中，再次通过随机数种子随机挑选出一个组，称之为该轮的委员会。每个节点有了自己的节点排名后，所有节点都可以提交候选区块，广播给所有的节点，但是大家在广播的过程中，诚实节点就会根据排名，给目前为止它收到的最高的块签名，签好后，广播给所有的节点，如果某一个区块获得1?2以上的合法签名，这个区块被称之为已验证的区块。一旦诚实节点收到已验证的区块，这一轮就会立马结束，并将这个已验证区块广播给所有其他节点。
图5:Dfinity的共识协议
由此可见，DRB协议生成的随机数种子至关重要。Dfinity所采用的DRB协议实际上就是v3.0b的第三种方法——分布式密钥生成门限签名。首先要有一个DKG协议来生成符合一定要求的总密钥对和密钥对份额，这个协议同样可以是(t,n)门限的。通过这个协议，每个人获得密钥对份额，但是没有人知道总私钥是什么。每个节点使用自己的私钥份额对再上一个轮次的随机数和轮次进行签名，签完名将签名结果广播，每个节点都可以用总公钥验证每个签名。然后通过门限签名的恢复算法使用t个签名恢复出来这一轮的总签名。整个过程的算法都是完全确定的，唯一不确定的是每个节点不知道其他节点的私钥份额是什么。Dfinity比较特殊的地方在于采用基于BLS的门限签名，比起其他的门限签名方案，好处有两个。第一个好处就是一次购买，终生免费。协议只需要在一开始的阶段运行一次DKG，进行密钥生成。之后的阶段只需要n个人中t个人提交有效的签名就可以生成随机数，协议就可以运行下去，这个过程是异步的。第二个好处就是确定性，无论哪t个人提交，最后生成的随机数都是一样的确定的结果，没有节点可以操纵最后的结果。
图6:Dfinity的DRB模型
Randao
Randao是基于以太坊合约的，用于在链上生成智能合约可用的随机数的一个项目。它采用的是v3.0a的方案。每个人在提交承诺的时候，都需要提交m个ETH的押金，揭示过程会持续w个区块时间。这里有三件事需要说明。第一点是，同一个地址的多个承诺只接受第一次。第二点是收集的全网提交的承诺数有最小数量的要求，如果没有收集到最够的数量，整个协议就会以失败的状态结束，然后再重新开始。第三点就是不按时揭示的地址的押金会被没收，并且一旦有人不揭示，协议就会以失败的状态结束，这样做为了确保随机数的公平性。协议的最后一步是Randao特别加入的——返还押金，给参与者奖励的步骤，其目的是给出激励，构建生态。
图7：Randao的DRB模型
随机数与共识
随机数生成与共识协议有着千丝万缕的关系，主要体现为以下两点。
防止女巫攻击的方法之一是不可预测的随机抽签。不论是PoW，还是PoS，我们都可以理解为一种随机抽签的方法。不管公有链上的共识协议再怎么设计，包括比特币在内，都是在通过某种方式产生一定的随机性。矿工通过PoW竞争出块，使得出块的人变得不确定，从而防止了通过伪装大量节点获利的女巫攻击。
区块链上的随机数安全依赖于共识协议。以Randao为例，针对Fomo3D的攻击同样对Randao有效。由于以太坊的激励机制和共识协议的特点，矿工会优先打包手续费高的交易，所以攻击者可以通过CensorshipAttack，人为调整打包区块时包含的交易，或者制造高手续费的垃圾交易，迅速的把区块的GasLimit耗光，阻止其他人的特定交易上链。当Randao即将计算出的结果不理想时，可以通过这种方式强行将协议终止，令无辜的节点蒙受损失，自己从中获利。尽管这样的手段有时成本较高，但这样的攻击仍然有无法忽略的可能性发生，而这样的攻击之所以成立的原因，实际上根植于共识协议的设计。再例如GrindingAttack。Fomo3D采用了取上一个块的哈希值作为种子的方法生成随机数。这种情况下，矿工可以把所有的区块组织的可能性都试验出来，然后选择一种对自己最有利的方式打包交易。这种攻击手段就是GrindingAttack。尽管这样的攻击手段有一定的成本，但是如果随机数所牵涉的利益足够，例如用在某些游戏里，矿工想要从中获利非常容易。
因此，区块链上随机数的生成是需要上下文环境的，必须要给定情景。拿Randao来讲，如果它的某一个随机数的生成，只和0.01个ETH相关，那么攻击者将没有足够的理由去破坏它的公平性。如果押金不够多，那么Randao就有可能是不安全的。
参考文献
Gilad,Yossi,etal.“Algorand:Scalingbyzantineagreementsforcryptocurrencies.”Proceedingsofthe26thSymposiumonOperatingSystemsPrinciples.ACM,2017.
“CardanoSettlementLayerDocumentation.”Cardano.Web.21Apr.2019.
Kiayias,Aggelos,etal.“Ouroboros:Aprovablysecureproof-of-stakeblockchainprotocol.”AnnualInternationalCryptologyConference.Springer,Cham,2017.
Hanke,Timo,MahnushMovahedi,andDominicWilliams.“Dfinitytechnologyoverviewseries,consensussystem.”arXivpreprintarXiv:1805.04548(2018).
YoucaiQian.“Randao:VerifiableRandomNumberGeneration.”Randao.Web.21Apr.2019.
来源链接：blog.priewienv.me
本文来源于非小号媒体平台：
NPC源计划
现已在非小号资讯平台发布1篇作品，
非小号开放平台欢迎币圈作者入驻
入驻指南：
/apply_guide/
本文网址：
/news/3627211.html
免责声明：
1.资讯内容不构成投资建议，投资者应独立决策并自行承担风险
2.本文版权归属原作所有，仅代表作者本人观点，不代表非小号的观点或立场
下一篇：
NuCypher工程师告诉你，链上私人数据如何安全存储与管理
郑重声明： 本文版权归原作者所有， 转载文章仅为传播更多信息之目的， 如作者信息标记有误， 请第一时间联系我们修改或删除， 多谢。