Cicada: 通过时间锁谜题和ZK实现链上私密投票

原文标题：《Building Cicada: Private on-chain voting using time-lock puzzles》

原文来源：a16z

原文作者：Michael Zhu

原文编译：Kxp，BlockBeats

所有的投票系统都需要依赖诚信和透明度才能发挥实际作用。从表面上看，区块链似乎是构建这些系统的理想平台。事实上，许多去中心化组织已经采用了无许可投票来表达集体意愿，通常是在行使重要财务权力或调整关键协议参数的情况下。然而，链上投票存在一些缺点，并且对于 Web3 投票系统而言，隐私问题尚未得到充分的探索，这给其带来了负面影响。在今天大多数使用的链上投票协议中，选票和投票结果都是完全公开的。缺乏隐私保护意味着投票结果容易受到操纵，同时也可能导致选民激励不一致，潜在地导致非民主的结果。

为此，我们推出了 Cicada：一个全新、开源的 Solidity 库，利用时间锁谜题和零知识证明来实现链上私密投票。与现有系统相比，Cicada 具备独特的隐私属性，最小化了对信任的依赖，并且在 Ethereum 主网上的使用效率也非常高。

在本文中，我们对投票隐私的现状进行了调研，并对 Cicada 的工作原理进行了高层次的介绍（正式证明将在后续提供）。我们还鼓励开发者们前往 GitHub 存储库查看详细信息——Cicada 可以根据不同的投票方案和特性进行灵活调整和扩展。我们期待与社区合作，共同探索这些可能性。

投票隐私性概述

在任何投票系统（链上或其他系统）中，我们都需要考虑许多不同层次的隐私性。个人选票的披露、持续的投票统计和选民身份都会以不同的方式影响到选民。在不同的投票中，所需的隐私属性也不尽相同，以下是密码学和社会科学文献中经常涉及的一些属性：

· 选票隐私性：秘密投票，也称为「澳大利亚式选举」（Australian ballot），是为了保护现实世界投票系统中个别选民的隐私，并减少贿赂和胁迫的一种方式（在链上环境中，我们可能需要比秘密投票更强大的机制，具体请参见下文的「无收据性」）。选票隐私性还可以减少社会期望偏差——人们不太会因为其他人对其选择的看法而投票。 

· 计票隐私性：许多投票系统在选民投票期间隐藏持续的投票统计，即每个选项收到的投票数量，以避免对投票率和选民激励产生影响。我们在现实世界中已经看到了这种情况：例如，较晚投票的美国参议员比较早投票的参议员更可能与他们的政党保持一致。而在链上的 Token 加权投票中，巨鲸可以通过让对手保持领先来维持他们的虚假安全感（有些人可能懒得投票，因为他们觉得这些人无论如何都会赢），然后在最后一刻投出自己的选票来左右结果。

· 选民匿名性：在许多现实世界的投票系统中，你的选票是保密的，但是你是否投票通常可以被其他人知晓。这可以作为防止选民欺诈的保护措施，因为公布谁投票的记录可以让人们检查是否有人以他们的名义投票。然而，在链上，我们可以使用密码原语防止选民欺诈，同时保持匿名性——例如，使用 Semaphore，你可以用零知识的方式证明自己是一个合格的选民，并且尚未投票。 

· 无收据性：选民不应该向第三方提供选票的「收据」，以证明他们的选票如何投给了某个人，否则可能导致选票出售。抵抗胁迫（coercion-resistance）是另一个与之密切相关的属性，防止某人被迫以某种方式投票。在去中心化环境中，这些属性尤其吸引人，因为通过智能合约市场，投票权可以变得流动起来。不幸的是，这些属性非常难以实现。事实上，Juels 等人指出，这些特性在没有可信硬件的无许可设置中是不可能实现的。 

Cicada 专注于持续的投票统计隐私，但是（正如我们后面将讨论的那样），它可以与零知识群组成员证明结合使用，以实现选民匿名性和选票隐私性。

Cicada：利用同态时间锁谜题实现计票隐私性

为了实现持续的投票统计隐私性，Cicada 借鉴了在链上（据我们所知）从未使用过的密码原语。

首先，时间锁谜题（Rivest，Shamir，Wagner，1996）是一种密码学谜题，只有在预定的时间段过去后才能揭示其背后的秘密——更具体地说，只能通过重复执行某些不可并行化计算来解密谜题。时间锁谜题在投票的背景下对于实现持续的投票统计隐私性大有作用：用户可以将他们的选票作为时间锁谜题提交，这样他们的选票在投票过程中将保密，但在投票后可以被披露。与其他大多数私密投票结构不同的是，这使得计票隐私性的实现不再需要依赖统计机构（如选举工作人员计算纸质或数字选票）、阈值加密（几个受信任方必须合作解密一个消息）或任何其他受信任方：任何人都可以解决时间锁谜题以确保结果在投票后被揭示。

其次，同态时间锁谜题（Malavolta Thyagarajan, 2019）具有一个额外的特性，即在了解秘钥、解密谜题或使用后门的情况下，可以对加密数值进行一些计算。特别是，线性同态时间锁谜题使我们能够将谜题组合在一起，生成一个新的谜题，其中包含原始谜题秘密数值的总和。

正如论文作者所指出的那样，线性同态时间锁谜题特别适用于私密投票：选票可以编码为谜题，并且可以对它们进行同态组合以获得编码最终统计的谜题。这意味着只需要一次计算即可揭示最终统计结果，而不是为每个选票解决一个唯一的谜题。

全新体系：效率与权衡

对于一个能够在链上实际应用的投票方案，还有几个要考虑的因素。首先，攻击者可能试图通过提交错误编码的选票来操纵投票结果。例如，我们可能期望每个选票的时间锁谜题编码一个布尔值：「1」表示支持所投议案，「0」表示反对。一个热心的支持者可能会尝试使用类似「100」的编码来增加他们的有效投票权。

我们可以通过要求选民在提交选票本身之外，还提交一个零知识证明来防止这种攻击。然而，零知识证明可能需要耗费大量的计算资源——为了使选民参与的成本尽可能低，证明应该（1）在客户端高效计算和（2）在链上高效验证。

为了使证明尽可能高效，我们使用了一种定制的 sigma 协议。这是一种为特定代数关系设计的零知识证明，而不是通用的证明系统。这大大加速了证明时间：在一台现成的笔记本电脑上，用 Python 生成一个选票有效性证明只需 14 毫秒。

虽然这个 sigma 协议的验证过程在概念上很简单，但它实际需要几次大型模数指数运算。Malavolta 和 Thyagarajan 的线性同态方案使用了 Paillier 加密，因此这些指数运算将在某个 RSA 模数 N^2 的模数下进行。对于一个相当大的 N，这些指数运算在大多数 EVM 链上是难以承受的（需要数百万个 gas）。为了降低这个成本，Cicada 改为使用指数 ElGamal，该指数仍然提供加法同态性，但是在一个更小的模数（N 而不是 N^2）上运算。

使用 ElGamal 的一个缺点在于，解密统计结果时需要穷举离散对数（请注意，这在链下完成，并在链上进行高效验证）。因此，它只适用于预期最终统计结果相对较小的情况（例如，小于 2^32，约 430 万票）。在最初基于 Paillier 的方案中，无论统计结果的大小如何，都可以高效地解密。

选择 RSA 模数 N 还涉及权衡。我们的方法使用了 1024 位的模数以提高 gas 效率。尽管这远高于已公开因子分解的最大 RSA 模数（为 829 位），但它低于通常推荐用于 RSA 加密或签名的 2048 位大小。然而，在我们的应用中，我们不需要长期安全性：一旦选举结束，如果未来 N 被分解，就不会有风险。在时间锁过期后，假设统计结果和选票将变得公开，因此使用相对较小的模数是合理的。（如果因子分解算法改进，这也可以很容易地在将来进行更新。）

匿名性和选民资格

如上所述，Cicada 提供持续的投票统计隐私性——时间锁谜题可以让统计结果在投票期间维持保密状态。然而，每个选票也是一个时间锁谜题，在相同的公共参数下进行加密。这意味着，就像统计结果可以解密一样（通过执行必要的计算），每个选票也可以解密。

换句话说，Cicada 仅保证选票在投票期间保密。如果一个好奇的观察者想解密特定选民的选票，他们也可以在投票结束后做到。解密任何一个选票的成本与解密最终统计结果的成本一样，因此完全解密一个包含 n 个选民的投票需要 O(n) 的工作。但是，所有这些选票可以并行解密（假设有足够的计算机），这一过程所需的时间与解密最终统计结果的时间相同。

对于某些投票来说，这可能并不理想。尽管我们对于临时的计票隐私性感到满意，但我们可能希望拥有永久的选票隐私性。为了实现这一点，我们可以将 Cicada 与匿名选民资格协议相结合，通过零知识群组成员证明来实现。这样，即使解密选票，它只会透露某个人以何种方式投票，而这在统计结果中已经得到了披露。

在我们的存储库中，我们提供了一个使用 Semaphore 进行选民匿名性的示例合约。请注意，Cicada 合约本身不对选民资格的确定或执行做任何假设。特别是，你可以将 Semaphore 替换为 Semacaulk 或 ZK 状态证明。

选票统计机构

设计 Cicada 时我们的首要目标之一是避免对选票统计机构的依赖：许多私密投票都需要一个半可信的统计机构（或通过安全多方计算协作的委员会），该机构接收并汇总选票。在区块链的环境中，这意味着这些方案不能仅通过智能合约进行，而需要一些人工干预和信任。

在大多数体制中，统计机构在诚信方面是可信的（它们不能操纵投票数），但是它们也必须保持活跃性——如果它们离线，最终结果将无法计算，投票结果将无限期地停滞。在某些体系中，统计机构在维护隐私方面也会得到信任。也就是说，它们了解每个选民的投票，但会在不透露此信息的情况下发布投票结果。

虽然在许多现实世界的场景中，统计机构是合理的（也是必要的），但它们在区块链的环境中并不理想，我们的目标是最小化信任并确保抗审查性。

结语

Cicada 探索了链上投票隐私领域的众多方向，与其他团队正在进行的研究互为补充。如上所述，Cicada 与 Semaphore、ZK 存储证明和流量限制无效化器（rate-limiting nullifier）等匿名群组成员技术相辅相成。Cicada 还可以与 Nouns Vortex 团队提出的 optimistic proof checker 相结合，以减轻选民的 gas 负担。

此外，我们还有机会将 Cicada 调整为支持不同的投票方案（如加权投票、平方投票），虽然更复杂的方案可能对 Ethereum 主网来说计算代价过高，但在 Layer 2 网络上可能是可行的。鉴于此，我们欢迎关于 Cicada 未来发展方向的任何建议。