探索：利用ZKP实现“圣诞老人送礼物”（Secret Santa）的游戏

Joe 发表于阅读:46 回复:0

今年早些时候，我们撰写了一篇研究论文，探讨如何在以太坊上实现（真正的）“秘密圣诞老人”（Secret Santa）游戏，同时保护参与者的隐私并确保游戏规则的正确性。

这里是论文在 arXiv 上的链接：https://arxiv.org/pdf/2501.06515

摘要
本文提出了一种三步式的“秘密圣诞老人”算法（含初始设置阶段），该算法利用零知识证明（ZKP）来建立礼物发送者与接收者之间的配对关系，同时保障发送者的身份保密性。该算法维持一个无不动点的排列（即错位排列，derangement），且无需依赖任何中心化权威即可成功运行。只要集成交易中继器（transaction relayer），该方案即可用 Solidity 实现。

1. 引言
圣诞节来临之际，人人都喜欢玩“秘密圣诞老人”游戏。然而，在链上实现这一游戏却面临若干挑战：

首先，以太坊区块链的公开透明特性使得私密计算难以直接进行。为隐藏“秘密圣诞老人”参与者的真实身份（地址），我们结合使用了交易中继器和零知识证明（ZKP）。

其次，由于链上缺乏（真正意义上的）随机性来源，礼物发送者与接收者的配对由参与者自己在线下完成，并通过零知识证明加以验证，从而确保没有人被分配给自己。

第三，协议通过引入“空值化器”（nullifiers，也称盲化器/blinders）的概念解决了“重复参与”（double voting）的问题。在不泄露参与者身份的前提下，系统能够有效验证每位用户仅参与一次。

2.协议描述

零知识秘密圣诞老人（ZKSS）协议是一个包含三个步骤的非交互式过程，需要所有游戏参与者共同参与。

该算法的核心依赖于若干密码学原语，以确保执行的正确性并保护用户隐私。设 Fp为一个以素数 $p$ 为模的有限域，记 image.svg?hash(m)%5Cto%20h%5Cin%20%7BF%7D_%7Bp%7D 为一个密码学哈希函数，它接受任意消息 $m$ 作为输入，并输出一个域元素 $h$ 。

证明关系定义为：

R={(w,x)∈W×X:ϕ 1(w,x),ϕ 2 (w,x),…,ϕ m (w,x)},

其中 ( w ) 为见证数据（witness），( x ) 为公开数据（public input），而 {ϕ1(w,x),ϕ2(w,x),…,ϕm(w,x)}是一组需同时被证明成立的约束关系。

协议使用 ecrecover 函数 [1]，根据 ECDSA 签名 ( \text{sig} ) 和所签名的哈希值 ( h ) 恢复出用户的以太坊地址。

最后，考虑 Merkle 证明 image.svg?%5Cpi%20%5Cin%20%7BF%7D%5E%7B(n)%7D_%7Bp%7D ，它是一组从叶节点到根节点路径上的中间节点值。对于某个元素 ( x )，其对应的 Merkle 证明可通过以下函数验证：
merkleVerify(x,π,root)→bool.

算法 1：初始化（Setup）
输入：

Inputs:

Public:
- addresses - ZKSS participants Ethereum addresses

Setup process:

The lead participant calls the register function on the smart contract providing addresses of all the participants.
The contract stores the addresses in a participants Sparse Merkle Tree (SMT) under a corresponding $i n d e x = h a s h (a d d r e s s)$ .

初始化流程：

主导参与者（lead participant）调用智能合约中的 register 函数，提交所有参与者的地址。
合约将这些地址存储在一个参与者稀疏默克尔树（Sparse Merkle Tree, SMT）中，并为每个地址分配对应的叶子节点。
该参与者 SMT [2] 在整个 ZKSS 协议过程中用于验证某参与者是否属于初始注册的参与者集合。

2.2 签名承诺（Signature Commitment）

第一步称为“签名承诺”，其目的是约束 ZKSS 参与者使用确定性生成的 ECDSA 签名。关于此步骤的必要性，请参见“ecdsa-non-determinism 安全性”一节。

算法 2: Signature commitment

Inputs:

Public:
- $H$ – a hash of user’s ECDSA signature of ( $a d d r e s s | | e v e n t I d$ ), where $a d d r e s s$ is the user’s Ethereum address, $e v e n t I d$ is ( $c o n t r a c t a d d r e s s | | n o n c e$ ), and $| |$ is a concatenation operation

Commitment process:

The participant signs the message $M$ = ( $a d d r e s s | | e v e n t I d$ ) and calculates the signature hash.
The participant calls the commit function on the smart contract with a hash as a parameter.
The contract stores the provided hash in a signature commitments SMT under a corresponding $i n d e x$ = $H$ .

2.3 礼物发送者确定（Gift Sender Determination）

Inputs:

Private:
- $s i g$ – user’s ECDSA signature of ( $a d d r e s s | | e v e n t I d$ )
- $a d d r e s s$ – user’s address
- $p_{p}$ – the Merkle proof for the user’s address inclusion
- $p_{c}$ – the Merkle proof for the user’s signature commitment inclusion
Public:
- $r$ – user’s unique randomness
- $e v e n t I d$ – a unique id of a ZKSS game
- $r o o t_{p}$ – participants SMT root
- $r o o t_{c}$ – signature commitments SMT root
- $n u l l_{s}$ – user’s nullifier to prevent double registration of randomness

Proving:

Generate proof $π_{e}$ for relation:

$R_{e} = {s i g, a d d r e s s, p_{p}, p_{c}, r, e v e n t I d, r o o t_{p}, r o o t_{c}, n u l l_{s} : n u l l_{s} \leftarrow h a s h (s i g . s), a d d r e s s \leftarrow e c r e c o v e r (s i g, (a d d r e s s | | e v e n t I d)), m e r k l e V e r i f y (a d d r e s s, p_{p}, r o o t_{p}) \to t r u e, m e r k l e V e r i f y (h a s h (s i g), p_{c}, r o o t_{c}) \to t r u e, r = r * r}$

第二步称为“发送者确定”，要求每位 ZKSS 参与者匿名地将自己的随机数 ( r ) 添加到礼物发送者数组中。

合约会验证零知识证明 ( \pi_e )。
如果验证通过，且该参与者的 nullifier（空值化器）nulls 尚未出现在已使用的 nullifier 列表中，则用户可通过交易中继器（relayer）将其随机数 ( r ) 加入数组。
随机数 ( r ) 与其对应的 nullifier 必须成对可访问（即能相互关联，但对外隐藏身份）。

在关系 ( R_e ) 中，最后一项操作 ( r = r * r ) 会引入额外的约束，用以“锚定” ( r ) 的值，从而确保协议的可靠性（soundness）。

每位参与者必须唯一生成自己的随机数 ( r )，并公开披露该值。
然而，( r ) 与具体参与者之间的关联通过零知识证明（ZKP）加以隐藏，由中继器代为发送交易。

建议：参与者应使用 2048 位 RSA 公钥作为随机数 ( r )。也就是说，每位 ZKSS 参与者需唯一生成一个 RSA 私钥（并妥善保管），然后公布对应的公钥（指数固定为 ( \text{exp} = 65537 )）。

这些公布的 RSA 公钥将在算法的第三步中用于加密礼物接收者的实际收件地址，使得只有对应的礼物发送者才能解密并获知收件信息。

2.4 礼物接收者披露（Gift Receiver Disclosure）

Algorithm 4: Disclosing gift receiver

Inputs:

Private:
- $s i g$ – user’s ECDSA signature of ( $a d d r e s s | | e v e n t I d$ )
Public:
- $a d d r e s s$ – user’s address
- $e v e n t I d$ – a unique id of a ZKSS game (contract address $| |$ nonce)
- $n u l l_{s}$ – sender’s nullifier

Proving:

Generate proof $π_{c}$ for relation:

$R_{c} = {s i g, a d d r e s s, e v e n t I d, n u l l_{s} : n u l l_{r} \leftarrow h a s h (s i g . s), a d d r e s s \leftarrow e c r e c o v e r (s i g, (a d d r e s s | | e v e n t I d)), n u l l_{r} \neq n u l l_{s}}$

第三步称为“接收者披露”，是 ZKSS 算法的最后一步。完成此步骤后，“秘密圣诞老人”的配对即告完成，礼物发送者便可开始寄送礼物。

此步骤无需中继器，因为接收者的身份（即 msg.sender）无论如何都会被公开。
合约会验证零知识证明 ( \pi_c )。
若验证成功，且接收者提供的 nullifier nullr 与之前步骤中使用的 nulls 不相等，则接收者的地址将被绑定到对应发送者的随机数（即其 RSA 公钥）上。

为避免泄露接收者在上一步中的位置，nullr ≠ nulls 这一不等式必须通过私有方式（例如在 ZKP 内部）进行验证。

为确保每位接收者仅披露一次，智能合约需公开维护一份唯一的 msg.sender 列表，并验证这些地址确实属于初始的 ZKSS 参与者集合。

若多个接收者同时选择同一个发送者，导致冲突，则其中一笔交易必须回滚（revert），被拒绝的接收者需重新尝试披露自己。

此外，礼物接收者可在披露时附上其加密后的现实世界收件地址，该地址使用前一步中对应发送者公布的 RSA 公钥进行加密。

ZKSS 协议的实现还可将 RSA 加密正确性检查纳入零知识证明的验证逻辑中，以进一步增强安全性。

3.安全性

3.1 ECDSA 非确定性问题
若省略“签名承诺”步骤，攻击者可能对 ZKSS 协议发起攻击，甚至导致游戏拒绝服务（DoS）。恶意参与者可生成非确定性的 ECDSA 签名，从而绕过 nullifier（空值化器）的保护机制，抢占所有发送者席位。

不过，也可以提出 ZKSS 协议的一个替代版本：使用 EdDSA 签名。由于 EdDSA 本质上是确定性的，因此可以跳过签名承诺步骤，移除用于存储签名承诺的稀疏默克尔树（SMT），并将 nullifier 直接构造为 hash(sig)，而非当前方案中的 hash(sig.s)。

3.2 接收者抢跑攻击（Receiver Frontrunning）
在协议的“接收者披露”阶段，存在一种轻微的抢跑攻击（frontrunning attack）可能性。

恶意的礼物发送者可以监控交易内存池（mempool），在合法接收者提交交易前抢先提交自己的交易（选择相同的发送者），从而提高该接收者在下一次尝试披露时选中该恶意发送者的概率。

然而，这种攻击仅能成功一次（因为每位接收者只能选择一个发送者一次），并且一旦该恶意发送者已被某人选择，此攻击便不再可行。

4.正确性（Correctness）

ZKSS 协议的关键在于严格分离第二步与第三步。

在第二步中使用了交易中继器（relayer），因此在第三步中，参与者无法判断哪个随机数 ( r ) 属于哪位参与者。
同时，每位参与者只能提交一次随机数，这一限制由 nullifier 逻辑强制执行。
此外，通过零知识证明（ZKP），我们确保没有任何参与者能够操纵协议，将礼物分配给自己，或指定特定的发送者。

为直观理解这些机制，可考虑以下“秘密圣诞老人”的类比：

假设有 ( n ) 位参与者聚集在一起（见算法 1）。
每位参与者将一张写有自己随机数的纸条秘密地放入一顶帽子中。所有人都匿名投递纸条，除了负责传递纸条的“运输机制”（即协议中的中继器，见算法 3）外，无人知道哪张纸条属于谁。参与者可通过 VPN 等技术进一步隐藏其与中继器之间的关联，但这些细节超出了本文范围。

随后，每位参与者从帽子中恰好抽取一张纸条。借助“魔法”——即由 ZKP 所保障的规则——他们不可能抽到自己的纸条（见算法 4）。当这些包含随机数的纸条被公开后，对应持有该随机数的参与者（即礼物发送者）便会向抽中该纸条的人（即接收者）寄送礼物。

此外，如果所选的随机数是一个 RSA 公钥，接收者便可使用该公钥通过 RSA 加密，安全地将自己的实际收件地址发送给对应的“圣诞老人”。

综上所述，协议正确性依赖于以下关键假设：

每位礼物发送者不会泄露自己身份，也不会泄露其在协议第二步中使用的随机数。
ECDSA 签名必须按照 RFC 6979 [3] 标准生成，并且仅接受椭圆曲线下半部分的签名（即 s 值需满足 ( s \leq n/2 )，以防止签名延展性攻击）。
每次 ZKSS 游戏的 eventId 必须全局唯一。
协议的可靠性（soundness）源自底层零知识证明系统的可靠性。
若参与者提供加密载荷（如加密的收件地址），则他们需自行确保加密数据的正确性。

原文：https://ethresear.ch/t/zk-secret-santa-protocol/23582

免责声明：本文为c2e Labs的第三方内容，仅供信息分享与传播之目的，不代表我们的立场或观点且不构成任何投资及应用建议。版权归原作者或来源方所有，如内容或素材有所争议请和我们取得联系。

收藏赞（1）

我来评论

登录后回复

Joe

第 2 位会员

注册于

Let's building Web3