a16z：Cicada如何利用時間鎖謎題和ZK證明實現鏈上投票
原文作者：Michael Zhu
原文編譯：Lynn，MarsBit
原文作者：原文編譯：Lynn，MarsBit原文作者：原文編譯：Lynn，MarsBit原文作者：
原文編譯：Lynn，MarsBit
所有無論以何種有意義的方式運作的投票系統都依賴於完整性和透明度。從表面上看，這使得區塊鏈成為構建這些系統的理想平台——事實上，許多去中心化的組織已經接受了無許可投票來表達集體意圖，通常是在揮舞大量財富或調整關鍵協議參數的情況下。但是鏈上投票也有缺點，
隱私仍未被探索和開發
，對Web3 投票系統不利——在目前使用的大多數鏈上投票協議中，選票和投票結果是完全公開的。如果沒有隱私，投票結果很容易被操縱和選民激勵錯位，可能會導致不民主的結果。
這就是為什麼我們要發布Cicada：一個新的、開源的Solidity 庫，利用時間鎖謎題和零知識證明來實現私人鏈上投票。與現有的系統相比，Cicada 具有新穎的隱私屬性，最大限度地減少了信任假設，並且足夠高效，可以在以太坊主網上使用。在這篇文章中，我們調查了投票隱私的情況，並提供了關於Cicada 如何工作的高層次描述（正式的證明即將到來）。我們還鼓勵開發者查看GitHub 倉庫
——Cicada 可以通過許多方式進行調整和擴展，以支持不同的投票方案和功能，我們希望與社區合作，探索這些可能性。
私人投票的簡要調查
選票隱私：秘密選票，也被稱為「指出」，是為現實世界的投票系統開發的，作為保持個人選民的偏好的一種方式，並減輕賄賂和脅迫（在鏈上設置，我們可能需要一個比選票隱私更強大的屬性——見下文的「無收據性」）。選票隱私還可以減輕社會期望偏差——某人基於他人對其選擇的看法而投票的壓力較小。
指出
選民的匿名性：在許多現實世界的投票系統中，你的投票是不公開的，但你投了票的事實往往是公開的。這對於防止選民欺詐很重要，因為公佈投票者的記錄可以讓人們檢查是否有其他人以他們的名義投票。然而，在鏈上，我們可以防止選民欺詐，同時使用加密基元保留匿名性——例如，通過Semaphore，你可以在零知識中證明你是一個還沒有投過票的合格的選民。
指出
無收據性：個人選民提供其選票的「收據」，以證明他們是如何向第三方投票的，否則可能導致賣票。一個密切相關但更強大的屬性是抗脅迫，它可以防止有人脅迫選民以某種方式投票。這些屬性在去中心化的環境中特別有吸引力，因為投票權可以通過智能合約市場實現流動性。不幸的是，它們也很難實現——事實上，Juels 等人Rivest, Shamir, Wagner, 1996 指出
，在沒有可信硬件的情況下，這在無許可的環境下是不可能的。Malavolta Thyagarajan, 2019 Cicada 專注於正在進行中計票隱私，但（正如我們在後面討論的）它可以與零知識組成員證明聯合，以達成選民的匿名性和選票隱私。
介紹Cicada： 來自同態時間鎖難題的計票隱私
為了實現正在進行中計票的隱私，Cicada 利用了（據我們所知）以前從未在鏈上使用過的密碼學基元。
首先，時間鎖謎題（
）是一個加密謎題，它封裝了一個秘密，只有在一些預定的時間過後才能被揭示——更具體地說，這個謎題可以通過重複進行一些非平行計算來解密。時間鎖定謎題在投票的背景下對於實現運行統計的隱私很有用： 用戶可以將他們的選票作為時間鎖謎題提交，這樣他們在投票過程中是保密的，但在投票後可以被揭露。與其他大多數私人投票結構不同的是，這使得運行統計隱私不需要依賴統計機構（如選舉工作人員計算紙質或數字選票）、閾值加密（幾個受信任方必須合作解密一個消息）或任何其他受信任方：任何人都可以解決一個時間鎖謎題，以確保投票後結果被揭示。
其次，一個同構的時間鎖謎題（
）具有額外的屬性，即在知道秘密密鑰、解密謎題或使用後門的情況下，對加密值的一些計算是可能的。特別是，一個線性同態的時間鎖謎題允許我們將謎題組合在一起，產生一個新的謎題，封裝了原始謎題的秘密值的總和。
正如論文作者所指出的，線性同態的時間鎖謎題是一種特別適合於私人投票的基元： 選票可以被編碼為謎題，並且它們可以被同態地組合起來，以獲得一個編碼最終計票的謎題。這意味著只需要一次計算就可以揭示出最終結果，而不是為每張選票解決一個獨特的謎題。
一個新的結構：效率和權衡
要使投票方案在鏈上實用，還需要考慮幾個問題。首先，攻擊者可能會試圖通過投一個不正確的編碼的選票來操縱投票。例如，我們可能希望每張選票的時間鎖謎題都編碼為一個布爾值：「 1 」表示支持被投票的提案，「 0 」表示反對。一個熱心的提案支持者可能會試圖編碼，例如「 100 」來擴大他們的有效投票權。
我們可以通過讓選民在提交選票本身的同時提交一份關於選票有效性的零知識證明來防止這種攻擊。不過零知識證明的計算成本很高——為了盡可能降低選民參與的成本，證明應該是（1 ）可有效計算的客戶端和（2 ）可有效驗證的鏈上證明。
為了使證明盡可能高效，我們使用了定制的sigma 協議——為特定代數關係設計的零知識證明，而不是通用的證明系統。這使得證明者的時間非常快：用Python 生成一個選票有效性證明，在一台現成的筆記本電腦上需要14 ms.
雖然該sigma 協議的驗證器在概念上很簡單，但它需要相當一部分大的模冪。 Malavolta 和Thyagarajan 的線性同態方案使用Paillier 加密，因此這些求冪將對某些RSA 模N 以N^ 2 為模執行。對於合理大小的N，在大多數EVM 鏈上，取冪非常昂貴（數百萬gas）。為了降低成本，Cicada 使用指數ElGamal——指數ElGamal 仍然提供加性同態，但在更小的模數上工作（N 而不是N^ 2 ） 。此處此處此處和此處和
此處
和
此處
和
此處
所建議的）。
統計當局
