流民主投票在以太坊上的实现和挑战

流民主投票委托「专业的人做专业的决策」，对提高现有治理场景中「投票的参与率」有很大的效果。

在区块链应用机制设计和去中心化治理场景中，投票机制和算法是十分重要的课题，我们也将持续在这个方向上进行研究和探索。此前我们简单分析了V神针对公共募资项目建立合理投票体系的“二阶投票”的数学模型和存在的挑战。

我们最近关注另一种投票模型是“流民主投票“。我们认为”流民主”可以认为是结合了直接投票和代议制投票的优点的一种投票形式，这种委托”专业的人做专业的决策“的投票机制，对提高现有治理场景中的“投票的参与率”有很大的效果。

投票是实现民主的重要方式之一。随着区块链技术的崛起，投票已经渗透到区块链的各个场景，例如PoW最长链原则，DPoS共识机制，以及如今广泛应用的DAO，BIP，和EIP等等。

除此之外区块链社区之外的很多组织也希望在区块链上进行投票活动。用区块链来实现民主或投票活动相对传统的投票形式有很多优势：

1.开放性，任何人在任何时间或地点都能很方便的参与；

2.透明性；

3.自计票：即参与者完成一次投票操作时，其投票信息即被计入区块链网络；

这种种优势，使得区块链上的投票不仅仅在区块链内部有很大的影响力，还蔓延到区块链外部的世界。

投票结果。一般来说，投票可以分为三种不同的投票方式：直接投票，代议制投票和流民主的投票形式。

直接投票即每位投票者均直接参与投票活动，投票给候选者，例如PoW选最长链就是该方式。

代议制投票是指投票者将自己的投票权交给某一位代表，让该代表替其行使投票权，例如美国大选，或者区块链上的DPoS等。

这两种投票形式在生活中都有广泛的使用，它们都有各自的优点，并不能明确指出哪一种更好。

从实际操作的反馈来看，虽然目前的一些统计数据显示虽然大多数人更倾向于直接投票形式来行使自己的民主权利，但是在实际操作中，但是世界上很多国家依然选择代议制的投票方式。

流民主可以认为是结合了直接投票和代议制投票的优点的一种投票形式，同样存在数百年的历史。它原本并不是一个区块链上专有的问题，然而由于它实现上的技术限制，使得其使用并不多见。

流民主是这样一种投票形式：任何一个投票者都可以委托他人为他投票或自己直接投票，而该被委托者也可以继续选择委托给其他人替其投票。当一个被委托人投票时，直接或间接委托给他的所有投票者的票权将同时被投出给他所投的候选人。如果任何一个委托者，不满意其被委托人（包括其间接被委托人）的投票，那他可以选择自己直接投票或重新委托其他人进行投票。

如图所示，Alice、Daisy和Ernie均将自己的票权委托给Bob（每人均只有一票），Bob又将其票权委托给Chris。委托之后，Bob的票权为4，Ernie的票权为2，Chris的票权为5。       

在这种治理框架下，追求的是将某个问题决策权交到“最有资格”决策的人手上，相对“精英”的人群或者KoL可以通过决策能力构建自己的声誉，而普通群众可以通过手上的”票权“来激励这群”KoL“。

相对于直接投票，流民主的委托形式使得投票者在没有足够多的时间时，或者对投票项目没有足够的专业认知时，依然能够通过委托票权给他所任何的朋友或相关专家来实现自己的民主权利。

而相对于代议制形式，流民主形式也能够更加自由和灵活的实现每个人的民主权利。投票者可以在不同的投票问题上去委托不同的人或自己直接行使民主权利。经验表明，直接投票对于较小规模的群体更加适用，而对于较大范围或者比较分散的群体，投票的参与度是比较低的。在比较活跃的公链上，大多数投票活动的参与人数也只有200人左右。而我们预期，如果使用流民主形式，能够大大提高投票的参与率。

用智能合约实现流民主投票的一个需求是实现合约（实时）自记票功能，即在投票进行时，任何用户可以通过询问合约变量直接获取投票状态（即每个候选者的现有票数），而不需要同步完整的区块链数据来本地计算。这需要智能合约能够对每一条投票信息实时更新并展示投票状态。然而该问题的一个难点在于，区块链上的智能合约在每一次调用时都会根据要执行的指令数产生一定的gas费用，而这个gas费用在每个区块都是有一定限制的（block_gas_limit），如果超出限制，指令则不能被执行。

实现智能合约实时自记票功能可抽象成下面这个问题：如图4所示，有编号为1到12的投票人，其票权刚好与其编号相同，他们经过委托之后最终得到图1的委托关系：关系图为一棵树，父节点均为孩子节点的委托人，父节点的总票权为其自身原本的票权加上其所有孩子节点的票权的总和，当任何一个投票人需要投票时，其实际票权为其总票权减去其孩子节点中已投票节点的总票权和。

    当1投票给A时，候选人A的总票数为78票，其他候选人票数均为0；

    接着当5投票给B时，B的票数为6+5=11票，A的票数变为78-11=67票；

    继而当3投票给C时，C的票数为33-11=22票，B的票数不变，A的票数变为67-22=45票。

不难看出，每当有一个投票者发起投票后，需要计算他的实际票权以及减少其他候选人的票权，传统算法通常需要将整颗树遍历一遍，链上时间复杂度（即执行智能合约的指令总数）为O(n)，n为总投票人数。因区块链最大gas费用限制，基本上只能满足n小于1000的情况，因此，当n大于1000时，传统算法无法满足需求。

Aragon 的CEO此前就在他们的论坛上发布了一个关于流民主问题的公开讨论，希望能够从社区中获得一个好的解决方案。

为了解决这一问题，使得能够实现区块链上的流民主，ASResearch提出了一种快速算法，来达到一个链上算法时间复杂度为O(logn)的流民主问题的解决方案。该算法的两个关键技术分别是默克尔树（Merkel Tree，一种链上存储方法）和线段树（一种数据结构）。它主要包括以下流程：

1. 在投票开始阶段，每位投票者通过快照以太坊的当前高度来获取委托关系图，然后执行时间复杂度为O(n)的链下初始化来获取其初始化数据；

2. 每位投票者在投票阶段不允许修改他的委托关系，但是可以通过发送一条带有其初始化数据的投票指令来直接投票给某个候选者，用默克尔树的方法（时间复杂度为O(log n)）来验证其初始化信息是否正确；

3. 当收到一条投票指令后，通过线段树这种数据结构来实现时间复杂度为O(log n)的投票状态的更新和显示。

其中，收到投票指令，并进行投票状态更新的过程为：

1.计算投票者的已损失票权，即其孩子节点中已投票节点的总票权和；

2.该投票者的实际票权t为其总票权减去其已损失票权，同时t也是其候选者此次获得（增加）的票权；

3.找到该投票者的最近投过票的父节点，更新其所投票的候选人的票数（减去t）；

4.更新所有该投票者的孩子节点的最近投票父节点信息。

5.更新从该投票者到其最近投过票父节点的路径上的所有投票者的已损失票权（增加t）。

下图展示在以太坊测试网中的实验结果，其中横坐标为投票者数目n，纵坐标为消耗gas数目，虚线为最大gas限制。结果表明用传统算法当n达到1000时已经超出了限制，而我们的算法在n等于3000时gas消耗仍然维持在一个很小的值，符合理论估计结果。

通过实验可以看出，此算法可以有效的解决智能合约的gas limit对于投票代理深度的问题，也为流民主投票在诸如以太坊的智能合约平台上实际展开应用铺平了道路。

算法论文全文：https://arxiv.org/abs/1911.08774

问题和讨论请访问:https://forum.gotoken.io/t/topic/20