zkVoting：基于零知识证明的抗胁迫和端到端可验证的电子投票系统

<!--StartFragment-->

这是一篇论文解读：<!--StartFragment-->

zkVoting : Zero-knowledge proof based coercion-resistant and E2E verifiable e-voting system

<!--EndFragment-->

zkVoting有哪些特性？

• 选票隐私（BP）： 选票不泄露选民的选择。
• 选民匿名性（VA）： 选票不泄露选民的身份。
• 无收据性（RF）： 选民无法证明他们的选择。
• 抗胁迫性（CR）： 选民能够在任何影响下投票。（通过可作废承诺实现）
• 个人可验证性（IV）： 选民必须能够验证其投票包含在公告栏中。
• 通用可验证性（UV）： 任何人都必须能够验证计票结果代表公告栏上的所有选票。
• 端到端可验证性（E2E V）： 选民可以通过某种方式识别其唯一的选票，并验证其选票是按预期投出，选择是按投出记录，结果是按记录计票。（通过ZK实现）
• 合格性可验证性（EV）： 任何人都可以验证选票仅由具有投票权的合格选民生成，所有选民至多投一票。（通过成员证明实现）

zkVoting由哪些密码学模块构建？

1. 可作废承诺

允许选民在生成真实投票的同时创建多个虚假投票，使他们能够提交虚假的选票以误导胁迫者，而权威机构又可以识别投票到底是真实的还是虚假的，虚假投票即是可作废的。

在可作废承诺方案中：

1. 拥有主密钥和主公钥对的管理者向选民发放承诺密钥ck。
2. 这个承诺密钥可以是真实的承诺密钥，也可以是虚假的承诺密钥，二者不可区分。
3. 使用主密钥，承诺cm可以被作废，这将承诺转换为另一种形式的承诺（零消息）。具体而言，在作废后，使用虚假密钥生成的新承诺以零消息打开，而使用真实密钥生成的承诺以原始消息打开。
4. 将可作废承诺密钥ck* 与标准的真实/虚假承诺密钥ck区分开来，ck*专门用于打开所有作废的承诺。

为了确保密钥发放的完整性，管理者与用户交互，通过一个证明过程（KeyProve ）验证接收到的密钥的真实性。虽然这种交互式设计使用户能够验证接收到的密钥的真实性，但普遍验证是不允许的，这使得除用户外的任何一方都无法区分真实和虚假的密钥。

可否认性确保用户可以合理地否认--接收到虚假的承诺密钥，并将其作为真实的承诺密钥--该特性由一个模拟算法（SimKeyProve）提供支持。

2. 混合加密

3. 零知识证明

4. 成员证明

zkVoting的投票方案

一个电子投票系统是由一组协议在一组实体之间执行的。根据其在投票系统中的角色和功能，这些实体可以分为三种类型。

1. 权威机构（Authority）： 权威机构监督整个投票系统，进行设置和注册阶段。在计票阶段，权威机构收集所有选票，计算结果并公布。
2. 选民（Voters）： 选民有权投票。他们需要注册才能投票。所有选民都有他们的ID以参与选举。
3. 公共公告栏（Public Bulletin Board, BB）： 公告栏是公共的，所有实体都可以访问。所有选民的选票都发布在公告栏上。BB被设计为一个基于Truffle框架的区块链智能合约。

• 为了增强电子投票系统的抗胁迫性，使用了可作废承诺方案的承诺密钥ck作为投票密钥。
• 通过引入伪造投票承诺密钥，允许选民提交假选票，从而形成抗胁迫的机制。 每个投票密钥被授权用于投出一张选票。虽然只允许一个真实的投票密钥，但可以颁发多个假投票密钥，以抵御可能的胁迫攻击。
• 在登记阶段结束时，投票密钥被上传到公告板并用于验证选民资格。
• 确保可验证性的核心概念是使用零知识证明系统（ZKP）来证明算法按预期执行，从而确保所有实体（如选民和当局）遵循协议。 在诸如冲突攻击的场景中（如两个选民为同一候选人投票），恶意投票设备或当局可能会使用相同的选票欺骗选民。两个选民并没有意识到他们查看的是同一张选票。因此，选票应附上选民的姓名或假名，以满足端到端（E2E）可验证性。
• 为了实现E2E可验证性，我们采用了序列号的概念。该序列号与选民的私钥和投票密钥通过密码学哈希函数绑定。这也防止了重复投票。这些技术使得能够构建E2E可验证的电子投票系统，并对选举的完整性提供了高度信心。
• 每个加密的选票都与使用ZKP的承诺相关联，并且通过同态聚合和可作废的承诺，计票过程得到了高效验证。

投票分为四个阶段：

1. 设置阶段

2. 注册阶段

3. 投票阶段

在投票阶段，选民使用之前获得的“投票密钥”进行投票。每次投票，系统都会生成一个独特的序列号SNR，类似于一张票据，这个票据记录了选民的投票行为。 序列号是加密的，因此没有人能够直接看到你投了谁，但它可以帮助你确认自己的投票已经被正确地提交。

4. 计票阶段

在投票结束后，系统进入计票阶段。此时，所有已经提交的选票都会从公告板上下载，并开始计票。因为每张选票都经过加密处理，计票系统必须先解密这些选票才能读取其中的投票内容。

解密之后，系统会筛选出哪些是有效的投票。 假设有选民使用了假的投票密钥进行投票，这些投票会被识别为无效并被剔除。这样可以确保最终的计票结果只包含那些合法的、使用真实投票密钥的选票。

计票完成后，系统会生成一个汇总的投票结果，并把它上传到公告板。任何人都可以查看这个结果，并验证计票的过程是公正和透明的。

实验

• 对于零知识证明系统，在C++中使用了Gro16 zkSNARK证明系统。该系统由于其固定大小的证明和高效的验证，非常适合区块链应用。
• 该系统的一个关键方面是可信设置阶段，在该阶段，权威机构准备公共随机字符串并将其上传至BB。
• 对于抗碰撞的哈希函数，我们采用了为zk-SNARKs优化的MiMC7哈希函数。
• 对于成员资格证明，我们使用了Merkle哈希树。
• 可作废的承诺方案是基于椭圆曲线实现的。由于这条曲线的阶为254位，因此支持最长254位的消息。相应地，我们将合格选民的最大数量nv设定为2^16，候选人数量为15。
• 权威机构：Intel Xeon Gold 6242R CPU with 250 GB RAM
• 投票设备：

• 下表分析了这些关系。Rvote包含成员资格证明和加密，导致大量约束并具有最大的CRS（公共参考字符串）。CRS大小的增加不仅会延长验证时间，还会影响应用程序的总体大小。

选民下载应用程序后，证明其身份并登记参加选举。

• 图(a)展示了不同设备在注册阶段的时间成本。
• 图(b)显示了投票阶段的执行时间。投票可以在几秒内完成，尤其是在高性能设备C、D和E上，投票时间不到3秒。投票交易在BB中处理，在以太坊上需要347,363 gas。请注意，由于350K gas的费用在公共区块链上相当昂贵，因此为BB设计专用侧链是合适的。
• 图(c)展示了计票阶段的执行时间，其中x轴表示选票数量。计票过程包括选票解密和计票证明生成。每张选票的解密时间为3.9毫秒，服务器上生成计票证明的时间为360毫秒。请注意，计票过程可以通过并行处理得到改进。

<!--EndFragment-->