匿名MACI的zkStark实验

概述

zkStark-amaci 是匿名MACI协议（aMACI）在 Starknet 上的 ZKSnark 实现。它把 aMACI 的协议状态转换和密码学校验逻辑写成 Cairo 程序，通过 zkSTARK proof 证明这些程序的执行正确性，再由 Starknet 合约消费已验证的 fact 并推进 round 状态。

这篇文档分成两部分：

电路部分：说明 Cairo 程序分别证明什么、public output 如何绑定状态、链上为什么可以只消费 fact。
aMACI round 流程实现部分：说明一轮 aMACI 从 signup 到 tally 如何执行，voter、operator、合约分别做什么。

当前实现围绕 Starknet 原生执行环境设计：协议状态转换和密码学校验关系由 Cairo 程序表达，证明由 zkSNARK proving system 生成。在 Atlantic 路径下，Atlantic 负责生成并提交证明，Integrity verifier 负责链上验证，aMACI 合约消费已注册的 fact 并推进 round 状态。

模块	当前实现
曲线	Starknet STARK curve
签名	STARK ECDSA
密钥协商	使用 STARK curve scalar multiplication 派生 ECDH shared point
密文关系	STARK curve 上的 ElGamal-style 点关系
Hash / KDF	Starknet Poseidon，并做 domain separation
证明系统	zkSTARK proving system（Stone）

需要先明确隐私边界：aMACI 协议模型中，Operator 负责解密和处理消息，因此 Operator 可以看到投票明文。当前实现的隐私目标主要是防止链上和公众观察者获得投票明文，并通过 proof 约束被合约接受的状态转换必须按电路规则执行。使用 Atlantic 时，witness 会进入 Atlantic 执行环境；生产环境如果不能接受这一点，应切换到自托管 prover。

第一部分：Cairo 电路与证明系统

1. 电路在这里是什么意思

这里的“电路”是可被证明执行的 Cairo 程序。

每个 Cairo 程序接收 witness 和公开字段，重新计算密码学关系，最终输出 public output。proof 证明的是：

对给定 Cairo 程序和公开输出，存在一组 witness，使得该程序执行成功并产生这组 public output。

2. 固定参数

当前完整 E2E 使用 2-1-1-3 参数规模：

参数	值	含义
`stateTreeDepth`	2	5 叉 StateTree，最多 25 个 state leaf
`intStateTreeDepth`	1	每个 tally batch 处理 5 个 state leaf
`voteOptionTreeDepth`	1	每个用户有 5 个 vote option
`messageBatchSize`	3	每个 process batch 处理 3 条消息

3. 四组核心电路

当前 aMACI round 的可验证执行由四组 Cairo 电路支撑：

这四组电路分别证明 round 中不同阶段的状态转换，并共同维护三类链上 commitment：

deactivateCommitment
stateCommitment
tallyCommitment

链上合约不可见 witness，也不重新执行私有计算；它只消费已验证 fact，并检查 proof 的 public output 中的 commitment 是否和当前链上状态连续。

ProcessDeactivate 电路

processDeactivate 证明一批停用消息按照协议规则被正确处理。当前每批处理 3 条 deactivate message。

对每条消息，电路验证：

消息公钥和协调者私钥派生的 ECDH shared key 正确；
encrypted deactivate command 解密正确；
旧 StateLeaf.pubKey 对 command 的 STARK ECDSA 签名有效；
command 中的 pollId、stateIndex 合法；
旧 key 当前仍处于 active 状态；
ActiveStateTree 和 DeactivateTree 更新正确。

该电路的 public output 会绑定新的 deactivateCommitment，供合约推进停用阶段状态。

AddNewKey 电路

addNewKey 证明用户可以用一个已停用旧 key 注册新 key。

它证明的不是“链上新增一个普通用户”，而是以下关系同时成立：

证明者知道某个已停用旧 key 的私钥；
该旧 key 在当前 poll 中尚未重复换 key；
新公钥与旧 key 的停用凭证正确绑定，但公开数据不能直接链接新旧 key。

电路主要检查：

nullifier = H(oldPrivKey, pollId, domain)，防止同一个旧 key 重复换 key；
旧私钥和协调者公钥派生出的 shared key，对应 DeactivateTree 中的 deactivateSharedKeyHash；
d1/d2 是 c1/c2 的合法重随机化结果；
DeactivateTree 的 Merkle inclusion path 正确；
新公钥被绑定到 public output。

该电路的 public output 会绑定 nullifier、新公钥和新的 stateCommitment，供合约完成新 key 注册。

ProcessMessages 电路

processMessages 证明一批投票消息按照协议规则被正确处理。当前每批处理 3 条 vote message，并按消息队列的反向顺序处理。

对每条消息，电路验证：

消息公钥和协调者私钥派生的 ECDH shared key 正确；
encrypted vote command 解密正确；
当前 StateLeaf.pubKey 对 command 的 STARK ECDSA 签名有效；
stateIndex 对应的 StateLeaf 存在；
当前 key 没有被 deactivate；
pollId、nonce、voteOptionIndex 合法；
VoteOptionTree 和 StateTree 更新正确。

每条 vote command 只更新一个 voteOptionIndex。如果消息来自已停用旧 key，则这条消息会按无效消息处理，不会改变最终投票状态。

该电路的 public output 会绑定新的 stateCommitment 和消息哈希链边界，供合约推进投票消息处理进度。

Tally 电路

tally 证明最终计票结果是从 processMessages 之后的 StateTree 正确累计得到的。

Tally 电路验证：

stateCommitment 等于最终 processMessages.newStateCommitment；
每个 StateLeaf.voteOptionRoot 和输入的 vote option 数组匹配；
当前 batch 的结果正确累加到 currentResults；
newTallyCommitment = H(H(newResults), salt) 正确。

该电路的 public output 会绑定新的 tallyCommitment。链上不保存明文 results，只保存 tallyCommitment。Operator 可以公布 raw results 和 salt，任何人都可以验证它们是否匹配链上的 commitment。

第二部分：aMACI Round 流程实现

1. 核心状态对象

对象	含义
`StateTree`	存储用户状态叶子。每个 `StateLeaf` 绑定用户公钥、投票状态、nonce、余额和停用标记密文。
`ActiveStateTree`	标记某个 stateIndex 是否仍可用。deactivate 后旧 key 对应位置会被更新。
`DeactivateTree`	存储停用凭证。`addNewKey` 通过它证明旧 key 已被停用，并通过重随机化避免从公开数据直接链接新旧 key。
`VoteOptionTree`	每个用户自己的投票选项树，记录该用户对各选项的投票权重。
`Message hash chain`	链上消息队列的哈希链，保证 Operator 不能跳过、替换或重排待处理消息。
`Commitment`	链上保存的状态承诺，例如 `stateCommitment` 、 `deactivateCommitment` 、 `tallyCommitment` 。

2. E2E Round 生命周期

用户注册初始公钥，合约把对应 StateLeaf 加入 StateTree。

Signup 只建立初始身份。此时用户还没有通过 deactivate / addNewKey 获得新的不可链接 key。

2. Deactivate

旧 key 发送一条加密停用消息。消息中包含 deactivate command，并由旧 key 签名。

这个阶段是用户侧动作：

Voter:
  生成 deactivate command
  使用一次性消息密钥加密 command
  使用 old key 签名 command
  发布 deactivate message

3. ProcessDeactivate

Operator 收集 deactivate messages，构造 witness，并提交 processDeactivate 证明任务。

这个阶段是 Operator 侧动作：

Operator:
  解密 deactivate message
  检查签名和状态
  更新 ActiveStateTree
  写入 DeactivateTree
  生成证明输入
  提交给 Atlantic

Integrity 验证通过并注册 fact 后，aMACI 合约消费该 fact，推进 deactivateCommitment。

4. AddNewKey

用户用旧 key 的停用凭证注册新 key。

这个阶段是用户侧动作：

Voter:
  使用 oldPrivKey 证明自己对应某个 deactivate leaf
  生成 nullifier 防止重复换 key
  对 c1/c2 做 rerandomization 得到 d1/d2
  绑定 newPubKey
  生成 addNewKey 证明输入

Integrity 验证通过并注册 fact 后，aMACI 合约消费该 fact：

consume nullifier register newPubKey keys_added += 1

5. Vote

当前有效 key 发送加密投票 command。

投票 command 的关键字段：

字段	含义
`stateIndex`	要操作哪个 `StateLeaf`
`voteOptionIndex`	要更新哪个投票选项
`newVoteWeight`	该选项的新权重
`nonce`	防止同一 key 重放旧 command
`pollId`	防止跨 round 复用
signature	当前 `StateLeaf.pubKey` 对 command 的签名

消息加密使用一次性消息公钥。Operator 用协调者私钥和消息公钥计算 ECDH shared key，再解密 command。

6. ProcessMessages

Operator 收集 vote messages，构造 witness，并提交 processMessages 证明任务。

这个阶段更新 StateTree：

读取 StateLeaf[stateIndex]
检查 active/deactivate 状态
检查 command 签名、pollId、nonce
更新该用户的 VoteOptionTree
得到新的 voteOptionRoot
写回 StateLeaf
更新 StateTree root

Integrity 验证通过并注册 fact 后，aMACI 合约消费该 fact，推进 stateCommitment 和 message batch counter。

7. Tally

Operator 从最终 StateTree 中读取每个用户的 voteOptionRoot，按 batch 累计结果，并提交 tally 证明任务。

Integrity 验证通过并注册 fact 后，aMACI 合约消费该 fact，推进 tallyCommitment。最终 raw results 不直接存链上；Operator 可以公布 raw results 和 salt，任何人通过：

H(H(results), salt) == tallyCommitment

验证公布结果是否对应链上 commitment。

3. aMACI round 证明链路与链上消费

四类电路（ProcessDeactivate、AddNewKey、ProcessMessages、Tally）以及各自的 witness 与 public input 会按 round 阶段提交给 Atlantic。Atlantic 在这里负责证明生成与提交：运行对应 Cairo 程序，生成该阶段的 STARK proof，并把 proof 提交到 Integrity verifier 合约。

Integrity verifier 合约负责链上验证 proof。验证通过后，对应 fact 会被注册到 FactRegistry。在当前 Atlantic 路径下，fact 绑定到 metadata wrapper output；aMACI 合约再从 metadata output 中校验业务 Cairo program hash 和业务 public output。

aMACI 合约处理链上提交时不重新执行电路，也不读取 witness。它只消费 FactRegistry 中已经注册且 security bits 满足要求的 fact，并结合 public output 检查当前 commitment 是否连续、下一步 commitment 是否可以写回，从而推进 deactivate、state 或 tally 状态。

总结

当前实现使用 Starknet 原生密码学原语，把 aMACI 的协议状态转换和密码学校验关系约束进 Cairo 程序：

STARK ECDSA 签名；
ECDH shared key；
ElGamal-style decrypt / rerandomize；
Poseidon stream 解密；
nullifier；
Merkle path；
message hash chain；
state / deactivate / tally commitment chain。

当前系统需要区分两层安全：

证明系统层：zkSTARK proving system
协议密码学层：STARK curve ECDSA / ECDH / ElGamal-style encryption

zkSTARK 证明系统不依赖椭圆曲线配对，也不需要 trusted setup；其安全性主要依赖哈希函数和代数一致性检查，因此证明系统层通常被认为具备后量子友好的安全基础。

但 aMACI 协议内部仍然使用 Starknet STARK curve 上的签名、ECDH 和 ElGamal-style 加密。这些属于椭圆曲线离散对数假设，不能抵抗足够强的量子计算攻击。

因此，当前实现中使用 zkSTARK 证明系统验证 aMACI 的协议状态转换和密码学校验关系：

证明系统层具备后量子友好的安全基础；
协议内部的身份、签名、加密和密钥协商仍然基于非抗量子的椭圆曲线密码学，不具备抗量子特性。