ZKテクノロジーの歴史的発展について要約する。

ゼロ知識証明（ZK証明）は、ある当事者（証明者）が、与えられた文が真であり有効であることを、個人情報を明かすことなく他の当事者（検証者）に納得させることができる強力な暗号プリミティブである。近年、ZKは検証可能な私的計算、コンピュータプログラムの正当性の証明、ブロックチェーンの分野で注目を集め、世界に大きなプラスの影響を与えている。

ZKは新興の技術ではあるが、その基本的なアイデアやコンセプトは1980年代にさかのぼる。ZK技術の開発は、ビットコインやイーサなどのブロックチェーンと組み合わされた後に大きく加速しました。ブロックチェーンはSNARKやSTARKを介して有効性の証明に使用できるため、スケーラビリティが大幅に向上し、ZKはブロックチェーン分野で注目の商品となりました。

Starkwareの創設者であるEli Ben-Sassonが言うように、近年、私たちは暗号証明システムの「カンブリア爆発」を目の当たりにしてきました。各証明システムにはそれぞれ独自の長所と短所があり、その設計においてトレードオフが行われてきました。ハードウェアの進歩、より優れたアルゴリズム、新しい論証、周辺ツールの登場により、ZKシステムの性能向上や新しいシステムの創造に拍車がかかっている。多くの証明システムが実用的なアプリケーションに採用され、人々は今もZKの境界を広げ続けている。

このことが、すべてのアプリケーションに対応する普遍的なZK証明システムは存在するのだろうか？

1.アプリケーションの多様性、

2.制約の種類の違い（メモリ、検証時間、証明時間を含む）、

3.制約の種類の違い（メモリ、検証時間、証明時間を含む）、

3.堅牢性の必要性（1つの証明システムがハッキングされても、保険として別の証明システムに切り替えることができる）。

これらの理由から、ZK証明システムは多様であるべきなのです。しかし、たとえ証明システムが多種多様であったとしても、1つの重要な共通点があるはずです。それは、ZK証明は素早く検証でき、依存する基本レイヤー（例えば、イーサ）に関連する困難に対処するために、新しい証明システムに容易に適応できる検証レイヤーを持っていることです。

ZK空間では、zk-SNARKがよく言及されます。zk-SNARKの特徴は、簡潔で非対話的な証明プロセスであり、何度もやりとりすることなく、証明者と検証者の間で必要な通信は1回のみです。さらに、zk-SNARKの証明サイズは非常に短く小さく、検証効率が高いため、リソースが限られた環境での使用に適しています。

また、zk-STARKは、zk-SNARKの制限のいくつかを克服することを目的とした、別の一般的な形式です。と証明の検証を行います。zk-STARKはzk-SNARKよりもスケーラブルで、より大規模な計算と高速な証明生成が可能ですが、証明自体のサイズは一般的に大きくなります。

zk-SNARKとzk-STARKはどちらもゼロ知識証明でよく使われる形式であると主張できますが、透明性、スケーラビリティ、証明サイズの点で異なります。

全体として、ZK証明システムは通常、PIOP（Polynomial Interactive Predictor）とPCS（Polynomial Commitment Scheme）の2つの主要部分から構成されています。一般的なPIOPスキームにはPLONKish、GKRなどがあり、一般的なPCSスキームにはFRI、KZG、IPAなどがあります。例えば、Zcash版Halo2はPlonkish+IPAの実装を使用しています。

さらに詳しく説明すると、証明システムの種類によって、異なる多項式コミットメントスキーム（PCS）、算術化スキーム、対話型予測子証明（IOP）、または確率論的にチェック可能な証明（PCP）が使用されます。"text-align: left;">暗号の仮定：衝突に強いハッシュ関数、楕円曲線上の離散対数問題、指数関数的な知識

以下では、ZK技法の起源に簡単に触れ、その基本的な構成要素を探り、さまざまなZK証明システムの盛衰について概説します。同時に、この記事では証明システムそのものを網羅的に分析するのではなく、むしろこの分野に大きな影響を与えた人々に焦点を当てます。結局のところ、どのような産業の発展も、それを実践した先駆者の偉大なアイデアによってのみ可能になるのです。

zk-SNARKの歴史

起源：1980年代～1990年代

起源：1980年代～1990年代

前述したように、ゼロ知識証明は新しい概念ではなく、その定義、基礎、重要な定理、さらには関連する重要なプロトコルは、早くも1980年代半ばに登場しています。最初に登場したのは、ゴールドワッサー、ミカリ（Algorandの創設者）、ラコフ（Rackoff.創設者）とラッコフの論文The Knowledge Complexity of Interactive Proof Systemsをきっかけに、1980年代に初めて登場した。

また、ZK-SNARKテクニックを構築するために今日私たちが使用している重要なアイデアやプロトコルは、1990年代に発表されました。このプロトコルは、ZK技術の重要な基礎を築きました。

つまり、ZKのアイデアの萌芽は、実際にはビットコインよりもずっと前にあったのです。しかし、当時はZKの適切なユースケースが一般的に不足しており、ZKの証明システムを満たすために必要な強力な演算を提供することができませんでした。結局のところ、1990年代のインターネットとハードウェア・デバイスはあまり発達していなかった。

GKRプロトコル（2007年）

GKR（Goldwasser-Kalai-Rothblum）は対話型プロトコルである。証明者の実行時間は回路内の論理ゲート数に線形に関係し、検証者の所要時間は回路サイズに準線形に関係する。GKRプロトコルでは、深さdの有限領域（層dが入力層、層0が出力層）で2入力の算術回路を実行した結果について、証明者と検証者が合意する必要がある。合意は、回路の出力に関する宣言から始まり、再帰によって前の層に関する宣言に還元される。最後に、出力に関する宣言を回路の入力パラメータに関する宣言に変換することができ、これは簡単に検証できる。GKRプロトコルは、前述のSumcheckプロトコルを高度に簡略化したものと言える。

KZG Polynomial Commitment Scheme (2010)

2010年、ZKの分野の3人の専門家が、ドイツの研究機関のケイト-ケイトと共同研究を行いました。strong>ドイツの研究機関MPI-SWSのKate氏、カナダの暗号会社Certicom ResearchのZaverucha氏、そしてウォータールー大学のGoldberg氏の3人が、共同論文「Constant-Size Commitments to Polynomomations」を発表しました。Size Commitments to Polynomialsand Their Applications "という共同論文を発表した。

コミットメントは1つのグループ要素で構成され、コミッターはバッチ処理技術の助けを借りて、複数の多項式について、多項式の任意の正しい和を効率的に明らかにすることができます。バッチ処理技術の助けを借りて、和の任意の正しい和を明らかにすることができる。KZGの約束は、いくつかの有名なZK証明システム（イーサネットのPESグループが使用するhalo2など）の基本的な構成要素のひとつとなり、さらにイーサネットのEIP-4844では中心的な役割を果たした。バッチ処理技術の概念をより直感的に理解するためには、Mina-Ethereum bridgeの記事を参照してください。

参考文献：https://blog.lambdaclass.com/mina-to-ethereum-bridge/

Practical Elliptic Curve Based ZK-SNARK System（2013）

Practical Elliptic Curve Based ZK-SNARK System（2013）

Practical Elliptic Curve Based ZK-SNARK System（2013"text-align: left;">ZK-SNARKの最初の実用的な構造は2013年に登場し、証明鍵と検証鍵を生成するための前処理ステップが必要で、プログラムまたは回路に特化しており、一般化はされていません。これらの鍵のサイズは非常に大きくなる可能性があり、秘密のパラメータ自体に依存します。この秘密が破られた場合、攻撃者は証明を偽造することができます。この実用的なZK-SNARKシステムでは、コードを証明できる形に変換するには、コードを数学的形式の多項式制約のセットにコンパイルする必要があります。

当初、上記のプロセスは手作業で行わなければならず、時間がかかり、エラーが発生しやすかった。

1. より効率的な証明を提供する

2. 多項式制約を手動で記述する代わりに、高レベル言語を使って回路を記述する方法を開発する

ピノキオプロトコル(2013)

Pinocchioプロトコルは、288バイトの初期証明サイズで、Quadratic Arithmetic Procedure (QAP)に基づく、実用的に使用可能な最初のzk-SNARKシステムです。Pinocchioのツールチェーンは、C言語を算術回路にコンパイルするコンパイラを提供し、それをさらにQAPに変換することができる。Pinocchioプロトコルは、証明者が鍵を生成することを要求するが、それは汎用的なものではなく、むしろ回路固有のものである。この証明システムの生成と鍵のセットアップの漸近的な時間複雑度は計算のサイズに線形に関係し、検証時間は共通の入力と出力のサイズに線形に関係する。

Groth16(2016)

Grothは、R1CS.R1CSを扱う際に高い性能を持つ新しいZKマイニングアルゴリズムを紹介している。すなわち、一階制約系であるRank-1 Constraint Systemは、zk-SNARKにおける多項式制約形式である。Gorthの証明は、データサイズが最も小さく（3つのグループ要素しか含まない）、検証も高速であり、3つのペア演算と参照文字列を構造化する前処理ステップしか必要としない。しかし、Gorthの主な欠点は、証明を必要とする各プログラムが異なるもっともらしい設定を必要とすることであり、これは実際にはかなり不便である。

後にGroth16は、よりよく知られたプライバシーブロックチェーンプロジェクトの1つであるZCashで使用されました（Starkwareの創設者であるEliの参加によって行われました）。

Bulletproofs and IPA (2016)

前述したKZG多項式コミットメントスキームの主な弱点の1つは、「もっともらしい」コミットメントスキームが必要なことです。Bootleらは、内積関係を満たすPedersenコミットメントの開きを解析する効率的なゼロ知識証明システムを提案している。この内積証明は、証明経過時間の複雑さが線形であり、証明者と検証者の間の相互作用の回数は対数であるが、検証時間は線形である。さらにBootleらは、もっともらしい設定を必要としない多項式コミットメント方式を開発した。これらのアイデアは後にHalo2やKimchiらによって採用された。

Sonic, Marlin, and Plonk (2019)

Sonic, Plonk, and Marlinは、以下の問題に対処した。Groth16アルゴリズムにおけるすべての手続きに対して信頼されたセットアップが必要であるという問題に対して、汎用的で更新可能な構造化参照文字列（一度だけ行う必要がある信頼されたセットアップを実装するために使用される）を導入することで対処した。とりわけ、MarlinはR1CSに基づく証明システムを提供し、Aleoの中核技術となった。

そしてPlonkは、新しい算術スキーム（後にPlonkishとして知られる）と、複製制約をチェックするための大積分の使用を導入した。「カスタムゲート」と呼ばれる。Aztec、zkSync、Polygon zkEVM、Mina、Ether PSEグループ、Scrollなど、多くの有名なブロックチェーンプロジェクト関係者が、Plonkのカスタマイズバージョンを使用してきました。

Spartan(2019)

Spartanは、R1CSで記述された回路を使用するSpartanの新しいバージョンを提供します。R1CSで記述された回路を使用して、多変数多項式および和チェック・プロトコルの特性を利用したIOPを提供します。適切な多項式コミットメントスキームを使用することで、透明性と証明生成のための線形時間複雑性を持つzk-SNARKシステムを実装している。

ルックアップ(2020)

2020年のGabizonとWilliamsonは、彼らの論文で次のように発表した。plookup,を発表した。これは、ある値が事前に計算された真理値表に含まれていることを証明するために大積を使用するもので、plookupパラメータをPlonkアルゴリズムに導入する方法を示している。

しかしながら、これらのルックアップ論証は、証明者が大きなコストをかけて完全な真理値表を構築する必要があるという点で共通の問題を抱えており、ルックアップに関するこれまでの研究は、証明のコストを最小化することに取り組んできました。

Haböckは論文の後半で、対数導関数を使用して大積チェックを逆数の和に変換するLogUpを紹介しました。モジュールに分割する必要があったからである。これらのモジュールは正しくリンクする必要があり、クロステーブル・ルックアップはこれを強制します。LogUp-GKRの導入により、GKRプロトコルを通じてLogUpのパフォーマンスが再び向上しました。

Caulkは、真理値表サイズに関して証明時間を非線形にした最初のスキームであり、前処理時間の複雑さはO(NlogN)、記憶占有空間の複雑さはO(N)（Nは真理値表サイズ）である。Baloo、lookup、cq、caulk+などのスキームがこれに続く。さらに、Lassoは、真理値表が特定の構造を持つ場合に、その真理値表へのコミットを回避するためのいくつかの改善スキームを提案した。

HyperPlonk（2022年）

HyperPlonkは、論文「HyperPlonk: Plonk with Linear-ime Prover and High-Time Prover」

で自身の研究を発表した。HyperPlonkは多変数多項式を用いたPlonkのアイデアに基づいている。制約の実行をチェックするために除算を使用する代わりに、総和チェックプロトコルに依存しています。また、証明生成時間に影響を与えることなく、より高次の制約をサポートしています。

多変数多項式を使用するため、高速フーリエ変換（FFT）を実行する必要がなく、証明生成時間は回路サイズに線形に関係します。HyperPlonkはまた、小さなフィールドのための新しい置換IOPを導入し、和チェックベースのプロトコルを使用することで、証明者の作業負荷、証明サイズ、検証時間を削減します。

衝突防止ハッシュ関数を使用したZK証明システム

2013年にPinocchioが提案されたのと同時に、回路/算術化スキームを生成するための多くの提案がありました。2013年にピノキオが提案されると同時に、仮想マシンによる命令の実行が正しい結果をもたらすことを実証する回路/演算スキームを生成するための提案が数多く行われた。VMのための算術化スキームを開発することは、いくつかのプログラムのために専用の回路を書くことよりも複雑であったり、効率が悪かったりしますが、重要な利点があります。

TinyRAMのアイデアのいくつかは、後にCairo仮想マシンの設計で洗練され、zk-evmやgeneric zkvmなどが続いた。証明システムに衝突に強いハッシュ関数を使うことで、もっともらしいセットアップや楕円曲線操作は不要になったが、その代償として証明時間は長くなった。

TinyRAM（2013）

「SNARKs for C」では、「SNARKs for C」に基づく証明システムを開発した。では、C言語で書かれたプログラムの実行結果が正しいことを証明するためのPCPに基づく証明システムを開発した。プログラムはTinyRAMにコンパイルされる。TinyRAMは、バイトレベルのアドレス可能なランダムメモリを持つ簡略化されたVMであり、ループ、制御フロー、メモリアクセスなどの操作を効率的に処理するために、計算スケール上で準線形的に成長する回路サイズを持つ。

ここでPCPとはProbabilistically Checkable Proofの略で、検証者は証明の無作為に選択された小さな部分のみを読むことによって、高い信頼度で証明の妥当性をチェックすることができます。検証者が証明全体をチェックする必要がある従来の証明システムとは異なり、PCPは効率的な検証のために限られたランダム性しか必要としません。

Ligero (2017)

Ligeroは、O(√￣n)のサイズの証明を達成する証明システムを紹介しています。ここでnは回路のサイズである。BrakedownはLigeroをベースに、ドメインに依存しない多項式コミットメントスキームの概念を導入しています。

STARKs (2018)

STARKs (Scalable TransparentARguments of Knowledge）は、2018年にEli Ben-Sassonらによって提案された。彼らは、?(log²?）の証明複雑度を実装し、検証速度が速く、もっともらしい設定を必要とせず、ポスト量子セキュアであると仮定されている。Cairo仮想マシンはStarkware/Starknetによって採用されている。主な革新技術として、代数的中間表現（Algebraic Intermediate Representation: AIR）と高速リードソロモン対話型オラクル近似証明（Fast Reed-Solomon Interactive Oracle Proof of Approximity: FRI）プロトコルがある。さらに、STARKは多くの有名なブロックチェーンプロジェクト（Polygon Miden、RiscZero、Winterfell、Neptune、ZeroSync、zkSyncなど）で使用されています。

新たな方向性

実世界のアプリケーションにおける異なる証明システムの使用は、異なるアプローチの利点を実証し、ZKの開発を後押しします。例えば、Plonkishの算術化スキームは、カスタム論理ゲートとルックアップ引数を含める簡単な方法を提供します。FRIはPCSとして優れた性能を示し、Plonkyの作成につながりました。FRIはPCSとして優れた性能を示し、Plonkyの誕生につながった。一方、AIRにおける大積チェックの使用（これは前処理ランダム化AIRをもたらした）は、その性能を向上させ、メモリアクセスパラメータを簡素化した。

新しい多項式コミットメントスキーム（2023年）

SpartanやHyperPlonkのような、効率的な多変数多項式ベースのSNARKが導入されたことで、多項式コミットメントスキームへの関心が高まっています。Binius、Zeromorph、およびBasefoldはすべて、多項式をコミットする新しい方法を提案しています。Biniusはデータ型を余分なオーバーヘッドなしに表現でき（他の多くの証明システムでは個々のビットを表現するために少なくとも32ビットのフィールド要素を使用する）、バイナリ領域で動作するという利点がある。BasefoldはFRIをReed-Solomon以上に拡張し、ドメインに依存しない多項式コミットメントスキーム（PCS）を可能にしている。

ドメイン非依存とは、多項式コミットメントスキームの特性であり、コミットメントプロセスが特定のドメインのいかなる特性にも依存しない多項式コミットメントスキームを指します。これは、コミットメントが、有限体、楕円曲線、さらには整数の環のような任意の代数構造の多項式に対して行われ得ることを意味します。

カスタマイズ可能な制約システム(2023)

CCSはR1CSを一般化したもので、R1CS、Plonkish、AIRの算術化を、追加のオーバーヘッドなしに同時に実現します。オーバーヘッドを追加することなくCCSをSpartan IOPと組み合わせて使用することで、SuperSpartanが生成される。SuperSpartanは、制約の次数に比例する暗号化コストを証明者が負担することなく、高次元制約をサポートする。

要約

この記事では、ZK技術の概要について説明します。本記事では、1980年代半ば以降のZK技術の進歩を概観する。コンピュータサイエンス、数学、ハードウェアの進歩は、ブロックチェーンの導入と相まって、より効率的な新しいZK証明システムの出現を生み、社会を変える可能性のある多くのアプリケーションへの道を開いた。

研究者やエンジニアは、証明サイズの大きさ、メモリ使用の度合い、透明性、反量子セキュリティ、証明時間、検証時間を中心に、需要に基づいてZKシステムの改善を打ち出してきました。ZKの主流実装には大きく分けて2つのカテゴリー（SNARKとSTARK）がありますが、両者の境界は曖昧になりつつあり、異なる算術化スキームと新しい多項式コミットメントスキームを組み合わせるなど、異なる証明システムの強みが組み合わされています。

新しいZK証明システムは、性能の向上とともに出現し続けることが予想されます。これらの証明システムを使用するアプリケーションにとって、最新技術の反復的な開発に従わず、最新のアルゴリズムをリファクタリングして適用し続けなければ、現在の主導的地位は一時的なものに過ぎません。

Link to original article:https://blog.lambdaclass.com/our-highly-subjective-view-on-the-歴史-オブ-ゼロ-知識-証明/