Cointime

扫码下载App
iOS & Android

a16z:构建Cicada,利用时间锁谜题和零知识证明实现链上私密投票

个人专家

所有投票系统都需要完整性和透明度才能真正发挥作用。从表面上看,这使得区块链成为构建这些系统的理想平台 —— 实际上,许多去中心化组织已经采用无许可投票来表达集体意愿,通常是在动用大量资金或调整关键协议参数的情况下。然而,链上投票也存在缺陷,尤其是隐私问题尚待解决,这对 web3 投票系统不利。在目前大多数链上投票协议中,选票和计票都是完全公开的。没有隐私保护,投票结果容易受到操纵和选民激励失衡,可能导致不民主的结果。

正因如此,我们推出了Cicada:一个全新的开源Solidity库,利用时间锁谜题(time-lock puzzles)和零知识证明(zero-knowledge proofs)实现链上私密投票。与现有系统相比,Cicada具有独特的隐私特性,最小化信任假设,并且效率足够高,可以在以太坊主网上运行。

在本文中,我们将探讨投票隐私的现状,并提供关于Cicada工作原理的概要说明。同时,我们鼓励开发者查阅GitHub。Cicada可以通过多种方式进行调整和扩展,以支持不同的投票方案和功能,我们希望与社区共同探讨这些可能性。

私密投票简要探讨

在任何投票系统(链上或其他),我们需要关注多种不同的隐私层次。个人选票的公开程度、实时计票以及选民身份都会以各种方式影响选民激励。所需的隐私属性取决于投票的具体场景。以下是密码学和社会科学文献中经常涉及的一些方面:

  • 选票隐私:无记名投票,又称“澳大利亚式选票”,是为现实世界投票系统设计的,旨在保护个人选民的偏好隐私,减少贿赂和胁迫(在链上环境中,我们可能需要比选票隐私更强的属性——见下文的“无收据”)。选票隐私还能减轻社会期望偏差,即人们根据他人对其选择的看法来投票的压力降低。
  • 实时计票隐私:许多投票系统对实时计票结果进行隐藏,或者在选民仍在投票时不公开各个选项的票数,以避免影响投票率和选民激励。我们在现实世界中已经看到了这种情况。例如,美国晚投票的参议员比早投票的参议员更有可能与他们的政党保持一致。在链上环境中,在代币加权投票中,大鳄可以通过让自己领先(有人可能因认为自己无论如何都会赢而懒得投票),给对手制造虚假的安全感,然后在最后一刻投票决定胜负。
  • 选民匿名:在许多现实世界投票系统中,虽然你的投票是保密的,但你投票的事实通常是公开的。这对于防止选民欺诈至关重要,因为公开有关谁进行投票的记录,可以让人们检查是否有人冒用他们的名义投票。然而,在链上环境中,我们可以在使用加密原语保持匿名的同时防止选民欺诈。例如,使用信标,你可以在零知识情况下证明你是一个尚未投票的合格选民。
  • 无收据:个人选民提供选票的“收据”,以证明他们是如何向第三方投票的,否则可能导致选票被出售。一个密切相关但更强大的属性是抗胁迫性,它可以防止某人强迫选民以某种方式投票。这些属性在去中心化环境中尤为有吸引力,因为在这种环境中,投票权可以通过智能合约市场实现流动。遗憾的是,这些属性也很难实现。实际上,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下以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 与匿名选民资格协议相结合,通过零知识组成员证明实例化。这样,即使选票被解密,它所揭示的信息也仅仅是有人以这种方式投票——而这一点我们已经从投票总数中了解到了。无需计票机构在设计 Cicada 时,我们的一个主要目标之一是避免依赖计票机构:许多私人投票方案需要一个半信任的计票机构(或权力委员会,通过安全的多方计算进行协调)来接收和汇总选票。在区块链环境中,这意味着这些方案不能仅通过智能合约实施,而需要一些人为干预和信任。

在大多数方案中,计票机构的诚实性不被信任(他们无法操纵选票计数),但他们的活跃度是可信的——如果他们离线,就无法计算最终结果,从而使投票结果无限期地延迟。在某些方案中,他们还被信任以维护隐私——即他们知道每个人的投票方式,但预计会在不泄漏此信息的情况下公布投票结果。

尽管在许多现实世界的场景中,计票机构是一个合理(且必要)的假设,但在区块链环境中,它们并不理想,我们的目标是尽可能减少信任并确保抗审查性。

Cicada 探索了链上投票隐私领域的多个方向之一,并与其他团队正在进行的大部分研究相互补充。如前所述,Cicada 与信号量、ZK 存储证明和限速无效器等匿名组成员技术密切相关。Cicada 还可以集成 Nouns Vortex 团队提出的乐观证明检查器,以减轻选民的 gas 负担。

有可能调整 Cicada 以支持不同的投票方案(例如代币加权投票、二次投票)——更复杂的方案对于以太坊主网来说计算成本可能过高,但它们在 L2s 上可能是实用的。考虑到这一点,我们欢迎您为 Cicada 的未来发展提供贡献、分叉和建议。

致谢:Cicada 是与 Joseph Bonneau 共同开发的。感谢 Andrew Hall 提供关于投票隐私历史背景的信息。同时要感谢 Robert Hackett 对本文的反馈。特别感谢 Stephanie Zinn 的编辑工作。

评论

所有评论

推荐阅读

  • 5月29日午间要闻速递

    1. BTC跌破68000美元

  • 加密资产金融服务提供商SCRYPT宣布完成500万美元的战略融资,Braza Bank领投

    加密资产金融服务提供商SCRYPT宣布完成500万美元的战略融资,本轮融资由布拉扎银行(Braza Bank)领投,Funfair Ventures、Cabrit Capital和Atlantic Labs等风险投资公司跟投。 SCRYPT最近还获得了瑞士监管机构的批准,可以推出资产管理解决方案,SCRYPT Digital Investments AG 将于2023年7月获得瑞士金融市场监管局(FINMA)颁发的投资组合经理许可证。

  • 美国财政部将发布NFT风险评估

    据Politico:美国财政部将发布NFT风险评估。

  • 预言机 API3 完成 400 万美元代币融资,DWF Labs 领投

    去中心化预言机 API3 宣布完成 400 万美元代币融资,DWF Labs 领投, Spartan Group、野村证券子公司 Laser Digital 和 Caladan(前 AlphaLab)参投。此轮融资将主要用于 OEV 网络主网的启动、去中心化应用(DApp)和区块链网络的进一步集成,以及支持 API3 服务的持续开发和推广。 API3 表示,此轮代币融资中 API3 以 2.81 USDC 的均价出售了 1,423,500 枚 API3 代币,出售的代币将采用 12 个月线性解锁和 6 个月锁仓的结构。

  • iGaming 项目 MetaToken 完成 500 万美元私募轮融资

    据 decrypt 报道,基于以太坊和 TON 的 iGaming 项目 MetaToken 宣布完成 500 万美元私募轮融资,若干风险投资机构、天使投资人和项目参与者参投,但具体投资方信息暂未披露。

  • MetaDragon:META NFT合约遭攻击,建议用户尽快将其转换为代币

    慢雾监测到与GameFi协议MetaDragon相关的潜在可疑活动,建议用户保持警惕。 MetaDragon在X平台发文表示,用户需尽快将METANFT转换为代币,以减少社区损失,META NFT合约刚刚遭到黑客攻击,黑客将钱包中的NFT转换为META代币并出售,攻击路径源自METANFT。

  • Aperture Finance完成A轮融资,估值2.5亿美元,将用于进一步发展其基于自然语言的DeFi平台。

    加州山景城的去中心化金融(DeFi)平台提供商Aperture Finance在A轮融资中获得了一笔不透露金额的资金,估值为2.5亿美元。此轮融资由Skyland Ventures、Blockchain Founders Fund和Krypital Group领投,Alchemy、SNZ、Stratified Capital、Tide、Cipholio、ViaBTC、CatcherVC和Double Peak等知名投资者参与。Aperture Finance将利用这笔资金进一步发挥其大型语言模型(LLM)接口的作用,将用户表达的自然语言意图转换为可以在链上编码的特定领域语言(DSL)。

  • 区块链扩展的下一个前沿:深入探索ZK Rollups

    · 虽然零知识证明(ZKPs)有望打造一个更加私密和可扩展的区块链生态系统,但许多关于零知识(ZK)的方面被误解或与普遍认知中的实施方式不同。 · ZKPs 主要有两个方面:「零知识」和「简洁性」。虽然这种说法没有错,但大多数 ZK rollups 只利用了简洁性属性,交易数据和账户信息并没有完全保持零知识或私密。 · 对于各种类型的 DApps,ZK rollups 可能不是最佳的开发堆栈选择。例如,生成 ZKPs 可能成为快速终结的瓶颈,从而降低 Web3 游戏的性能,而基于状态差异发布的数据可用性保证方法可能会损害 DeFi 借贷协议的服务。

  • 专注于零知识证明的区块链Gevulot完成600万美元种子轮融资,Variant领投

    专注于零知识证明的区块链Gevulot完成600万美元种子轮融资,Variant领投,RockawayX、Volt Capital 和 Stake Facilities 以及 Polygon Labs 首席执行官 Marc Boiron 和 Manta Network 创始人 Shumo Chu 等个人支持者参与。 Gevulot 没有透露其估值。 Gevulot 计划将资金分配给其L1区块链的推出,该区块链使开发人员能够利用ZK 证明并将计算任务委托给先进的硬件运营商网络。

  • 中科大首次实现以器件无关量子随机数产生器,消除非交互式零知识证明安全隐患

    中国科学技术大学潘建伟院士等研究者首次实现一套以器件无关量子随机数产生器作为熵源,以后量子密码作为身份认证的随机数信标公共服务,将其应用到零知识证明领域中,消除了非交互式零知识证明中实现真随机数的困难所带来的安全隐患,提高了非交互式零知识证明的安全性。非交互式零知识证明广泛应用于数字签名、区块链和身份认证等领域,由于真随机数生成器难以实现,通常会使用确定性的伪随机数算法来替代。 据了解,此次研究工作首次将量子非局域性、量子安全算法和零知识证明3个不同的领域结合起来,大幅提升了零知识证明的安全性,其中构建的面向公众的随机数服务在密码学、彩票业和社会公益等领域有着重要的应用潜力。