a16z: Cicada がオンチェーン投票にタイムロック パズルと ZK 証明を活用する方法
原作者：Michael Zhu
オリジナルコンピレーション: Lynn、MarsBit
原作者：オリジナルコンピレーション: Lynn、MarsBit有意義に機能するすべての投票システムは、完全性と透明性に依存しています。一見すると、ブロックチェーンはこれらのシステムを構築するための理想的なプラットフォームになります。実際、多くの分散型組織がブロックチェーンを採用しています。許可なく投票する多くの場合、多額の富を振り回したり、主要なプロトコルパラメータを微調整したりしながら、集団的な意図を表現します。しかし、オンチェーン投票には欠点もあります。
プライバシーは依然として解明されておらず、未解明のままです
、Web3 投票システムには適していません - 現在使用されているほとんどのオンチェーン投票プロトコルでは、投票用紙と投票結果は完全に公開されます。プライバシーがなければ、投票結果は簡単に操作され、投票者のインセンティブが調整されず、非民主的な結果につながる可能性があります。だからこそ、私たちは Cicada をリリースするのです。これは、タイムロック パズルとゼロ知識証明を活用してプライベートなオンチェーン投票を可能にする、新しいオープンソースの Solidity ライブラリです。既存のシステムと比較して、Cicada は新しいプライバシー特性を備え、信頼の前提を最小限に抑え、イーサリアムのメインネットで使用できるほど効率的です。この投稿では、投票のプライバシーの状態を調査し、Cicada がどのように機能するかについて概要を説明します (正式な証明は近日中に行われます)。また、開発者には以下を確認することをお勧めします。
GitHubリポジトリ
- Cicada はさまざまな投票スキームや機能をサポートするためにさまざまな方法で適応および拡張できます。私たちはコミュニティと協力してこれらの可能性を探求したいと考えています。
私設投票に関する簡単な調査どのような投票システム (オンチェーンかどうかにかかわらず) においても、考慮すべきさまざまなレベルのプライバシーが存在します。個人の投票用紙、候補者数、および有権者の身元情報の開示はすべて、さまざまな形で有権者の動機に影響を与えます。どのプライバシー プロパティが必要かは、投票の状況によって異なります。暗号学や社会科学の文献で頻繁に登場するいくつかの例は次のとおりです。投票のプライバシー: 秘密投票、別名「」
オーストラリアの投票
」は、個々の有権者の好みを保持し、贈収賄と強制を軽減する方法として、現実世界の投票システム用に開発されました（オンチェーン設定では、投票のプライバシーよりも強力なプロパティが必要になる場合があります。以下の「受領不可」を参照） ")。投票のプライバシーにより、社会的望ましさのバイアスも軽減されます。自分の選択について他人がどう思うかに基づいて投票するというプレッシャーが軽減されます。
投票者の匿名性: 現実世界の多くの投票システムでは、投票は公開されませんが、投票したという事実は多くの場合公開されます。投票者記録を公開すると、他の人が自分の名前で投票したかどうかを確認できるため、これは不正投票を防ぐために重要です。ただし、オンチェーンでは、暗号化プリミティブを使用して匿名性を維持しながら不正投票を防ぐことができます。たとえば、Semaphore を使用すると、知識ゼロで自分がまだ投票していない有効な有権者であることを証明できます。指摘した受領書の不在: 個々の有権者は、第三者にどのように投票したかを証明するために投票用紙の「受領書」を提出します。そうしないと、チケットが販売される可能性があります。密接に関連していますが、より強力な特性は強制耐性です。これは、誰かが有権者に特定の方法で投票を強制することを防ぎます。これらの特性は、スマートコントラクト市場を通じて議決権を流動化できる分散型環境において特に魅力的です。残念ながら、これらは実装するのも困難です。実際、Juels らは次のように述べています。
指摘した
これは、信頼できるハードウェアがないパーミッションレス環境では不可能です。
Cicada は進行中の投票数のプライバシーに重点を置いていますが、(後で説明するように) ゼロ知識グループのメンバーシップ証明と組み合わせることで、有権者の匿名性と投票のプライバシーを実現できます。
Cicada の紹介: 準同型タイムロック問題からの投票集計プライバシーRivest, Shamir, Wagner, 1996 進行中の投票集計のプライバシーを確保するために、Cicada は (私たちの知る限りでは) これまでオンチェーンで使用されたことのない暗号化プリミティブを利用しています。
まずはタイムロックパズル（Malavolta Thyagarajan, 2019 ) は、あらかじめ決められた時間が経過した後にのみ明らかにされる秘密をカプセル化した暗号パズルです。具体的には、非並列計算を繰り返し実行することで解読できるパズルです。タイムロック パズルは、統計を実行する際のプライバシーを確保するために投票のコンテキストで役立ちます。ユーザーはタイムロック パズルとして投票を送信できるため、投票プロセス中は秘密に保たれますが、投票後には公開されます。他のほとんどの民間投票構造とは異なり、これにより、統計機関 (紙やデジタル投票用紙を数える選挙職員など)、しきい値暗号化 (メッセージを復号するには複数の信頼できる関係者が協力する必要がある)、またはその他の信頼できる関係者に依存することなく、統計的プライバシーを運用できます。誰でもタイムロック パズルを解いて、投票後に結果が確実に明らかになるようにすることができます。
2 番目は、同型タイムロック パズル (
) には、秘密鍵、復号化パズル、またはバックドアの使用の知識があれば、暗号化された値の一部の計算が可能であるという追加の特性があります。特に、線形準同型タイムロック パズルを使用すると、パズルを組み合わせて、元のパズルの秘密の値の合計をカプセル化する新しいパズルを作成できます。
論文の著者が指摘しているように、線形準同型タイムロック パズルは、プライベート投票に特に適したプリミティブです。投票はパズルとしてエンコードでき、それらを準同型的に組み合わせて、エンコードされた最終的なカウンティング パズルを取得できます。これは、投票ごとに固有のパズルを解くのではなく、最終結果を明らかにするために必要な計算が 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 を設計する際の私たちの最優先事項の 1 つは、統計機関の必要性を回避することでした。多くの民間投票構造では、投票を受け取って集計するために、半信頼された統計機関 (または、安全な複数政党間計算によって調整された委任委員会) が必要です。ブロックチェーンのコンテキストでは、これは、これらのスキームはスマート コントラクトだけでは実行できず、人間の介入と信頼が必要であることを意味します。
ほとんどの構造では、集計当局は整合性については信頼されていません (投票数を操作できない) が、有効性については信頼されています。オフラインの場合、最終結果を計算できず、投票が無期限に遅れます。一部の組織では、プライバシーを維持することも信頼されています。つまり、各個人がどのように投票するかを知っていますが、この情報を明らかにせずに投票結果を公開することが期待されています。
現実世界の多くのシナリオでは、統計的権威は合理的な (そして必要な) 仮定ですが、信頼を最小限に抑えて検閲への耐性を確保することが目標であるブロックチェーン環境では理想的ではありません。
Cicada は、オンチェーン投票プライバシーの分野における多くの方向性の 1 つを探求しており、他のグループによって行われている研究の多くを補完します。前述したように、Cicada は、セマフォ、ZK のストレージ証明、レート制限無効化機能などの匿名グループ メンバーシップ テクノロジと密接に関連しています。 Cicada は、有権者のガス負担を軽減するために、Nouns Vortex チームが提案した楽観的プルーフ チェッカーを統合することもできます。
