Algorand 系列一：VRF 密码学抽签原理及其在 Algorand 中的应用

YOUChainResearch

YOUChain研究团队，成员毕业于国内外顶级名校，有长期的工业界经验。我们持续跟踪的区块链学界和业界的前沿发展，致力于深入区块链本质，推动学术和技术发展。团队诚邀加密、算法、区块链、工程人才加入！

本文来自

1VRF介绍

随着Algorand项目的发起，原来越多的人对其所应用到的密码学抽签技术产生了兴趣并探索相关的应用。目前，随着Algorand项目的主网上线，该技术也开始了接受大规模的正式实践检验，我们拭目以待。

目前虽然国内已经有大量文章对VRF技术进行了一些介绍，但是目前看都不够全面深入。因此我们「YOUChainResarch」打算重新梳理，希望能尽可能全面地介绍该技术，作为我们「Algorand技术解析系列」系列文章的开篇，与大家分享及交流探讨。

1.1简介

VRF全称为VerifiableRandomFunctions，翻译为“可验证随机函数”，由SilvioMicali，MichaelRabiny，SalilVadhan于1999年提出，是一种基于公私钥的密码学哈希函数。。只有拥有VRF私钥才能计算哈希，但任何拥有对应公钥的人都可以验证该哈希的正确性。

VRF的一个关键应用就是，提供对存储在基于散列的数据结构中的数据的隐私保护，防止离线枚举。在这种应用中，证明人持有VRF私钥，并使用VRF哈希在输入数据上构造基于散列的数据结构。由于VRF的性质，只有证明人才能回答关于数据结构中是否存储了某些数据的查询。任何知道VRF公钥的人都可以验证证明人正确地回答了查询。但是，不能对数据结构中存储的数据进行脱机推断(即不查询验证器的推断)。

简单来说，可验证随机函数可以基于私钥对一个输入，产生一个唯一的固定长度的输出，以及一个对应的证明。其他人在知道了公钥、输出、证明之后就一定能验证这三者的正确性，并且也只有在知道了这三者之后才能验证其正确性。

上面提及的这个过程以及相关的数据，是符合若干安全特性的，接下来会具体描述。

在VRF论文发出来后，到目前已有不同的团队做出了不同的实现。而IETF目前正在为VRF的实现制定标准，目前还处于草案阶段，并于2019-2-8已发布第四版草案。链接见文后参考部分。

1.2基本算法表述

从一个概要逻辑来说，VRF总共涉及到几个相关函数，联合起来完成一个证明和验证的闭环。

首先简单定义一下标识符：

SK：VRF的私钥PK：VRF的公钥alpha:VRF的输入，将对其进行哈希beta:VRF哈希输出pi:VRF证明Prover:持有VRF公私钥的人就可以称为证明人Verifier:只持有VRF公钥的人，可以称为验证人VRF的基本算法，是很简单清晰的，如下：

前提是有一个秘钥对生成算法，来生成VRF需要用到的公私钥对；证明人计算输入的哈希：beta=VRF_hash(SK,alpha);>注意，VRF_hash算法是确定性的，对于相同的私钥及相同的输入，必定生成一个相同的输出。证明人还需要用私钥及输入计算一个证明：pi=VRF_prove(SK,alpha)验证人通过对应的公钥可以验证结果的正确性：VRF_verify(PK,alpha,pi)实际实现中，上面2和3可以放在一起，得到如beta,pi=VRF(SK,alpha)这样的函数。

Algorand 基金会任命 Anil Kakani 为印度地区负责人:金色财经报道，Algorand 基金会任命 Anil Kakani 为印度地区负责人，Kakani 将领导 AlgoBharat 团队和 Algorand 在印度的所有编程和项目，包括大学教育项目、社区项目以及私人和公共合作伙伴关系。

据悉，Kakani 此前在华盛顿特区的公共和私营部门担任过多个职务，包括担任美国财政部的印度高级顾问，在那里他建立了美国财政部和印度财政部之间的第一个双边伙伴关系。他还曾担任康宁公司印度商业发展总监，并在印度的 Anand Rathi Investment Banking 和美国的 Vikasa Holdings 担任高级领导职务。[2022/11/29 21:10:27]

1.3所需满足的安全特性

基于上一节的内容，还不能理解VRF的本质。如果不考虑相关的安全特性，那上面的实现是没有意义的。那么，VRF需要满足哪些安全特性呢？

总结起来，主要包括3种安全特性：唯一、防碰撞、伪随机。另外，对于IETF的实现标准，即使在秘钥对生成不够可信的情况下，也可以保持“不可预测性”。

1.3.1完全唯一和可信唯一

唯一是指对于任意固定的VRF公钥以及任意的输入alpha，都存在唯一的可被证明有效的输出beta。

完全唯一指在可计算范围内对手不可能找到一个公钥pk，一个输入alpha，以及两个证明pi1和pi2使得VRF_verify(pk,alpha,pi1)输出(VALID,beta1)，VRF_verify(pk,alpha,pi2)输出(VALID,beta2)，而beta1不等于beta2。

一个相对弱一点的安全特性叫可信唯一，对很多应用来说这就够了。可信唯一只在VRF公私钥是以一种值得信任的方式生成的情况下，才满足唯一性，其他就和完全唯一一样。换句话说，如果秘钥对生成方式有问题或者使用了不好的随机数，则唯一性可能无法保证。

直白来说，就是对于特定的一对公私钥，任意一个alpha都有并且只有一对(beta,pi)，不存在说对于某个或某些输出无法生成证明的情况；对于任意特定的alpha，系统中的任何一对公私钥，都能生成唯一的与其他人不相同的(beta,pi)，不存在说对于某些输入有些私钥能构造有效证明但有些私钥却不能构造有效证明的情况。其中可信唯一相对弱一点是在于，对于只满足这个特性的系统来说，可以特意构造某个公钥PK，对于某个输入alpha，可以构造两个或多个不同的证明pi，用该PK都能验证通过。

严格来说，世界上没有绝对的事，上面的表述都是基于密码学安全的意义之上的，就是说只要概率足够小，我们就认为它不会发生，比如概率小于2^{-256}2?256。

由上面表述可以看到，一个好的秘钥对生成算法，对VRF实现的唯一特性的保障是很重要的，这在我们选择某种VRF实现的时候，应该要加以考量。

1.3.2完全防碰撞和可信防碰撞

完全防碰撞是指，对手要找到具有相同输出的两个不同的输入alpha1和alpha2，在计算上是不可能的，即使他知道私钥也是如此。

相对弱一点的安全特性是可信防碰撞，这指的是防碰撞特性需要基于一种可信的生成公私钥的方式。

1.3.3完全伪随机和选择性伪随机

伪随机性确保对手在知道输出beta但是不知道证据pi的情况下，beta是随机的，不可能将其跟一个随机值进行辨别。

更精确地说，假设公私钥(pk,sk)是以一种可信方式生成的。伪随机性确保了即使输入是由对手仔细选择的，对于计算能力有限的对手，只要他不知道私钥，那么输出beta对他而言也是随机不可分辨的。甚至在对手有意选择多个输入并观察对应输出及证明的情况下，也是如此。简单举个例子就是，分别对一组有规律的输入计算其对应的输出，你去观察研究这些输出，不可能找出某种确定的规律。

FAMEEX上线新币种ALGO（Algorand）:据官方消息，FAMEEX于2020年10月20日上线新币种ALGO（Algorand）；平台将于2020年10月20日16点开放ALGO充值，18点开放提现业务；同时，将于10月20日18点开放ALGO/USDT、ALGO/BTC、ALGO/ETH币对交易。[2020/10/20]

举个例子，伪随机特性可以保证，你想要生成一个小于某个值的哈希，然后希望能快速推断出一个输入x使其满足你的要求，这是做不到的。除了按穷举法计算VRF哈希之外，别无捷径。

拥有完全伪随机特性，则允许对手在任意时刻选择输入。直白但可能不够准确地说，就是不管你什么时候给一个什么样的输入给我，你都无法知道我对该输入产生的输出哈希是大于还是小于某个值。

选择性伪随机是一个弱一点的安全特性，对于很多应用来说这也是足够的。这时，对手选择目标输入需要独立于VRF公钥，并且要在他观察到他选择的alpha'所对应的beta'和pi'之前。直白但可能不够准确地说，就是你知道了我的公钥以及我曾经的一些(alpha,beta,pi)信息，然后你特意构造一个新的输入，这时你可能可以知道我对该输入的VRF输出将会大于或小于某个值，而不用等我真正告诉你结果。

需要记住，VRF的输出beta对证明人来说，是不随机的。他们只要将beta和VRF_hash(sk,alpha)的结果进行比较，就可以轻易地将beta和一个随机值区分出来。

同时，对于任何知道了对应pi的人，beta看起来也是不随机的。只要检查VRF_verify(PK,alpha,pi)是否返回(VALID,beta)，就可以将beta跟一个随机值区别开。

还有，如果VRF秘钥对不是用可信方式生成的，那么beta也可能看上去不是随机的。

1.3.4一个“类随机预言机”的不可预测特性

上面提到的伪随机性，在秘钥是由对手特意生成的情况下，是不满足的。例如，如果对手输出的秘钥是确定地生成的，那么任何人都很容易获得VRF的输出。

然而，在一些VRF应用中，存在一种不同类型的不可预测性。这种特性类似于由一种密码学哈希函数所提供的不可预测性：如果输入具有足够的熵，那么正确的输出也是均匀不可辨别的。

虽然关于此特性在密码学文献中既没有正式的定义，也没有证明，但在IETF中呈现的VRF实现方案中，只要公钥是以一种可信任的方式生成的，那么就可以相信满足了这个特性。额外地，如果公钥满足一些特定验证过程，那么即使公钥不是可信方式生成的，ECVRF也满足此特性。

1.4几种实现方式概述及选择考量

VRF都是基于非对称加密技术来构建的，当前主流的非对称加密技术，有RSA和椭圆曲线密码学这两种。这两种技术都可以用于构建VRF实现。

具体实现就不做详细介绍了，感兴趣的还是以参考IETF的标准为主。

一般而言，一个基于RSA的VRF实现，能满足可信唯一、可信防碰撞和完全伪随机特性。不过，RSA方案的一个问题是，要起到足够的安全性，则RSA的秘钥长度需要比较长，这在很多应用场景下都不是很理想。

而目前，在非对称加密领域，椭圆曲线加密是越来越被重视、越来越成为主流的非对称加密技术。因此，对于VRF的实现也应该尽量选用基于椭圆曲线的实现方案，这种方案可简称为ECVRF。

ECVRF在具体实现时，可以有很多细分方案，包括选用不同的椭圆曲线、选用不同的将消息映射到曲线上的点的算法、选用不同的随机数生成算法等等。

一般而言，ECVRF能满足可信唯一、可信防碰撞和完全伪随机特性，并且，如果在接收到一个VRF公钥时，做一些额外验证以验证公钥的有效性，那么ECVRF就能满足完全唯一和完全防碰撞特性。

动态 | Algorand发布透明度报告，新投入流通1.26亿枚Algo:金色财经报道，Algorand基金会今日发布了针对2019年11月2日至2020年2月10日的透明度报告。在该报告所述期间，Algorand基金会投入流通的Algo总数约为1.26亿，低于前一时期注入流通的4.5亿。其中1.01亿Algo用于奖励所有Algo持有者，也是迄今为止占通证分发总额最大比例的部分；二是市场分发，约1700万Algo，是用于为运营提供资金，建立生态系统和社区，支持研究和开发，以及加速通证流通和去中心化建设；三是节点奖励，740万Algo，2019年11月2日至12月31日为暂停解锁期；四是用于Algorand基金会董事会和咨询委员会成员的报酬共计12.5万Algo；五是用于推进大使项目和社区合作，共31.2万Algo。报告称，正如“Algo Dynamics”所述，Algorand基金会承诺在2020年将出售不超过1.5亿Algo。[2020/2/13]

1.4.1额外讨论：关于椭圆曲线的选择

椭圆曲线是由如下形式方程式所定义的曲线：y^2=ax^3bx^2cxdy2=ax3bx2cxd

其中，可用于密码学用途的椭圆曲线有很多，曾几何时，最主流的曲线及相关算法都是由NIST选定和推荐的，称为NIST-P系列，比如广泛使用的P-256曲线。这种情况持续到了2013年，那一年，一个叫“爱德华·斯诺登”的牛人曝光了NSA的棱镜计划，其中曝光了NIST标准中一个基于椭圆双曲线的随机数生成器，叫Dual_EC_DRBG，包含后门，这可以使掌握该后门的NSA只根据生成器过去所产生的随机数样本，就可以预测后续的随机数输出，这样的随机数，对我们来说是伪随机的，对NSA来说是可预测的。这个事件引起了人们对NIST的信任危机，虽然这个Dual_EC_DRBG跟NIST-P的加密算法没有直接联系，人们可以使用其他的伪随机数生成算法，但是人们发现NIST-P曲线中都存在一些来历不明的没有任何说明的随机数种子，比如下面的常数：

P-224:bd71344799d5c7fcdc45b59fa3b9ab8f6a948bc5

P-256:c49d360886e704936a6678e1139d26b7819f7e90

P-384:a335926aa319a27a1d00896a6773a4827acdac73

这时，一个新的曲线就闪亮登场了：Curve25519。Curve25519/Ed25519/X25519是著名密码学家DanielJ.Bernstein在2006年独立设计的椭圆曲线加密/签名/密钥交换算法，和现有的任何椭圆曲线算法都完全独立。这些算法在开始的时候乏人问津，但在2013年之后一下子变得炙手可热，成为绝对的主流已是大势所趋了。

这一方面是因为这套算法完全开放设计，没有任何秘密，没有任何可疑的参数；同时，这套算法确实足够优秀，足够安全。此外，还有点题外话，这位Bernstein之前还曾因为将自己设计的加密算法Snuffle发布到网上而遭到美国政府起诉，他抗争了6年，最后还是美国政府撤销了指控，但之后他还反诉政府，直到2003年底法院驳回他的诉讼，要他在政府制造了“具体威胁”之后再来。

关于算法的安全性，Bernstein进行了全面的考察，结果见下面截图，具体参见这里：

safecurves

目前Curve25519/Ed25519已得到广泛应用，人们正在全面抛弃NIST，拥抱Curve25519，应用情况可参见：https://ianix.com/pub/curve25519-deployment.html和https://ianix.com/pub/ed25519-deployment.html。

动态 | Algorand 将于今日完成v2.0.2网络升级:Algorand 将于区块高度 3,705,466 完成 Algorand v2.0.2 网络升级（目前区块高度为 3,701,530，预计于今日达到升级区块高度）。据 Algorand 社区《Algorand v2.0.2 Release Notes》公告，此次升级是为了在达到投票数之后，延长节点升级到新共识版本的时间。[2019/12/16]

1.5VRF与数字签名算法方案的区别

对于刚接触VRF的人来说，可能很容易产生一个疑问：非对称数字签名算法，跟VRF有什么区别？或者说，非对称数字签名算法起不到VRF的作用吗？

在非对称加密领域，存在数字签名算法，对于一对秘钥来说，可以计算消息m的签名s=SIG(sk,m)，然后知道公钥的人可以验证s是否确实是签名者用私钥对m的签名：Verify(pk,m,s)。另外，通过密码学哈希算法，也能得到消息m的哈希值。

因此，这就跟VRF比较像了：

私钥拥有者可以声明自己的签名结果s，其他人通过公开信息可以验证该声明；

s是不可预测的，这具有密码学上的安全性；可以再通过对s进行密码学哈希，得到一个不可预测的哈希值。

那么为什么还需要VRF呢，直接用数字签名的方案不行吗？关于此问题，主要原因是，VRF相比于数字签名方案，具有前面所描述的更多安全特性。对于数字签名方案，有以下主要缺陷：

签名结果s不是唯一的！对于很多数字签名方案，同一个私钥对同一个消息，可以给出不同的签名。比如对于EdDSA，如果s=SIG(sk,m)，那么s\ells?也会是一个有效的签名，其中\ell?是对应椭圆曲线基点的阶。

s是不可预测的，但是s不一定是伪随机的。也就是说，s在取值范围内的分布可能不是均匀的。

对于上面第1点，当然存在一些特定的数字签名实现，比如将中的数字签名方案中的随机数，使用中的GGM伪随机预言机代替之后，数字签名可以是唯一的。但是人们没办法确认签名者是否采用了这么一种方案，因此也就是说唯一性是无法保证的。

无法保证唯一性的数字签名方案，可以认为是一种“可验证不可预测函数”，但不是“可验证(伪)随机函数”。

2AlgorandVRF密码学抽签算法及应用

2.1抽签算法原理剖析

2.1.1抽签原理

基于VRF的密码学抽签算法用于根据每个用户的权重，随机选出用户的一个子集。整个抽签过程中，需要保证：

不存在上帝角色操纵整个抽签；每个参与者独立做自己的抽签，在主动公布自己的抽签结果之前，其他任何人都不可能知道该抽签结果；参与者公布自己的抽签结果后，系统中的其他参与者都可以验证该结果，参与者不需要泄漏自己的私钥；在一轮抽签开始之前，任何参与者都不能预先计算自己的抽签结果；抽签对所有参与者都是公平公正的；防女巫攻击。具体做法就是，假设参与者ii的权重是w_iwi?，所有参与者的权重总和W=\sum_i{w_i}W=∑i?wi?，对于具体的抽签目的，我们设置一个期望值tt，表示在所有的权重当中，希望抽出tt份权重。这样，我们基于“伯努利试验”的抽签方式，按p=\frac{t}{W}p=Wt?的概率，让每个参与者ii依据自己的权重w_iwi?做w_iwi?次抽签，这样所有参与者就总共做了WW次抽签，抽签结果将是符合二项分布的。

接下来，需要做的就是构造这个“伯努利试验”，这就用到了VRF。首先，要求每个参与者都拥有一对公私钥，(pk_i,sk_i)(pki?,ski?)，然后，为了满足前面提到的要求，还需要定义一个种子seed，以及标识抽签阶段的一些数据，比如round。其中，需要尽可能让参与者在开始某一轮抽签的时候，才知道所用到的seed，这个根据具体的应用场景来定。

金色晚报 | 中国区块链大数据交易实验室正式启动 区块链公司Algorand获6200万美元的风险投资:印度近58%组织在招聘区块链等IT人才；NULS成为“公有链技术联盟”首批合作伙伴；粤港澳大湾区区块链产业达成战略合作。更多晚报内容，请查看图片。[2018/10/24]

这时，就可以基于VRF构建我们的“伯努利试验”了。设x是由seed、round等组成的抽签参数，则参与者先计算x的VRF哈希及证明：hash,pi=VRF_{sk_i}(x)hash,pi=VRFski??(x)。这时得到的哈希的长度是固定的，比如32字节，由VRF的安全特性，我们知道hash是在区间内均匀分布的，将该哈希值变为一个小数，即d=\frac{hash}{2^{256}}d=2256hash?，这时dd就在区间之间均匀分布。

另外，已知以概率p做n次伯努利试验，实际成功次数为k次的概率，计算公式如下：\binom{n}{k}p^k(1-p)^{n-k}(kn?)pk(1?p)n?k

将k=0...j所对应的概率加起来，假设用Sum(j)表示，我们找到一个j值，使其满足式子Sum(j)\led\ltSum(j1)Sum(j)≤d0j>0时表示抽中了jj份权重。

由于用户的权重越大，即w越大，其抽签次数就越多，从而基于相同的概率p，得到j>0j>0的概率也就会越大，因此，用户被选中的概率是跟他们的权重是成比例的。另外，当j>0j>0，我们可以想象成用户有jj个子用户被抽中了，如果是投票，就可以投jj票。这样一来，w个权重为1的用户，有j个被抽中的概率，跟1个权重为w的用户，有j个子用户被抽中的概率，是一样的。也就是说，这种抽签是防女巫攻击的。

最后，对于验证者来说，他可以基于VRF验证机制，验证抽签参与者的哈希及证明，验证通过之后，执行相同的抽签计算，看结果j'j′跟jj是否一致。

2.1.2抽签算法

对应前面的描述，抽签算法如下：\begin{aligned}&\text{VrfSortition}(sk,seed,round,role,t,w,W):\\&\quad\langlehash,\pi\rangle\getsVRF_{sk}(seed\|role\|round)\\&\quadp\gets\frac{t}{W}\\&\quadj\gets0\\&\quadwhile\frac{hash}{2^{hashlen}}otin\bigg[\sum_{k=0}^{j}B(k;w,p),\sum_{k=0}^{j1}B(k;w,p)\bigg)\do\\&\quad\\big\lfloor\j\\&\quadreturn\\langlehash,\pi,j\rangle\\\end{aligned}?VrfSortition(sk,seed,round,role,t,w,W):?hash,π?←VRFsk?(seed∥role∥round)p←Wt?j←0while2hashlenhash?∈/?[k=0∑j?B(k;w,p),k=0∑j1?B(k;w,p))do?jreturn?hash,π,j??其中，sksk为用户私钥，rolerole参数和roundround参数用于区分共识过程中的角色与阶段，一个阈值t用于确定本次抽签所期望选中的用户数。hash,\pihash,π分别为VRF哈希值及证明。

3.2抽签验证算法

验证过程算法描述如下：\begin{aligned}&\text{VrfVerifySortition}(pk,seed,round,role,\pi,t,w,W):\\&\quadifegVerifyVRF_{pk}(hash,\pi,seed\|role\|round)\then\return\0;\\&\quadp\gets\frac{t}{W}\\&\quadj\gets0\\&\quadwhile\frac{hash}{2^{hashlen}}otin\bigg[\sum_{k=0}^{j}B(k;w,p),\sum_{k=0}^{j1}B(k;w,p)\bigg)\do\\&\quad\\big\lfloor\j\\&\quadreturn\j\\\end{aligned}?VrfVerifySortition(pk,seed,round,role,π,t,w,W):if?VerifyVRFpk?(hash,π,seed∥role∥round)thenreturn0;p←Wt?j←0while2hashlenhash?∈/?[k=0∑j?B(k;w,p),k=0∑j1?B(k;w,p))do?jreturnj?验证过程先验证\piπ是否合法有效，然后依据与抽签类似的过程获得用户被选中的子用户数(0表示根本没被抽中)，从而与用户随消息广播出来的j值做比较以验证其正确性。

2.2抽签结果的概率分布

根据前面的描述，我们知道整个VRF密码学抽签算法，是概率性的，概率符合二项分布。也就是说，给定期望值t，实际结果k是不固定的。在这种情况下，密码学抽签怎么应用与具体的场景，那就得具体情况具体分析了。

在这里，我们先看一下如何计算抽签结果的概率分布。如果总权重W是比较小的，从而概率p是比较大的，那这时直接用二项分布公式进行计算就可以了。

但如果W很大，那就要考虑别的方式了。首先，再列一下二项分布概率公式：\binom{U}{K}p^K(1-p)^{U-K}(KU?)pK(1?p)U?K将其展开得如下式子：\frac{U!}{K!(U-K)!}(\frac{t}{U})^K(1-\frac{t}{U})^{U-K}=\frac{U\dots(U-K1。{U^K}\frac{t^K}{K!}(1-\frac{t}{U})^{U-K}K!(U?K)!U!?(Ut?)K(1?Ut?)U?K=UKU…(U?K1)?K!tK?(1?Ut?)U?K

由于K是个比较小的值，当U很大时，下面的等式是可以接受的；或者换个方式说，当U大到我们可以接受如下式子的时候，U就足够大了：\frac{U\dots(U-K1。{U^K}=1UKU…(U?K1)?=1另外，U足够大时，我们肯定还能接受如下等式。其中分子转换成常数e的指数，这是根据指数函数的定义来的。(1-\frac{t}{U})^{U-K}=\frac{(1-\frac{t}{U})^U}{(1-\frac{t}{U})^K}=\frac{e^{-t}}{1}=e^{-t}(1?Ut?)U?K=(1?Ut?)K(1?Ut?)U?=1e?t?=e?t综合起来就得到当U很大，且期望为t时，实际抽签结果为K的概率为：\frac{t^K}{K!}e^{-t}\quad\quad\text{(1。K!tK?e?t(1)

2.3在区块链中的应用及要解决的问题

Algorand项目开创了密码学抽签算法在区块链中的应用，主要用在两种场景下：通过抽签获得区块提议者；通过抽签获得区块验证委员会。

对于第一种场景，期望值t应该是比较小的，主要需要考虑的是，实际抽签结果k应该以很高的概率大于0，同时k又不应该很大。Algorand给出了一个值t=26，这时k在1到70之间的概率为：\sum_{k=1}^{70}\frac{26^k}{k!}e^{-26}>1-10^{-11}k=1∑70?k!26k?e?26>1?10?11

对于第二种场景，就比较复杂了。除了单纯抽签概率上的考虑，还要考虑网络中恶意用户或者说拜占庭节点的影响，以及投票通过的阈值。

根据Algorand的分析，假设网络中诚实用户所占的权重比例为h，委员会期望权重为t，由上面的公式，可以得到最终诚实权重为k的概率为：\frac{(ht)^K}{K!}e^{-ht}\quad\quad\text{(2。K!(ht)K?e?ht(2)

在一个存在拜占庭节点的投票委员会中，设投票通过的阈值为r，则要保证系统的活性即能完成投票，需要满足下面的条件1：

条件1：\#good>t*r#good>t?r>\#good#good表示诚实票数

通过上面的概率公式，这个条件不满足的概率是可以计算出来的，不满足的概率为:\sum_{K=0}^{t*r}\frac{(ht)^K}{K!}e^{-ht}K=0∑t?r?K!(ht)K?e?ht

另外，考虑拜占庭节点，要保证系统的安全性，假设#bad表示不诚实的票数，那么要保证安全性就要满足下面的条件：

条件2：\frac{1}{2}\#good\#bad\let*r\,21?#good#bad≤t?r

对于条件2，抽取#good=K并且#bad=L的概率如下：\frac{(ht)^K}{K!}e^{-ht}\frac{((1-h)t)^L}{L!}e^{-(1-h)t}K!(ht)K?e?htL!((1?h)t)L?e?(1?h)t

条件2不满足的概率是不大好算的，实际评估时，我们可以先计算条件2满足的概率，公式为:\sum_{K=0}^{2t*r}\sum_{L=0}^{\frac{2*t*r-K}{2}}\frac{(ht)^K}{K!}e^{-ht}\frac{((1-h)t)^L}{L!}e^{-(1-h)t}K=0∑2t?r?L=0∑22?t?r?K??K!(ht)K?e?htL!((1?h)t)L?e?(1?h)t

用1.0减去计算结果，可得到条件2被违背的概率。>当然，先计算概率大的情况时，计算精度会降低。

上面两个条件均不满足的概率需要极小极小，才可以认为不会影响系统的活性和安全性。举个浅显的例子就是：假设定下来t=100,r=0.7,h=0.8。那么投票阈值就是70，但是由于抽签结果的概率性，那么如果抽签结果不足70，那就完不成投票了，如果抽签结果大于140，那在网络不好的情况下是不是可能出现分歧呢？另外，由于总体诚实比例只有0.8，那也有可能抽签结果中不诚实数直接就超过70，那也可能搞乱整个投票，这时，确切地说就是条件2的情况。

综上，理论上来说，活性和安全性都是无法绝对保障的，但是可以考虑一个很小的概率F，当两个条件被违背的概率均小于F时，我们可以认为这样的事件基本不会发生。

这个F跟t,r,h都有一定的负相关关系，就是t,r,h中任意两个值不变的情况下，第三个值越大，F就越小。例如，r,h不变时，t越大，F越小。

还有一个问题，t也不是越大越好的。t很大时，虽然可以使F很小，但是在一个分布式网络中，t越大则完成投票所需要的通信量也就越大，所以这需要权衡考虑。

以上，就是本文分享的所有内容了。至于Algorand项目中是如何权衡相关问题的，敬请关注后续分享。

参考

VerifiableRandomFunctions

https://www.odaily.com/post/5133096

https://tools.ietf.org/pdf/draft-irtf-cfrg-vrf-04.pdf

https://datatracker.ietf.org/doc/draft-irtf-cfrg-vrf/

ShafiGoldwasser,SilvioMicali,andRonaldL.Rivest.Adigitalsignatureschemesecureagainstadaptivechosen-messageattacks.SIAMJournalonComputing,17(2):281–308,April1988.

ShafiGoldwasser,SilvioMicali,andCharlesRack-off.Theknowledgecomplexityofinteractiveproofsystems.SIAMJournalonComputing,18(1):186–208,February1989.

curve25519

https://en.wikipedia.org/wiki/Daniel_J._Bernstein

https://en.wikipedia.org/wiki/Bernstein_v._United_States

https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number

http://cr.yp.to/djb.html

http://cr.yp.to/ecdh.html

https://safecurves.cr.yp.to/

https://ianix.com/pub/curve25519-deployment.html

https://en.wikipedia.org/wiki/Dual_EC_DRBG

Algorand-ScalingByzantineAgreementsforCryptocurrencies

标签：ALGLGOALGORACAlgebra0xAlgoalgo币最新官方消息RACA

SHIB热门资讯