原文标题：《Building Cicada: Private on-chain voting using time-lock puzzles》

作者：Michael Zhu，a16z

编译：Lynn，MarsBit

すべての意味のある方法で機能する投票システムは、完全性と透明性に依存しています。一見すると、これによりブロックチェーンはこれらのシステムを構築するための理想的なプラットフォームとなります------実際、多くの分散型組織は、無許可投票を受け入れて集団の意図を表現していますが、通常は大量の富を振りかざしたり、重要なプロトコルパラメータを調整したりする場合です。しかし、オンチェーン投票には欠点もあり、プライバシーは未探索であり開発されていないため、Web3投票システムにとって不利です------現在使用されているほとんどのオンチェーン投票プロトコルでは、投票用紙と投票結果は完全に公開されています。プライバシーがなければ、投票結果は簡単に操作され、選挙人のインセンティブがずれる可能性があり、非民主的な結果を引き起こす可能性があります。

これが、私たちがCicadaを発表する理由です：時間ロックパズルとゼロ知識証明を利用してプライベートなオンチェーン投票を実現する新しいオープンソースのSolidityライブラリです。既存のシステムと比較して、Cicadaは新しいプライバシー属性を持ち、信頼の仮定を最小限に抑え、イーサリアムメインネットで使用するのに十分な効率を持っています。

この記事では、投票プライバシーの状況を調査し、Cicadaがどのように機能するかの高レベルの説明を提供します（正式な証明は近日公開予定です）。また、開発者にGitHubリポジトリを確認することをお勧めします------Cicadaは、さまざまな投票スキームや機能をサポートするために多くの方法で調整および拡張できます。私たちはコミュニティと協力して、これらの可能性を探求したいと考えています。

プライベート投票の簡単な調査

あらゆる投票システム（オンチェーンまたはその他）には、考慮すべきさまざまなレベルのプライバシーがあります。個々の投票用紙の開示、進行中の集計、選挙人の身元は、異なる方法で選挙人のインセンティブに影響を与えます。どのプライバシー属性が必要かは、投票の背景によって異なります。暗号学と社会科学の文献でよく見られるいくつかの属性は次のとおりです：

• 投票用紙のプライバシー：秘密投票、または"オーストラリアの投票用紙"は、現実世界の投票システムのために開発され、個々の選挙人の好みを保持し、賄賂や脅迫を軽減する方法です（オンチェーンの設定では、投票用紙のプライバシーよりも強力な属性が必要になるかもしれません------下記の"無領収書性"を参照）。投票用紙のプライバシーは、社会的期待の偏差を軽減することもできます------他者の選択に対する見解に基づいて投票するプレッシャーが少なくなります。
• 進行中の集計のプライバシー：多くの投票システムは、選挙人がまだ投票している間、進行中の集計や各オプションにどれだけの票が投じられたかを隠して、投票率や選挙人のインセンティブに影響を与えないようにします。私たちは現実世界でこのような状況を見てきました；例えば、遅れて投票するアメリカの上院議員は、早く投票する上院議員よりもより可能性が高い自党に一致します。そしてオンチェーンでは：トークン加重投票では、クジラが対戦相手にリードを維持させることで彼らの虚偽の安全感を欺くことができます（投票を怠る人もいるかもしれません、彼らがどうせ勝つと思っているので）、そして最後の瞬間に自分の投票用紙を投じて結果を左右します。
• 選挙人の匿名性 ：多くの現実世界の投票システムでは、あなたの投票は公開されていませんが、あなたが投票した事実はしばしば公開されています。これは、選挙人詐欺を防ぐために重要です。なぜなら、投票者の記録を公開することで、他の誰かが彼らの名の下に投票したかどうかを確認できるからです。しかし、オンチェーンでは、暗号的な基本要素を使用して選挙人詐欺を防ぎつつ匿名性を保持できます------例えば、Semaphoreを使用することで、あなたがまだ投票していない資格のある選挙人であることをゼロ知識で証明できます。
• 無領収書性：個々の選挙人は、彼らがどのように第三者に投票したかを証明するための"領収書"を提供します。さもなければ、売票につながる可能性があります。密接に関連していますが、より強力な属性は抗脅迫であり、誰かが選挙人に特定の方法で投票するように脅迫するのを防ぎます。これらの属性は、投票権がスマートコントラクト市場を通じて流動性を持つ分散型環境では特に魅力的です。不幸なことに、これらは実現が難しい------実際、Juelsらは信頼できるハードウェアなしでは、無許可の環境でこれを実現することは不可能であると指摘しています。

Cicadaは進行中の集計プライバシーに焦点を当てていますが（後で議論するように）、ゼロ知識グループメンバー証明と組み合わせることで、選挙人の匿名性と投票用紙のプライバシーを達成できます。

Cicadaの紹介：同態時間ロックパズルからの集計プライバシー

進行中の集計のプライバシーを実現するために、Cicadaは（私たちの知る限り）これまでオンチェーンで使用されたことのない暗号学的基本要素を利用しています。

まず、時間ロックパズル（Rivest, Shamir, Wagner, 1996）は、秘密をカプセル化する暗号パズルであり、ある予め定められた時間が経過した後でのみ明らかにされます------より具体的には、このパズルは、いくつかの非平行計算を繰り返すことで解読できます。投票の文脈において、時間ロックパズルは進行統計のプライバシーを実現するのに役立ちます：ユーザーは、投票プロセス中に秘密を保持しつつ、投票後に明らかにできるように、投票用紙を時間ロックパズルとして提出できます。他のほとんどのプライベート投票構造とは異なり、これにより進行統計のプライバシーは、統計機関（選挙スタッフが紙またはデジタル投票用紙を計算する）や閾値暗号（複数の信頼された当事者が協力してメッセージを解読する必要がある）や他の信頼された当事者に依存する必要がなくなります：誰でも時間ロックパズルを解決して、投票後の結果が明らかにされることを保証できます。

次に、同態の時間ロックパズル（Malavolta Thyagarajan, 2019）は、秘密鍵を知っている場合、パズルを解読する場合、またはバックドアを使用する場合に、暗号化された値に対していくつかの計算が可能であるという追加の属性を持っています。特に、線形同態の時間ロックパズルは、パズルを組み合わせて、元のパズルの秘密値の合計をカプセル化した新しいパズルを生成することを可能にします。

論文の著者が指摘するように、線形同態の時間ロックパズルはプライベート投票に特に適した基本要素です：投票用紙はパズルとしてエンコードされ、同態的に組み合わせることができ、最終的な集計をエンコードしたパズルを得ることができます。これは、各投票用紙のためにユニークなパズルを解決するのではなく、最終結果を明らかにするために一度の計算だけで済むことを意味します。

新しい構造：効率とトレードオフ

投票スキームをオンチェーンで実用化するためには、いくつかの問題を考慮する必要があります。まず、攻撃者は不正なエンコードの投票用紙を投じることで投票を操作しようとするかもしれません。例えば、私たちは各投票用紙の時間ロックパズルがブール値でエンコードされることを望むかもしれません："1"は投票された提案を支持することを示し、"0"は反対を示します。熱心な提案支持者は、例えば"100"をエンコードして有効な投票権を拡大しようとするかもしれません。

このような攻撃を防ぐために、選挙人が投票用紙を提出する際に、その投票用紙の有効性に関するゼロ知識証明を同時に提出させることができます。しかし、ゼロ知識証明の計算コストは非常に高い------選挙人の参加コストをできるだけ低く抑えるために、証明は（1）クライアント側で効率的に計算可能であり、（2）オンチェーンで効率的に検証可能であるべきです。

証明をできるだけ効率的にするために、特定の代数関係のために設計されたゼロ知識証明であるカスタムのsigmaプロトコルを使用しました。これにより、証明者の時間が非常に速くなります：Pythonで投票用紙の有効性証明を生成するのに、一般的なノートパソコンで14msかかります。

このsigmaプロトコルの検証器は概念的には非常にシンプルですが、かなりの部分の大きなモジュロのべき乗を必要とします。MalavoltaとThyagarajanの線形同態スキームはPaillier暗号を使用しているため、これらのべき乗は特定のRSAモジュロNに対してN^2のモジュロで実行されます。合理的なサイズのNでは、ほとんどのEVMチェーンでべき乗は非常に高価です（数百万ガス）。コストを削減するために、Cicadaは指数ElGamalを使用します------指数ElGamalは加法的同態を提供し続けますが、より小さなモジュロ（NではなくN^2）で動作します。

ElGamalを使用することの欠点は、カウントの最終的な解読ステップが離散対数のブルートフォース攻撃を必要とすることです（これはオフチェーンで行われ、オンチェーンで有効に検証されます）。したがって、期待される最終票数がかなり小さい場合（例えば2^32未満、約430万票）にのみ適用されます。最初のPaillierベースのスキームでは、サイズに関係なく、カウントは効果的に解読されることができます。

RSAモジュロNを選択することもトレードオフを伴います。私たちの実装は、ガス効率を向上させるために1024ビットのモジュロを使用しています。これは、これまでに公開された最大のRSAモジュロ（829ビット）を大きく上回りますが、RSA暗号化や署名に推奨されるサイズ2048ビットよりは小さいです。しかし、私たちのアプリケーションは長期的な安全性を必要としません：選挙が終了した後、将来Nを考慮するリスクはありません。カウントと投票用紙は時間ロック期間が満了した後に公開されると仮定されるため、比較的小さなモジュロを使用することは合理的です。（分解アルゴリズムが改善された場合、これも将来簡単に更新できます。）

匿名性と選挙人資格

前述のように、Cicadaは進行中の集計プライバシーを提供します------時間ロックパズルの属性は投票中に集計のプライバシーを保持します。しかし、各個別の投票用紙も同じ公共パラメータの下で暗号化された時間ロックパズルです。これは、カウントを解読できるように（必要な計算を実行することで）するのと同様に、各投票用紙も解読できることを意味します。言い換えれば、Cicadaは投票中にのみ投票用紙のプライバシーを保証します------好奇心旺盛な観察者が特定の選挙人の投票用紙を解読したい場合、彼らはそれを行うことができます。任意の個別の投票用紙を解読することは、最終的なカウントを解読するのと同じくらい高価であり、n人の選挙人がいる場合、完全に解読するにはO(n)の作業が必要です。しかし、これらすべての投票用紙は並行して解読でき（十分な数のマシンがあると仮定して）、かかる実時間は最終的なカウントを解読するのに必要な時間と同じです。

特定の投票用紙にとって、これは望ましくないかもしれません。進行中の集計プライバシーには満足していますが、無期限の投票プライバシーを望むかもしれません。これを実現するために、Cicadaを匿名選挙人資格プロトコルと組み合わせ、ゼロ知識グループメンバー証明を通じてインスタンス化することができます。こうすることで、投票用紙が解読されても、それが示すのは誰かがこの方法で投票したということだけです------私たちはすでに集計からこれを知っています。

私たちのリポジトリには、Semaphoreを使用して選挙人の匿名性を実現するサンプルコントラクトが含まれています。しかし、Cicadaコントラクト自体は、選挙人資格をどのように決定または実行するかについての仮定を持っていないことに注意してください。特に、SemaphoreをSemacaulkやZK状態証明（こちらおよびこちらで提案されたもの）に置き換えることができます。

統計機関

Cicadaを設計する際の最優先事項の1つは、統計機関の必要性を回避することでした：多くのプライベート投票構造は、半信頼の統計機関（または認可された委員会が安全なマルチパーティ計算を通じて調整する）に投票用紙を受け取り、集計することを要求します。ブロックチェーン環境では、これらのスキームは単にスマートコントラクトによって実行されることができず、いくつかの人為的な介入と信頼が必要です。

ほとんどの構造では、集計機関は完全性の面で信頼されていません（彼らは投票用紙のカウントを操作できません）が、活性の面では信頼されています------彼らがオフラインの場合、最終結果を計算できず、投票結果を無期限に遅延させることになります。特定の構造では、彼らはプライバシーを維持することも信頼されています------つまり、彼らは誰がどのように投票したかを知っていますが、この情報を公開せずに投票結果を発表することが期待されています。

多くの現実世界のシナリオでは、統計機関は合理的（かつ必要な）仮定ですが、ブロックチェーン環境では理想的ではなく、私たちの目標は信頼を最小限に抑え、検閲耐性を確保することです。

Cicadaは、オンチェーン投票プライバシーの分野を探求する多くの方向性の1つであり、他のチームが進めている研究を補完します。前述のように、CicadaはSemaphore、ZKストレージ証明、レート制限無効化器などの匿名グループメンバー技術と密接に関連しています。Cicadaは、Nouns Vortexチームが提案した楽観的証明チェッカーを統合して、選挙人のガス負担を軽減することもできます。

Cicadaをさまざまな投票スキーム（例えばトークン加重投票、二次投票）をサポートするように調整する機会もあります------より複雑なスキームはイーサリアムメインネットでは計算コストが高すぎるかもしれませんが、L2では実用的かもしれません。この点を考慮して、Cicadaを次のステップに進めるための貢献、フォーク、提案を歓迎します。