李无知

algorand中区块的生产者proposer是随机选举产生的，但是又不要完全无规律的随机，algorand带有pos性质，比如A和B同时参加proposer的选举，其中A质押了1Token， B质押了10Token，B选举成功的概率应该是A的约十倍左右。

总的来说，algorand希望proposer的选举具备以下性质：

1. 随机性，每一轮的proposer选举本身是随机的
2. pos特性，质押数越多的，选举成功概率越大

algorand采用了VRF加二项式分布随机数算法达成此效果。

VRF前面讲过，用于产生随机数，解决了proposer选举中的随机性，现在要解决的就是pos特性了，algorand中采用了二项分布随机数的方式来处理该问题。

二项分布算法

1. 二项分布场景

当满足以下几个条件时，就属于二项分布场景：

1. 是否要进行固定次数的尝试
2. 每次尝试是否只有两种结果：成功/失败
3. 成功的概率是否固定的
4. 每次尝试之间是独立的，结果不相互影响

用掷骰子来举例，骰子有六个面，掷到数字6的比例为1/6。

现在有个问题：掷一百次骰子，要求十次掷到6，概率是多少？

我们用前面四个条件来看该问题是否属于二项分布场景：

1. 是否要进行固定次数的尝试？

是的，尝试100次

2. 每次尝试是否只有两种结果：成功/失败？

是的，结果要么为6要么不是6

3. 成功的概率是否固定的？

是的，单次掷到6的概率固定为为1/6

4. 每次尝试之间是独立的，结果不相互影响？

是的，上一次掷骰子的结果不影响下一次掷骰子的结果

因此该问题属于二次分布场景。

2. PMF, CDF算法

二次分布场景中我们关注PMF, CDF算法：

• PMF算法:掷一百次骰子，要求十次掷到6，概率是多少？
• CDF算法：掷一百次骰子，要求十次或十次以内掷到6，概率是多少？意思掷到6的次数小于等于10次就满足条件，比如或者1次，9次，6次就满足条件。反之掷到11次6就不满足条件

我们这里关注cdf，用一个公式来表示cdf算法就是：r = cdf(n, p, k)

• n是尝试次数，比如掷100次骰子，n为100
• p是单次成功的概率，比如掷到6的概率，p为1/6
• k对应多少次以内成功，比如上面例子中，k为10
• r为计算出来的概率值

3. 逆变换运算

在公式r = cdf(n, p, k)中，固定n,p,k值，可以计算出r值。

那同样的，固定n, p, r值，也能计算出k，这种运算叫做逆变换运算。

在逆变换运算的基础上，可以计算二项分布随机数，基本思路是：

1. 固定n, p， 随机产生r，r由于代表着概率，要求值在0～1之间
2. 根据r计算出k

由于r是随机的，k对应也有随机性，二者是从二项分布算法中计算出来的，因此k叫做二项分布随机数。

4. 二项式分布随机数的应用

在固定n, p, 随机产生r的情况下，产生k值。这种应用在实际生活中使用比较有限。

但仔细观察cdf公式，会发现，如果固定r和p，则n越大，k越大。

可以在一些网上cdf产生器中试一下，比如https://homepage.divms.uiowa.edu/~mbognar/applets/bin.html：

• p = 0.1, n=20, k = 2, 则r=0.67693
• p = 0.1, n=200, k = 21, 则r=0.64835

如果固定p，随机r，则会观察到一种现象：n越大，k有较高的可能性越大，这个现象非常符合一种加权随机场景：

• 做某件事成功的概率是固定的。即固定了p
• 人们拥有不同的权重，n不同
• 重复无限次，单次成功的概率随机。但无限次下来，权重越大（n越大）的人，总体上成功的可能性越大（k越高）

就有点像买彩票，每期彩票售出100张彩票，中奖率为1/100。A每期只买了10张，B只买了1张。对单期而言，A和B的中奖是随机的，但是长期而言，A中奖概率是B的10倍。

algorand中pos分析

algorand中基于pos的proposer选举就属于该场景：

• 一轮的总质押量为1000，要选出10个账户参加初选，则每个账户的选举概率p = 10/1000
• 10个账户的抵押量各不相同，即n不同
• 单次选举随机，但总体上来看，质押量越高（n越大），选举成功的几率越大

具体代码见以下函数：

1. 计算N
2. 计算P
3. 计算随机概率r
4. 计算K

其中N越大，总体概率上K就会更大，因此质押量越高，权重越大，成为proposer出快的概率越大。

总结

algorand和传统的pos不同，并非严格的按照质押量的多少来顺序，或者轮循选取proposer，而是通过二项式随机数的方式选取，其中的特点在于：

• 每一轮propoer的选举都是随机的
• 总体来看，proposer的选举次数是按pos比例分配的

二项分布随机数适合于加权随机数场景：

• 二项分布随机数的使用前提是二项分布场景中
• 单次结果是随机
• 无限次结果后，权重越大，产生的随机数越大