跨世纪的技术结合 — 波卡选举机制

介绍

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 票。

Figure 1: Basic Phragmén

Weighted Phragmén

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

Figure 2: Weighted Phragmén

Algorithm 2 加权算法

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

Figure 3: 参选者初始分数
Figure 4: Load
Figure 5: Load
Figure 6: Load

总结

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

--

--

Distributed blockchain research institution. Focusing on underlying technology research and practice. Support us: http://giveth.io/project/cyc

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
CYC

CYC

307 Followers

Distributed blockchain research institution. Focusing on underlying technology research and practice. Support us: http://giveth.io/project/cyc