DAOrayaki ｜详解最小化反共谋基础设施（MACI）

DAOrayaki DAO研究奖金池：

资助地址:  DAOrayaki.eth

投票进展：DAO Committee 2/0 通过

赏金总量：80 USDC

研究种类：MACI, Dorahacks, Hackerlink

原文作者:   Kyle Charbonnet

贡献者：[email protected]

审核者：[email protected]

原文:   A Technical Introduction to MACI 1.0

DAOrayaki 是一个去中心化的研究者组织和去中心化媒体，通过 DAO的形式去中心化地资助世界各地的研究者进行研究、翻译、分析等工作。DAOrayaki 由早期的 DAO 组织 DAOONE 核心成员发起，得到了Dora Factory基础设施的支持。欢迎通过文末方式提交星际移民、量子计算、DAO等相关研究，瓜分10000USDC赏金池！了解去中心化自治组织（DAO），探讨最新治理话题，关注DAO的发展趋势，欢迎加入DAOrayaki社区！

MACI是Minimal Anti-Collusion Infrastructure的缩写，是一种允许用户进行链上投票过程的应用程序，其有很强的抗串通/共谋能力。当今链上投票过程中的一个常见问题是，贿赂选民使其为某一特定选项投票十分容易。很多时候，这种贿赂采取的形式是 "加入我们的池子（按我们的方式投票），我们会给你分红（贿赂）"。由于区块链上的所有交易都是公开的，如果没有MACI，投票者可以很容易地向贿赂者证明他们投票给了哪个选项，从而获得贿赂奖励。

MACI通过使用zk-SNARKs来解决这个问题，从本质上隐藏了每个人的投票方式，同时仍然显示最终的投票结果。用户无法证明他们投票给哪个选项，因此贿赂者无法可靠地相信用户所投的票是投给了贿赂者所指定的选项。例如，一个选民可以告诉贿赂者他们投的是选项A，但实际上他们投的是选项B。没有可靠的方法来证明选民实际上投的是哪个选项，所以贿赂者没有动机去付钱给选民来投他们的票。

a.背景

关于MACI的总体概况、历史和重要性，可以查看往期的这些文章：

DAOrayaki ｜MACI: 链上治理中的抗勾结框架

DAOrayaki ｜MACI 中的匿名化

DAOrayaki ｜向MACI 添加匿名化方法

DAOrayaki ｜[op/zk] rollup / mixers / MACI的批量处理存款

同时，建议了解zk-SNARKs背后的基本理念，因为这些是MACI的核心组成部分。

DAOrayaki ｜创建假的zkSNARK证明

本文将介绍 MACI 的一般工作流程以及它如何能够提供以下原则（逐字逐句摘自 Wei Jie 的文章）：

1. 反对共谋。除了受信任的协调者之外，没有人可以确定投票的有效性，从而降低贿赂的有效性。

2. 无收据性。没有投票者可以证明（除了向协调者）他们投票的方式。

3. 隐私。除了受信任的协调者，没有人能够解密投票。

4. 不可审查性。任何人（甚至是受信任的协调者）都不能审查投票。

5. 不可伪造性。只有用户私钥的所有者可以投票与其对应的公钥相关联

6. 不可抵赖性。何人都不能在投票后修改或删除投票，尽管用户可以再次投票以使其无效

7. 正确执行。任何人（甚至是受信任的协调者）都不应该能够产生虚假的选票。

a.角色

在MACI工作流程中，有两种不同的角色：用户（投票者）和一个受信任的协调者。用户通过MACI智能合约在区块链上投票，协调者统计票数并发布最终结果。

协调者必须使用zk-SNARKs来证明他们的最终统计结果是有效的，而不公布每个人的投票。因此，即使协调者是腐败的，他们也无法改变用户的投票或自己增加额外的投票。腐败的协调者可以通过从不公布结果来阻止投票，但他们不能公布虚假的结果。

在将他们的投票发送到区块链上之前，用户使用一个只有用户和协调者才可以知道的共享密钥对他们的投票进行加密。这个密钥方案的设计是为了让每个单独的用户与协调者共享一个不同的密钥。这可以防止任何贿赂者简单地读取交易数据，以便查看用户投票给哪个选项。加密后的投票将被认为是一个 "消息"，用户将这个消息发送到MACI智能合约上，并存储在链上。

这种加密原理的一个非常简化的说明如下所示：

b.选票覆盖和公钥转换

在用户投票之前，他们必须通过向MACI智能合约发送他们希望用于投票的公钥来进行注册。这个公钥在投票时充当他们的身份。他们可以从任何地址投票，但他们的信息必须包含该公钥的签名。在注册后进行实际投票时，用户将把一些变量，包括公钥、他们的投票选项、他们的投票金额和其他一些变量捆绑到一个所谓的 "命令 "中。然后，用户用他们最初用于注册的公钥签署该命令。之后，用户将签名和命令一起加密，这样它就被认为是一个消息。关于说明如何构造更复杂消息的描述如下：

只要用户使用之前的公钥签署他们的命令，就能够推翻他们之前的投票。如果该命令被用户以前的公钥正确签署，那么该信息就被认为是有效的，协调者将把这算作正确的投票。因此，当用户在投票中提供的公钥与他们之前的公钥不同时，他们可以提交一个由这个新公钥签名的新投票，以推翻他们之前的投票。如果该签名不是来自以前的公钥，该信息将被标记为无效，不计入统计。因此，公钥可以被认为是用户的投票用户名，而签名就是投票密码。如果他们提供了正确的签名，他们就可以提交投票或更改他们的公钥，或两者兼而有之。

这个功能，我称之为公钥切换，旨在对抗贿赂攻击，用户只需向贿赂者展示他们的信息，然后解密，让贿赂者看到用户的投票方式。公钥转换允许用户改变他们的公钥，并创建有利于贿赂者的无效信息。贿赂者没有办法知道用户在发送显示给贿赂者的投票之前是否切换了他们的公钥。

1. Bob用公钥1注册

2. Bob创建了一个命令，其中包含--对选项A的投票和公钥2

3. Bob用公钥1，也就是他用来注册的密钥，签署这个命令

4. Bob把这个命令加密成一个消息，并把它提交给MACI智能合约

5. 协调者解密这个消息，并检查以确保该命令是由Bob之前的密钥--公钥1签署的。这个消息是有效的。

6. 协调者记录Bob对选项A的投票，并将其公钥更新为公钥2

Bob已经成功地投票给了选项A，为了推翻这个投票，必须发送一个带有公钥2签名的新投票。在这一点上，一个贿赂者现在试图让Bob投票给选项B。

1. Bob创建一个命令，其中包含--对选项B的投票和公钥1

2. Bob用公钥1签署这个命令，对信息进行加密，并将其提交给MACI智能合约

3. Bob向贿赂者展示解密后的信息，作为他对选项B投票的证明

4. 协调者解密了Bob的消息，看到签名与公钥2--Bob之前的消息中添加的密钥不一致。因此，这条信息是无效的，这张票不会被计入最后的统计。

5. 贿赂者没有办法知道投票是有效还是无效的，因此没有动力向其他用户提供贿赂

为了更好地了解MACI是如何工作的，最重要是要知道zk-SNARKs如何能够证明协调者解密了每个消息并正确地统计了投票。下一节对zk-SNARKs做了一个快速的、过于简化的概述。

c.zk-SNARKs

从本质上讲，zk-SNARKs允许用户证明他们知道一个特定数学方程的答案，而不透露这个答案是什么。以下面这个方程为例。

X + Y = 15

我可以证明我知道两个满足方程的数值，即X和Y，而不需要透露这两个数值是什么。当我为我的答案创建一个zk-SNARK时，任何人都可以使用SNARK（一组数字）并根据上述方程进行验证，以证明我确实知道该方程的一个解决方案。用户无法使用SNARK来找出我对X和Y的答案。

对于MACI来说，这个方程式要复杂得多，但可以总结为以下几个方程式：

encrypt(command1) = message1

encrypt(command2) = message2

encrypt(command3) = message3

…

Command1 from user1 + command2 from user2 + command3 from user3 + … = total tally result

在这里，每个人都能看到区块链上的消息和总的财务结果。只有协调者通过解密消息知道各个命令/投票是什么。所以，协调者使用zk-SNARK来证明他们知道所有的投票：

1. 对区块链上的信息进行加密

2. 对统计结果进行求和

然后，用户可以使用SNARK来证明计票结果是正确的，但不能用它来证明任何个人的投票选择。

一般的工作流程可以分为4个不同的阶段：

1. 注册

2. 发布信息

3. 处理信息

4. 统计结果

这些阶段利用了3个主要的智能合约--MACI、Poll和PollProcessorAndTallyer。这些合约可以在MACI github页面上找到。MACI合约负责通过记录每个用户的初始公钥来跟踪所有用户的注册情况。当投票要进行时，用户可以通过MACI.deployPoll()部署一个Poll智能合约。

最后，PollProcessorAndTallyer合约被协调者用来在链上证明他们正确地统计了每张投票。这个过程将在下面的处理信息和统计结果部分详细解释。

a.注册

MACI的注册过程是通过MACI.sol智能合约处理的。用户在调用MACI.signUp()时需要发送三条信息。

1. 公钥

2. 注册守卫数据

3. 初始语音信用代理数据

公钥是上述章节中提到的原始公钥，用户需要用它来投票。正如前面几节所解释的，一旦投票开始，他们可以在以后改变这个公钥。用户用于注册的公钥在每次投票中都是共享的。

MACI允许合同创建者/所有者设置一个 "注册守卫"。它是指另一个智能合约的地址，它决定了签到的规则。因此，当一个用户调用MACI.signUp()时，该函数将调用注册守卫数据，以检查该用户是否有效签约。

MACI还允许合同创建者/所有者设置一个 "initialVoiceCreditProxy"。这代表了决定一个给定用户获得多少票数的合同。因此，当用户调用MACI.signUp()时，该函数将调用初始语音信用代理来检查他们可以花费多少票数。每次新的投票，用户的语音信用余额都会被重置为这个数字。

一旦MACI检查到用户是有效的，并检索到他们有多少语音点数，MACI就会将以下用户信息存储到Sign Up Merkle Tree中。

1. 公共密钥

2. 语音积分

3. 时间戳

b.发布信息

一旦到了投票时间，MACI创建者/所有者将部署一个Poll智能合约。然后，用户将调用Poll.publishMessage()并发送以下数据：

如上文各节所述，协调者将需要使用加密密钥，以得出共享密钥。然后，协调者可以使用共享密钥将消息解密为一个命令，其中包含投票。

一旦用户发布了他们的消息，投票合同将把消息和加密密钥存储到Message Merkle Tree中。

c.处理信息

一旦特定投票完成，协调者将使用PollProcessAndTallyer合约，首先证明他们已经正确地解密了每个消息，并应用它们来正确地创建一个更新的状态树。这个状态树记录了所有应该被计算的有效投票。因此，在处理消息时，协调者不会在状态树内保留那些后来被更新的消息所覆盖的消息。例如，如果一个用户投票给选项A，但后来又发送了一个新消息投票给选项B，协调者将只计算选项B的投票。

协调者必须分组处理消息，以便在链上证明不超过数据限制。然后协调者创建一个zk-SNARK，证明他们的状态树正确地只包含有效的消息。一旦证明准备好了，协调者调用PollProcessorAndTallyer.processMessages()，提供状态树的哈希值和zk-SNARK证明作为输入参数。

PollProcessorAndTallyer合约将把证明发送给一个单独的验证器合约。验证器合约是专门用来读取MACI zk-SNARK证明并判断它们是否有效的。因此，如果验证者合同返回为真，那么每个人都可以在链上看到协调者正确处理了那批消息。协调者重复这个过程，直到所有消息都被处理。

d.统计结果

最后，一旦所有信息都被处理，协调者就会统计有效信息的票数。协调者创建一个zk-SNARK，证明状态树中的有效消息（在处理消息步骤中证明）包含的票数之和为既定的统计结果。然后，他们调用PollProcessorAndTallyer.tallyVotes()，用正确统计结果的哈希值和zk-SNARK证明。与processMessages函数类似，tallyVotes函数将把证明发送给一个验证器合约，以确保它是有效的。

只有当验证者合约返回证明是有效时，tallyVotes函数才会成功。因此，一旦tallyVotes函数成功，用户就可以相信协调者已经正确地统计了所有的有效投票。在这一步之后，任何人都可以看到最终的计数结果，并证明这些结果是发送到 Poll 合约的正确结果。用户将无法看到任何个人是如何投票的，但可以相信这些投票是被正确处理和计算的。

MACI在防止链上投票的共谋方面迈出了一大步。虽然它不能防止所有共谋的可能性，但它确实使之更难。MACI已经可以在DoraHacks、clr.fund中看到并使用。如，今年2月11日开始的美国区块链和Web3黑客马拉松ETH Denver，现场共有九个赛道：ColoradoJam、DAOs & Communities、Defi、Impact、Mobile-First Focus、NFTs、Gaming & Metaverse、Infrastructure & Scalability、太空技术和新领域；Hackathon现场参赛者通过DoraHacks开发者激励平台HackerLink.io提交项目，并角逐200万美金的Grant和超过100万美金的Bounty任务。这个过程中，现场新增了基于零知识证明的隐私二次方投票，社区可以通过DoraHacks提供的MACI最小抗共谋基础设施进行匿名、隐私的二次方投票，并获得SPORK奖金池资助。

DoraHacks实现了MACI的第一次中等规模的应用。具体基于MACI 隐私投票排行榜可以查看：https://hackerlink.io/grant/ethdenver22/top

当让用户投票决定哪些项目可以得到资助。尤其是资金数额变得非常大时，用户和组织就有很大的动力去共谋，以获得这些资金的一部分。这就是MACI能够真正发挥作用的地方，保护诸如DoraHacks这样的重要投票过程的公平性。