ログイン/ 登録

知識ゼロの永続性証明イノベーションが出現した理由は何か？

JinseFinance

2024/02/19 18:53

従う

Author: LambdaClass; translated by mutourend; Yiping, IOSG Ventures

Part.1 洞察

Zero Knowledge（ゼロ・ナレッジ永続性を証明するイノベーションが出現する理由は何でしょうか？

Originally posted on https://blog.lambdaclass.com/our-highly-subjective-view-on-the-history-of-zero-.knowledge-proofs/

1.はじめに

ゼロ知識・簡潔・非対話的知識証明(zk-SNARKs）は強力な暗号プリミティブであり、証明者はある文の正しさを、その文以上の情報を明かすことなく検証者に納得させることができる。検証可能な私的計算、コンピュータプログラム実行の正しさの証明、ブロックチェーン拡張への応用により、zk-SNARKは多くの注目を集めています。zk-SNARKは、異なる多項式コミットメントスキーム、算術化スキーム、対話的予測子証明、または確率論的検定可能証明を使用する、さまざまなタイプの証明システムをカバーしています。しかし、基本的なアイデアとコンセプトは1980年代半ばにさかのぼる。ビットコインとイーサが登場して以来、zk-SNARKの開発は著しく加速しています。zk-SNARKは、ゼロ知識証明（この特定のユースケースでは有効性の証明と呼ばれることが多い）を使用することで拡張できるためです。zk-SNARKはブロックチェーンのスケーラビリティにおいて重要な役割を果たしています。Ben-Sasson氏が説明するように、近年、暗号証明のカンブリア爆発が起きています。それぞれの証明システムには利点と欠点があり、特定のトレードオフを念頭に置いて設計されている。ハードウェア、アルゴリズム、新しい証明、ツールの進歩によって性能は向上し続け、新しいシステムも生まれている。これらのシステムの多くはすでに実用化されており、我々はその限界を押し広げ続けている。すべてのアプリケーションに対応する普遍的な証明システムはできるのだろうか？

1）アプリケーションの多様性。

2）さまざまな種類の制約（メモリ、検証期間、証明期間）。

3）堅牢性の必要性（1つの証明システムが壊れても、他の証明システムがある）。

証明システムが大きく変わったとしても、それらはすべて、証明を迅速に検証できるという重要な特性を提供します。証明を検証し、新しい証明システムに簡単に適応できるレイヤーを持つことで、基本レイヤーの変更に伴う困難を解決できます（イーサリアムなど）。透明な設定と信頼できる設定。

3）証明の長さ：線形と超線形。

4）証明者の時間：一定時間、対数、サブリニア、リニア。

5）証明サイズ

6）簡単な再帰。

7) 算術化スキーム。

8) 一変量多項式と多変量多項式。

本論文では、SNARKの起源、基本的な構成要素の一部、さまざまな証明システムの台頭（と衰退）について見ていきます。本稿の意図は、証明システムを網羅的に分析することではない。むしろ、私たちに影響を与えたものだけに焦点を当てる。もちろん、これらの発展は、この分野の先駆者たちの偉大な仕事とアイデアによってのみ可能であった。

2.基礎

ゼロ知識証明は新しいものではありません。定義、基礎、重要な定理、そして重要なプロトコルさえも、1980年代半ばから開発されてきました。現代のSNARKを構築するために使用されている重要なアイデアやプロトコルのいくつかは、ビットコイン（2007年のGKR）の登場以前にも、1990年代に提案されていた（sumcheckプロトコル）。これを使用する際の主な問題は、堅牢なユースケースの欠如（1990年代はインターネットが十分に発達していなかった）と必要な計算能力に関連していた。

1）ゼロ知識証明：起源（1985/1989）。

ゼロ知識証明の分野は、Goldwasser、Micali、Rackoffの論文「The knowledge complexity of interactive proof systems」によって学術文献に登場しました。その起源については、2023年1月のZKP MOOC Lecture 1: Introduction and History of ZKPをご覧ください。この論文では、完全多重性、信頼性、ゼロ知識証明の概念を紹介し、二次残差性と二次非残差性の構成を提供しています。残差性の構成。

2）Sumcheckプロトコル（1992年）。

Sumcheckプロトコルは、1992年のAlgebraic Methods for Interactive Proof Systemsの論文で、Lund、Fortnow、Karloff、Nisanによって提案された。簡潔な対話的証明のための最も重要な構成要素の一つである。

3) Goldwasser-Kalai-Rothblum (GKR) (2007)。

GKRプロトコル（論文「Delegating Computation: interactive Proofs for Muggles」参照）は、証明者が回路のゲート数に応じて線形に実行し、検証者が回路のサイズに応じて非線形に実行する対話型プロトコルである。演算を行う。このプロトコルでは、深さddの有限領域のfan-in-two算術回路（層ddが入力層、層0 00が出力層に相当）について、証明者と検証者が合意する。プロトコルは、回路の出力に関する記述から始まり、それは前の層の値に関する記述に還元される。再帰を使用すると、これは回路の入力に関する宣言に変換でき、簡単にチェックできる。これらの削減はsumcheckプロトコルを使って実装される。

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

2010年のKate、Zaverucha、GoldbergのConstant-Size Commitments to Polynomials and Their Applicationsでは、多項式コミットメントスキームにバイリニア対群を用いることを紹介しています。多項式コミットメント・スキームである。コミットメントは1つのグループ要素で構成され、コミッターは多項式の正しい評価に対して効果的にコミットメントをオープンすることができます。KZGコミットメントは、Pinocchio、Groth16、Plonkなどのいくつかの効率的なSNARKの基本的な構成要素の1つです。バッチ技術を視覚化するには、Mina to Ethereum ZKブリッジをご覧ください。

3.align: left;">最初の実用的なSNARKの構築は2013年に登場しました。これらの構成では、証明鍵と検証鍵を生成するための前処理ステップが必要であり、プログラム/回路に固有です。コードを証明可能なコードに変換するには、コードを多項式制約系にコンパイルする必要がある。コードを証明可能なコードに変換するには、コードを多項式制約系にコンパイルする必要がある。

1）より効率的な証明器を持つ。

2）前処理の量を減らす。

3）回路固有のセットアップではなく、一般的なセットアップを行う。

4）信頼できるセットアップを避ける。

5)多項式制約を手作業で書くのではなく、高水準言語を使って回路を記述する方法を開発する。

現在、楕円曲線を使用した実用的なSNARKsスキームは以下の通りです：

1）ピノキオ（2013）

2) Groth 16 (2016)

3) Bulletproofs & IPA (2016)

4) Sonic, Marlin, and Plonk(2019)

5）ルックアップ（2018/2020）

6）スパルタン（2019）

7) HyperPlonk (2022)

8) Folding schemes (2008/2021)

3.1.Pinocchio (2013)

Pinocchio（論文Pinocchio: Nearly Practical Verifiable Computationを参照）は、最初の実用的で使用可能なzk-SNARKです。SNARKは四則演算プログラム（QAP）に基づいている。pinocchioのツールチェーンは、Cコードから算術回路、さらにQAPへのコンパイラを提供している。楕円曲線のペアリングを使って方程式をチェックする。証明の生成と鍵のセットアップの漸近は計算のサイズに線形に関係し、検証の長さは共通の入力と出力のサイズに線形に関係する。

3.2グロース16(2016)

グロース2016年の論文On the Size of Pairing-based Non-interactive Argumentsは、R1CSによって記述される問題の性能を向上させる新しい知識論証を紹介している。これは最小の証明サイズ（3つのグループ要素のみ）と3つのペアリングを含む高速な検証を持つ。また、構造化された参照文字列を得るための前処理ステップを含む。主な欠点は、証明するプログラムごとに異なる信頼されたセットアップが必要であり、不便であることである。詳細は、ブログAn overview of the Groth 16 proof systemも参照のこと。3.3 Bulletproofs & IPA (2016)

KZG PCSの弱点の一つは、もっともらしい設定を必要とすることである。本論文では、内積（inner product）関係を満たすPedersenコミットメント・オープンに対する効率的なゼロ知識論証システムを紹介する。この内積証明システムは、通信と相互作用が対数的でありながら、検証時間が線形である線形証明器を持つ。また、もっともらしいセットアップを必要としない多項式コミットメントスキームも開発されている。Halo 2とKimchiの両方がIPA PCSのアイデアを採用している。

3.4ソニック、マーリン、プロンク（2019）

ソニック、プロンク、マーリンは、IPA PCSの考え方を採用している。Groth16.Marlinでは、Aleoの心臓部であるR1CSに基づく証明システムを提供している。

Plonkは、新しい算術スキーム（後にPlonkishとして知られる）と、コピー制約に対する大積チェックの使用を導入した。ゲートとして知られる。Plonkのカスタマイズ・バージョンは、Aztec、ZK-Sync、Polygon ZKEVM、Mina's Kimchi、Plonky2、Halo 2、Scrollなど、いくつかのプロジェクトで利用できる。ブログ「All you wanted to know about Plonk」をご覧ください。

3.5 Lookups (2018/2020)

GabizonとWilliamsonは2020年にplookupを導入した。これは、値が事前に計算された値の表に含まれていることを証明するために大積チェックを使用する。ルックアップ引数は以前Aryaで提案されていたが、その構築にはルックアップの乗数を決定する必要があり、効率が悪い。PlonkUp論文はPlonkにルックアップ引数を導入する方法を示している。これらのルックアップ引数の問題点は、ルックアップの回数に関係なく、テーブル全体の代償を証明者に強いることである。これは、大きなテーブルは非常にコストがかかることを意味し、多くの努力が、使用するルックアップの数に対する証明者のコストを削減するために費やされてきました。

Haböckは、対数導関数を使用して積のチェックを逆数の和に変換するLogUpを紹介しました。LogUpは、Polygon plonky2のZKEVM（Beyond Limits: Bushing Boundaries of ZK-EVM）のパフォーマンスにとって非常に重要である。LogUp-GKRの導入は、GKRプロトコルを活用し、LogUpのパフォーマンスを向上させます。Caulkは、テーブルサイズに対して証明者時間がサブ線形である最初のルックアップ引数であり、その前処理時間は↪C_200D↩O ( Nlassoは、テーブルが指定された構造を持っている場合、テーブルへのコミットを避けるためにいくつかの改良を提案した。Joltは、ルックアップを通して仮想マシンの実行を証明するためにLassoを使用しています。

3.6スパルタン（2019）

スパルタンは、R1CSを使って記述された回路のIOPを提供します。sumcheckプロトコルの特性を利用している。

3.7 HyperPlonk (2022)

HyperPlonkは多変数多項式を使うというPlonkのアイデアに基づいて作られています。制約の実行をチェックするために商に依存する代わりに、sumcheckプロトコルに依存します。また、証明者の実行時間を犠牲にすることなく、高次制約をサポートします。HyperPlonkは、より小さなドメインのための新しい順列IOPと、sumcheckに基づくバッチオープニングプロトコルを導入し、証明者の作業負荷、証明のサイズ、検証者の時間を削減します。

3.8フォールディングスキーム（2008/2021）

Novaはフォールディングスキームという考え方を導入している。長さkkkの2つの証明を長さkkkの1つの証明に結合する方法を示したValiantに遡る概念であるIncremental Verifiable Computing (IVC)を実装する新しい方法です。この考え方は、ステップi iiからステップi + 1 i+1i+1への実行が正しいことを証明し、ステップi - 1 i-1i-1からステップi iiへの遷移証明が正しいことを検証するために、再帰的な証明を使用することができるというもので、これにより、任意の長く実行される計算を証明することができます。

Novaは一様な計算でうまく機能する。後に、R1CSの緩和版を使用し、友好的な楕円曲線上で動作するSupernovaの導入により、異なるタイプの回路を扱うように拡張された。IVCのための友好的な曲線サイクル（例えば、パスタ曲線）の使用は、クリーンな状態を達成するために、Minaの主要なベースモジュールであるPicklesでも使用された。しかし、フォールディングの考え方は、再帰的SNARK検証とは異なる。アキュムレータの考え方は、バッチ証明の概念により深く関連している。Haloは、再帰的な証明の組み合わせの代替としてアキュムレータの概念を導入している。Protostarは、高次ゲートとベクトルルックアップをサポートするPlonk用の非一様IVCスキームを提供している。

4. SNARKs with collision-resistant hash functions

ピノキオが開発されたのとほぼ同時期に、仮想ハッシュ関数の正しさを証明できる回路/算術スキームを生成するアイデアが現れました。仮想マシンの実行の正しさを証明できる回路/算術スキームを生成するアイデアが登場した。仮想マシン用の演算を開発するのは、プログラムによっては専用の回路を書くよりも複雑だったり効率が悪かったりするかもしれないが、どんなに複雑なプログラムでも、仮想マシンで正しく実行されることを示すことで証明できるという利点があった。改良点

1）TinyRAM（2013年）

SNARKsでは、PCPベースのSNARKsである。for Cでは、TinyRAM（Thin Instruction Set Computer）にコンパイルされたCプログラムの実行の正しさを証明するために、PCPベースのSNARKが開発された。このコンピュータは、バイトレベルのアドレス可能なランダムアクセスメモリを備えたハーバードアーキテクチャを持つ。非決定性を利用することで、回路の大きさは計算の大きさと相似的に線形準線形となり、任意のデータ依存ループ、制御フロー、メモリアクセスを効率的に扱うことができる。

2）STARKs（2018年）

STARKsは、Ben Sassonらによって導入された。2018年に提案された。その実装はO(log2n)の証明サイズを持ち、高速な証明者と検証者を持ち、信頼されたセットアップを必要とせず、ポスト量子セキュアと考えられている。Starkware/StarknetがCairo仮想マシンで最初に使用した。
代数的中間表現（AIR）
とFRIプロトコル（Fast Reed-SolomonInteractive Oracle Proof of Proximity)があります。

STARKはまた、他のプロジェクト（Polygon Miden、Risc0、Winterfell、Neptune）、またはその一部（ZK-SyncのBoojum、Plonky2、Starky）。

3）Ligero（2017）

Ligeroは、証明サイズがO(root n;)の証明システムを紹介しています。多項式係数を行列形式で並べ、線形コードを使用する。
Brakedownは、Ligeroの研究を基に構築され、ドメインに依存しないコードという考え方を導入している。ドメインに依存しない多項式コミットメントスキームのアイデアを導入しています。

5.ZKPにおけるいくつかの新しい発展

生産における異なる証明システムの使用は、各アプローチの利点を示し、新しい発展につながりました。発展をもたらした。同様に、AIRにおける大積チェックの使用（前処理によるランダム化AIRにつながる）は、その性能を向上させ、メモリアクセス引数を単純化する。ハッシュベースの約束は、ハードウェアのハッシュ関数の速度や、SNARKに適した新しいハッシュ関数の導入に基づいて、流行しました。

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

SpartanやHyperPlonkのような多変数多項式に基づく効率的なSNARKの出現により、このタイプの多項式に適した新しいコミットメントスキームへの関心が高まっています。Binius、Zeromorph、Basefoldはいずれも多変数多項式にコミットするための新しい方式を提案しています。Biniusはデータ型をゼロのオーバーヘッドで表現できるという利点があり（多くの証明システムでは1ビットを表現するために少なくとも32ビットのドメイン要素を使用します）、2進ドメイン上で動作します。basefoldはFRIをReed-Solomon以外のコードに拡張し、ドメインに依存しないPCSを実現します。

2）カスタマイズ可能な制約システム（Customizable Constraint Systems: CCSCCS (Customizable Constraint Systems) (2023)

CCSはR1CSを一般化し、オーバーヘッドなしでR1CS、プロンキッシュ、AIR演算を同時に捕捉する。CCSをSpartan IOPと組み合わせることで、SuperSpartanが生成される。SuperSpartanは、制約の次数に応じてスケールする暗号化コストを証明者に要求することなく、高次制約をサポートする。

6.結論

本稿では、SNARKの導入以来の進歩について説明する。1980年代半ばの導入以来のSNARKの進歩について述べた。コンピュータサイエンス、数学、ハードウェアの進歩は、ブロックチェーンの導入と相まって、より効率的な新しいSNARKを生み出し、社会を変革しうる多くのアプリケーションへの扉を開いた。研究者やエンジニアは、証明サイズ、メモリ使用量、透過設定、ポスト量子セキュリティ、証明者時間、検証者時間に焦点を当て、ニーズに基づいてSNARKの改善や調整を提案してきました。

当初は2つのメインスレッド（SNARK対STARK）がありましたが、異なる証明システムの長所を組み合わせる試みがなされるなど、両者の境界は薄れ始めています。例えば、異なる算術スキームと新しい多項式コミットメントスキームの組み合わせなどである。今後も新しい証明システムが登場し、性能が向上していくことが予想されるが、コアとなるインフラの一部を変更することなくツールを簡単に使用できない限り、適応に時間がかかるシステムにとっては、これらの開発に追いつくことは難しいだろう。