'CryptoYC'
研究|跨世纪的技术结合--波卡选举机制
🌿

研究|跨世纪的技术结合--波卡选举机制

人们对于POW密码学货币的经济和环境成本有诸多顾虑,一些人建议转向权益证明免去绝大部分成本。我们要知道密码学货币本质是一个交易列表,同时也是一个可以决定那些交易能够被添加进列表的协议。

发展至今,我们已经看到POW与安全性紧密耦合,且已经存在并证明自身能继续强大,我们尚不清楚POS能做到什么程度。波卡项目的创始人GavinWood,一直把人类的治理与协作放在最重要的位置,在共识的设计上思考深刻。这里我们一起看看波卡中的投票选举采用的是权重 Phragmén 算法。

介绍

Phragmén算法是在 19 世纪末被瑞典数学家 Lars Edvard Phragmén提出来用来选举瑞士议会议员的一种方法。当时的方法都是将所有席位给受欢迎的政党,他提出的方法保证了分给每个政党的席位数和他们获得的选票成正比,给了少数人更多的选举权。波卡的选举机制就是建立在 Phragmén选举制度之上,是每次选举的票位比例合理。波卡要优化的指标有三个:最大化 stake 数量,保证 stake 尽量均衡分配到每个验证者,使被投票最少的验证者获得的 backing stake 数量尽可能大,使所有验证者的 backing stake 偏差最小。

Basic Phragmén

波卡中的投票选举采用的是权重Phragmén算法,要理解权重,先要理解 Basic Phragmén,这个特定算法在 brill 等人的论文 Phragmén’s voting methods and justified representation 中有详细描述。Basic 是没有权重的,意思是一个人投 2 票给一个候选者和两个人投 1 票给同个候选人的权重在数学上是相等的。每一轮都进行一个迭代算法,具体算法描述如下:

Algorithm1 基础算法

1. 投票人给 n 个候选人进行投票,一旦提交不可更改。投票规则:每个投票者最投一个人,最多投 n-1 票。

2. 每个选票初始 load 为 0。

3. 当一个候选人支持者的 least average cost 最小,那么这个候选人将会得到一 个席位。

4. 用所获得票数的倒数作为候选人的 load,即得到 n 票支持,那么 load 为 1/n。

5. 将获胜者的选票负载平均化,每个 load 相等。

6. 如果还有席位,返回 3 重复一遍流程,否则结束。

举个例子,有 ABCD 四个候选人,5 个投票者,3 个席位,初始 load 设置为 0

Figure 1: Basic Phragmén
Figure 1: Basic Phragmén

L0 是初始 load,根据算法第四步,A 的 loa 为 1,B=1/4 , C=1/2 , D=1/3 , B 最小,所以第一个获得席位的就是 B,并且将 B 的 average load 作为新 load 更新到所有投了 B 的投票者中,作为 L1 列。B 就会被移出参选者的名单。还有两个席位,回到算法第三步继续迭代。

在第二轮选举中,A 只有 V4 一票,V1 的 load=1/4,以此类推 C 的支持者 load 为 0 和 1/4。然后我们计算 average-load,这里有个公式

image

所以:

image

D 的平均 load 最小,所以 D 获得第二个席位。然后再将每个投了 D 的投 票者 load 设置为 D 的 average-load,由此得到 L2 列,直到没有席位结束计算。

Weighted Phragmén

Basic 在权重相同的条件下可以良好运行,但是在波卡中,选举是有代币数量加权的,有点类似股东投票,持有代币数量更多的权力更大,但这样的做法不太民主。所以波卡想要既能尽可能让投票者将他们的偏好在结果中表达,又能将 stake 尽量平均分布,也能表达少数人的意愿。使用加权 Phragmén 能实现这些目标。

加权算法在每一轮选举结束时,候选人(验证者)将被添加到候选人集合里,但是同时会构建一个加权映射,定义为每个投票者(提名者)对候选人每次选择的权重。

这里官网给出了第二个例子:5 个候选人,5 个投票者,括号里为投票人持有的 budget,初始 load 为 0(L0 = 0)。

Figure 2: Weighted Phragmén
Figure 2: Weighted Phragmén

Algorithm 2 加权算法

1. 将投票者,投票者质押数量,和他们支持的参选人建立成列表。

2. 生成一个从投票者到参选者的初始 edge-weighted 映射,每个边缘权重为每 个投票者所持有的潜在权重(stake)。每个参选者得到的所有潜在权重的总和就 叫做 approval stake。

3. 这一步骤就要开始选择候选人,他们获得的分数就是 approval stake 的倒数。

4. 对于每个投票人,更新他们支持的候选人的得分,通过 voter budget×voter load/ candidate approval stake, 这里 vote budget 就是 stake 数量。

5. 确定分数最低的参选者,并选定该参选者,然后将他从候选人池中移除。

6. 给被选上的候选者投了票的投票者将会被更新 edge load, edge load = elected candidate score — voter′ s load,随后投票者的 load 也会被 更新:voter load = candidate score, candidate score = candidate score + voter budget × voter load / candidate approval stake。

7. 如果依然剩余有席位给候选人,返回第三步继续,否则进行下一步。

8. 现在投票者的 stake 被分配给了至少一名候选人,他之间的关系用 backing stake 来计算,baking stake = voter budget × edge load/ candidate load。

通过 figure 2,首先排除候选人 E,因为没有人给他投票。然后计算每个候 选人的初始分数,即算法第三步,得到下图,A 的分数最低,所以 A 被选进候 选人集合。到这一步,第一轮的选人结束。

Figure 3: 参选者初始分数
Figure 3: 参选者初始分数

接下来进行数据的更新,先更新 edge load,根据第6步,edge load=0.091,再将给 A 投过票的 voter,voter load 更新为候选人 A 的分数 0.091。最后进行候 选人的分数更新(此时 A 已经被移除,分数无需更新)。到这时一次算法就结束 了,因为还有剩余席位,所以回到第三步,D的分数最低,D就被选为第二个候选人。将 edge 的 load 更新为D的分数,即得到 L2 列。以此类推得到 Figure2。

image

完成候选人的选举之后计算算法的最后一步 backing stake。公式有如下两个 load 参数:

Figure 4: Load
Figure 4: Load

分别计算每个 nominator 的投票在每个 validator 中所占的 edge load。如图 5

通过算法最后一步得到每个validator所得到的backing stake。并且可以计算出每个 nominator 所提供的 stake 是多少。

Figure 6: Load
Figure 6: Load

提名者的计算结果也是对以下 3 个问题进行优化:

1. 最小化每个提名者的验证者数量,是为了减少支付数量,如果 1000 个提名者,没人支持 20 个验证者,那么将以工作产生 20000 笔交易,如果每人减少到 2 个验证者,那么减少到 2000 笔交易,少了一个数量级,可以减少网上和链上 的负载。波卡投票机制限制每个投票者最多只能给 16 个候选人投票。

2. 保持 stake 尽可能均匀分配,这样也降低了被攻击的概率。比如有总数 100 个 stake 的提名人集合 {10, 2, 8, 30, 50}, 一般来说攻击者只需要持有 3 个 stake 就可以进入提名者集合,一共需要 23 个 stake 就可以获得大部分验证者进行欺诈。但如果是 {20, 20, 20, 20, 20},那么 63 个才可以获得超过半数的验证者,将大大提高攻击成本。

3. 减少计算时间。因为 Phragmén 算法很复杂,所以为了保证恒定 6s 出块, 大部分计算在链下。在一个纪元(era)的后 25% 时间内,用户不能进行修改。对复杂度方面,可以通过限制提名者对验证者的数量降低。

总结

波卡的选举制度建立在 Phragmén 算法上,利用加权保证了 stake 数量最大化,保证 stake 均衡分布,且使所有的验证者获得的 stake 偏差最小。同时达到了提高了攻击者的门槛的目的。而针对提名者选择验证者人数的限制,降低了算法的复杂度。链下计算保证了区块产生时间。