ZK-SNARKs：更新可能なブロックチェーンの設定

導入以来、ゼロ知識証明（ZKP）は、プライバシーと整合性のバランスを必要とする多数の設定の中で、検証可能な外部委託計算から匿名のクレデンシャルに至る潜在的アプリケーションをサポートするために使用されてきました。ZKPを使用すると、一方の当事者は、特定の声明または主張が真実であることを、内容を明らかにすることなく他方に証明できます。さまざまなオンチェーンのユースケースでのZKPの適用は、プライバシー、相互運用性、およびスケーラビリティの問題の解決に貢献します。

本稿では、さまざまなZKPタイプと、その具体的なユースケースを取り上げます。また、ZK-SNARKとそのアプリケーションに関する既知の問題について解説し、ブロックチェーンプロトコルに相当する条件下で安全性を持つブロックチェーンメカニズムを提案します。本稿は、Thomas Kerber、Aggelos Kiayias、Markulf Kohlweissによる研究論文「Mining for Privacy: How to Bootstrap a Snarky Blockchain（プライバシーのためのマイニング：Snarkyブロックチェーンをブートストラップする方法）」に基づいています。

さまざまなZKPタイプ

ブロックチェーンの設定に共通して、クライアントはネットワークに公開されたすべてのトランザクションをダウンロードして検証します。これは、ゼロ知識プロトコルを実際にデプロイするためには、証明のサイズが小さいこと、そして、検証時間が素早いことが重要になることを意味しています。選択肢となる実用的なスキームはいくつかありますが、パフォーマンスと暗号化の前提条件には膨大なトレードオフがあります。

• NIZK（Non-Interactive Zero-Knowledge arguments：非対話型ゼロ知識証明）：最も一般的な概念です。NIZKは簡潔（succinct）ではない（すなわち証明サイズが小さくない）場合がありますが、利点として、標準的な暗号化の前提に依存し、多くの場合、強力なセキュリティ保証を満たします。
• SNARG（Succinct Non-interactive zero-knowledge ARGuments：簡潔な非対話型ゼロ知識証明）：より強力な暗号化の前提を犠牲にして簡潔さを実現し、多くの場合、セキュリティ保証は弱まります。
• SNARKあるいはZK-SNARK（Zero-Knowledge Succinct Non-interactive ARuments of Knowledge：ゼロ知識の簡潔な非対話型知識証明）：知識の証明とゼロ知識の証明でもあるSNARGです。ルイス・キャロルのナンセンス詩「スナーク狩り」のおかげで、名前も知られています。
• STARK（Succinct Transparent ARguments of Knowledge：簡潔な透明性のある知識証明）：ここで言う透明性とは信用されたハッシュ関数のみを必要とするセットアップを指します。これは有益ですが、パフォーマンスのオーバーヘッドが生じる可能性があります。

現在、検証者（verifier）の観点から最も魅力的な証明システムは、（前処理された）簡潔で非対話的な知識の証明、すなわち ZK-SNARKです。これは、任意の大きな関係であっても証明サイズは小さく一定で、一定時間の検証コストを持ちます。ZK-SNARKは、プライバシー、相互運用性、スケーラビリティのアプリケーションを持つ、ブロックチェーンと分散型台帳の「アーミーナイフ」として実証されています。

ユースケース

ZK-SNARKのユースケースは極めて多彩です。SNARKはシステムのパフォーマンスおよび簡潔さを高めるために使用されることもあります。ZK-SNARKをプライバシー向上のために採用する場合もあります。場合によっては、1つの役割で両方の側面を持つ、混合ケースもあります。

ブロックチェーンの設定では、パフォーマンスと簡潔さについて考慮した場合、ZK-SNARKは以下のようなユースケースで大きく貢献することができます。

• ライトクライアント：パラメーターの効率およびアプリケーションの構造全体を強化します。効率的な証明システム（ゼロ知識を必要としない）は、ライトクライアントのブートストラップで重要な役割を果たします。再帰的証明システムもこのユースケースに適したものとして機能し、無制限の再帰のセキュリティと、再帰的証明での外部関数（ハッシュ関数など）の使用を保証します。
• スマートコントラクト：パブリックスマートコントラクトの実行による台帳の混雑の可能性を緩和します。オンチェーンコードをSNARKにコンパイルすると、一定または対数の検証時間で、より複雑なバリデーターが可能になります。
• プルーフオブユースフルワーク（PoUW）：SNARKは、マイナーが実行する「有用な計算」を検証するカギとなりえます。そうでなければ、オンチェーンで検証するのに費用がかさむことになります。

プライバシーの観点から、多くのアプリケーションが安全な決済ソリューションの展開、オプションの交換、ID管理、投票、オークション、検証可能な統計（ブロックチェーンオラクルの一種）、またはインセンティブ付きの匿名通信のためにゼロ知識証明を採用しています。ユースケースには以下が含まれる可能性があります。

• プライベートスマートコントラクト：SNARKは、現在のプライベートスマートコントラクトの設計に不可欠です。重要なのは、ユーザーがデプロイするスマートコントラクトをサポートするための普遍性と、コンパイルの容易さの2つです。スマートコントラクトの表現力を排除して、問題の領域を縮小できます。たとえば、制限のないループと再帰を許可しないことで、再帰的なSNARK構成が不要になります。基本的に、高レベルのコントラクト言語のサブセットの一部は、SNARK回路にコンパイルできます。
• プライベート決済：資産は、希少性のモデリングを含む特定の形式のアイデンティティの主張と見なすことができます。プライベート決済の提案は、マルチ資産とNFTをサポートし、これらのトークンをスマートコントラクトに結びつけることもできます。
• ID管理：検証可能なクレデンシャルという面においては、発行者は、暗号化オブジェクト（クレデンシャル）を生成することにより、対象者に関して主張できます。対象者は後に検証者として機能する他のユーザーにクレデンシャルを提示します。検証者は、クレデンシャルを提示する対象者について発行者が主張したことを検証することができます。
• 投票とトレジャリー：ZK証明は、トレジャリー投票で使用することができます。たとえば、暗号資産用トレジャリーシステムのプロトコルは、投票者の投票用紙は暗号化され、その後準同型計算を使用して集計するという、プライバシーを保護した投票スキームを提供します。トレジャリーにおけるZK証明は、プロトコルのさまざまな段階で暗号化されたメッセージの正確性を証明する（例：暗号化された投票者の投票用紙に正しく構成された投票用紙が含まれていること）ために使用される、DLPに基づく非対話型Sigmaプロトコルです。

混合タイプのユースケースには以下が含まれます。

• ブロックチェーンオラクル：SNARKは、複数のソースからデータを集約する際の検証コストを削減できます。また、すべてのデータポイントではなく、集約された値と証明のみを含めることで、送信されるオンチェーンデータのサイズを削減できます。これら2つの特性を達成するために、関係者は、多数のデータポイントとそれぞれの平均、中央値、分散に関する署名の知識を簡潔に証明できる必要があります。
• サイドチェーン：チェーンペギング構成の中のチェーンは、他のチェーンに対するライトクライアントとして機能し、他のチェーンのクロスチェーントランザクションを検証できます。その際、チェーン全体を検証する必要はありません。違いは、このペギングは長期にわたって維持されることが多いため、証明を定期的に「更新可能な」方法で提供できることです。詳細はProof of stake Sidechains（プルーフオブステークサイドチェーン）をご覧ください。

既知の問題

非対話型ゼロ証明には、共有されたランダム性、または共通の参照文字列が必要です。多くの簡潔なシステムでは、より強力なプロパティが必要です。

共有ランダム値が必要なだけでなく、特定の構造に準拠する必要があります。構造化参照文字列（SRS）は通常、関連するグループ要素で構成されます。 すなわち、すべてのi∈𝕫_nにとってg^x^^i^^ です。

このような参照文字列を公開性のランダム性からサンプリングする明白な方法では、使用されている指数が暴露されます。 そして、これらの値を知っていると、証明システム自体の健全性が損なわれます。さらに悪いことに、これらのシステムのセキュリティは通常、（とりわけ）指数知識の前提に依存しています。そのような方法で関連する群要素を作成するには、基礎となる指数を知っている必要があり、それゆえ、どのSRSサンプラーも、使用される指数を「知って」いて、それらを消去するために信頼される必要があり、事実上、基盤となるシステムの単一障害点になります。

安全なマルチパーティ計算（MPC）は、このようなセットアッププロセスに置かれた信頼を低下させるために使用でき、実際にされてきました。ただし、MPCプロトコルによるSRS生成のセキュアな計算と検証のために参加者を選択することは、中央集権化の要素を残します。MPCの使用は、SNARKを必要とする分散型システムのセットアップにおいて、依然として物議を醸す要素です。

安全なSRS生成でプライバシー問題を解消

更新可能な構造化参照文字列（uSRS）は、ブロック生成者が初期セットアップ期間中に変化するuSRSで更新を実行することを必須とすることによって、分散型台帳を使用して安全に初期化できます。最終uSRSでの同意を待った後、安全に使用することができます。

これの証明は、ナカモト式台帳の基本的な操作方法に依存しています。ある条件を満たすことができれば、さまざまなユーザーがブロックのチェーンを拡張できます。この条件は、攻撃者が実行できる拡張の数が制限されることを保証するタイプの硬度に関連付けられています。このような構造を考えると、1つのuSRSの更新は時間𝛿₁より前に各ブロックに関連付けられます。この時間は、台帳のセキュリティプロパティにより、この時点で各競合チェーンでブロックの少なくとも1つが正直であることを保証するように選択されます。

これは、マイナーがuSRS更新をエンコードするためにブロックに埋め込んだ情報から派生した、台帳機能の追加的なリーダーシップ状態から構築できます。これは、他の用途にも使用できる程度の汎用性があります。基本的な考え方は、リーダーシップ状態でuSRSの更新を実行する台帳が、そうでない台帳と同等であることを示すことですが、安全なuSRSが付随されています。𝛿₁時間後、共通プレフィックスによりすべてのパーティが参照文字列に同意したことが保証されるまで、ユーザーはさらに𝛿₂の期間待機します。

提案された台帳の抽象化

更新可能な構造化参照文字列機能の構築は、ナカモト式コンセンサスアルゴリズムのGarayらによるビットコインのバックボーン分析で定義されたcommon prefix、chain quality、chain growthのプロパティに依存しています。

• common prefix：2つのパーティの現在のチェーン𝛱₁と𝛱₂を指定し、最初のブロックからkブロックを削除すると、2番目のプレフィックス𝛱₁^⌊k ≺𝛱₂になります。
• existential chain quality：当事者の現在のチェーン𝛱では、このチェーン内の連続するlブロックには正直な当事者によって作成されたブロックが少なくとも1つ含まれます。
• chain growth：当事者のチェーンの長さがcで、s時間スロットの後、長さは少なくともc+𝛾になります。

分散型uSRSの構築

論文「Mining for Privacy（プライバシーのためのマイニング）」で紹介する構築案はシンプルです。各チェーンは特定のuSRSに関連付けられ、マイナーがチェーンを新調させる場合は追加的なuSRS更新を実行します。チェーンのジェネシスにおいては、既知のランダム性が使用されます（あるいはランダム性は使用されません）。この設計の背後にある原則は単純です。uSRSの更新可能性により、単一の更新が正直に実行された場合（真のランダム性を使用し、さらに更新の実行後にこのランダム性を消去した場合）、更新後のuSRSを安全に使用できることが保証されます。この保証は、Existential chain qualityプロパティに依存しています。 lブロックが生成されると、そのうちの少なくとも1つが正直なマイナーによって作成される必要があるため、lブロック後、チェーンのuSRSは安全になります。

ただし、特定のチェーンの参照文字列が安全であることを知るだけでは十分ではありません。ほとんどの実用的なアプリケーションでは、すべてのユーザーが参照文字列に同意する必要があります。これはcommon prefixプロパティによって提供されます。このプロパティは、l+k ブロックの長さのチェーンについて、他のすべてのユーザーがこのチェーンによって生成されたものと同じ参照文字列を持つことを保証します。 これは、ユーザーがlブロック後に更新を停止した場合です。

最後に、chain growthにより、関心のあるイベントは、誰もが参照文字列に同意した場合、最終的に発生することが保証されます。これにより、ユーザーが最終的に長さl+kのチェーンを持つことが保証されます。具体的には、s単位時間ごとにブロックが生成されるため、イベントは遅くとも時刻⌈(l+k)/s⌉で発生します。

これは抽象的にはすべてうまくいきますが、実用性の問題が残ります。このような抽象的な分析では、更新はほとんどまたはまったくコストをかけずに作成でき、標準のマイニング手順に影響を与えないと仮定しています。ただし、これはプルーフオブワークのマイニングには当てはまりません。

1. 更新は比較的コストがかかり、対象のuSRSのサイズにもよりますが、計算に5～10分かかります。
2. 参照文字列のセキュリティを追加せずに更新をより高速に実行して、更新をごまかすことができます。

これらの要因が組み合わさると、マイナーがブロックのマイニングを開始する「前」に更新を実行する必要があるプルーフオブワークの設定で、特に課題が生じます。これにより、不正行為を行っているマイナーがマイニングに取り掛かかるなか、不正行為を行っていないマイナーは出遅れてしまいます。その結果、マイニングの難易度（ブロック間の意図された時間に対応）は低すぎないようにしなければならなくなります。低ければ低いほど、不正行為を行うマイナーのメリットが大きくなるためです。一方で、難易度が高いと、コンセンサスに達する時間は自然と長くなります。図1はこのトレードオフを示しています。

難易度が適切に調整されている場合、シミュレーション分析にはこの影響がセキュリティ全体にダメージを与えないことが示されます。許容できる失敗の確立（є）と防御したい攻撃者のマイニング力の割合（а）に応じて、uSRSは、図1に示すように、数時間以内、またはより悲観的なシナリオでは数か月以内にこの方法で安全に生成できます。

図1：ターゲットブロック時間の関数として、少なくとも1回の正直な更新が保証されるまでに必要な時間

出典：研究論文「Mining for Privacy: How to Bootstrap a Snarky Blockchain」

合理的行動を考えても、類似した問題が生じます。利益のみを求めるマイナーも、悪意からではなく、単純にブロックをより早く生成できるという理由から更新をごまかします。これは、良い行動に追加的報酬を与えることで回避できます。マイナーのサンプルに事後に更新のランダム性を提供し、それが適切な方法で（たとえばハッシュ関数を使用するなど）サンプリングされたことを示すよう求めることができます。これができれば、追加報酬を受け取ることができ、ごまかさないことによって生じた何らかの損失も相殺できます。

まとめると、ZK-SNARKの適用性は、プライバシー、相互運用性、およびスケーラビリティの問題を解決するさまざまなオンチェーンのユースケースに大きなメリットをもたらします。多くのZK-SNARKに必要とされる信頼できるセットアップは、分散型台帳の分散性と相容れないように見えますが、更新可能な参照文字列によってSNARKを完全に分散型の方法で実行できます。原理的には、Haloなどの透明性のあるSNARKも使用可能ですが、上記の手法により、更新可能な参照文字列に依存するPlonkなどもオンラインアプリケーションで安全に使用することができます（状況によってはこちらの方が効率が良い可能性があります）。SNARKのセットアップが不透明すぎて信頼できないなどということはもはやありません。