ZK技術の歴史的発展の整理

2024.08.09

共有先

TechFlow厳選深潮セレクト

ZK技術の歴史的発展の整理

ZK技術の発展史に関する線形的歴史年表。

2024.08.09 - 15:35:14

Web3業界の深掘り報道に専念し潮流を洞察

ZK技術の発展史に関する線形的歴史年表。

執筆：Lambda Class

翻訳：白丁、Faust、Nickqiao

英語原文公開日：2024年2月17日

ゼロ知識証明（ZK Proofs）は強力な暗号学的プリミティブであり、一方の当事者（証明者）が他方の当事者（検証者）に対して、ある命題が真であることを、秘密情報を一切開示せずに納得させることが可能になります。近年、ZKは検証可能なプライベート計算、コンピュータプログラムに対する有効性証明、およびブロックチェーン分野において注目を集めており、世界に大きな積極的な影響を与えています。

ZKは新興技術ですが、その基本的なアイデアや概念は1980年代まで遡ることができます。ビットコインやイーサリアムなどのブロックチェーンと統合されたことで、ZK技術の発展は著しく加速しました。 SNARKやSTARKを通じてブロックチェーン上で有効性証明を実現することで、拡張性が大幅に向上したため、ZKはブロックチェーン分野で非常に注目されるようになりました。

Starkware創設者のEli Ben-Sassonが述べたように、近年我々は暗号証明システムにおける「カンブリア爆発」を目にしてきました。各証明システムにはそれぞれ独自の長所と短所があり、設計上さまざまなトレードオフがなされています。 ハードウェアの進歩、より優れたアルゴリズム、新たな議論、周辺ツールの登場により、ZKシステムの性能向上や新システムの誕生が促進されています。多くの証明システムはすでに実用化されており、ZKの限界は今なお拡大し続けています。

こうした状況は、次の問いを深く考えさせます：すべてのアプリケーションに適用できる汎用的なZK証明システムは存在するのでしょうか？私たちの見解では、その可能性は低いと考えられます。 理由は以下の3点です。

アプリケーションの多様性
異なる制約条件（メモリ、検証時間、証明生成時間など）
堅牢性への要求（ある証明システムがハッキングされた場合でも、他のシステムに切り替えるという保険が必要）

これらの理由から、ZK証明システムは多様であるべきです。しかし、証明システムの種類が多くても共通する顕著な特徴があります。それは、ZK証明は高速に検証可能であり、 基盤レイヤー（例えばイーサリアム）の課題に対応するために、新しい証明システムに容易に適応できる検証層を持つことです。

ZK分野では、zk-SNARKが頻繁に言及されます。これは複雑な数学的手法（双線形ペアリングや算術回路など）を用いて効率的なゼロ知識証明を実現する方式の一つです。zk-SNARKの特徴は、証明プロセスが簡潔かつ非対話的であり、証明者と検証者の間で一度の通信で済む点です。さらに、zk-SNARKの証明サイズは非常に小さく、検証効率も高いため、リソースが限られた環境での使用に適しています。

一方、zk-STARKはzk-SNARKのいくつかの限界を克服することを目指した別の形式です。zk-STARKは信頼できるセットアップに依存せず、多項式コミットメントや有限体演算、ハッシュ衝突など、より透明性の高い数学的構造を使用して証明を生成・検証します。zk-STARKはzk-SNARKよりも拡張性が高く、大規模な計算に適しており、証明生成速度も速いですが、証明自体のサイズは通常大きくなります。

つまり、zk-SNARKとzk-STARKはどちらもゼロ知識証明でよく使われる形式ですが、透明性、拡張性、証明サイズといった点で異なります。

全体として見ると、ZK証明システムは通常、PIOP（多項式インタラクティブオラクルプロトコル）とPCS（多項式コミットメントスキーム）の二つの主要部分から構成されます。一般的なPIOPスキームにはPLONKish、GKRなどがあり、PCSスキームにはFRI、KZG、IPAなどが含まれます。例えば、Zcash版Halo2はPlonkish+IPAを採用しており、zk-STARKは実質的にFRIに基づく特殊なzk-SNARKと見なすこともできます。

より詳しく言えば、異なるタイプの証明システムは異なる多項式コミットメントスキーム（PCS）、算術化スキーム、インタラクティブオラクル証明（IOP）、または確率的検査可能証明（PCP）を使用します。

さらに言えば、異なるZK証明システムは以下の指標においてしばしば異なります：

暗号学的仮定：衝突耐性ハッシュ関数、楕円曲線上の離散対数問題、知識の指数
透明セットアップ vs 信頼できるセットアップ
証明生成時間：線形 vs 超線形
証明検証時間：定数時間、対数時間、準線形、線形
証明サイズの大きさ
再帰の容易さ
算術化スキーム
単一変数 vs 多変数多項式

以下では、ZK技術の起源に触れ、その基本構成要素を探り、異なるZK証明システムの台頭と衰退の過程を概観します。また、本稿は証明システム自体の詳細分析ではなく、この分野に深い影響を与えた人物に焦点を当てます。なぜなら、あらゆる業界の発展は先駆者の偉大なアイデアとその実践によってのみ達成され得るからです。

zk-SNARKの歴史的発展

起源：1980～90年代

前述のように、ゼロ知識証明は新しい概念ではありません。その定義、基礎、重要な定理、さらに関連する重要なプロトコルは、1980年代半ばにはすでに登場していました。最初に登場したのはGoldwasser、Micali（Algorand創設者）、Rackoffの論文『The Knowledge Complexity of Interactive Proof Systems』です。

今日、ZK-SNARK技術構築に用いられるキーアイデアやプロトコルの多くは1990年代に生まれました。 例えばSumcheckプロトコルは、多元多項式の評価総和に関する主張を、楕円曲線上のランダム選択された点での単一評価に還元するもので、ZK技術の重要な基盤となりました。

したがって、ZKの思想の萌芽はビットコインの登場より遥かに前から存在していたのです。 ただし当時は適切なユースケースが乏しく、ZK証明システムに必要な強力な計算能力も提供できませんでした。1990年代のインターネットやハードウェア機器は未発達だったからです。

GKRプロトコル（2007年）

GKR（Goldwasser-Kalai-Rothblum）は対話型プロトコルであり、証明者の実行時間は回路内の論理ゲート数に線形に比例し、検証者の時間は回路サイズに対して準線形です。GKRプロトコルでは、証明者と検証者が有限体上の二入力算術回路の結果について合意します。回路の深さはdで、第d層が入力層、第0層が出力層です。プロトコルは回路出力に関する主張から始まり、再帰的に上位層の主張に還元されます。最終的に出力に関する主張を回路入力パラメータに関する主張に変換でき、これは容易に検証可能です。GKRプロトコルは前述のSumcheckプロトコルを高度に簡略化したものと言えます。

KZG多項式コミットメントスキーム（2010年）

2010年、ZK分野の専門家3人――ドイツの研究機関MPI-SWS所属のKate、カナダの暗号企業Certicom ResearchのZaverucha、カナダウォータールー大学のGoldberg――が共同で論文『Constant-Size Commitments to Polynomials and Their Applications』を発表しました。この論文では、双線形対を用いる群上の多項式コミットメントスキーム「KZG」を提案しました。

このコミットメントは単一の群要素からなり、コミットメント作成者は任意の正しい多項式評価を効率的に開示できます。バッチ処理技術を活用すれば、複数の多項式評価を同時に開示可能です。KZGコミットメントは有名なZK証明システムの基本構成要素の一つとなり（例：イーサリアムPSEチームが使用するHalo2）、イーサリアムのEIP-4844においても中心的な役割を果たしています。バッチ処理の概念を直感的に理解したい場合は、「Mina-Ethereum bridge」に関する記事を参照してください。

参考資料：https://blog.lambdaclass.com/mina-to-ethereum-bridge/

楕円曲線ベースの実用的ZK-SNARKシステム（2013年）

ZK-SNARKの最初の実用的構造は2013年に登場し、証明鍵と検証鍵を生成するための前処理ステップを必要としました。また、これはプログラムや回路に固有のもので、汎用性はありませんでした。これらの鍵のサイズは非常に大きく、秘密パラメータ自体に依存しました。もし秘匿性が破られれば、攻撃者は証明を偽造できるようになります。このような実用的ZK-SNARKシステムでは、コードを証明可能な形式に変換するために、コードを数学的形式の多項式制約の集合にコンパイルする必要があります。

当初、このプロセスは手動で行われる必要があり、時間がかかりやすくエラーも起こりやすかった。その後の技術革新は主に以下の核心課題の解決を目指しました：

より効率的な証明の提供
前処理回数の削減
回路固有ではなく汎用的なセットアップの実現
信頼できるセットアップの回避
多項式制約を手動で書く代わりに、高水準言語で回路を記述する方法の開発

Pinocchioプロトコル（2013年）

Pinocchioプロトコルは最初に実用可能なzk-SNARKシステムであり、二次算術プログラム（QAP）に基づいており、初期の証明サイズは288バイトでした。PinocchioのツールチェーンはC言語を算術回路にコンパイルするコンパイラを提供し、さらにそれをQAPに変換できます。Pinocchioプロトコルでは検証者が鍵を生成する必要がありますが、これは汎用的ではなく回路固有のものです。この証明システムの証明生成および鍵設定の漸近的時間複雑度は計算規模に線形に比例し、検証時間は公開入出力のサイズに線形に比例します。