DAVINCI协议白皮书

[D]ecentralized [A]utonomous [V]ote [I]ntegrity [N]etwork with [C]ryptographic [I]nference

摘要

DAVINCI 是 Vocdoni 投票协议的演进，旨在通过提供安全、可验证和匿名的数字投票的基本工具来增强公民社会的能力。利用零知识证明和区块链技术的最新进展，Vocdoni 协议转变为专用 zkRollup 系统，该系统继承了以太坊主网等结算层的网络安全性。该系统完全依赖于加密证明来确保完整性和安全性，从而消除了对中心化机构的需求。通过集成 zkSNARKs 和阈值同态加密 (ElGamal)，DAVINCI 实现了投票过程中的端到端可验证性、隐私性和无需信任。

该协议采用在排序器之间进行分布式密钥生成，通过以太坊智能合约进行协调，并利用以太坊数据 blob (EIP-4844) 来实现数据可用性。DAVINCI 专注于可访问性、可扩展性、抗收据性和自动化，旨在促进高频率、低成本的投票，从而促进电子投票的大规模采用并简化公民参与。最后，Vocdoni Token (VOC) 的引入协调了参与者之间的激励，从而确保了网络的可持续性。

愿景和背景

Voĉdoni 在世界语中意为“给予声音”，体现了我们从基层增强公民社会力量的使命。我们的目标是构建基本的原语和工具，使任何集体——从小组到数百万公民——都能被倾听，无论他们的处境或可用资源如何。

我们的理念设想投票超越了传统的民族国家选举； 我们将其视为一种集体信号机制，具有完整性和结果的加密保证。

为了应对这一挑战，我们开发了一种端到端可验证和匿名的投票系统，旨在可在任何设备上使用，包括智能手机。 我们还成功部署了一个最大限度地提高弹性、中立性和透明度的基础设施。

2018 年 Vocdoni 刚开始时，zkSNARKs 还只是一项新兴技术。 我们选择将我们的解决方案建立在名为 Vochain 的定制拜占庭容错 L1 区块链之上。 这使我们能够实现可扩展性（大约每秒 700 笔交易），利用在基于 EVM 的区块链上成本高昂的高级加密工具，并使用户能够免费发送投票交易。

这一经验为我们提供了宝贵的见解，使我们能够克服技术和运营方面的挑战。 尽管此解决方案已有效地满足了用户需求并证明了其可行性，但作为通用投票协议，进一步的开发对于其广泛采用至关重要。

DAVINCI 代表了 Vocdoni 投票协议的演进。 它集成了用于编排的智能合约、用于验证和累积投票的基于 zkSNARK 的状态机以及用于确保抗审查性的去中心化数据可用性层。

设计原则

为了构建 DAVINCI 堆栈，我们坚持以下设计原则：

1. 加密技术作为真理的来源： 我们完全依赖于加密证明 -> 广泛验证的加密方案，以确保投票过程的完整性和安全性。 通过仅信任加密技术，我们消除了对中心化机构的需求，从而使系统本质上安全透明。

2. 无需信任： 我们的系统运行无需信任任何一方。 通过加密协议和去中心化基础设施，我们确保系统完整性并防止任何恶意行为者的破坏。

3. 端到端可验证性： 每位选民都可以验证他们的投票从投票到结果计算（字体）。 此外，任何第三方都可以审核选举数据以确认结果（字体，因为它是一项像“无需信任”一样的原则）并验证每张选票都来自唯一注册的选民（字体）。 透明的加密机制使这成为可能。

4. 可组合性： 该系统是模块化的，由可互换的组件组成，这些组件可以通过适应性强的接口重新排列或与外部系统集成。 这允许冗余、灵活性以及与第三方应用程序的无缝集成，我们的 Voting-as-a-Service 的API就是例证。

5. 可访问性： Vocdoni 的投票平台（应用程序）是开源的、公开可用的且用户友好的。 该界面对于所有用户来说都很直观，包括那些不太熟悉技术的用户，并且可以容纳使用屏幕阅读器等辅助技术的选民。

6. 开源： 通过公开我们的代码，我们邀请任何人进行审核和贡献，从而增强安全性并促进社区参与。 透明度使得通过默默无闻来确保系统安全变得完全不必要，并加速了创新。

7. 弹性： 我们的设计旨在防范硬件故障、网络中断和审查。 基础设施去中心化和分布式所有权提高了系统的可用性和抵抗攻击的能力。

8. 可扩展性： 我们的解决方案可以高吞吐量地处理投票，超出当前需求以适应未来的增长。 去中心化基础设施随着使用量的增加而有机地扩展，从而确保一致的性能。

9. 抗收据性： 为了减轻勾结、胁迫和购买选票的风险，该系统使选民能够验证他们的选票，而无需向他人证明他们是如何投票的，从而减少了胁迫和贿赂的动机。 此外，允许选民在保持保密性的同时覆盖他们的选票。

10. 自动化： 我们通过智能合约和加密协议最大限度地减少人为干预，从而降低成本和人为错误。 自动化确保一致的运行，并释放资源用于选民支持、审计和自动执行。

---

使用的关键技术

1. zkSNARKs

零知识简洁非交互式知识论证是确保投票结果有效性的关键组成部分。 选民生成 zkSNARK 证明来证明他们加密的选票符合投票过程的规则和要求，而不会泄露有关其选择的任何信息。 Sequencer 还生成 zkSNARK 证明，以证明投票正确聚合到共享状态中，该状态维护投票过程的状态。

2. Merkle 树

Merkle 树用于创建选民登记（人口普查）和投票过程状态的加密表示：

• 人口普查： 每位选民都会被分配一个 Merkle 证明，他们使用该证明来证明他们有资格投票。 这种机制确保了选民资格的有效且安全的验证。
• 状态： 投票过程状态表示为 Merkle 树，新投票被添加到该树中。 此 Merkle 树的根存储在以太坊上，允许多个排序器参与投票阶段并确保一致性。

3. 阈值同态加密

阈值同态加密，特别是 ElGamal 方案，用于允许在不解密的情况下对加密投票进行求和。 这使得系统能够在维护个人投票隐私的同时计算最终投票总数。 通过确保在聚合阶段不会公开任何投票，此方案可以保护选民的机密性并提供反胁迫保护，因为一旦添加加密投票，选民就无法向第三方证明他们的选择。

4. 分布式密钥生成 (DKG)

DKG 协议用于以去中心化的方式生成加密公钥 (EPK)。 Sequencer 协同参与 DKG 过程以创建 EPK，从而确保没有单方完全控制密钥。 这种方法保证了加密密钥的安全性，并且只有当达到阈值数量的 Sequencer 发布其份额时，才有可能解密结果。

5. 以太坊智能合约

以太坊智能合约用于协调投票过程、管理状态转换以及存储关键数据，例如当前状态根和加密公钥。 这些智能合约提供了一个无需信任的环境，确保所有参与者都可以确信投票过程规则得到正确执行。

6. 以太坊数据 Blob (EIP-4844)

EIP-4844 用于数据可用性，从而可以以太坊数据 blob 的形式存储状态转换数据。 这种机制允许 Sequencer 协作构建和验证投票过程状态，从而确保高效且去中心化的数据可用性。

---

组件概览

下面，我们详细介绍了架构的组件，这些组件共同支持投票系统的运行和管理。

以太坊

与以太坊兼容的网络被用作投票系统的真理来源。 通过利用 EVM 区块链，流程管理可确保所有转换对于所有参与者都是不可变且可验证的。 为此，我们实施了多个智能合约。

• 流程管理： 此智能合约负责投票流程的生命周期管理。 它包括投票事件的启动、配置、监控、执行和关闭。

• 结果验证： 此智能合约维护每次投票流程的投票和流程生命周期的完整性。 它通过检查提交的 zkSNARK 证明来验证 Sequencer 提交的每个状态转换是否符合预定义的规则。

• Sequencer 注册表： 此智能合约跟踪现有的可用 Sequencer，存储抵押品以确保良好行为，并用于在创建新的投票流程时协调分布式密钥生成。

Sequencer

Sequencer 是一种专用组件，旨在采用零知识证明机制处理投票过程。 它确保与此过程相关的所有交易都经过验证和排序。 Sequencer 定期将投票过程的状态提交给以太坊。

前端用户界面

用户界面充当选民和组织者的主要交互层。 它提供了设置、管理和监督选举、投票等工具和功能。 此界面隐藏了管理去中心化投票系统的复杂性。

数据可用性

对于每个投票过程，系统都会跟踪当前状态 Merkle 树，其中包含此类过程的所有信息。 公共数据可用性层确保所有状态转换都可用且可验证，并允许同一投票过程中多个 Sequencer 的参与。

---

运行概览

该流程包括投票事件的初始化、分布式密钥生成、加密投票、投票验证和累积，最终公布并公开验证结果。 每个阶段都利用先进的加密技术来确保投票过程的完整性、隐私性和普遍可验证性。

1. 组织者创建一个新的投票流程
   • 准备人口普查数据。
   • 设置投票详细信息，例如持续时间、选项、类型等。
   • 将交易发送到以太坊流程智能合约。
2. Sequencer 创建分布式阈值加密密钥
   • 使用 Sequencer 注册表智能合约来协调分布式密钥生成 (DKG)。
   • 提供抵押品以确保正确参与 DKG。
   • 下载处理新投票过程所需的所有数据，例如人口普查 Merkle 树。
3. 一旦加密公钥 (EPK) 可用，投票就开始
4. 选民投票
   • 选择任何可用的 Sequencer。
   • 获取他们的人口普查 Merkle 证明以证明资格。
   • 使用 EPK 加密他们的选票。
   • 生成一个 zkSNARK 来证明加密选票（ballotproof）的有效性以及遵守投票过程规则。
   • 生成身份验证证明，该证明由资格的人口普查 Merkle-Proof 和前一个 ballotproof 输入的签名组成。
   • 将加密的选票、ballotproof 和身份验证证明发送给 Sequencer。
5. Sequencer 验证和累积投票
   • 获取当前状态：从以太坊智能合约检索当前的有效流程状态根，并从以太坊 blob 中检索关联的数据。
   • 生成状态转换的 zkSNARK，递归证明：
     • zkSNARK 加密选票证明的有效性。
     • 身份验证和资格证明的有效性。
     • 来自用户的投票的正确累积，将它们添加到流程状态。
     • 使用 ElGamal 的同态属性正确地对新的加密投票求和。
     • 新投票来自符合条件的用户，方法是检查人口普查 Merkle 证明。
     • 新投票者尚未通过检查其无效器进行投票，或者它是正确的投票覆盖
     • 数据 blob 哈希与用于验证转换的数据匹配。
   • 提交更新的状态：将新状态根发送到智能合约，并将更新的数据存储在以太坊 blob 中。
6. 智能合约验证状态转换
   • 验证 Sequencer 提供的 zkSNARK 证明。
   • 确保原始根与当前存储的状态根相对应。
   • 确认 blob 哈希与以太坊中存储的哈希匹配。
7. 重复直到投票结束
   • Sequencer 累积更多投票并创建状态转换，直到流程最终完成。
8. 创建解密密钥
   • 投票结束后，Sequencer 将 EPK 的份额发布到以太坊智能合约。
   • 解密结果：当达到股份阈值时，任何人都可以解密结果。
   • Sequencer 根据排序投票的数量获得正确参与的奖励。
9. 公开验证最终结果
   • 投票期结束后，结果被解密后，任何人都可以验证最终结果的正确性。
   • 使用 zkSNARK 状态证明和链上公开可用的数据来确保整个投票过程的完整性和正确性。

Sequencer 和状态转换

当新的投票流程开始时，Sequencer 会初始化一个新状态，该状态由 Merkle 树的根哈希表示。 此树封装了有关投票过程的所有基本信息，包括过程参数、选民登记（人口普查）、投票配置和初始结果。

对于每批新投票，Sequencer 都会通过生成一个 zkSNARK 证明来更新状态，该证明验证从当前根到新根的状态转换。 此证明会提交到链上进行结算。 这样做，我们在区块链上维护了一个不可变且可验证的投票过程记录。

这种方法允许任何人从结果验证智能合约访问投票过程的最新验证状态，以及处理后续状态更新所需的数据。 该系统的设计使多个 Sequencer 能够参与计票。 他们可以获取当前状态根及其关联的数据来构建下一个状态，并将新投票纳入计票中。 Sequencer 的这种去中心化有助于防止潜在的审查，并增强投票过程的稳健性。

维护完整性链

完整性链通过智能合约强制执行和严格的 zkSNARK 电路约束来维护。 这确保了每个状态转换都是有效的，并且建立在上次接受的状态之上，而无需额外的机制。

• 连续状态根： 在处理一批投票后，每个状态转换都会将 Merkle 树从先前的根 (`Root1`) 更新到新根 (`Root2`)。
• 智能合约强制执行： 智能合约验证 zkSNARK 证明中提供的 `Root1` 是否与链上存储的上次提交的状态根匹配。 这保证了所有转换都是连续的，并且基于最新的验收状态。
• 证明验证： 智能合约使用 zkSNARK 验证密钥来验证提交的证明。 有效的证明确认从 `Root1` 到 `Root2` 的转换符合电路强制执行的所有协议规则。
• 状态更新： 成功验证后，智能合约会将存储的状态根哈希更新为 `Root2`, 从而确保不可变且连续的状态链。

状态 Merkle 树结构

状态树包含一些特殊的地址（索引），用于存储有关投票过程的一些所需数据：

• 地址 `0x0`: 流程标识符: 存储投票流程的唯一标识符。
• 地址 `0x1`: 人口普查根和类型: 包含验证投票证明所需的信息。
• 地址 `0x2`: 投票模式: 编码验证投票的规则，例如最大可选选项数。
• 地址 `0x3`: 阈值加密密钥: 用于加密投票的公钥。
• 地址 `0x4`: 添加的结果累加器: 存储需要添加的聚合加密投票结果。
• 地址 `0x5`: 减去的结果累加器: 存储需要减去的聚合加密投票结果。
• 任何地址: 投票地址: 存储在状态树中，指向存储为叶子的上次加密投票。
• 任何地址: 投票标识符: 存储在状态树中，指向空叶子。

初始状态

投票过程从初始状态开始，其中建立 Merkle 树根并在流程管理智能合约上发布。 包含预定义的参数，但结果初始化为零，并且不存在任何无效器。

流程组织者交易包含初始根和必要 Merkle 证明。 这些证明验证初始参数根据投票流程信息是否正确，并且没有存储任何其他信息。 由于初始状态的 `ProcessId` 是一个唯一标识符，因此对于不同的流程不会有重复的根。

状态转换

为了验证和处理状态转换，我们采用了一个 zkSNARK 电路来强制执行所有协议约束。 此电路证明，基于新处理的投票，从先前的状态根到新状态根的转换是有效的。

该电路具有以下输入（验证证明需要公共输入）。 请注意，我们将电路拆分为 3 个链式电路，每个电路负责验证过程的特定部分。 但是，为简单起见，我们将在本节中将整个电路称为一个电路。

• 公共输入：
  • 先前状态根 (Root1)：状态转换之前的 Merkle 树根。
  • 新状态根 (Root2)：状态转换之后的 Merkle 树根。
  • Blob 数据承诺 (blobCommitment)：对包含已修改和新添加的重新加密投票的数据 blob 的承诺。
• 私有输入：
  • 投票：正在处理的新投票列表，包括人口普查证明和身份验证数据。
  • 无效器包含的 Merkle 证明：每个选民无效器都包含在人口普查中的证明。
  • 结果更新的 Merkle 证明：流程结果已正确更新的证明。
  • Merkle 树更新见证：将 Merkle 树从 Root1 更新到 Root2 所需的数据（例如，Merkle 路径）。
  • 流程参数：从电路内的 Root1 检索。

电路必须强制执行以下约束。

• 不可变的流程参数： 确保从 `Root1` 检索的关键流程参数（例如 censusRoot 或 processId）保持一致，并且在转换中不会更改。
• 投票有效性： 验证每个投票证明是否正确。
• 选民资格 通过根据从 Root1 检索的 censusRoot 验证包含的 Merkle 证明，确认每位选民都包含在人口普查中。
• 无效器不存在： 确保每个投票的无效器都不存在于当前状态 (`Root1`) 中，防止重复投票。
• 无效器添加： 将每个新无效器正确添加到状态，从而生成 Root2，相应地更新 Merkle 树。
• 结果更新： 确保通过将新投票添加到从 Root1 检索的先前结果来准确更新投票结果，以便 results2 = results1 + votes。
• Blob 数据完整性： 确认用于构建新状态的电路（重新加密的选票）中使用的数据与作为公共输入提供的 blobCommitment 相对应。
• 状态转换有效性： 确保新状态根（Root2）是通过将经过验证的投票和更新应用于 Merkle 树从 Root1 正确计算得出的。

投票流程的最终确定

在投票期结束时，智能合约停止接受新的状态更新，从而有效地最终确定该流程。 然后可以在链上验证最终状态，从而提供投票结果的不可变记录。

---

人口普查

人口普查代表符合资格的选民列表以及他们各自的投票权重。 它以二进制 Merkle 树的形式实现，使用 iden3 稀疏 Merkle 树 (SMT) 和一个 zkSNARK 友好的哈希函数，以确保与零知识证明的兼容性。

在此 Merkle 树中：

• 路径对应于选民的地址（例如，他们的以太坊地址或任何唯一标识符）。
• 叶值存储分配给该地址的投票权重。

此结构允许高效生成和验证 Merkle 证明，使选民能够在不泄露整个人口普查数据的情况下证明他们的资格和投票权重。

投票流程的组织者负责构建人口普查数据。 只有人口普查 Merkle 树的 根哈希 存储在链上，从而在最大限度地降低链上数据存储成本的同时，确保透明度和不变性。 完整的人口普查数据在链下共享，通常通过 IPFS 或 HTTPS 端点，允许参与者和 Sequencer 获取数据并根据需要生成 Merkle 证明。

尽管构建人口普查数据的方法超出了核心协议的范围，但我们提供了对常见方法的见解，以适应各种用例。

1. 私有数据集

对于维护符合资格的选民及其投票权重的私有列表的组织（例如会员数据库、CRM 系统或 CSV 文件），可以针对每个投票流程直接从此数据集构建人口普查数据。 组织者将列表转换为 Merkle 树格式，确保每个选民的地址和权重都正确地表示在叶子中。 这种方法很简单，并且使选民登记保持机密性，因为只有根哈希是公开的。

2. 自主身份 (SSI)

该协议支持使用自主身份系统。 如果选民的身份通过 SSI 解决方案进行管理，并且他们的地址在链上或链下可用，则人口普查数据可以包含此信息。 组织者聚合 SSI 数据以构建 Merkle 树，从而允许选民使用其自我管理的身份安全地参与投票过程。

3. 基于以太坊的 Token

要利用现有的基于以太坊的 Token（例如 NFT 或 ERC20 Token）作为人口普查数据的基础，有两种主要方法：

• 乐观方法： 在乐观方法中，使用与该区块对应的状态根，在特定的以太坊区块高度拍摄 Token 持有者的快照。 第三方（或组织者）获取所有 Token 持有者的地址和余额，从此数据构建人口普查 Merkle 树，并将根哈希提交给投票智能合约。

为了确保准确性并防止欺诈，会有一个异议期，在此期间，任何人都可以质疑人口普查数据的有效性。 如果发现差异，例如不正确的余额或缺失的地址，挑战者可以提交欺诈证明。 这通常涉及提供来自人口普查数据的 Merkle 证明和以太坊存储证明（根据 EIP-1186），以显示指定区块高度的正确余额。 如果挑战有效，则可以拒绝人口普查数据。

• ZK 方法： ZK 方法涉及生成使用零知识证明进行加密验证的人口普查数据。 对于给定的以太坊区块号和状态根，链下 zkSNARK 电路验证了人口普查 Merkle 树的正确构建：

  • 余额验证 对于每位 Token 持有者，该电路使用以太坊存储证明验证他们的余额。
  • 总供应量一致性 所有经过验证的余额的总和必须与 Token 的总供应量匹配。
  • 证明生成 该电路输出一个证明，证明人口普查数据是根据指定区块的以太坊状态正确构建的。
• • *

投票

投票包含多个组件，这些组件协同工作以确保安全、私密且可验证的投票。 这些组件包括：

1. 流程标识符 (PID)
2. 人口普查资格证明
3. 加密投票
4. 选票加密有效性的 ZK 证明
5. 地址
6. VoteId
7. 签名

下面，我们详细介绍了每个组件及其在投票流程中的作用。

1. 流程标识符

流程标识符 (`ProcessId`) 是一个唯一的 32 字节数字，用于唯一标识 DAVINCI 网络中的特定投票流程。 它通过附加链 ID、组织者的地址和一个 nonce 来确保唯一性而形成的。 此标识符由流程管理智能合约管理。

2. 人口普查资格证明

人口普查证明充当选民的身份验证机制，确保只有符合资格的选民才能参与。 根据流程配置，选民提供：

• 基于 Merkle 树的证明 显示包含在人口普查中的 Merkle 证明。
• 凭证服务提供商 (CSP) 受信任的第三方颁发的凭证。

3. 加密投票和零知识证明 (ZKP)

选票包含根据选票协议规则编码的选民选择。 为了确保隐私，选票使用椭圆曲线上的 ElGamal 密码系统加密，该系统允许对加密的投票进行同态组合。

加密过程：

• 选民的选择

m 被编码为一个点

M 在椭圆曲线上。

• 选民选择一个随机标量

k∈[1,n−1]，其中

n 是椭圆曲线群的阶。

• 计算密文分量：
  • C1=k⋅G
  • C2=M+k⋅H
• 密文是配对

(C1,C2)。

零知识证明 (ZKP)：

选民生成一个 ZKP 来证明选票和加密过程的正确性：

1. 加密的正确性 确保密文

(C1,C2) 是从明文消息正确计算出来的

M 和随机标量

k。

2. 符合选票协议规则 明文投票

m 遵循选票协议约束，例如有效选择和允许的选择数量。

3. 正确计算投票 ID 从哈希选民的地址、流程标识符和随机标量

k。

ZKP 电路的输入：

• 公共输入：

  • 加密选票

  (C1,C2)。

  • 选票协议配置。
  • 选民的权重。
  • VoteId

  V.

  • 地址

  A。

  • ProcessId

  PID。

• 私有输入：

  • 明文选票

  m。

  • 随机标量

  k。

4. VoteId

VoteId

V 是一个唯一的标识符，用于标识已投的选票。 由于选民可以发出多个选票，因此 VoteId 可用于跟踪每个选票。 它还用于防止重放选票，因为它属于状态 Merkle 树的一部分。 VoteId 的计算方法如下：

V=Hash(Address∥ProcessId∥k)

其中：

• 地址 选民的地址或唯一标识符。
• ProcessId 投票过程的唯一标识符。
• k 加密过程中使用的随机标量。

5. 地址

地址是选民的唯一标识符，通常是他们的以太坊地址或投票过程中使用的任何其他唯一标识符。 它用于将选票链接到选民，并确保每位选民每个投票过程只能投一张选票。

6. 签名

签名验证选票并确保它是经合法选举人投出的。 选民使用其私钥签署必要的组件，具体取决于人口普查配置（例如，ECDSA、EdDSA、RSA）。

---

选票协议

Vocdoni 选票协议定义了一种简单有效的机制，用于在任何类型的选举或集体决策过程中进行投票和计票。 每个投票过程由一个或多个字段组成，选民需要在选票中为每个字段提供回复。

选票中的回复表示为一系列自然数，每个自然数对应于选民对相应字段的选择。结果累积到一个数组中。 数组中的每个位置对应于所有选民对该字段投出的所有选票的总和。

选票协议由一组可配置的变量定义，这些变量规定了投票的方式。 这样，该协议可以适应各种投票过程和行为。

1. numFields 定义选票中的最大字段数（最多 64 个）。
2. maxValue 选票中任何字段的最大允许值（如果大于 0）。
3. minValue 选票中任何字段的最小允许值（默认为 0）。
4. uniqueValues 指定选民是否可以在选票中多次选择相同的值（默认为 false）。
5. maxValueSum 限制选票中所有字段值的总和（如果大于 0）。
6. minValueSum 指定选票中字段值的最小必需总和（默认为 0）。
7. costExponent 定义用于计算每个字段的选票“成本”的指数（默认为 1）。

示例 1：评价候选人

考虑一个投票过程，选民被要求评价三位候选人：Lennon、Hendrix 和 Joplin。选民为每位候选人评出 0 到 5 星，并且每个选票都表示为一个数组，其中每个位置对应于候选人的评级。

配置：

• numFields：3
• maxValue：5
• uniqueValues：是

选票：

• 投票 1：[3, 2, 5]（为 Lennon 3 星，为 Hendrix 2 星，为 Joplin 5 星）
• 投票 2：[4, 3, 2]
• 投票 3：[2, 4, 5]

在累积投票后：

• 结果数组：[3+4+2, 2+3+4, 5+2+5] = [9, 9, 12]

Lennon 获得 9 分，Hendrix 获得 9 分，Joplin 获得 12 分。

示例 2：资源分配的二次方投票

在选民在不同选项之间分配固定数量的信用额度（例如，选择 NGO 的资助级别）的方案中，选票允许选民分配多个点数，但对单个选项投出多个选票的成本呈平方级增长。

配置：

• numFields：4
• maxValueSum：12（信用额度）
• costExponent：2（二次方）

选票：

• 投票 1：[2, 2, 2, 0]
• 投票 2：[1, 1, 3, 1]
• 投票 3：[0, 2, 1, 2]

在累积投票后：

• 结果数组：[2+1+0, 2+1+2, 2+3+1, 0+1+2] = [3, 5, 6, 3]

数组中的每个位置代表分配给每个 NGO 的信用额度总和。

---

投票加密密钥

投票过程的隐私通过使用阈值同态加密方案来确保。 具体来说，使用的是 椭圆曲线上的阈值 ElGamal 密码系统。 此密码系统提供安全且可验证的数字投票所必需的同态和阈值属性。 加密消息可以组合起来，以生成原始明文总和的加密，而无需解密它们。在投票的背景下，这允许安全地聚合选票，同时保持选民选择的私密性。

1. 协同密钥生成：
   • 公钥由排序器协同生成，没有任何一方知道完整的私钥。
   • 利用分布式密钥生成 (DKG) 协议，使用阈值方案在 s 个 n 个排序器之间共享私钥。

2. 加密： 给定一条消息 m 被编码为椭圆曲线上的一个点 M ( M=mG)：

   • 选择一个随机标量 k∈[1,n−1] 并考虑 H=sG。
   • 计算：
     • C1=k⋅G
     • C2=M+k⋅H
   • 密文是 (C1,C2)。
3. 同态加法： 椭圆曲线上的 ElGamal 密码系统支持表示为点的消息的加法同态：
   • 给定两个密文 (C1(1),C2(1)) 和 (C1(2),C2(2))，它们的组件级加法产生：
     • C1(sum)=C1(1)+C1(2)
     • C2(sum)=C2(1)+C2(2)
   • 聚合的密文解密为消息的总和：
     • M(sum)=M1+M2
4. 解密：
   • 要解密聚合的密文（投票总和），最少数量的排序器（阈值 t) 必须提供他们的部分解密份额。每个排序器计算 Di=si⋅C1
   • 组合部分解密：
     • 使用拉格朗日插值法组合 Di 并恢复 s⋅C1。
     • 从 C2 中减去以获得聚合的消息点：
     • M(sum)=C2−s⋅C1
     • 通过求解离散对数从 M 中提取消息 m：
     • m=logG⁡M

对于求解离散对数问题并计算最终结果，由于消息很小，因此可以通过暴力搜索或使用 baby-step giant-step 算法来完成。

---

分布式密钥生成（DKG）

DAVINCI 采用分布式密钥生成 (DKG) 协议，该协议允许一组参与者（排序器）共同为 ElGamal 密码系统生成公钥/私钥对，而无需任何单个参与者知道完整的私钥。相反，每个参与者都持有私钥的一部分，并且只有达到阈值数量的参与者可以协作解密消息（阈值是可配置的）。这消除了对可信经销商的需求，并防止了单点故障，从而增强了安全性。

属性

• 去中心化密钥生成： 没有单一方知道完整的密钥。
• 通过以太坊进行协调： 各方不需要直接交互，他们使用以太坊智能合约来引导流程并交换所需的信息。
• 阈值安全： 需要最少数量的参与者（阈值）来重建密钥。
• 可验证的份额： 各方和以太坊可以验证他们收到的份额的正确性。
• 可扩展性： 支持任意数量的参与者和可配置的阈值。

协议步骤

1. 初始化：
   • 以太坊智能合约提供初始参数：
     • 阈值 t：解密消息所需的最少参与者数量。
     • 总参与者 n：涉及的排序器总数。
     • 椭圆曲线参数： 选择具有生成点 G 和阶数 q 的合适椭圆曲线。
2. 秘密多项式生成：
   • 每个参与者 Pi 生成一个 t−1 阶的随机秘密多项式： fi(x)=ai,0+ai,1x+ai,2x2+⋯+ai,t−1xt−1
     • 系数 ai,j∈Zq 是随机选择的。
     • 常数项 ai,0 是 Pi 的个人秘密。
3. 系数承诺：
   • 参与者计算其多项式系数的公共承诺： Ci,j=ai,j⋅G
     • 这些承诺是椭圆曲线上的点，并发布给所有参与者。
     • 这确保了透明度，并允许其他人验证份额，而无需泄露秘密。
4. 份额计算：
   • 每个参与者计算每个其他参与者 Pj 的份额： si,j=fi(j)
     • 份额 si,j∈Zq 是秘密标量值。
5. 安全且经过验证的分配：
   • 在分配之前，使用简化版本的 椭圆曲线集成加密方案 (ECIES) 加密份额，因为我们只需要加密一个标量：
   • 每个参与者都提供一个 zkSNARK 证明来证明：
     • 加密份额的正确性。
     • 符合 DKG 协议规则。
   • 这允许以太坊上的智能合约验证有效性，而无需泄露秘密。
6. 份额聚合：
   • 每个参与者通过将收到的份额（包括他们自己的份额）相加来计算他们的私钥份额： sj=∑i=1nsi,jmodq
   • 这成为 Pj 的集体私钥的一部分。

7. 公钥计算：

   • 参与者计算集体公钥： PK=∑i=1nCi,0

     • 由于 Ci,0=ai,0⋅G, 公钥实际上是： PK=s⋅G

     其中 s=∑i=1nai,0modq 是集体私钥（任何单个参与者都不知道）。

8. 公钥分配：
   • 任何参与者都可以将集体公钥 PK 发布到以太坊智能合约。

---

无收据性

在民主进程中，选民能够自由地投票，而不受不当影响或胁迫的能力至关重要。维护这种自由的一个关键方面是确保无收据性，防止选民能够向第三方证明他们如何投票。DAVINCI 利用 ElGamal 密码系统和 zkSNARK 的属性来实现无收据性。

选票重新加密

椭圆曲线上的 ElGamal 密码系统支持加法同态，允许对密文执行操作，这些操作会转换为基础明文的加法。重新加密是一个刷新密文的随机性而不更改基础明文消息的过程。这使得计算上无法将原始密文和重新加密的密文联系起来。

处理收据

为了防止选民能够证明他们如何投票，DAVINCI Z 采用排序器对选票进行重新加密。当选民提交加密的选票时，排序器会重新加密它，然后再将其存储在状态 Merkle 树中。

这样，系统确保选民不能通过泄露 r 来生成其投票的收据，因为存储的密文不再对应于 r。 这可以防止第三方进行买票和胁迫。

处理共谋

为了进一步增强无收据性并减轻选民和排序器之间共谋的风险，DAVINCI 允许选民覆盖他们的选票。选民可以提交多个选票，每次新提交都会替换上一个选票。

当排序器收到来自已投票的选民的新选票时，它将执行以下步骤：

1. 检测覆盖： 排序器使用选民的无效器检查状态 Merkle 树，以确定选民是否之前已投票。
2. 减去上一次投票： 排序器获取现有的加密选票，并将其添加到“减法结果”累加器中。这实际上抵消了最终计票中的上一次投票。
3. 添加新投票： 新的加密选票被添加到“结果”累加器中。
4. 更新状态 Merkle 树： 排序器重新加密新选票，并使用此重新加密的选票更新状态 Merkle 树。

隐藏投票覆盖

为了防止观察者检测到何时发生覆盖，排序器在每次状态更新期间定期重新加密状态 Merkle 树中随机选定的选票子集。此过程模糊了覆盖的发生，因为重新加密与为增强隐私而执行的标准重新随机化无法区分。

通过将随机选票重新加密，系统会增加熵，并使对手在统计上不可能确定特定选票是被覆盖还是只是被重新随机化。

---

如何保护用户隐私

DAVINCI 通过匿名化选票和选民身份来确保用户匿名性，采用密码学技术来维护隐私，即使面对未来的量子计算威胁也是如此。该系统使用 ElGamal 同态加密方案 来加密选票，从而可以在不泄露个人选择的情况下聚合选票。由于加密的选票存储在公共存储库（如以太坊 blobs）中——尽管在几周后会被删除，但可能仍然可以访问——因此至关重要的是要防止解密的选票与选民身份之间存在任何关联。通过使用秘密和密码学哈希将选民身份与其加密的选票分离，即使对手将来解密选票，他们也无法将其链接回个别选民。

身份匿名化充当双重安全因素，增强了长期隐私。虽然处理投票的排序器可以识别选民（因为选民提交资格证明和承诺），但排序器没有动力公开此信息，并且排序器无法解密选民的选票，因为他们不拥有私有解密密钥。这确保了选民的选择保持机密。

我们采用了这种部分身份匿名化，因为直接从数字签名（例如，ECDSA/EdDSA 或 RSA）使用 zkSNARK 生成完全匿名的证明，对于浏览器和智能手机等客户端设备来说，计算量很大。我们的首要任务是支持各种设备，使尽可能多的选民可以访问该系统。将来，随着密码学技术的进步和客户端设备变得更加强大，我们预计能够有效地在客户端生成此类零知识证明。除了选票之外，这将使我们能够完全匿名化客户端的身份，从而在不影响可访问性或用户体验的情况下进一步增强用户隐私。

---

量子抗性

随着量子计算技术的进步，它对支持数字系统（包括像 DAVINCI 这样的投票平台）安全的经典密码学方案提出了重大挑战。确保系统在面对量子威胁时保持安全对于其寿命和可信度至关重要。

量子计算机有可能比经典计算机更快地解决某些数学问题。值得注意的是，Shor 算法 允许量子计算机有效地分解大整数并计算离散对数，从而破坏了广泛使用的密码学方案（如 RSA、DSA、ECDSA 和 ElGamal 密码系统）的安全性。

但是，DAVINCI 的设计包含即使在面对未来的量子攻击时也能保留选民匿名性的机制：

• 身份和加密选票的分离： 选民的身份及其加密的选票通过无效器中的秘密分离。无效器计算如下： N=Hash(Commitment∥s)

  其中 s 是只有选民知道的秘密。这意味着，即使对手使用量子计算机解密加密的选票，他们也无法在不知道密钥 s 的情况下将解密的投票链接回人口普查中的选民身份。

• 量子抗性哈希函数： Nullifier 和 Commitment 是使用密码学哈希函数计算的，这些函数被认为是能够抵抗量子攻击的（例如，SHA-3）。虽然 Grover 算法可以在搜索原像时提供二次加速，但使用足够长的哈希输出（例如，256 位）可以缓解此风险。

为了进一步防范量子威胁，将来可以实施以下措施：

1. 采用后量子签名方案。用基于硬格问题的量子抗性算法（如 CRYSTALS-Dilithium、Falcon 或 Rainbow）代替 ECDSA/EdDSA。

2. 探索基于格的同态加密方案。用量子抗性替代方案（如 Brakerski-Gentry-Vaikuntanathan (BGV) 方案或 Brakerski/Fan-Vercauteren (BFV)）代替 ElGamal 密码系统。

3. 采用量子抗性零知识证明系统，例如基于后量子假设或 zkSTARK 的 zkSNARK 构造。

---

Vocdoni 代币 (VOC)

我们引入 Vocdoni 代币 (VOC) 作为其去中心化投票生态系统的关键要素，在协议的可持续性中发挥着至关重要的作用。

该代币具有多种实用功能，可协调所有参与者（投票组织者、排序器和选民）的激励机制，从而确保投票系统的完整性、效率和安全性。

VOC 代币的角色

1. 排序器的抵押品： 排序器需要质押 VOC 代币作为参与协议的抵押品。这是一种安全措施，可确保负责任的参与。如果排序器的行为不当（无论是出于恶意还是无意的错误），它可能会面临惩罚，包括损失部分抵押代币。
2. 激励机制： 排序器根据其对处理有效投票和维护网络的贡献而获得 VOC 代币奖励。奖励与成功添加到共享状态的有效投票数量成正比。
3. 投票流程的付款： 投票流程组织者使用 VOC 代币来支付创建和管理投票流程的成本。成本取决于投票登记规模、投票期持续时间以及所需的安全级别（基于参与排序器的数量）等因素。
4. 治理： VOC 代币通过赋予代币持有者参与项目治理的权利来促进去中心化治理。代币持有者可以影响重要事项，例如协议升级、生态系统开发以及旨在增强 DAVINCI 各个方面的其他举措。这确保了项目以透明的、社区驱动的方式发展。

组织者的经济学

投票流程组织者支付 VOC 代币费用来创建和管理其投票活动。这些费用涵盖运营成本并激励排序器。

投票流程的成本因以下因素而异：

• 最大投票数： 较大的选民登记需要更多的处理资源。
• 投票持续时间： 较长的投票期需要排序器的延长资源承诺。
• 安全级别： 组织者可以调整参与排序器的数量，以在成本和安全需求之间取得平衡。

费用必须预先支付，但可以部分报销。计算报销额的公式为：

Reimbursement=TotalCost−TotalReward−BaseCost

鉴于每个投票流程都有一个符合条件的选民名单，组织者应预留等于最大选民数的空间，预计所有符合条件的选民都可能参与。但是，由于这种情况不太可能发生，因此可以报销一部分奖励池。

此公式的组成部分在以下各节中定义。

投票流程成本模型

流程成本模型定义了如何计算给定流程的成本。

考虑到排序器特定的容量、流程持续时间、选民人数和安全成本，我们定义以下组成部分公式：

totalCost=baseCost+capacityCost+durationCost+securityCost

组成部分定义

• baseCost： 基本成本是排序器收取的固定费用，用于根据固定值加上 maxVotes 的数量和固定因子来设置投票流程。它与流程持续时间或安全级别无关。这部分费用无法报销，因此是 totalCost 的一部分，将始终奖励给排序器。

baseCost=fixedCost+maxVotes⋅p

其中：

• fixedCost 是协议中定义的固定基本费用。
• maxVotes 是给定投票流程的最大投票数。
• p 是协议中定义的小的线性因子。
  • capacityCost： 它定义了给定排序器网络当前占用率的成本。此组件模拟为投票流程预留空间的成本，相对于可用排序器的数量、正在运行的投票流程的数量和最大选民数量。成本随着可用排序器数量接近排序器总数以及正在运行的投票流程数量的增加而非线性地增加，因此当可用的排序器较少且正在运行的投票流程数量较多时，容量变得更有价值。

k1⋅(totalVotingProcessestotalSequencers−usedSequencers+ϵ⋅maxVotes)a

• k1： 控制排序器利用率影响的缩放因子。
• totalVotingProcesses： 正在运行的投票流程总数。
• totalSequencers： 注册的排序器总数。
• usedSequencers： 已经处理其他投票流程的排序器数量。
• a： 一个指数，控制当已用容量接近总可用容量时，成本增加的剧烈程度。换句话说，它控制成本增加的非线性。
• ϵ： 是一个非常小的数字，可避免零除。
  • durationCost： 此组件模拟运行特定持续时间的流程的成本，其中较长的流程会产生更多成本。缩放是非线性的，这意味着较短的流程更具成本效益，而较长的流程则越来越昂贵。

预计会有最小和最大持续时间阈值（例如，1 小时到 1 年）。

k2⋅processDurationb

• k2： 流程持续时间的缩放因子。
• processDuration： 流程的持续时间（以小时为单位）。
• b： 一个指数，控制流程持续时间的非线性缩放。
  • securityCost： 安全成本模拟使用多个排序器来确保流程的安全。成本根据所使用的排序器数量呈指数级缩放，但随着排序器的数量接近可用排序器总数，收益会递减：

k3⋅ec⋅(numSequencerstotalSequencers)d

• k3： 控制安全成本总体权重的缩放因子。
• c： 控制安全成本指数缩放的陡峭程度。
• numSequencers： 此流程中使用的排序器数量。
• totalSequencers： 网络中可用的排序器总数。
• d： 一个指数，控制随着排序器的数量接近可用排序器总数，安全成本增加的速度。

约束

需要在公式中强制执行一些约束，以避免不可行的方案。

• 如果 processDuration>maxDuration 则： totalCost=∞
• 如果 numSequencers>totalSequencers 则： totalCost=∞

排序器的经济学

要成为排序器并获得奖励，参与者必须质押 VOC 代币作为抵押品。此抵押品在 Sequencer Registry 智能合约中的排序器注册期间被锁定，并且可以在履行排序器承诺后提取。

排序器根据以下内容获得奖励：

• 他们包含在共享状态中的投票数量。
• 他们包含在共享状态中的投票重写数量。
  • 投票重写可以是投票覆盖（选民投了覆盖上一次投票的另一张选票）或投票重新加密（由排序器执行）。重新写入投票为选民提供了更大的灵活性，并且是 无收据性 的关键机制。
  • 预计排序器会最大限度地增加投票重写的次数，因为无法区分投票覆盖和投票重新加密。这被认为是积极的行为，因为它有助于协议的无收据性机制。
  • 投票和投票重写是可以区分的，因为前者包括一个从未包含在特定流程中的无效器。
  • 鉴于每个排序器都将提交一个 ZK 证明，以验证状态转换到结算层智能合约中，因此可以直接计算每个排序器处理的投票数量和投票重写数量。
  • 排序器可以允许投票重写高达 T 次的任何状态转换的新投票数量。 T 将被定义为协议中的常量。
• 与最大选民数量相关的未处理投票数量。

获得的奖励总额可以表示为：

sequencerRewardi=R⋅(votesimaxVotes)+W⋅(voteRewritesitotalRewrites)

并受以下约束：

voteRewritesivotesi≤T

totalReward=R+W

R>W

• R>W，因为排序器必须优先处理投票，而不是激励仅重写现有投票。

其中：

• R： 分配给特定投票流程的奖励池的一部分。
• votesi： 排序器 i 为特定投票流程处理的投票数。
• maxVotes： 参与投票流程的最大选民数量。
• W： 分配给特定投票流程的奖励池的一部分。
• voteRewritesi： 排序器 i 为特定投票流程处理的投票重写数。
• totalRewrites： 特定流程的投票重写总数。

处罚：

• 未参与： 未能履行其义务的排序器，在统计阶段未提供密钥共享，可能会被削减其抵押品。

排序器的惩罚可以表示为：

SlashedAmouti=s⋅StakedCollaterali

其中：

• SlashedAmounti： 给定排序器的总削减金额。
• s： 削减系数 0≤s≤1。
• StakedCollaterali： 给定排序器质押的 VOC 代币金额。

总结

总成本公式结合了四个主要组成部分：

1. 用于设置流程的基本成本。
2. 基于选民人数、正在运行的流程总数和可用排序器容量的容量成本。
3. 基于流程持续时间的持续时间成本。
4. 基于所使用的排序器数量的安全成本，对于使用超过一定数量的排序器，收益会递减。

所提出的公式确保：

• 小型流程具有成本效益。
• 较大的流程或使用高比例可用排序器容量的流程会产生更高的成本。
• 如果使用更多的排序器，安全成本会迅速增加，但超过一定数量添加排序器会导致收益递减。
• 无法达到不可行的方案。

优化说明

在提出的模型中，我们可以清楚地看到两个主要参与者的目标存在冲突：

• 组织者（服务的“买方”）希望最大限度地降低运行流程的成本。
• 排序器（容量的“卖方”）希望最大限度地提高其奖励。排序器可以根据预期利润决定是否参与。

这些是自然冲突的目标，可以建模为战略游戏。但是，对协议的这种均衡进行建模不在此文档的范围内，将在单独的文章中介绍。

---

zkSNARK 电路

DAVINCI 投票流程使用四个密码电路链：一个由用户生成，三个由排序器生成。每个电路都以先前的证明为基础进行递归。通过将排序器的工作分为三个电路，我们可以实现并行处理，从而提高可扩展性，并最大限度地减少多个排序器同时生成状态转换时发生冲突的风险。此外，我们确保可以在任何设备（包括智能手机和网络浏览器）上进行投票，同时将排序器的计算要求保持在具有 64 GiB 内存的可访问的、基于 CPU 的计算机的能力范围内。

1. 投票电路

由用户在投票时生成，此电路证明加密的选票有效，并且无效器和承诺已正确生成。

• 约束： 约 53,000
• 曲线： BN254
• 框架： Circom/SnarkJS
• 角色： 用户

断言：

• 选票符合协议规则提供的选票模式。
• 选票加密正确。
• 无效器和承诺已正确计算。

2. 身份验证电路

由排序器生成，此电路将投票证明转换为 BLS12-377 曲线以进行本机递归，并在人口普查中验证用户的资格及其签名。

• 约束： 约 310 万
• 曲线： BLS12-377
• 框架： Gnark
• 角色： 排序器

断言：

• 投票 zkProof 对于提供的输入有效。
• 提供的输入的签名对于选民的公钥有效。
• 从用户公钥派生的地址是人口普查的一部分，并使用提供的用户权重验证人口普查证明。

3. 聚合电路

此电路将多个经过身份验证的投票累积到单个证明中。它还会验证所有累积的投票是否属于同一投票流程。

• 约束： 40,000 ×（投票数）
• 曲线： BW6-761
• 框架： Gnark
• 角色： 排序器

断言：

• 累积的 zkProof 有效。
• 所有这些证明的 ProcessId、CensusRoot、BallotMode 和 EncryptionPubKey 均相同。

4. 状态转换电路

给定聚合的投票证明，此电路验证所有新投票是否正确包含到流程的状态 Merkle 树中。它生成最终状态转换证明，该证明将由以太坊智能合约验证。

• 约束： 约 400 万
• 曲线： BN254
• 框架： Gnark
• 角色： 排序器

断言：

• 集成的 zkProof 有效。
• MerkleTree 转换见证证明了 Root1 和 Root2 之间的每次更改。
• ProcessID、BallotMode、CensusRoot、EncryptionKey 保持不变。
• 选票被正确地计为新的或被覆盖的，并添加到结果累加器中。

---

致谢

作者要感谢以下审阅者和贡献者，感谢他们宝贵的反馈和支持：

• Vocdoni 团队
• Jordi Baylina（Iden3 和 Polygon）
• Adrià Maçanet（隐私扩展探索，以太坊基金会）
• Arnaucube (0xPARC)
• Alex Kampa (AZKR)
• Roger Baig（加泰罗尼亚理工大学）
• Javier Herranz（加泰罗尼亚理工大学）
• Jordi Puiggali（Secrets Vault）
• Marta Bellés（Dusk Network）

• 原文链接： hackmd.io/@vocdoni/BJY8E...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～