Zk-SNARKは、ブロックチェーンと分散型台帳のための「スイスアーミーナイフ」であることが証明されており、プライバシー、相互運用性、スケーラビリティの分野で応用されています。
IOGがブログが、さまざまな種類のZKPとその具体的なユースケースを記事で伝えています。
以下はIOGブログに掲載された記事「Zk-SNARKs: updatable setups on the blockchain」を翻訳したものです。
Zk-SNARKs：ブロックチェーン上の更新可能なセットアップ
by Thomas Kerber 2022年9月1日 12分 読了
Zk-SNARKs：ブロックチェーン上の更新可能なセットアップ
ゼロ知識証明（ZKP）は、その登場以来、プライバシーと完全性のバランスを必要とする多くの設定の中で、検証可能な外部委託計算から匿名認証に至る潜在的なアプリケーションをサポートするために使用されています。ZKPは、ある当事者が他の当事者に対して、ある文や主張が真実であることを、その文の内容を明らかにすることなく証明することを可能にする。ZKPを様々なオンチェーンユースケースに適用することで、プライバシー、相互運用性、スケーラビリティの問題解決に貢献することができます。
この記事では、さまざまな種類のZKPとその具体的なユースケースを紹介します。また、zk-SNARKsとその適用におけるいくつかの既知の問題について説明し、ブロックチェーンプロトコルと同等の条件下で安全な特性を持つブロックチェーン機構を提案します。この記事は、Thomas Kerber、Aggelos Kiayias、Markulf Kohlweissによって書かれた研究論文「Mining for Privacy：How to Bootstrap a Snarky Blockchain」に基づいています。
さまざまなタイプのZKP
ブロックチェーンでは、ネットワークに公開されたすべての取引をクライアントがダウンロードして検証することが一般的です。つまり、ゼロ知識プロトコルの実用的な展開には、小さな証明サイズと高速な検証時間が重要である。実用的なスキームがいくつかあり、性能と暗号の仮定におけるトレードオフの空間が広大であることから、そこから選択することができます。
- 非対話的ゼロ知識引数（NIZK）：これは最も一般的な概念です。NIZKの利点は、標準的な暗号の仮定に依存し、多くの場合、強力なセキュリティ保証を満たすことができることです。
- 簡潔な非対話的ゼロ知識引数（SNARGs）：暗号学的仮定が強く、安全性保証が弱い場合が多いが、簡潔さを達成することができる。
- 簡潔な非対話的ゼロ知識論証(SNARKs or sometimes zk-SNARKs)：知識とゼロ知識の証明でもあるSNARGsである。ルイス・キャロルのナンセンス詩「The Hunting of the Snark」にちなんで、この名前も有名。
- 簡潔で透明な知識証明（STARKs）：ここでいう透明とは、信頼できるハッシュ関数を必要とするだけのセットアップのことである。これは有益であるが、パフォーマンスのオーバーヘッドを伴うことがある。
現在、検証者の観点から最も魅力的な証明システムは、（前処理）簡潔な非対話的知識論証、略してzk-SNARKであり、小さな定数証明サイズと任意に大きな関係に対しても定数時間の検証コストを持つものである。k-SNARKは、ブロックチェーンや分散台帳の「スイスアーミーナイフ」として、プライバシー、相互運用性、スケーラビリティの分野で応用されていることが実証されています。
使用例
Zk-SNARKsの使用例は非常に多様です。SNARKは、システムのパフォーマンスと簡潔性の特性を改善するために採用されることもあります。その他の使用例では、プライバシーを向上させるためにzk-SNARKが使用されます。両方の側面が役割を果たす、混合型のケースもあります。
ブロックチェーンの設定では、パフォーマンスと簡潔性を考慮すると、zk-SNARKSは以下のようなユースケースに大きく貢献することができます。
- ライトクライアント：パラメータの効率とアプリケーションの全体的な構造を向上させる。効率的な証明システム（ゼロ知識要件なし）は、ライトクライアントのブートストラップにおいて重要な役割を果たす。また、再帰的証明システムはこのユースケースと相性が良く、無限の再帰性に対するセキュリティや、再帰的証明における外部関数（例えばハッシュ関数）の利用を保証するものです。
- スマートコントラクト：公開されたスマートコントラクトの実行により、元帳が混雑する可能性があるため、その負荷を軽減する。オンチェーンコードをSNARKにコンパイルし、検証時間を一定または対数にすることで、より複雑な検証を可能にすることができます。
- Proof of useful work (PoUW)：SNARKは、オンチェーンでの検証にはコストがかかる採掘者による「有用な計算」を検証する鍵となりえます。
プライバシーの観点から、多くのアプリケーションは、安全な支払いソリューションの展開、オプションの交換、アイデンティティの管理、投票、オークション、検証可能な統計（ブロックチェーンオラクルの一種）、またはインセンティブ付きの匿名通信のためにゼロ知識証明を採用しています。ユースケースとしては、以下のようなものが考えられます。
- プライベートスマートコントラクト：SNARKは、現在のプライベートスマートコントラクトの設計に不可欠です。ユーザーが展開するスマートコントラクトをサポートするための普遍性と、コンパイルの容易さの2つが最重要です。スマートコントラクトの表現力は、問題空間を縮小するために排除することができます。例えば、非限定ループや再帰を禁止することで、再帰的なSNARKの合成が不要になります。基本的に、高レベルの契約言語のあるサブセットは、SNARK回路にコンパイルすることができます。
- プライベートペイメント：資産は、希少性のモデル化を含む特定の形のアイデンティティ主張と見なすことができる。プライベートペイメントの提案は、マルチアセットと非ファンジブルトークンをサポートし、これらのトークンをスマートコントラクトに接続することも可能です。
- アイデンティティ管理：検証可能なクレデンシャルのコンテキストでは、発行者は暗号オブジェクト（クレデンシャル）を生成することで、被験者に関する主張を行うことができます。被験者はその後、検証者である他のユーザーに自分のクレデンシャルを提示する。検証者は、発行者がクレデンシャルを提示した対象者について主張を行ったことを検証することができる。
- 投票と国庫：ZK証明は国庫投票に使用することができる。例えば、暗号通貨プロトコルのための国庫システム（treasury system for cryptocurrencies）は、投票者の投票が暗号化され、後に同型計算を使用して集計される、プライバシー保護された投票方式を提供する。国庫のZK証明は、プロトコルの様々な段階で暗号化されたメッセージの正しさを証明するために使用されるDLPベースの非対話型シグマプロトコルです（例えば、暗号化された投票者の投票用紙が正しく構成された投票用紙を含んでいること）。
混在するユースケースは以下の通りです。
- ブロックチェーンオラクル：SNARKは、複数のソースからデータを集約する際の検証コストを削減でき、また、すべてのデータポイントではなく、集約された値と証明のみを含めることで、投稿されるオンチェーンデータのサイズを縮小することができる。この2つの特性を実現するために、当事者は、多数のデータポイントの署名とそれぞれの平均値/中央値/分散値の知識を簡潔に証明できる必要があります。
- サイドチェーン：チェーンペギング構成における一方のチェーンは、他方のチェーンに対してライトクライアントとして機能し、そのチェーン全体を検証することなく、他方のチェーン上のクロスチェーン取引を検証することができます。違いは、このペギングがしばしば長期的に維持されるため、証明を定期的に、「更新可能」な方法で提供できることである。詳しくはProof of stake Sidechainsを参照。
既知の問題
非対話的ゼロ知識は、共有されたランダム性、または共通の参照文字列を必要とします。多くの簡潔なシステムでは、より強力な性質が必要です。
共有された乱数値が必要なだけでなく、特定の構造に従わなければなりません。構造化参照文字列（SRS）は通常、関連するグループ要素、すなわち、すべてのi∈l56bnに対してgxiで構成されています。
このような参照文字列を公開ランダム性からサンプリングする明らかな方法は、使用される指数を明らかにするものであり、これらの値を知ることは証明システム自体の健全性を破壊する。さらに悪いことに、これらのシステムのセキュリティは、通常、指数の仮定に依存しており、そのような方法で関連するグループ要素を作成するには、基礎となる指数を知る必要があることを述べています。
安全なマルチパーティ計算（MPC）は、このようなセットアッププロセスの信頼性を低下させるために使用することができ、これまでも使用されてきました。しかし、MPCプロトコルによる安全な計算とSRSの生成の検証のための参加者の選択は、中央集権の要素を保持しています。MPCの使用は、SNARKを必要とする分散型システムのセットアップにおいて、依然として論争の的となる要素である。
安全なSRS生成によるプライバシー問題の解決
更新可能な構造化参照列（uSRS）は、最初のセットアップ期間中にブロック作成者に進化するuSRSの更新を要求することで、分散台帳を使用して安全に初期化することができます。最終的なuSRSの合意を待った後、それを安全に使用することができます。
この証明は、中本式台帳の基本的な操作方法に依存している。異なるユーザーがある条件を満たすことができれば、ブロックのチェーンを拡張することができ、この条件は、攻撃者が実行できる拡張の数が制限されることを保証する硬さの種類に関連している。このような構造が与えられた場合、時間ǿ1の前に各ブロックにuSRSの更新を関連付ける。この時間は、元帳のセキュリティ特性により、この時点で各競合連鎖において少なくとも1つのブロックが正直であることが保証されるように選択される。
これは、採掘者がuSRSの更新を暗号化するためにブロックに埋め込む情報から得られるリーダーシップの状態を追加した元帳機能から構築することができる。これは、他の用途も可能にするために十分に一般的なものとして残されている。基本的な考え方は、リーダーシップ状態でuSRSの更新を行う台帳は、そうでない台帳と同等であるが、安全なuSRSを伴っていることを示すことである。時間ǖの後、ユーザーは共通の接頭辞によってすべての当事者が参照文字列に同意することが保証されるまで、さらに時間ǖ秒秒秒待つ。
提案する台帳の抽象化
更新可能な構造化参照文字列機能の構築は、GarayらによるBitcoinバックボーン分析で定義された、Nakamotoスタイルの合意アルゴリズムに対する共通プレフィックス、チェーン品質、チェーン成長の特性に依存する。
- Common prefix：2者の現在の鎖ǖ1とᵯ2が与えられ、最初の鎖からkブロックを取り除くと、2番目の鎖の接頭辞となる：ǖ1⌊k ≺ᵯ2.
- Existential chain quality：任意の当事者の現在の鎖ǖについて、この鎖の任意の連続したl個のブロックは、正直な当事者によって作成された少なくとも1つのブロックを含む。
- Chain growth：ある当事者の鎖の長さがcである場合、s時間後に少なくともc+_1FEとなる。
分散型uSRSの構築
Mining for Privacyという論文で詳述されているように、我々が提案する構造はシンプルである。各チェーンは特定のuSRSと関連付けられており、採掘者がチェーンを拡張する際、追加でuSRSの更新を行う。チェーン生成時に、既知のランダム性（またはランダム性なし）を使用することができます。uSRSの更新可能性は、一回の更新が正直に行われた場合（真のランダムネスを使用し、更新後にこのランダムネスを消去する）、結果として得られるuSRSが安全に使用できることを保証するものだからです。l個のブロックが生成されたら、そのうちの少なくとも1個は正直な採掘者によって作成されなければならない。したがって、l個のブロックの後では、チェーンのuSRSは安全です。
しかし、特定のチェーンの参照文字列が安全であることを知るだけでは十分ではない。ほとんどの実用的なアプリケーションでは、すべてのユーザーが参照文字列に同意することが望ましい。これは共通プレフィックスの特性で、l+kブロックの長さのチェーンでは、他のすべてのユーザーがこのチェーンで生成されたものと同じ参照文字列を持つことが保証されています。
最後に、連鎖の成長は、我々が関心を持つ事象、つまり、誰もが参照文字列に合意するときが最終的に起こることを保証している。これは、ユーザーが最終的に長さl+kの連鎖を持つことを保証している。具体的には、s個の時間単位でブロックが生成されるので、遅くとも時間⌈(l+k)/s⌉にイベントが発生することになります。
このような抽象的な分析では、更新はほとんどコストをかけずに作成でき、標準的な採掘手順に影響を与えないことを前提としているため、実用性に疑問が残ります。しかし、プルーフ・オブ・ワークのマイニングでは、これはまったく当てはまりません。
- アップデートは比較的コストがかかり、対象となるuSRSのサイズにもよりますが、計算には5～10分かかります。
- 更新には比較的コストがかかり、対象となるuSRSのサイズにもよりますが、5～10分ほどかかります。更新をより速く行うことでごまかすことは可能ですが、参照文字列のセキュリティは追加されません。
これらの要因が組み合わさると、特にプルーフ・オブ・ワークの設定では、採掘者がブロックの採掘を開始する前に更新を実行する必要があるため、課題が生じます。このため、不正を行っていないマイナーが遅れてしまい、その間に不正を行っているマイナーがすでに採掘を始めてしまうのです! その結果、採掘難易度（ブロック間の予定時間に相当）は低すぎてはならず、低ければ低いほど、不正を行った採掘者が大きな利益を得ることになるからです。一方、採掘難易度が高ければ、当然コンセンサスに達するまでの時間が長くなる。このトレードオフは図1に示されています。
難易度が適切に設定されていれば、シミュレーション分析により、この効果は全体的な安全性を損なわないことが示されています。許容できる失敗の確率（є）と、攻撃者の採掘力のうち保護したい割合（а）に応じて、図1に示すように、uSRSは数時間以内に、あるいはより悲観的なシナリオでは数ヶ月以内に安全に生成することが可能です。
出典：「Mining for Privacy: How to Bootstrap a Snarky Blockchain：スナークス・ブロックチェーンをブートストラップする方法」研究論文
利益のみを追求するマイナーも、悪意からではなく、単にそうすればより早くブロックを生成できるため、更新をごまかそうとします。採掘者のサンプリングは、事後的に更新のためのランダム性を提供し、それが適切な方法（例えば、ハッシュ関数を使用して）でサンプリングされたことを証明するように要求することができます。もしそうすることができれば、彼らは追加報酬を得ることができ、不正行為をしなかったことによる損失を相殺することができます。
要約すると、zk-SNARKsの適用により、プライバシー、相互運用性、およびスケーラビリティの問題を解決するさまざまなオンチェーンユースケースに大きなメリットがもたらされます。多くの zk-SNARKs に必要な信頼された設定は、分散型台帳の分散的性質と相容れないように見えるが、更新可能な参照文字列を持つ SNARKs では完全に分散的な方法で実行することが可能である。原理的にはHaloのような透明なSNARKを使用することも可能ですが、上記の技術により、更新可能な参照文字列に依存するPlonkなどのSNARKをオンチェーンアプリケーションに安全に使用することができます。
