a16z: Cicada がタイムロック パズルとゼロ知識証明を使用してオンチェーン投票を可能にする方法

Cicada は新しいプライバシー特性を備え、信頼の前提を最小限に抑え、イーサリアムのメインネットで使用できるほど効率的です。

**執筆者:**Michael Zhu

編集者: Lynn、MarsBit

有意義に機能するすべての投票システムは、完全性と透明性に依存しています。一見すると、これにより、ブロックチェーンはこれらのシステムを構築するための理想的なプラットフォームになります。実際、多くの分散型組織は集合的意図を表現する手段としてパーミッションレス投票を採用しており、多くの場合、莫大な富を行使したり、場合によっては主要なプロトコルパラメータを微調整したりしています。しかし、オンチェーン投票には欠点もあり、プライバシーはまだ解明されておらず未開発であり、Web3 投票システムにとっては良くありません。現在使用されているオンチェーン投票プロトコルのほとんどでは、投票用紙と投票結果は完全に公開されています。プライバシーがなければ、投票結果は簡単に操作され、投票者のインセンティブが調整されず、非民主的な結果につながる可能性があります。

だからこそ、私たちは Cicada をリリースするのです。これは、タイムロック パズルとゼロ知識証明を活用してプライベートなオンチェーン投票を可能にする、新しいオープンソースの Solidity ライブラリです。既存のシステムと比較して、Cicada は新しいプライバシー特性を備え、信頼の前提を最小限に抑え、イーサリアムのメインネットで使用できるほど効率的です。

この投稿では、投票のプライバシーの状態を調査し、Cicada がどのように機能するかについて概要を説明します (正式な証明は近日中に行われます)。また、開発者には GitHub リポジトリをチェックすることをお勧めします。Cicada はさまざまな投票スキームや機能をサポートするためにさまざまな方法で調整および拡張できます。私たちはコミュニティと協力してこれらの可能性を探求したいと考えています。

民間世論調査の簡単な調査

どのような投票システム (オンチェーンかどうかにかかわらず) においても、考慮すべきさまざまなレベルのプライバシーが存在します。個人の投票用紙、候補者数、および有権者の身元情報の開示はすべて、さまざまな形で有権者の動機に影響を与えます。どのプライバシー プロパティが必要かは、投票の状況によって異なります。暗号学や社会科学の文献で頻繁に登場するいくつかの例は次のとおりです。

• 投票のプライバシー: 「オーストラリアの投票」としても知られる秘密投票は、個々の有権者の好みを保持し、贈収賄と強制を軽減する方法として、現実世界の投票システム用に開発されました (オンチェーンで設定されるため、投票よりも強力なプロパティが必要になる場合があります)プライバシー - 下記の「受領不能性」を参照)。投票のプライバシーにより、社会的望ましさのバイアスも軽減されます。自分の選択について他人がどう思うかに基づいて投票するというプレッシャーが軽減されます。
• 進行中の集計のプライバシー: 多くの投票システムは、投票率や投票者のインセンティブへの影響を避けるために、有権者がまだ投票している間、進行中の集計、つまり各選択肢にすでに投じられた投票数を隠します。私たちはこれが現実の世界で起こっているのを見てきました。たとえば、後で投票する米国上院議員は、早く投票する上院議員よりも自分の党に同調する可能性が高くなります。そしてオンチェーン: トークン重み付け投票では、クジラは相手を優位に保つことで相手を誤った安心感に誘い込み(いずれにせよ勝つだろうと考えて投票するのが面倒な人もいるかもしれません)、その後自分の票を投じます。最後の最後に来て結果を決めてください。
• 有権者の匿名性: 現実世界の多くの投票システムでは、投票は公開されませんが、投票したという事実は多くの場合公開されます。投票者記録を公開すると、他の人が自分の名前で投票したかどうかを確認できるため、これは不正投票を防ぐために重要です。ただし、オンチェーンでは、暗号化プリミティブを使用して匿名性を維持しながら不正投票を防ぐことができます。たとえば、Semaphore を使用すると、知識ゼロで自分がまだ投票していない有効な有権者であることを証明できます。
• 受領不可: 個々の有権者は、第三者にどのように投票したかを証明するために投票用紙の「受領書」を提出します。そうしないと、チケットが販売される可能性があります。密接に関連していますが、より強力な特性は強制耐性です。これは、誰かが有権者に特定の方法で投票を強制することを防ぎます。これらの特性は、スマートコントラクト市場を通じて議決権を流動化できる分散型環境において特に魅力的です。残念ながら、これらは実装するのも難しく、実際、信頼できるハードウェアがなければパーミッションレス環境では不可能だとジュエルズらは指摘している。

Cicada は機内集計のプライバシーに重点を置いていますが、(後で説明するように) ゼロ知識グループのメンバーシップ証明と組み合わせることで、有権者の匿名性と投票のプライバシーを実現できます。

Cicada の紹介: 準同型タイムロック問題からの投票集計プライバシー

進行中の投票集計のプライバシーを確保するために、Cicada は (私たちの知る限りでは) これまでオンチェーンで使用されたことのない暗号化プリミティブを利用しています。

まず、タイムロック パズル (Rivest、Shamir、Wagner、1996 年) は、あらかじめ決められた時間が経過した後にのみ明らかにされる秘密をカプセル化した暗号化されたパズルです。より具体的には、このパズルは、次のような方法で繰り返すことができます。復号化するための並列計算。タイムロック パズルは、統計を実行する際のプライバシーを確保するために投票のコンテキストで役立ちます。ユーザーはタイムロック パズルとして投票を送信できるため、投票プロセス中は秘密に保たれますが、投票後には公開されます。他のほとんどの民間投票構造とは異なり、これにより、統計機関 (紙やデジタル投票用紙を数える選挙職員など)、しきい値暗号化 (メッセージを復号するには複数の信頼できる関係者が協力する必要がある)、またはその他の信頼できる関係者に依存することなく、統計的プライバシーを運用できます。誰でもタイムロック パズルを解いて、投票後に結果が確実に明らかになるようにすることができます。

第二に、同型タイムロック パズル (Malavolta Thyagarajan、2019) には、秘密鍵、パズルの復号化、またはバックドアの使用の知識があれば、暗号化された値の一部の計算が可能であるという追加の特性があります。特に、線形準同型タイムロック パズルを使用すると、パズルを組み合わせて、元のパズルの秘密の値の合計をカプセル化する新しいパズルを作成できます。

論文の著者が指摘しているように、線形準同型タイムロック パズルは、プライベート投票に特に適したプリミティブです。投票はパズルとしてエンコードでき、それらを準同型的に組み合わせて、エンコードされた最終的なカウンティング パズルを取得できます。これは、投票ごとに固有のパズルを解くのではなく、最終結果を明らかにするために必要な計算が 1 回だけであることを意味します。

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

投票スキームをオンチェーンで実用化するには、考慮すべき問題がいくつかあります。まず、攻撃者は、誤ってエンコードされた投票用紙を投じて投票を操作しようとする可能性があります。たとえば、各投票用紙のタイムロック パズルをブール値としてエンコードしたい場合があります。投票対象の提案には "1"、反対には "0" となります。熱心な提案支持者は、有効投票力を拡大するために「100」のようなコードを作成しようとするかもしれません。

この攻撃は、投票者に投票自体と一緒に投票の有効性を証明するゼロ知識証明を提出させることで防ぐことができます。ただし、ゼロ知識証明は計算コストが高くなります。投票者の参加コストをできるだけ低く抑えるために、証明は (1) クライアント側で効率的に計算可能であり、(2) オンチェーンで効率的に検証可能である必要があります。

証明をできるだけ効率的に行うために、一般的な証明システムではなく、特定の代数関係用に設計されたゼロ知識証明であるカスタム シグマ プロトコルを使用します。これにより、証明者の時間が非常に速くなります。Python で投票用紙の有効性証明を生成するには、既製のラップトップで 14 ミリ秒かかります。

シグマ プロトコルのバリデーターは概念的には単純ですが、かなりの数のべき乗剰余演算が必要です。 Malavolta と Thyagarajan の線形準同型スキームは Paillier 暗号化を使用するため、これらのべき乗は一部の RSA モジュロ N に対してモジュロ N^2 を実行します。 N が適切なサイズの場合、ほとんどの EVM チェーンではべき乗に非常にコストがかかります (数百万ガス)。コストを削減するために、Cicada は Exponential ElGamal を使用します。Exponential ElGamal は引き続き加法準同型性を提供しますが、より小さい係数 (N^2 ではなく N) で動作します。

ElGamal を使用する場合の欠点の 1 つは、カウントを復号する最後のステップで個別のログに対するブルートフォース攻撃が必要になることです (これはオフチェーンで実行され、オンチェーンで効果的に検証されることに注意してください)。したがって、予想される最終投票数がかなり小さい場合 (たとえば 2^32、つまり約 430 万票未満) の場合にのみ機能します。元の Paillier ベースのスキームでは、カウントはそのサイズに関係なく効率的に復号化できます。

RSA モジュラス N の選択にはトレードオフも関係します。私たちの実装では、ガス効率を高めるために 1024 ビットの係数を使用しています。これは、これまで公的にファクタリングされた最大の RSA モジュラス (829 ビット) をはるかに上回っていますが、RSA 暗号化または署名に一般的に推奨されるサイズの 2048 ビットを下回っています。ただし、私たちのアプリケーションは長期的なセキュリティを必要としません。選挙が終了すれば、将来 N を考慮してもリスクはありません。タイムロックの期限が切れた後に集計と投票が公開されると仮定すると、比較的小さな係数を使用するのが合理的です。 (これは、分解アルゴリズムが改善された場合には、将来簡単に更新することもできます。)

匿名性と投票資格

上で述べたように、Cicada は実行カウントのプライバシーを提供します。これは、投票中に投票数を非公開に保つ、タイムロックされたパズルのプロパティです。ただし、個々の投票用紙はタイムロック パズルでもあり、同じ公開パラメータの下で暗号化されます。これは、カウントを (必要な計算を実行することで) 復号化できるのと同じように、各投票も復号化できることを意味します。言い換えれば、Cicada は投票中のみ投票用紙のプライバシーを保証します。好奇心旺盛な観察者が特定の投票者の投票用紙を解読したい場合は、そうすることができます。個々の投票用紙の解読は、最終集計の解読と同じくらいコストがかかるため、単純に言えば、n 人の投票用紙を完全に解読するには O(n) 回の作業が必要です。ただし、これらの投票はすべて並行して復号化でき、(十分なマシンがあると仮定して)、最終的な集計を復号化するのにかかる実時間と同じ時間がかかります。

投票によっては、これが望ましくない場合もあります。一時的に投票集計のプライバシーを実行することに満足していますが、投票のプライバシーを無期限に維持したい場合もあります。これを達成するには、Cicada を、ゼロ知識グループのメンバーシップ証明でインスタンス化された匿名有権者資格プロトコルと組み合わせます。そうすれば、たとえ投票用紙の機密が解除されたとしても、明らかになるのは誰かがそのように投票したということだけであり、それは集計結果からすでにわかっています。

私たちのリポジトリには、投票者の匿名化にセマフォを使用するサンプル コントラクトが含まれています。ただし、Cicada 契約自体は、有権者の資格がどのように決定または強制されるかについて何ら仮定を行っていないことに注意してください。特に、Semaphore を Semacaulk または ZK Proof of State などに置き換えることができます (こことここで提案されているように)。

統計当局

Cicada を設計する際の私たちの最優先事項の 1 つは、統計機関の必要性を回避することでした。多くの民間投票構造では、投票を受け取って集計するために、半信頼された統計機関 (または、安全な複数政党間計算によって調整された委任委員会) が必要です。ブロックチェーンのコンテキストでは、これは、これらのスキームはスマート コントラクトだけでは実行できず、人間の介入と信頼が必要であることを意味します。

ほとんどの構造では、集計当局は整合性については信頼されていません (投票数を操作できない) が、有効性については信頼されています。オフラインの場合、最終結果を計算できず、投票が無期限に遅れます。一部の組織では、プライバシーを維持することも信頼されています。つまり、各個人がどのように投票するかを知っていますが、この情報を明らかにせずに投票結果を公開することが期待されています。

現実世界の多くのシナリオでは、統計的権威は合理的な (そして必要な) 仮定ですが、信頼を最小限に抑えて検閲への耐性を確保することが目標であるブロックチェーン環境では理想的ではありません。

Cicada は、オンチェーン投票プライバシーの分野における多くの方向性の 1 つを探求しており、他のグループによって行われている研究の多くを補完します。前述したように、Cicada は、セマフォ、ZK のストレージ証明、レート制限無効化機能などの匿名グループ メンバーシップ テクノロジと密接に関連しています。 Cicada は、有権者のガス負担を軽減するために、Nouns Vortex チームが提案した楽観的プルーフ チェッカーを統合することもできます。

さまざまな投票スキーム (トークン重み付け投票、二次投票など) をサポートするように Cicada を適応させる機会もあります。より複雑なスキームはイーサリアム メインネットにとって計算コストが高すぎる可能性がありますが、L2 では実用的である可能性があります。これを念頭に置いて、Cicada を次にどこに連れて行くかについて、皆様の貢献、フォーク、提案を歓迎します。

*謝辞: Cicada は Joseph Bonneau と共同開発されました。投票プライバシーの歴史的背景に関する背景情報を提供してくれた Andrew Hall に感謝します。この記事に対するフィードバックをくださった Robert Hackett にも感謝します。編集してくれた Stephanie Zinn に感謝します。 *