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

这是arXiv上论文的链接。

抽象的

本文提出了一种三步秘密圣诞老人算法，该算法利用零知识证明（ZKP）建立礼物发送者和接收者之间的关系，同时确保发送者的隐私。该算法维护排列错乱，且无需中央机构即可成功运行。只要与交易中继器集成，该方法即可用 Solidity 实现。

1. 引言

圣诞节来临之际，每个人都喜欢玩“秘密圣诞老人”游戏。但是，在线玩这个游戏却面临着一系列挑战。

首先，以太坊区块链的开放性不允许我们进行私密计算。为了隐藏“秘密圣诞老人”活动参与者的身份（地址），我们使用了交易中继器和零知识证明（ZKP）。

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

第三，通过引入无效化器（或称盲化器）的概念，可以解决“双重投票”问题。该协议能够在不泄露玩家隐私的前提下，验证他们的参与情况。

2. 协议描述

ZK Secret Santa (ZKSS) 协议是一个三步非对等交互过程，需要所有游戏参与者的参与。

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

\mathsf{hash}(m) \;\rightarrow\; h \;\in\; \mathbb{F}_p h a s h ( m ) → h ∈ 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)\}, R = { ( w , x ) ∈ W × X ： ϕ 1 ( w , x ) , ϕ 2 ( w , x ) , … , ϕ m ( w , x ) } ,

其中 w是见证数据， x是公开数据， \{\phi_1(w,x), \phi_2(w,x), \dots, \phi_m(w,x)\} { ϕ 1 ( w , x ) , ϕ 2 ( w , x ) , … , ϕ m ( w , x ) }是必须同时证明的关系集。

函数\mathsf{ecrecover} e c r e c o v e r [1] 用于根据 ECDSA 签名 \ mathsf{sig} s i g和签名哈希h h恢复用户的\mathsf{address} a d d r e s s 。

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

\mathsf{merkleVerify}(x, p_i , root ) \ ; \ rightarrow \ ; \ mathsf { bool } .merkleVerify ( x , p_i , root ) →布尔。​​​

2.1 设置

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

由于设置过程是公开的，可以选择一名主要参与者代表所有玩家安全地在一次交易中注册所有玩家。

算法 1：设置

输入：

• 民众：
  • 地址 - ZKSS 参与者以太坊地址

安装过程：

1. 主参与者调用智能合约中的注册函数，提供所有参与者的地址。
2. 合约将地址存储在参与者的稀疏默克尔树 (SMT) 中，对应的索引为\mathsf{index} = \mathsf{hash}(\mathsf{address}) i n d e x = h a s h ( a d r e s s ) 。

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

2.2. 签字承诺

第一步称为签名承诺，其目的是约束零知识共享系统 (ZKSS) 参与者使用确定性导出的 ECDSA 签名。有关此步骤背后的原理，请参阅ecdsa-non-determinism安全部分。

算法 2：签名承诺

输入：

• 民众：
  • H H – 用户 ECDSA 签名的哈希值（地址||事件ID ） | | 事件ID ） ，其中\ mathsf {address}是用户的以太坊地址，事件ID是( \ mathsf { contract \ address}\ ||\ \ mathsf { nonce } contract ) 。 地址​​​​​​ | | n o n c e )，并且|| | |是连接操作

承诺过程：

1. 参与者在消息M M = ( \mathsf{address}\ ||\ \mathsf{eventId} a d d r e s s上签名 | | 事件ID ）并计算签名哈希。
2. 参与者调用智能合约上的提交函数，并将哈希值作为参数。
3. 合约将提供的哈希值存储在签名承诺 SMT 中，对应的索引为\mathsf{index} i n d e x = H H 。

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

2.3. 礼品赠送者认定

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

算法 3：礼物赠送者判定

输入：

• 私人的：

  • \mathsf{sig} s i g – 用户对 ( \mathsf{address}\ ||\ \mathsf{eventId} a d d r e s s的 ECDSA 签名 | | 事件I d ）​​​
  • 地址–用户地址​​​​
  • p_p p p – 用户地址包含的默克尔证明
  • p_c p c – 用户签名承诺包含的默克尔证明

• 民众：

  • r r – 用户独特的随机性
  • \mathsf{eventId}事件ID – ZKSS游戏的唯一ID
  • \mathsf{root_p} r o o t p – 参与者 SMT 根
  • \mathsf{root_c} r o o t c – 签名承诺 SMT 根
  • \mathsf{null_s} n u l l s – 用户用于防止重复注册随机性的无效化符

证明：

生成关系式π_e π 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 \ } Re = { 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 , null l s : null s ← hash ( s i g . s ) ,​​​​​​地址←隐藏（签名， （地址​​​​​​​​​​ ​​​​​ ​​​​​​​ | | 事件I d ) ) ，​​​​ merkle验证（地址、 pp 、 root ） →真，​ ​​​​​​​​​​​ ​​​​​​​​​​​​merkle验证（ hash （ sig ） ， pc ， rootc ） →真，​​​​​​​​ ​​​​​​​ ​​​​​ ​​​r = r ∗ r }

合约会验证证明\pi_e π e 。如果证明正确，且\mathsf{null_s} n u l l s未包含在已使用的无效化符列表中，则用户通过中继器将其随机数添加到数组中。随机数和无效化符必须能够成对访问。

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

每个参与者都必须唯一地生成r r并公开披露。然而，在通过中继发送交易的零知识证明 (ZKP) 中， r r与\mathsf{participant} p a r t i c i p a n t之间的关系是隐藏的。

建议玩家使用 2048 位 RSA 公钥作为随机数r r 。也就是说，ZKSS 参与者生成唯一的 RSA 私钥（他们必须记住这些私钥），并根据\mathsf{exp} e x p = 65537 发布相应的公钥。

然后，在算法的第三步中使用已发布的 RSA 公钥来加密礼物接收者的送货地址，以便只有相应的礼物发送者才能读取这些地址。

2.4. 礼品接收者披露

第三步，即接收者信息披露，是零知识共享系统（ZKSS）算法的最后一步。之后，秘密圣诞老人礼物分发活动即告完成，送礼者可以开始向接收者发送礼物了。

接收者披露步骤可以不通过中继器执行，因为接收者身份（ \mathsf{msg.sender} m s g . s e n d e r ）无论如何都会被披露。

算法 4：披露礼物接收者

输入：

• 私人的：

  • \mathsf{sig} s i g – 用户对 ( \mathsf{address}\ ||\ \mathsf{eventId} a d d r e s s的 ECDSA 签名 | | 事件I d ）​​​

• 民众：

  • 地址–用户地址​​​​
  • \mathsf{eventId}事件ID – ZKSS游戏的唯一ID（合约地址|| | | nonce）
  • \mathsf{null_s} n u l l s – 发送者的无效化符

证明：

生成关系式π_c π 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}\ } R c = { s i g , a d d r e s s , e v e n t I d , nu l l s : null r ← hash ( sig.s ) ,​​​ ​​​​​​​地址←隐藏（签名， （地址​​​​​​​​​​ ​​​​​ ​​​​​​​ | | 事件I d ) ) ，​​​​ n u l l r ≠ n u l l s }

合约验证证明\pi_c π c 。如果验证成功且\mathsf{null_r} n u l l r不等于选定的\mathsf{null_s} n u l l s ，则将接收者的\mathsf{address} a d d r e s s分配给相应的发送者的随机数（RSA 公钥）。

必须私下验证无效化不等式，以免泄露接收者在上一步中的位置。

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

如果多个接收者同时选择同一个发送者发生冲突，则其中一个交易必须回滚，被丢弃的接收者必须再次尝试披露自己。

除了零知识证明（ZKP）之外，收礼人还可以提供他们希望接收礼物的加密（真实）地址。加密过程使用之前提供的发送者的RSA公钥完成。

ZKSS 协议的实施可能会在 ZKP 验证方案中添加 RSA 加密正确性检查。

3. 安全性

3.1. ECDSA 非确定性

如果没有签名承诺步骤，就可能攻击零知识共享安全协议 (ZKSS) 并导致游戏崩溃。不诚实的参与者可以生成非确定性的 ECDSA 签名，绕过无效化保护，从而占据所有发送者的槽位。

也就是说，可以使用 EdDSA 签名提出 ZKSS 协议的替代版本。它们的确定性允许跳过签名承诺步骤，移除签名承诺 SMT，并且直接构造无效化器为\mathsf{hash}(\mathsf{sig}) h a s h ( s i g ) ，而不是\mathsf{hash}(\mathsf{sig.s}) h a s h ( s i g . s ) 。

3.2. 接球手领先

在协议的接收方披露步骤中，存在发生轻微抢先攻击的可能性。

不诚实的送礼者可能会监控交易池，抢在收礼者之前（通过选择相同的送礼者），以增加收礼者在下次披露尝试中选择不诚实送礼者的几率。

然而，这种攻击只能奏效一次（接收者只能选择一次发送者），而且当已经选择了不诚实的发送者时，这种攻击是不可能的。

4. 正确性

ZKSS 的核心在于将第二步和第三步分离。由于第二步使用了交易中继器，第三步的参与者无法确定哪个随机数属于哪个参与者。此外，参与者只能生成一次随机数，这是通过无效化逻辑强制执行的。再者，通过采用零知识证明（ZKP），我们确保任何参与者都无法操纵协议，例如给自己发送礼物或选择特定的发送者。

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

每个参与者将写有自己随机数的纸条安全地放入帽子中。每个人都秘密地将自己的纸条放入帽子里，除了“传输”机制（对应于我们协议中的中继器，参见算法 3）之外，任何人都无法得知哪张纸条属于谁。可以使用各种技术（例如 VPN）来确保中继器的匿名性，但这超出了本文的讨论范围。

最后，每位参与者从帽子里随机抽取一张纸条，并且——由于“神奇”的机制（由零知识证明保证）——他们无法取回自己的纸条（参见算法4）。在随机数字的纸条全部展示完毕后，与特定数字对应的参与者会向抽出该纸条的人赠送礼物。

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

综上所述，该协议正确性的关键假设如下：

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

参考

1. [Woo24] Gavin Wood. 以太坊：一个安全、去中心化的通用交易账本。https://
2. ethereum.github.io/yellowpaper/paper.pdf 。版本 f3553dd。访问日期：2025-01-08。2024。
   [ide24] iden3. 稀疏默克尔树。https ://docs.iden3.io/publications/pdfs/Merkle-Tree.pdf
   访问日期：2025年1月8日。2024年。
3. [Por13] Thomas Pornin. 数字签名算法 (DSA) 和椭圆函数的确定性使用
   曲线数字签名算法（ECDSA）。RFC 6979。2013 年 8 月。doi：10.17487/RFC6979。
   url: RFC 6979 相关信息 » RFC 编辑器。