区块链算法抽签区块链抽奖算法

波场币 2023年02月26日 14:01 252 0

本篇文章主要给网友们分享区块链算法抽签的知识，其中更加会对区块链抽奖算法进行更多的解释，如果能碰巧解决你现在面临的问题，记得关注本站！

知链区块链金融应用实践平台成绩怎么算

1. 工作量证明（PoW）

中本聪在2009年提出的比特币（Bitcoin）是区块链技术最早的应用，其采用PoW作为共识算法，其核心思想是节点间通过哈希算力的竞争来获取记账权和比特币奖励。PoW中，不同节点根据特定信息竞争计算一个数学问题的解，这个数学问题很难求解，但却容易对结果进行验证，最先解决这个数学问题的节点可以创建下一个区块并获得一定数量的币奖励。中本聪在比特币中采用了HashCash[4]机制设计这一数学问题。本节将以比特币采用的PoW算法为例进行说明，PoW的共识步骤如下：

节点收集上一个区块产生后全网待确认的交易，将符合条件的交易记入交易内存池，然后更新并计算内存池中交易的Merkle根的值，并将其写入区块头部；

在区块头部填写如表1.1所示的区块版本号、前一区块的哈希值、时间戳、当前目标哈希值和随机数等信息；

表1.1 区块头部信息

随机数nonce在0到232之间取值，对区块头部信息进行哈希计算，当哈希值小于或等于目标值时，打包并广播该区块，待其他节点验证后完成记账；

一定时间内如果无法计算出符合要求的哈希值，则重复步骤2。如果计算过程中有其他节点完成了计算，则从步骤1重新开始。

比特币产生区块的平均时间为10分钟，想要维持这一速度，就需要根据当前全网的计算能力对目标值（难度）进行调整[5]。难度是对计算产生符合要求的区块困难程度的描述，在计算同一高度区块时，所有节点的难度都是相同的，这也保证了挖矿的公平性。难度与目标值的关系为：

难度值=最大目标值/当前目标值（1.1）

其中最大目标值和当前目标值都是256位长度，最大目标值是难度为1时的目标值，即2224。假设当前难度为，算力为，当前目标值为，发现新区块的平均计算时间为，则

根据比特币的设计，每产生2016个区块后（约2周）系统会调整一次当前目标值。节点根据前2016个区块的实际生产时间，由公式（1.4）计算出调整后的难度值，如果实际时间生产小于2周，增大难度值；如果实际时间生产大于2周，则减小难度值。根据最长链原则，在不需要节点同步难度信息的情况下，所有节点在一定时间后会得到相同的难度值。

在使用PoW的区块链中，因为网络延迟等原因，当同一高度的两个区块产生的时间接近时，可能会产生分叉。即不同的矿工都计算出了符合要求的某一高度的区块，并得到与其相近节点的确认，全网节点会根据收到区块的时间，在先收到的区块基础上继续挖矿。这种情况下，哪个区块的后续区块先出现，其长度会变得更长，这个区块就被包括进主链，在非主链上挖矿的节点会切换到主链继续挖矿。

PoW共识算法以算力作为竞争记账权的基础，以工作量作为安全性的保障，所有矿工都遵循最长链原则。新产生的区块包含前一个区块的哈希值，现存的所有区块的形成了一条链，链的长度与工作量成正比，所有的节点均信任最长的区块链。如果当某一组织掌握了足够的算力，就可以针对比特币网络发起攻击。当攻击者拥有足够的算力时，能够最先计算出最新的区块，从而掌握最长链。此时比特币主链上的区块大部分由其生成，他可以故意拒绝某些交易的确认和进行双花攻击，这会对比特币网络的可信性造成影响，但这一行为同样会给攻击者带来损失。通过求解一维随机游走问题，可以获得恶意节点攻击成功的概率和算力之间的关系：

图1.1 攻击者算力与攻击成功概率

2. 权益证明（PoS）

随着参与比特币挖矿的人越来越多，PoW的许多问题逐渐显现，例如随着算力竞争迅速加剧，获取代币需要消耗的能源大量增加，记账权也逐渐向聚集了大量算力的“矿池”集中[6-9]。为此，研究者尝试采用新的机制取代工作量证明。PoS的概念在最早的比特币项目中曾被提及，但由于稳健性等原因没被使用。PoS最早的应用是点点币（PPCoin），PoS提出了币龄的概念，币龄是持有的代币与持有时间乘积的累加，计算如公式（1.4）所示。利用币龄竞争取代算力竞争，使区块链的证明不再仅仅依靠工作量，有效地解决了PoW的资源浪费问题。

其中持有时间为某个币距离最近一次在网络上交易的时间，每个节点持有的币龄越长，则其在网络中权益越多，同时币的持有人还会根据币龄来获得一定的收益。点点币的设计中，没有完全脱离工作量证明，PoS机制的记账权的获得同样需要进行简单的哈希计算：

其中proofhash是由权重因子、未消费的产出值和当前时间的模糊和得到的哈希值，同时对每个节点的算力进行了限制，可见币龄与计算的难度成反比。在PoS中，区块链的安全性随着区块链的价值增加而增加，对区块链的攻击需要攻击者积攒大量的币龄，也就是需要对大量数字货币持有足够长的时间，这也大大增加了攻击的难度。与PoW相比，采用PoS的区块链系统可能会面对长程攻击（Long Range Attack）和无利害攻击（Nothing at Stake）。

除了点点币，有许多币也使用了PoS，但在记账权的分配上有着不同的方法。例如，未来币（Nxt）和黑币（BlackCion）结合节点所拥有的权益，使用随机算法分配记账权。以太坊也在逐步采用PoS代替PoW。

3. 委托权益证明（DPoS）

比特币设计之初，希望所有挖矿的参与者使用CPU进行计算，算力与节点匹配，每一个节点都有足够的机会参与到区块链的决策当中。随着技术的发展，使用GPU、FPGA、ASIC等技术的矿机大量出现，算力集中于拥有大量矿机的参与者手中，而普通矿工参与的机会大大减小。

采用DPoS的区块链中，每一个节点都可以根据其拥有的股份权益投票选取代表，整个网络中参与竞选并获得选票最多的n个节点获得记账权，按照预先决定的顺序依次生产区块并因此获得一定的奖励。竞选成功的代表节点需要缴纳一定数量的保证金，而且必须保证在线的时间，如果某时刻应该产生区块的节点没有履行职责，他将会被取消代表资格，系统将继续投票选出一个新的代表来取代他。

DPoS中的所有节点都可以自主选择投票的对象，选举产生的代表按顺序记账，与PoW及PoS相比节省了计算资源，而且共识节点只有确定的有限个，效率也得到了提升。而且每个参与节点都拥有投票的权利，当网络中的节点足够多时，DPoS的安全性和去中心化也得到了保证。

4. 实用拜占庭容错算法（PBFT）

在PBFT算法中，所有节点都在相同的配置下运行，且有一个主节点，其他节点作为备份节点。主节点负责对客户端的请求进行排序，按顺序发送给备份节点。存在视图（View）的概念，在每个视图中，所有节点正常按照处理消息。但当备份节点检查到主节点出现异常，就会触发视图变换（View Change）机制更换下一编号的节点为主节点，进入新的视图。PBFT中客户端发出请求到收到答复的主要流程如图4.1所示[10] [11]，服务器之间交换信息3次，整个过程包含以下五个阶段：

图4.1 PBFT执行流程

目前以PBFT为代表的拜占庭容错算法被许多区块链项目所使用。在联盟链中，PBFT算法最早是被Hyper ledger Fabric项目采用。Hyperledger Fabric在0.6版本中采用了PBFT共识算法，授权和背书的功能集成到了共识节点之中，所有节点都是共识节点，这样的设计导致了节点的负担过于沉重，对TPS和扩展性有很大的影响。1.0之后的版本都对节点的功能进行了分离，节点分成了三个背书节点(Endorser)、排序节点(Orderer)和出块节点(Committer)，对节点的功能进行了分离，一定程度上提高了共识的效率。

Cosmos项目使用的Tendermint[12]算法结合了PBFT和PoS算法，通过代币抵押的方式选出部分共识节点进行BFT的共识，其减弱了异步假设并在PBFT的基础上融入了锁的概念，在部分同步的网络中共识节点能够通过两阶段通信达成共识。系统能够容忍1/3的故障节点，且不会产生分叉。在Tendermint的基础上，Hotstuff[13]将区块链的块链式结构和BFT的每一阶段融合，每阶段节点间对前一区块签名确认与新区块的构建同时进行，使算法在实现上更为简单，Hotstuff还使用了门限签名[14]降低算法的消息复杂度。

5. Paxos与Raft

共识算法是为了保障所存储信息的准确性与一致性而设计的一套机制。在传统的分布式系统中，最常使用的共识算法是基于Paxos的算法。在拜占庭将军问题[3]提出后，Lamport在1990年提出了Paxos算法用于解决特定条件下的系统一致性问题，Lamport于1998年重新整理并发表Paxos的论文[15]并于2001对Paxos进行了重新简述[16]。随后Paxos在一致性算法领域占据统治地位并被许多公司所采用，例如腾讯的Phxpaxos、阿里巴巴的X-Paxos、亚马逊的AWS的DynamoDB和谷歌MegaStore[17]等。这一类算法能够在节点数量有限且相对可信任的情况下，快速完成分布式系统的数据同步，同时能够容忍宕机错误（Crash Fault）。即在传统分布式系统不需要考虑参与节点恶意篡改数据等行为，只需要能够容忍部分节点发生宕机错误即可。但Paxos算法过于理论化，在理解和工程实现上都有着很大的难度。Ongaro等人在2013年发表论文提出Raft算法[18]，Raft与Paxos同样的效果并且更便于工程实现。

Raft中领导者占据绝对主导地位，必须保证服务器节点的绝对安全性，领导者一旦被恶意控制将造成巨大损失。而且交易量受到节点最大吞吐量的限制。目前许多联盟链在不考虑拜占庭容错的情况下，会使用Raft算法来提高共识效率。

6. 结合VRF的共识算法

在现有联盟链共识算法中，如果参与共识的节点数量增加，节点间的通信也会增加，系统的性能也会受到影响。如果从众多候选节点中选取部分节点组成共识组进行共识，减少共识节点的数量，则可以提高系统的性能。但这会降低安全性，而且候选节点中恶意节点的比例越高，选出来的共识组无法正常运行的概率也越高。为了实现从候选节点选出能够正常运行的共识组，并保证系统的高可用性，一方面需要设计合适的随机选举算法，保证选择的随机性，防止恶意节点对系统的攻击。另一方面需要提高候选节点中的诚实节点的比例，增加诚实节点被选进共识组的概率。

当前在公有链往往基于PoS类算法，抵押代币增加共识节点的准入门槛，通过经济学博弈增加恶意节点的作恶成本，然后再在部分通过筛选的节点中通过随机选举算法，从符合条件的候选节点中随机选举部分节点进行共识。

Dodis等人于1999年提出了可验证随机函数（Verifiable Random Functions，VRF）[19]。可验证随机函数是零知识证明的一种应用，即在公私钥体系中，持有私钥的人可以使用私钥和一条已知信息按照特定的规则生成一个随机数，在不泄露私钥的前提下，持有私钥的人能够向其他人证明随机数生成的正确性。VRF可以使用RSA或者椭圆曲线构建，Dodis等人在2002年又提出了基于Diffie-Hellman 困难性问题的可验证随机函数构造方法[20]，目前可验证随机函数在密钥传输领域和区块链领域都有了应用[21]。可验证随机函数的具体流程如下：

在公有链中，VRF已经在一些项目中得到应用，其中VRF多与PoS算法结合，所有想要参与共识的节点质押一定的代币成为候选节点，然后通过VRF从众多候选节点中随机选出部分共识节点。Zilliqa网络的新节点都必须先执行PoW，网络中的现有节点验证新节点的PoW并授权其加入网络。区块链项目Ontology设计的共识算法VBFT将VRF、PoS和BFT算法相结合，通过VRF在众多候选节点中随机选出共识节点并确定共识节点的排列顺序，可以降低恶意分叉对区块链系统的影响，保障了算法的公平性和随机性。图灵奖获得者Micali等人提出的Algorand[22]将PoS和VRF结合，节点可以采用代币质押的方式成为候选节点，然后通过非交互式的VRF算法选择部分节点组成共识委员会，然后由这部分节点执行类似PBFT共识算法，负责交易的快速验证，Algorand可以在节点为诚实节点的情况下保证系统正常运行。Kiayias等人提出的Ouroboros[23]在第二个版本Praos[24]引入了VRF代替伪随机数，进行分片中主节点的选择。以Algorand等算法使用的VRF算法为例，主要的流程如下：

公有链中设计使用的VRF中，节点被选为记账节点的概率往往和其持有的代币正相关。公有链的共识节点范围是无法预先确定的，所有满足代币持有条件的节点都可能成为共识节点，系统需要在数量和参与度都随机的节点中选择部分节点进行共识。而与公有链相比，联盟链参与共识的节点数量有限、节点已知，这种情况下联盟链节点之间可以通过已知的节点列表进行交互，这能有效防止公有链VRF设计时可能遇到的女巫攻击问题。

7. 结合分片技术的公式算法

分片技术是数据库中的一种技术，是将数据库中的数据切成多个部分，然后分别存储在多个服务器中。通过数据的分布式存储，提高服务器的搜索性能。区块链中，分片技术是将交易分配到多个由节点子集组成的共识组中进行确认，最后再将所有结果汇总确认的机制。分片技术在区块链中已经有一些应用，许多区块链设计了自己的分片方案。

Luu等人于2017年提出了Elastico协议，最先将分片技术应用于区块链中[25]。Elastico首先通过PoW算法竞争成为网络中的记账节点。然后按照预先确定的规则，这些节点被分配到不同的分片委员会中。每个分片委员会内部执行PBFT等传统拜占庭容错的共识算法，打包生成交易集合。在超过的节点对该交易集合进行了签名之后，交易集合被提交给共识委员会，共识委员会在验证签名后，最终将所有的交易集合打包成区块并记录在区块链上。

Elastico验证了分片技术在区块链中的可用性。在一定规模内，分片技术可以近乎线性地拓展吞吐量。但Elastico使用了PoW用于选举共识节点,这也导致随机数产生过程及PoW竞争共识节点的时间过长，使得交易延迟很高。而且每个分片内部采用的PBFT算法通讯复杂度较高。当单个分片中节点数量较多时，延迟也很高。

在Elastico的基础上，Kokoris-Kogias等人提出OmniLedger[26]，用加密抽签协议替代了PoW选择验证者分组，然后通过RandHound协议[27]将验证者归入不同分片。OmniLedger。OmniLedger在分片中仍然采用基于PBFT的共识算法作为分片中的共识算法[28]，并引入了Atomix协议处理跨分片的交易，共识过程中节点之间通信复杂度较高。当分片中节点数量增多、跨分片交易增多时，系统TPS会显著下降。

Wang等人在2019年提出了Monoxide[29]。在PoW区块链系统中引入了分片技术，提出了连弩挖矿算法（Chu ko-nu mining algorithm），解决了分片造成的算力分散分散问题，使得每个矿工可以同时在不同的分片进行分片，在不降低安全性的情况下提高了PoW的TPS。

区块链算法抽签区块链抽奖算法

区块链抽签是什么意思?

区块链抽签意思如下：

以网易区块链抽奖服务为例，网易联合杭州互联网公证处，搭建基于区块链的可信抽签系统，为用户分配区块链上的唯一专用抽奖码，并通过区块链智能合约自动生成抽奖结果。其中该平台抽奖算法已通过测评机构关于其随机性、公平性、稳定性等的专业测试。

在此过程中，杭州互联网公证处全程监督、存证，对护航抽签全程透明可信、结果公平公正进行护航。该平台目前应用场景包括车房摇号、活动抽奖、游戏规则制定、新品发售等不同的场景。

简评三个基于VRF的共识算法

上交所技术公司朱立

Algorand、Dfinity和Ouroboros Praos三个共识算法（Dfinity虽然是项目名，这里用来称呼其共识算法也应无不妥）近期较受关注，而且都是基于VRF(Verifiable Random Function) 设计，可以对照学习。Algorand的版本很多，以下单指 1607.01341v9 ，暂称其为Algorand'（笔者手中另有Algorand的最新版本，其中已对下文提及的几处问题完成了修正，可与本文参看）。

一、VRF的共性

VRF的意义很好理解——用以完成出块人（群）的随机选择。为此，VRF的返回值应尽力难以预测。先看Algorand'和Dfinity的套路是怎么做的：大体上是先将前一个随机数（最初的随机数却是协议给定的）和某种代表高度、轮次的变量进行组合，用某种私钥对之进行签名（或者是先签名再组合），最后哈希一下得出最新的随机数。这样产生的随机数旁人很容易验证其合乎算法，"V"就这样得到了；而哈希返回值又是随机分布的，“R”也因此得到保证。在此过程中，为降低操纵结果的可能性，有两个注意事项： A) 签名算法应当具有唯一性，也就是用同一把私钥对同样的信息进行签名，只有一个合法签名可以通过验证——普通的非对称加解密算法一般不具备这个属性，如SM2。如果用的签名算法没有这种uniqueness属性，那在生成新随机数的时候就存在通过反复多次尝试签名以挑出最有利者的余地，会降低安全性。 B) 避免在生成新随机数时将当前块的数据作为随机性来源之一，比如引用本块交易列表的merkle root值等等，因为这样做会给出块人尝试变更打包交易顺序、尝试打包不同交易以产生最有利的新随机数的余地。在设计和检视新的共识算法时，以上两个注意事项是要特别留意的。

考察一下VRF的返回结果应该如何运用。目前所见用法中，VRF的返回结果可以用来公开完成节点或节点群体的选择，也可以私密地完成选择。以Dfinity为例，它是利用mod操作来唯一、公开地确定一个Group。Algorand'、Ouroboros Praos是私密选择的范例，大致套路是对VRF的最新返回值，配上轮次等变量后用私钥进行签名并哈希，如果哈希值小于某个阈值，节点就可以私密地知道自己被选中。这种方法很可能在网络节点数较多时的表现会更稳定，否则幸运儿个数上下波动会较大，进而影响协议表现，包括空块和分叉。

二、简评强同步假设版本的Algorand'

私密选择提供了较强的抗击定点攻击的能力，但由于幸运儿的总数对于任何一个幸运儿都是不能预知的，也因此给后续共识算法的设计和区块链的优化带来了困难。Algorand‘采用了很强的同步网络假设（同步网络假设下的共识算法当然容易做一些），要求预先知道网络消息传播时间的上限：在固定时间内完成对固定比例的用户的网络传播。比如要知道，1KB消息，在1秒钟内完成全网95%的传播，而1MB消息需要1.5分钟完成全网95%的传播。但这个传输上限应该如何选择？通过一段时间的统计结果再乘以一个系数这种经验统计？只能说“感觉上可以”，但如果要严谨和安全，Algorand‘算法应该补充证明即使在遭遇DDOS或互联网拥堵的情况下消息传播严重超限后算法仍然能够保证安全——然而这个证明是缺失的。作为对照，Ouroboros Praos公开承认之前在同步网络假设下设计的Ouroboros协议在异步网络条件下会出错，所以才又做了Ouroboros Praos；新版本的Algorand承认在弱同步网络时会在不同的块上达成共识（后续网络恢复强同步时分叉可以得到解决）云云，这些都可资参考。

即使我们暂且认可Algorand'算法可以通过设定一个很大的传播时间上限来回应上述问题，但随之而来的是此时可以看出此算法缺乏一个非常好的特性：Responsiveness。这个特性指的是：若一个协议被设计为在一个较大的传播时间上限DELTA下工作，但若实际传播时间是较小的delta，则协议的实际推进步调将只和delta有关，这种协议被称为Responsive的。具有Responsive特性的共识算法再配以同步网络假设会非常理想——出于安全，上限可以设置很大，然而协议执行速度只和当时网络条件有关。Algorand'并不具有这种特性。平均而言，Algorand'完成共识所需的消息传送次数是11轮，每轮如果要确保安全，完成共识的时间就会很长，单个分区的吞吐量就不会太高。当然，架构设计涉及很多取舍，最终评价一个算法好还是不好还是要回到初心——准备拿来实现的目标是什么。上述分析只是尝试客观地指出Algorand'算法的几个少为人知的固有特征，供读者自行评估。

三、简评Dfinity的可扩展性问题

私密选择并且立即上任的做法，也给系统分片带来了极大挑战。Dfinity是明确要做分片(Sharding)的，所以必须直面挑战。可扩展性问题非常复杂，完整解决这个问题需要通盘考虑网络、存储、计算三方面的可扩展性——时下大多数区块链3.0项目只注意到计算的分片和可扩展性，忽略了其余二者，从而不可能真正实现理想的扩展。由于公链节点网络带宽的制约，计算合约所需的数据通常很难迅速地从一个节点拷贝到另一节点，所以就算用VRF实现了飘忽来去的出块节点选择，存储节点是没法同样飘逸如风的。明显的选择有那么几个：全部节点存储全部数据，不同节点静态地分配用来存储不同分区。前者的可扩展性很差，对于后者而言，如果出块节点漂浮不定且出块节点还需要完成合约运算，就意味着基于P2P网络来回远程访问存储，性能多半急剧下降；动态决定的出块节点只完成排序共识，计算能力和存储捆绑，通过静态分区提供可扩展性，可能是合理的应对。然而，最可恨的就是“然而”二字——即使如此，系统还存在一处对存储和网络构成压力的所在：最终用户提交的待打包交易。普通公链（先不考虑EOS那种）的带宽有限，如果用户提交的待打包交易必须粗放型地全网泛滥传播，那现有网络带宽可以提供多少TPS？如果出块节点是静态分区或者至少提前一段时间公开知晓，事情尚有回旋余地；如果出块节点是如此飘忽不定，而且直到最后一刻也只有这些节点自己知道，那无论是用户还是出块节点候选人看起来最直接的应对之道就是全网泛滥传播全部待打包交易、保存全部待打包交易，这样带宽和存储仍然成为系统瓶颈。

所以这里碰到的，本质上还是安全、可扩展性、去中心化的不可能三角。

四、简评Ouroboros Praos

BM怼 Ouroboros的文字已经流传广泛。BM的话当然有些明显是不对的，比如Ouroboros的DPOS是指"Dynamic [stake distribution] POS"而不是BM的Delegate POS，但其关于Pareto分布的评论则值得玩味。如果我们仔细浏览后出的Ouroboros Praos，可以发现协议的安全假设和安全证明完全没有考虑经济博弈因素，因此洋洋洒洒的证明很可能会不得要领而错过真正需要防护的方向——毕竟一直以来POS/DPOS这些协议的血管里面流淌的就是基于经济博弈和人性进行设计的血液。最明显的例子是在forward secure signature的实现方法上，协议目前的设计是要求每个好的节点自觉主动地安全删除用过的私钥，而完全没有考虑近乎零的私钥保存成本如何面对bribe attack的诱惑，然而这却是值得考虑的。除了形式化证明之外，Ouroboros Praos本身并没有太多值得关注的协议特征，总体上就是用VRF抽签结合POS算法并针对某些安全假设进行了形式化证明，其做事的态度是非常值得赞赏的。

五、总结

这几个算法本身颇有创意，也很值得学习。与此同时，在看过以太坊CASPER目前披露的分区技术后，笔者的体会是：区块链3.0的竞争才刚刚开始，从以太坊团队的技术路线看，他们的技术考量和选择要比很多宣称要超越以太坊的团队来得深刻和全面。如果当真要超越以太坊，还是应该先从理解以太坊开始。

顺便感谢趣链邱炜伟博士对本文的贡献！