a16z 详解 Cicada 原理：如何通过时间锁谜题与 ZK 证明实现隐私链上投票？

原文作者：Michael Zhu  ，a16z crypto 研究工程师 来源：a16zcrypto  翻译：DeFi之道

一般来说，所有投票系统都依赖于良好完整性和透明度，以此才能以任何有意义的方式发挥作用。从这点来看，区块链成为了构建这一系统的理想实现路径，事实上许多去中心化组织已经通过采用无许可投票来表达集体意图，一般是在通过动用大量资金或调整关键协议参数的情况下来实现。但链上投票也有缺点，即隐私性不足，这对 web3 投票系统尤其不利，在当前的大多数链上投票协议中，选票和计票都是完全公开的，没有隐私，那么投票结果容易受到操纵和选民激励失调，最终可能导致不民主的结果。

这就是我们发布 Cicada 的原因：一个新的开源 Solidity 库，它利用时间锁定谜题和ZK零知识证明进行链上投票。与现有系统相比，Cicada 具有新颖的隐私属性，最小化信任化假设，并且足够高效，可以在以太坊主网上使用。

在这篇文章中，我们调查了投票隐私的概况，并阐述了 Cicada 工作原理（将提供正式证明）。我们还鼓励开发人员查看 GitHub 存储库——Cicada 可以通过多种方式进行调整和扩展，以支持不同的投票方案和功能，我们希望与社区合作探索这些可能性。

隐私投票背景概述

在任何投票系统中，都需要考虑许多不同的隐私层。个人选票数据的披露、连续计票和选民身份都会以不同方式影响选民激励，哪些隐私属性是必需的取决于投票的具体规则。以下是密码学和相关科学文献中经常出现的一些内容：

选票隐私：无记名投票，也称为“澳大利亚选票（ Australian ballot）”，是为物理现实世界的投票系统开发的一种投票方式，目的是保护个人选民的偏好，并减少贿赂和胁迫（在链上设置中，我们可能需要比选票隐私更强大的属性——参见下面的“无收据”）。投票隐私也减轻了社会期望偏差——即人们根据别人对自己选择的看法进行投票的压力较小。

计票结果隐私：许多投票系统在选民仍在投票时会隐藏计票结果，每个选项已投了多少票是未知的，以免影响投票率和选民激励。我们在现实世界中可以看到很多类似的情况，例如：晚些时间开始投票的美国参议员相比早些时间投票的参议员，前者之间更有可能与自己的政党结盟。链上：在代币加权投票中，鲸鱼可以让对手保持领先，让他们产生一种虚假的安全感(有些人可能懒得投票，认为他们无论如何都会赢)，然后在最后一刻投票，以改变结果。

选民匿名投票：在许多现实世界的投票系统中，个人的投票是私密的，但您投票的事实通常是公开的，这对于防止选民欺诈很重要，因为公布谁投票的记录可以让人们检查是否有其他人以他们的名义投票。然而，在链上，我们可以在使用加密原语保持匿名的同时防止选民欺诈——例如使用Semaphore，您可以在零知识的情况下证明您是尚未投票的合格选民。

无收据投票：个人选民自己提供他们选票的“收据”以证明他们是如何投票给第三方的，不然可能会导致选票出售。一个相关性很强的属性是 coercion-resistance，它可以防止某人以某种方式强迫选民投票。这些属性在去中心化环境中特别有吸引力，在这种环境下，可以通过智能合约市场使投票权流动，不幸的是，它也很难实现，事实上 Juels 等人声明在没有可信硬件的情况下，在未经许可的环境中是不可能实现的。
Cicada 专注于运行计票隐私，它可以与零知识组证明相结合，以获得选民匿名和选票隐私等功能。

Cicada 简介：从同态时间锁谜题中计算隐私

为了实现计票结果，Cicada 借鉴了（据我们所知）以前从未在链上使用过的加密原语。

首先，时间锁谜题 (Rivest, Shamir, Wagner, 1996) 是一种加密谜题，它封装了一个秘密，只有经过一段预定的时间后才能揭示——更具体地说，这个谜题可以通过重复执行一些操作来解密不可并行计算。时间锁定谜题在投票的背景下非常有用，可以实现计票结果隐私：用户可以将他们的选票作为时间锁定谜题提交，这样他们在投票期间是完全隐私的，但可以在投票后公开。与大多数其他私人投票结构不同，这可以在不依赖计票机构（如选举工作人员清点纸质选票或数字选票）、阈值加密（threshold encryption 其中多个受信任方必须合作解密消息）或任何其他受信任方情况下，任何人都可以运行计票隐私可以解决时间锁定难题，来确保在投票后公布结果。

其次，同态时间锁谜题 (Malavolta Thyagarajan, 2019) 具有额外的属性，即在知道密钥、解密谜题或使用后门的情况下，可以对加密值进行一些计算。特别是，线性同态时间锁谜题允许我们将谜题组合在一起，产生一个新的谜题，封装了原始谜题的秘密值。

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

新结构：效率和权衡

要使投票方案在链上切实可行，还需要考虑更多的因素。首先，攻击者可能会尝试通过投出编码不正确的选票来操纵投票。例如，我们可能希望每个选票的时间锁定谜题都编码一个布尔值：“1”表示支持投票的提案，“0”表示反对。该提案的热心支持者可能会尝试编码，例如“100”来放大他们的有效投票权。

我们可以通过让选民与选票本身一起提交选票有效性的零知识证明来防止这种攻击。尽管零知识证明在计算上可能很昂贵——为了尽可能降低选民参与的成本，证明应该是 (1) 客户端可有效计算和 (2) 链上可有效验证。

为了使证明尽可能高效，我们使用定制的 sigma 协议——一种为特定代数关系设计的零知识证明，而不是通用证明系统。这实现了极快的证明时间：在现成的笔记本电脑上用 Python 生成选票有效性证明需要 14 毫秒。
虽然这个 sigma 协议的验证器在概念上很简单，但它需要一些大的模幂运算。 Malavolta和Thyagarajan的线性同态方案使用Paillier加密，因此这些幂运算将对某些RSA模N取模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 仅在投票期间保证选票隐私——如果好奇的观察者希望解密特定选民的选票，他们可以这样做。解密任何个人选票与解密最终计票一样昂贵，所以它需要O(n)的工作来完全解密一张有n个选民的选票。但是，所有这些选票都可以并行解密(假设有足够多的机器)，所需的时间与解密最终计票所需的时间相同。

对于某些选票，这可能是不可取的。虽然我们对临时的运行计票隐私感到满意，但有时我们可能想要无限期的投票隐私。为实现这一点，我们可以将 Cicada 与匿名选民资格协议结合起来，通过零知识组成员身份证明进行实例化。这样，即使选票被解密，它所揭示的只是有人以这种方式投票，而不知道具体是谁。

计票机构

我们在设计 Cicada 时的首要任务之一是避免需要一个计票机构：许多私人投票结构都需要一个半信任的计票机构（或权力委员会，或通过安全的多方计算进行协调）来接收和汇总选票，如果将其强行映射到区块链环境中，就意味着这些方案不能完全由智能合约执行，需要一些人为干预和中心化的信任。

在大多数结构中，计票机构的完整性不受信任，但他们的活跃度值得信任——如果他们离线，则无法计算最终结果，从而无限期地拖延投票结果。在某些结构中，他们也有一定的隐私性，也就是说，他们了解每个人如何投票，但预计会在不透露此信息的情况下公布投票结果。

在现实世界的场景中，计票机构是一个合理且必要组织，但它在区块链环境中并不需要，我们的目标是最大限度地减少信任并确保一定的审查阻力。 

Cicada 只是探索了链上投票隐私领域众多方向中的一个，并补充了其他团队正在进行的相关研究。如上所述，Cicada 与Semaphore、ZK 存储证明和RLN (Rate-Limiting Nullifier)等匿名技术密切相关，Cicada 还可以集成Nouns Vortex 团队提出的 optimistic proof checker ，以减轻选民的 gas 负担。

另外，还可以调整 Cicada 以支持不同的投票方案（例如代币加权投票、二次投票），更复杂的方案对于以太坊主网来说可能计算成本太高，但它们在 L2 上是很实用的，考虑到这一点，我们欢迎您的贡献、Fork和建议，和我们一起讨论下一步该把Cicada带到何处