各位以太坊研究者們好！隨著冬天的到來，我決定也在論壇上分享一下這個有趣的協議。今年早些時候，我們撰寫了一篇研究論文，探討如何在以太坊上實現（真正的）秘密聖誕老人遊戲，同時保障玩家隱私和遊戲的正確性。很想知道你們對 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 參與者以太坊地址
安裝過程：
- 主參與者調用智能合約中的註冊函數，提供所有參與者的地址。
- 合約將地址存儲在參與者的稀疏默克爾樹 (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 )，並且|| | |是連接操作
承諾過程：
- 參與者在消息M M = ( \mathsf{address}\ ||\ \mathsf{eventId} a d d r e s s上簽名 | | 事件ID ）並計算簽名哈希。
- 參與者調用智能合約上的提交函數，並將哈希值作為參數。
- 合約將提供的哈希值存儲在簽名承諾 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 }都是唯一的。
- 該協議的可靠性源於底層零知識證明系統的可靠性。
- 如果參與者提供加密有效載荷，則他們有責任確保加密數據的正確性。
參考
- [Woo24] Gavin Wood. 以太坊：一個安全、去中心化的通用交易賬本。https://
- 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年。 - [Por13] Thomas Pornin. 數字簽名算法 (DSA) 和橢圓函數的確定性使用
曲線數字簽名算法（ECDSA）。RFC 6979。2013 年 8 月。doi：10.17487/RFC6979。
url: RFC 6979 相關信息 » RFC 編輯器。
