Cicada: 通過時間鎖謎題和ZK實現鏈上私密投票

所有的投票系統都需要依賴誠信和透明度才能發揮實際作用。從表面上看，區塊鏈似乎是構建這些系統的理想平台。事實上，許多去中心化組織已經採用了無許可投票來表達集體意願，通常是在行使重要財務權力或調整關鍵協議參數的情況下。然而，鏈上投票存在一些缺點，並且對於 Web3 投票系統而言，隱私問題尚未得到充分的探索，這給其帶來了負面影響。在今天大多數使用的鏈上投票協議中，選票和投票結果都是完全公開的。缺乏隱私保護意味著投票結果容易受到操縱，同時也可能導致選民激勵不一致，潛在地導致非民主的結果。

為此，我們推出了 Cicada：一個全新、開源的 Solidity 庫，利用時間鎖謎題和零知識證明來實現鏈上私密投票。與現有系統相比，Cicada 具備獨特的隱私屬性，最小化了對信任的依賴，並且在 Ethereum 主網上的使用效率也非常高。

在本文中，我們對投票隱私的現狀進行了調研，並對 Cicada 的工作原理進行了高層次的介紹（正式證明將在後續提供）。我們還鼓勵開發者們前往 GitHub 儲存庫查看詳細資訊——Cicada 可以根據不同的投票方案和特性進行靈活調整和擴展。我們期待與社區合作，共同探索這些可能性。

投票隱私性概述

在任何投票系統（鏈上或其他系統）中，我們都需要考慮許多不同層次的隱私性。個人選票的披露、持續的投票統計和選民身份都會以不同的方式影響到選民。在不同的投票中，所需的隱私屬性也不盡相同，以下是密碼學和社會科學文獻中經常涉及的一些屬性：

· 選票隱私性：秘密投票，也稱為「澳洲式選舉」（Australian ballot），是為了保護現實世界投票系統中個別選民的隱私，並減少賄賂和脅迫的一種方式（在鏈上環境中，我們可能需要比秘密投票更強大的機制，具體請參見下文的「無收據性」）。選票隱私性還可以減少社會期望偏差——人們不太會因為其他人對其選擇的看法而投票。 

· 計票隱私性：許多投票系統在選民投票期間隱藏持續的投票統計，即每個選項收到的投票數量，以避免對投票率和選民激勵產生影響。我們在現實世界中已經看到了這種情況：例如，較晚投票的美國參議員比較早投票的參議員更可能與他們的政黨保持一致。而在鏈上的 Token 加權投票中，巨鯨可以通過讓對手保持領先來維持他們的虛假安全感（有些人可能懶得投票，因為他們覺得這些人無論如何都會贏），然後在最後一刻投出自己的選票來左右結果。

· 選民匿名性：在許多現實世界的投票系統中，你的選票是保密的，但是你是否投票通常可以被其他人知曉。這可以作為防止選民欺詐的保護措施，因為公布誰投票的記錄可以讓人們檢查是否有人以他們的名義投票。然而，在鏈上，我們可以使用密碼原語防止選民欺詐，同時保持匿名性——例如，使用 Semaphore，你可以用零知識的方式證明自己是一個合格的選民，並且尚未投票。 

· 無收據性：選民不應該向第三方提供選票的「收據」，以證明他們的選票如何投給了某個人，否則可能導致選票出售。抵抗脅迫（coercion-resistance）是另一個與之密切相關的屬性，防止某人被迫以某種方式投票。在去中心化環境中，這些屬性尤其吸引人，因為通過智能合約市場，投票權可以變得流動起來。不幸的是，這些屬性非常難以實現。事實上，Juels 等人指出，這些特性在沒有可信硬體的無許可設置中是不可能實現的。 

Cicada 專注於持續的投票統計隱私，但是（正如我們後面將討論的那樣），它可以與零知識群組成員證明結合使用，以實現選民匿名性和選票隱私性。

Cicada：利用同態時間鎖謎題實現計票隱私性

為了實現持續的投票統計隱私性，Cicada 借鑑了在鏈上（據我們所知）從未使用過的密碼原語。

首先，時間鎖謎題（Rivest，Shamir，Wagner，1996）是一種密碼學謎題，只有在預定的時間段過去後才能揭示其背後的秘密——更具體地說，只能通過重複執行某些不可並行化計算來解密謎題。時間鎖謎題在投票的背景下對於實現持續的投票統計隱私性大有作用：用戶可以將他們的選票作為時間鎖謎題提交，這樣他們的選票在投票過程中將保密，但在投票後可以被披露。與其他大多數私密投票結構不同的是，這使得計票隱私性的實現不再需要依賴統計機構（如選舉工作人員計算紙質或數字選票）、閾值加密（幾個受信任方必須合作解密一個消息）或任何其他受信任方：任何人都可以解決時間鎖謎題以確保結果在投票後被揭示。

其次，同態時間鎖謎題（Malavolta Thyagarajan, 2019）具有一個額外的特性，即在了解秘鑰、解密謎題或使用後門的情況下，可以對加密數值進行一些計算。特別是，線性同態時間鎖謎題使我們能夠將謎題組合在一起，生成一個新的謎題，其中包含原始謎題秘密數值的總和。

正如論文作者所指出的那樣，線性同態時間鎖謎題特別適用於私密投票：選票可以編碼為謎題，並且可以對它們進行同態組合以獲得編碼最終統計的謎題。這意味著只需要一次計算即可揭示最終統計結果，而不是為每個選票解決一個唯一的謎題。

全新體系：效率與權衡

對於一個能夠在鏈上實際應用的投票方案，還有幾個要考慮的因素。首先，攻擊者可能試圖通過提交錯誤編碼的選票來操縱投票結果。例如，我們可能期望每個選票的時間鎖謎題編碼一個布爾值：「1」表示支持所投議案，「0」表示反對。一個熱心的支持者可能會嘗試使用類似「100」的編碼來增加他們的有效投票權。

我們可以通過要求選民在提交選票本身之外，還提交一個零知識證明來防止這種攻擊。然而，零知識證明可能需要耗費大量的計算資源——為了使選民參與的成本儘可能低，證明應該（1）在客戶端高效計算和（2）在鏈上高效驗證。

為了使證明儘可能高效，我們使用了一種定製的 sigma 協議。這是一種為特定代數關係設計的零知識證明，而不是通用的證明系統。這大大加速了證明時間：在一台現成的筆記本電腦上，用 Python 生成一個選票有效性證明只需 14 毫秒。

雖然這個 sigma 協議的驗證過程在概念上很簡單，但它實際需要幾次大型模數指數運算。Malavolta 和 Thyagarajan 的線性同態方案使用了 Paillier 加密，因此這些指數運算將在某個 RSA 模數 N^2 的模數下進行。對於一個相當大的 N，這些指數運算在大多數 EVM 鏈上是難以承受的（需要數百萬個 gas）。為了降低這個成本，Cicada 改為使用指數 ElGamal，該指數仍然提供加法同態性，但是在一個更小的模數（N 而不是 N^2）上運算。

使用 ElGamal 的一個缺點在於，解密統計結果時需要窮舉離散對數（請注意，這在鏈下完成，並在鏈上進行高效驗證）。因此，它只適用於預期最終統計結果相對較小的情況（例如，小於 2^32，約 430 萬票）。在最初基於 Paillier 的方案中，無論統計結果的大小如何，都可以高效地解密。

選擇 RSA 模數 N 還涉及權衡。我們的方法使用了 1024 位的模數以提高 gas 效率。儘管這遠高於已公開因子分解的最大 RSA 模數（為 829 位），但它低於通常推薦用於 RSA 加密或簽名的 2048 位大小。然而，在我們的應用中，我們不需要長期安全性：一旦選舉結束，如果未來 N 被分解，就不會有風險。在時間鎖過期後，假設統計結果和選票將變得公開，因此使用相對較小的模數是合理的。（如果因子分解算法改進，這也可以很容易地在將來進行更新。）

匿名性和選民資格

如上所述，Cicada 提供持續的投票統計隱私性——時間鎖謎題可以讓統計結果在投票期間維持保密狀態。然而，每個選票也是一個時間鎖謎題，在相同的公共參數下進行加密。這意味著，就像統計結果可以解密一樣（通過執行必要的計算），每個選票也可以解密。

換句話說，Cicada 僅保證選票在投票期間保密。如果一個好奇的觀察者想解密特定選民的選票，他們也可以在投票結束後做到。解密任何一個選票的成本與解密最終統計結果的成本一樣，因此完全解密一個包含 n 個選民的投票需要 O(n) 的工作。但是，所有這些選票可以並行解密（假設有足夠的計算機），這一過程所需的時間與解密最終統計結果的時間相同。

對於某些投票來說，這可能並不理想。儘管我們對於臨時的計票隱私性感到滿意，但我們可能希望擁有永久的選票隱私性。為了實現這一點，我們可以將 Cicada 與匿名選民資格協議相結合，通過零知識群組成員證明來實現。這樣，即使解密選票，它只會透露某個人以何種方式投票，而這在統計結果中已經得到了披露。

在我們的儲存庫中，我們提供了一個使用 Semaphore 進行選民匿名性的示例合約。請注意，Cicada 合約本身不對選民資格的確定或執行做任何假設。特別是，你可以將 Semaphore 替換為 Semacaulk 或 ZK 狀態證明。

選票統計機構

設計 Cicada 時我們的首要目標之一是避免對選票統計機構的依賴：許多私密投票都需要一個半可信的統計機構（或通過安全多方計算協作的委員會），該機構接收並匯總選票。在區塊鏈的環境中，這意味著這些方案不能僅通過智能合約進行，而需要一些人工干預和信任。

在大多數體制中，統計機構在誠信方面是可信的（它們不能操縱投票數），但是它們也必須保持活躍性——如果它們離線，最終結果將無法計算，投票結果將無限期地停滯。在某些體系中，統計機構在維護隱私方面也會得到信任。也就是說，它們了解每個選民的投票，但會在不透露此資訊的情況下發布投票結果。

雖然在許多現實世界的場景中，統計機構是合理的（也是必要的），但它們在區塊鏈的環境中並不理想，我們的目標是最小化信任並確保抗審查性。

結語

Cicada 探索了鏈上投票隱私領域的眾多方向，與其他團隊正在進行的研究互為補充。如上所述，Cicada 與 Semaphore、ZK 儲存證明和流量限制無效化器（rate-limiting nullifier）等匿名群組成員技術相輔相成。Cicada 還可以與 Nouns Vortex 團隊提出的 optimistic proof checker 相結合，以減輕選民的 gas 負擔。

此外，我們還有機會將 Cicada 調整為支持不同的投票方案（如加權投票、平方投票），雖然更複雜的方案可能對 Ethereum 主網來說計算代價過高，但在 Layer 2 網路上可能是可行的。鑒於此，我們歡迎關於 Cicada 未來發展方向的任何建議。

原文連結