ZK Secret Santa 协议 - 隐私

嘿 ethresearchers！随着冬天的到来，我决定也在论坛上分享这个有趣的协议。今年早些时候，我们写了一篇关于如何在以太坊上实现（真正的）秘密圣诞老人的研究论文，同时保护玩家的隐私和游戏的正确性。想知道你们对 ZKSS 协议的看法！

这是 arXiv 上论文的链接。

摘要

本文提出了一种三步秘密圣诞老人算法，该算法利用零知识证明 (ZKP) 建立礼物发送者/接收者关系，同时保持发送者的机密性。该算法维护一个排列错位，并且不需要中央机构即可成功执行。所描述的方法可以在 Solidity 中实现，前提是与交易中继器集成。

1. 简介

圣诞节来临时，每个人都喜欢玩秘密圣诞老人。但是在链上玩这个游戏有一些挑战需要克服。

首先，以太坊区块链的开放性不允许我们私下执行计算。为了隐藏秘密圣诞老人参与者的身份（地址），使用了事务中继器和 ZKP。

其次，由于链上没有（真正的）随机性来源，礼物发送者/接收者对的选择外包给秘密圣诞老人参与者，并通过 ZKP 进行验证，确保没有人选择自己。

第三，“重复投票”的问题通过 nullifier（掩码）的概念来解决。在不丢失玩家机密性的前提下，该协议可以验证他们的参与。

2. 协议描述

ZK 秘密圣诞老人 (ZKSS) 协议是一个三步非点对点交互过程，需要所有游戏参与者的参与。

该算法的核心依赖于几种密码学原语，以确保执行正确性并维护用户机密性。设 $\mathbb{F}_p$ 是素数 $p$ 上的有限域，并设

$\mathsf{hash}(m) \;\rightarrow\; h \;\in\; \mathbb{F}_p$

表示一个密码哈希函数，它接受任意消息 $m$ 作为输入，并返回一个域元素 $h$。

证明关系定义为

$\mathcal{R} = {(w, x) \in \mathcal{W} \times \mathcal{X} \;:\; \phi_1(w,x), \phi_2(w,x), \dots, \phi_m(w,x)},$

其中 $w$ 是 witness 数据，$x$ 是公共数据，${\phi_1(w,x), \phi_2(w,x), \dots, \phi_m(w,x)}$ 是必须同时证明的关系集合。

函数 $\mathsf{ecrecover}$ [1] 用于根据 ECDSA 签名 $\mathsf{sig}$ 和已签名的哈希 $h$ 恢复用户的 $\mathsf{address}$。

最后，考虑 Merkle 证明 $p_i \in \mathbb{F}_p^{(n)}$，它是指向根值的节点值列表。元素 $x$ 的 Merkle 证明可以通过以下方式验证

$\mathsf{merkleVerify}(x, p_i, root) \;\rightarrow\; \mathsf{bool}$.

2.1. 设置

初步的 setup 需要所有 ZKSS 参与者在智能合约中公开注册他们的地址。设置只需完成一次，允许参与者集合在多个游戏中重复使用。

由于设置是一个开放的过程，因此可以选择一个 lead participant 代表他们安全地在单个事务中注册所有玩家。

算法 1：设置

输入：

• 公共：
  • addresses - ZKSS 参与者的以太坊地址

设置过程：

1. lead participant 在智能合约上调用 register 函数，提供所有参与者的地址。
2. 合约在对应的 $\mathsf{index} = \mathsf{hash}(\mathsf{address})$ 下，将地址存储在参与者稀疏 Merkle 树 (SMT) 中。

参与者 SMT [2] 在整个 ZKSS 中用于验证参与者是否属于初始的参与者集合。

2.2. 签名承诺

第一步，称为 signature commitment，要求 ZKSS 参与者使用确定性派生的 ECDSA 签名。有关此步骤背后的基本原理，请参见 ecdsa-non-determinism 安全部分。

算法 2：签名承诺

输入：

• 公共：
  • H - 用户 ECDSA 签名 ($\mathsf{address} || \mathsf{eventId}$) 的哈希值，其中 $\mathsf{address}$ 是用户的以太坊地址，$\mathsf{eventId}$ 是 ($\mathsf{contract\ address} || \mathsf{nonce}$)，而 $||$ 是串联操作

承诺过程：

1. 参与者签署消息 M = ($\mathsf{address} || \mathsf{eventId}$)，并计算签名哈希值。
2. 参与者在智能合约上调用 commit 函数，并将哈希值作为参数。
3. 合约在对应的 $\mathsf{index} = H$ 下，将提供的哈希值存储在签名承诺 SMT 中。

此外，在签名承诺步骤中，智能合约必须验证 $\mathsf{msg.sender}$ 是否属于 ZKSS 参与者的初始集合。

2.3. 礼物发送者确定

第二步，称为 sender determination，要求每个 ZKSS 参与者匿名地将其随机数 $r$ 添加到礼物发送者数组中。

算法 3：礼物发送者确定

输入：

• 私有：
  • $\mathsf{sig}$ - 用户 ECDSA 签名 ($\mathsf{address} || \mathsf{eventId}$)
  • $\mathsf{address}$ - 用户的地址
  • $p_p$ - 用户地址包含的 Merkle 证明
  • $p_c$ - 用户签名承诺包含的 Merkle 证明
• 公共：
  • $r$ - 用户唯一的随机数
  • $\mathsf{eventId}$ - ZKSS 游戏的唯一 ID
  • $\mathsf{root_p}$ - 参与者 SMT 根
  • $\mathsf{root_c}$ - 签名承诺 SMT 根
  • $\mathsf{null_s}$ - 用户的 nullifier，以防止重复注册随机数

证明：

为关系生成证明 $\pi_e$：

$\mathcal{R}_{e} = { \mathsf{sig}, \mathsf{address}, p_p, p_c, r, \mathsf{eventId}, \mathsf{root_p}, \mathsf{root_c}, \mathsf{null_s}: \ \mathsf{null_s} \leftarrow \mathsf{hash}(\mathsf{sig.s}), \ \mathsf{address} \leftarrow \mathsf{ecrecover}(\mathsf{sig}, (\mathsf{address} || \mathsf{eventId})), \ \mathsf{merkleVerify}(\mathsf{address}, p_p, \mathsf{root_p}) \rightarrow \mathsf{true}, \ \mathsf{merkleVerify}(\mathsf{hash}(\mathsf{sig}), p_c, \mathsf{root_c}) \rightarrow \mathsf{true}, \ r = r * r }$

证明 $\pi_e$ 由合约验证。如果证明正确，并且 $\mathsf{null_s}$ 未包含在已用 nullifier 列表中，则用户通过中继器将其随机数包含到数组中。随机数和 nullifier 必须是成对可访问的。

关系 $\mathcal{R}_{e}$ 中的最后一个操作 $r = r * r$ 生成额外的约束来“锚定”$r$ 值，以确保协议的可靠性。

$r$ 必须由每个参与者唯一生成并公开披露。但是，$r$ 与 $\mathsf{participant}$ 之间的关系隐藏在带有中继器的 ZKP 中，该中继器发送事务。

建议玩家对随机数 $r$ 使用 2048 位 RSA 公钥。也就是说，ZKSS 参与者唯一地生成 RSA 私钥（他们必须记住），并给出 $\mathsf{exp} = 65537$，发布相应的公钥。

发布的 RSA 公钥随后用于算法的第三步，对礼物接收者的收货地址进行加密，以便只有各自的礼物发送者才能读取它们。

2.4. 礼物接收者披露

第三步，称为 receiver disclosure，是 ZKSS 算法的最后一步。之后，秘密圣诞老人的分配将完成，礼物发送者可以开始向接收者发送礼物。

接收者披露步骤可以在没有中继器的情况下执行，因为接收者身份 ($\mathsf{msg.sender}$) 无论如何都会被揭示。

算法 4：披露礼物接收者

输入：

• 私有：
  • $\mathsf{sig}$ - 用户 ECDSA 签名 ($\mathsf{address} || \mathsf{eventId}$)
• 公共：
  • $\mathsf{address}$ - 用户的地址
  • $\mathsf{eventId}$ - ZKSS 游戏的唯一 ID（合约地址 $||$ nonce）
  • $\mathsf{null_s}$ - 发送者的 nullifier

证明：

为关系生成证明 $\pi_c$：

$\mathcal{R}_{c} = { \mathsf{sig}, \mathsf{address}, \mathsf{eventId}, \mathsf{null_s}: \ \mathsf{null_r} \leftarrow \mathsf{hash}(\mathsf{sig.s}), \ \mathsf{address} \leftarrow \mathsf{ecrecover}(\mathsf{sig}, (\mathsf{address} || \mathsf{eventId})), \ \mathsf{null_r} \neq \mathsf{null_s} }$

证明 $\pi_c$ 由合约验证。如果验证成功，并且 $\mathsf{null_r}$ 不等于选择的 $\mathsf{null_s}$，则接收者的 $\mathsf{address}$ 将分配给相应的发送者随机数（RSA 公钥）。

必须私下验证 nullifier 的不等式，以不披露上一步中接收者的位置。

为了强制执行接收者披露的唯一性，智能合约（公开）必须维护唯一 $\mathsf{msg.senders}$ 的列表，并验证它们是否属于 ZKSS 参与者的初始集合。

如果多个接收者同时选择同一发送者时发生冲突，则其中一个事务必须还原，并且丢弃的接收者必须尝试再次披露自己。

除了 ZKP，礼物接收者还可以提供他们的加密（真实世界）地址，他们希望将礼物运送到该地址。加密是使用先前提供的发送者的 RSA 公钥执行的。

ZKSS 协议的实现可以向 ZKP 验证方案添加 RSA 加密正确性检查。

3. 安全性

3.1. ECDSA 非确定性

如果没有签名承诺步骤，则可能会攻击 ZKSS 协议并 DoS 游戏。不诚实的参与者可能会生成非确定性 ECDSA 签名并绕过 nullifier 保护，从而占用所有发送者的插槽。

话虽如此，可以使用 EdDSA 签名提出 ZKSS 协议的替代版本。它们的确定性允许跳过签名承诺步骤，删除签名承诺 SMT，并将 nullifier 直接构造为 $\mathsf{hash}(\mathsf{sig})$，而不是 $\mathsf{hash}(\mathsf{sig.s})$。

3.2. 接收者抢跑

在协议的接收者披露步骤中，可能会发生轻微的抢跑攻击。

不诚实的礼物发送者可能会监视事务 mempool 以抢跑接收者（通过选择同一发送者），以增加该接收者在其下一次披露尝试期间选择不诚实发送者的机会。

但是，此攻击仅有效一次（接收者只能选择一次发送者），并且当已经选择了不诚实的发送者时，此攻击是不可能的。

4. 正确性

ZKSS 的基本要素是分离其第二步和第三步。由于在第二步中使用了事务中继器，因此第三步中的参与者无法确定哪个随机数属于哪个参与者。此外，参与者只能投递一次随机数，这是由 nullifier 逻辑强制执行的。此外，通过采用 ZKP，我们确保没有参与者可以操纵协议将礼物发送给自己或选择特定的发送者。

为了说明这些概念，请考虑以下秘密圣诞老人的类比。想象一下 $n$ 个聚集在一起的参与者（参见算法 1）。

每个参与者安全地将一张包含其随机数的纸条放入帽子中。每个人都会秘密地添加各自的音符，除了“传输”机制（对应于我们协议中的中继器）之外，没有人可以观察到哪个音符属于谁（参见算法 3）。各种技术，VPN 等，可用于确保有关中继器的匿名性，但它们超出了本文的范围。

最后，每个参与者从帽子中抽取一张便条，并且 - 通过“魔术”（由 ZKP 保证） - 他们无法取回自己的便条（参见算法 4）。在显示带有随机数的便条后，与某个数字相关的相应参与者会将礼物发送给抽出便条的人。

此外，如果选择的随机数是 RSA 公钥，则接收者可以通过 RSA 加密安全地将送货地址传输给他们的圣诞老人。

总而言之，关于协议正确性的关键假设如下：

• 每个礼物发送者都不会透露自己和协议第二步中使用的随机数。
• ECDSA 签名必须按照 RFC 6979 [3] 构建。必须仅接受来自曲线下部的签名。
• $\mathsf{eventId}$ 对于每个 ZKSS 游戏都是唯一的。
• 协议的可靠性源于底层 ZK 证明系统的可靠性。
• 如果参与者提供加密的有效负载，他们有责任确保加密数据的正确性。

参考文献

1. [Woo24] Gavin Wood. Ethereum: A Secure Decentralised Generalised Transaction Ledger. https://
2. ethereum.github.io/yellowpaper/paper.pdf. Version f3553dd. Accessed: 2025-01-08. 2024.

[ide24] iden3. Sparse Merkle Tree. https://docs.iden3.io/publications/pdfs/Merkle-Tree.pdf.

Accessed: 2025-01-08. 2024.

3. [Por13] Thomas Pornin. Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic

Curve Digital Signature Algorithm (ECDSA). RFC 6979. Aug. 2013. doi: 10.17487/RFC6979.

url: Information on RFC 6979 » RFC Editor.

• 原文链接： ethresear.ch/t/zk-secret...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～