Zenn
Open3

ZKの歴史（研究サイド）

mameta29mameta29

https://www.youtube.com/watch?v=9jPDuj3cSs8

研究面での流れ

  • ゼロ知識証明は1982年に発明され、1985年に初めて発表 https://dl.acm.org/doi/pdf/10.1145/22145.22178
  • 発明者はGOLDWASSER, MICALI, RACKOFFです。マイカリとゴールドヴァッサーは後の2012年にこの業績の一部としてチューリング賞を受賞
  • これは主にアカデミアの世界に留まっていました。新しい研究論文は出てきましたが、実用には遅すぎる
  • 3つの特徴
    • 完全性：「正しい主張」に対して、証明が必ず成功することを保証する。例：「私はこの金庫の暗証番号を知っています」という主張が本当である場合、証明者は必ず検証者に証明できる
    • 健全性：「誤った主張」に対して、証明が失敗することを保証する。例：実際には金庫の暗証番号を知らない人が、知っていると偽って証明しようとしても、検証者を騙すことはできない
    • ゼロ知識性：ステートメントが真実であるかどうか以外の情報が漏洩しない
  • 2012年に、あるいは今日私が学んだところによると少し前に、SNARKsの概念が最終的に定義
  • SNARKsは簡潔な非対話型知識証明（Succinct Non-interactive Arguments of Knowledge）の略で、これがZKPを実用的な方法で実装して使用できるようになった最初の機会
    • 信頼された設定が必要
    • これらのSNARKsをブロックチェーンと組み合わせられることに気づきました。
  • 2013年にゼロコイン論文が発表されました。これは後に、ここから複雑になりますが、2014年にゼロキャッシュ論文へと発展します。これはゼロコイン論文の拡張版です。
  • 2015年にゼロキャッシュの著者たちがゼロコイン社を設立し、その後ゼロコインはZcashにリブランドされ、同時期にこの研究に基づいて別のプロジェクトであるZcoinもリリースされました。つまり、ZcashとZcoinがあり、どちらもゼロキャッシュに基づいていて、それはゼロコインに基づいていたhttps://ieeexplore.ieee.org/document/6956581 https://wired.jp/2015/11/29/zerocoin-startup/
  • 2016年にGroth16が発表, Groth16は証明システムで、今日でも多くのプロジェクトが使用している
  • 2017年にFRIの論文が発表され、これは後で重要になります。FRIは後にSNARK構造の多くに組み込まれるようになった
  • 研究面での2018年のハイライトは、STARKsとBulletproofsの発表
  • 2019年の大きな研究のハイライトはPLONKとSonicでしたが、特にPLONKは重要で、それ以来PLONKはGroth16のように様々な方法で実装されている
  • 2020年には以下の研究が発表されました。Fractal、PLUP、Halo 2、HaloとHalo 2は両方ともその年に出たと思います。MinaチームからのPickles、Quarks、そして最初のPLONKyです。この世代のHalo 2は恐らく最も関連性が高く、再び非常に重要な証明システムとなり、多くの実装がなされ、皆さんが知っているZKチームの多くが使用しています。Groth16、何らかの形のPLONK、あるいはおそらく何らかの形のHalo 2を使用しています。全てではありませんが、多くが使用しています。Plookupはまた、私たちのコンテキストでルックアップテーブルが導入された最初の例でもあり、これは効率性の向上をもたらしました。
  • 2021年にはIVCまたはフォールディングと呼ばれる別の技術がNova論文で導入
  • 2022年にはPLONKy2が登場し、これも再びエコシステムに影響を与えた重要な研究の一つに分類されます。そしてHyperPLONKのようなPLONKのバリエーション、SupernovaのようなNovaのバリエーションが登場し、PLUPから始まったルックアップの研究が 続いています
  • 2023年のハイライトはHypernovaでしょう。これはフォールディングを使用しながら、新しいレベルに引き上げたものです。（jolt）Binuisも登場しました。後で著者の一人からお話を聞くことになっています。そして昨年はジャスティン・トールのSum-Checkの研究でJoltとLassoも登場しました。
  • 2024 STIR, Polymath, Plonky3：これはFRIを取り上げています。FRIについて言及しましたが、FRIはもともとSTARKsのみに使用されていましたが、その後SNARKsと組み合わされ始め、それが本当に分野を開拓しました。今やStirによって、これはFRIの改良版となっています。
  • ZKの歴史のまとめですが、2013年まで主にアカデミックで理論的で実用的ではありませんでした。ZKとブロックチェーンが組み合わさり、それは研究の爆発的な増加をもたらし、明らかにその研究への資金提供も爆発的に増加しました。ZKのパフォーマンスは指数関数的に向上し、現在ではWeb3を超えて使用されています

プロジェクトの流れ

  • 2017年、ZKの焦点は主にプライバシー、特に匿名での支払いにありました。ZKに取り組んでいた設立された会社は2つだけで、それはZcashと現在のFである以前のZcoinでした
  • 2019年になると、ZKがスケーリングに使える可能性があることに気づきました。また、AztecとZK sync、そして当時Codaと呼ばれていたMinaのような新しいプライバシープロジェクトも登場し、ブロックチェーンの圧縮やスケーリングの形態であるRecursionという概念を導入しました。
  • 2020年には、L2sまたはZKロールアップという概念が導入されました。当時、Aztecはまだロールアップではなかったかもしれません。今はそうですが。ZK syncはご存知の通り、その後ロールアップになり、Dark Forestという形で最初のZKゲームも登場しました。
  • 2024 支払い、L2s、L1s、ゲームです。明らかにもっとたくさんのプロジェクト
  • DeFiがあり、ZKMLがあり、ハードウェアがあります。突然、これらの証明をより効率的にする作業をしていましたが、それを実行できるハードウェアがあれば、その改善にも貢献できるということに気づきました。ゲームも明らかに成長しています。また、スケーリングや圧縮のためにZKを使用するというこのアイデアは、ライトクライアントやクロスチェーンに使用できるかもしれないということを意味します。実際にZK for IDのユースケースは長い間存在していましたが、特に今年は多くのチームがそれを使い始めるのを見ています。ZKの証明システムやZKツールが、はるかに使いやすくなった
mameta29mameta29

https://medium.com/@emilpepil/history-of-the-formation-of-zkp-151dd7001ffa

  • 2011年にSNARKsの定義が出る https://eprint.iacr.org/2011/443.pdf
    • この論文はECR（Extractable Collision Resistance）ハッシュ関数と呼ばれるものを使ってSNARKS（簡潔な非対話的知識論証）を作成できることを示した。 SNARKSは基本的に「簡潔な」ZKPであり、サイズが小さく、数秒で検証できることを意味する。
  • 2013年にPinocchioが誕生
  • zkSNARKsの2つの問題
    • Trusted setup
    • 量子耐性がない
  • 2018 - STARKS
    • 「ポスト量子セキュア」であり、証明メカニズムを楕円曲線ではなくハッシュ関数に依存している。
    • STARKSは信頼されたセットアップを必要としない。その代わり、zk-STARKSは公開されている検証可能な乱数源を初期パラメータとして使用する。
    • zk-STARKSの最大の欠点は、証明サイズが大きいことだった。このため、オンチェーンでの保管にはコストがかかるため、ブロックチェーンには不向きだった。しかし、STARKSはSNARKSにステップアップを促し、信頼できるセットアップから脱却させた。
  • 2019 - SNARKSの年
  • SONIC
    • ソニックが行った大きな貢献は、「ユニバーサル」で継続的にアップグレード可能なリファレンス・ストリングをサポートしたことだ。これは、すべてのプログラムの初期パラメータを生成するためにトラステッド・セットアップを行う必要がないことを意味します。その代わり、一度トラステッド・セットアップを行えば、すべてのプログラムに同じパラメーターを使うことができる。これにより、トラステッド・セットアップの欠点が完全に軽減されたわけではないが、間違いなく改善された。
  • Marlin
    • MarlinはSonicの大幅な改良版で、プルーフ時間を10倍に短縮した。
  • PLONK
    • PLONKは 「Permutations over Lagrange-bases for Oecumenical Non Interactive Arguments of Knowledge 」の略で、SONICの改良版である。ここでの大きな革新は、PLONKが通常の加算/乗算以外のカスタムゲートを可能にしたことで、より複雑なプログラムに対してzk証明を構築できるようになった。
    • PlonKとMarlinはどちらも、Groth16の回路固有の信頼できるセットアップをユニバーサルなセットアップに置き換えた。PLONKの導入により、暗号コミュニティは「zkEVM」さえ構築できることに気づき、イーサリアム上のあらゆるスマート・コントラクトのコードをゼロ知識証明に変換できるようになった。
    • これは、イーサリアム上のあらゆるスマート・コントラクトのコードをゼロ知識証明に変換できるようにするものです！
  • 2020年、ZcashチームはPLONKとBulletproofsの両方の長所を組み合わせたHALO 2（HALOの後継）を導入し、信頼できるセットアップなしで高速な検証を可能にしました。
  • 2022年：HYPERPLONK, PLONKY 2
    • PLONKY 2：これは再帰的SNARKであり、既存の代替案よりも100倍高速である。PLONKとFRIを組み合わせることで、STARKの長所（すなわち、高速な証明と信頼できるセットアップなし）とSNARKの長所（すなわち、再帰のサポートとイーサリアム上での低検証コスト）を実現しています。
mameta29mameta29

https://medium.com/starkware/cambrian-explosion-of-cryptographic-proofs-5740a41cdbd2

ゼロ知識証明の歴史に関する私たちの主観的な見解

ゼロ知識、簡潔、非対話型の知識の議論（zk-SNARKs）は、証明者が検証者に対して、その声明の妥当性以外の何も明かさずに、与えられた声明が真であることを納得させることができる強力な暗号プリミティブです。これらは、検証可能なプライベート計算への応用、コンピュータプログラムの実行の正しさの証明の提供、およびブロックチェーンのスケーリングの支援により、広く注目を集めています。私たちの投稿で説明しているように、SNARKsは私たちの世界の形成に大きな影響を与えると考えています。SNARKsは、異なる多項式コミットメントスキーム（PCS）、算術化スキーム、対話型オラクル証明（IOP）または確率的に検証可能な証明（PCP）を使用する、さまざまな種類の証明システムの総称として機能します。ただし、基本的なアイデアと概念は1980年代半ばまで遡ります。この開発は、ビットコインとイーサリアムの導入後に大きく加速しました。これらは、ゼロ知識証明（この特定のユースケースでは一般的に妥当性証明と呼ばれる）を使用してスケーリングできることが証明された、エキサイティングで強力なユースケースであることが判明したためです。SNARKsはブロックチェーンのスケーラビリティにとって不可欠なツールです。Ben-Sassonが説明しているように、ここ数年は暗号証明のカンブリア爆発を目の当たりにしています。各証明システムは長所と短所を持ち、特定のトレードオフを念頭に置いて設計されました。ハードウェアの進歩、より良いアルゴリズム、新しい議論、ガジェットにより、パフォーマンスが向上し、新しいシステムが誕生しています。その多くは実際に使用されており、私たちは境界を押し広げ続けています。すべてのアプリケーションに対する一般的な証明システムを持つことになるのか、それとも異なるニーズに適した複数のシステムを持つことになるのでしょうか？私たちは、1つの証明システムがすべてを支配することはありそうにないと考えています。その理由は：

  • アプリケーションの多様性
  • メモリ、検証時間、証明時間に関する制約の種類
  • 堅牢性の必要性（1つの証明システムが破られても、他のシステムがある）

証明システムが大きく変化しても、それらはすべて重要な特性を提供します：証明は迅速に検証できます。証明を検証し、新しい証明システムを処理するように簡単に適応できるレイヤーを持つことで、イーサリアムなどのベースレイヤーの変更に関連する困難を解決します。SNARKsの異なる特徴の概要を示すと：

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

この投稿では、SNARKsの起源、いくつかの基本的な構成要素、そしてさまざまな証明システムの台頭（と衰退）について見ていきます。この投稿は、証明システムの包括的な分析を意図したものではありません。代わりに、私たちに影響を与えたものに焦点を当てています。もちろん、これらの開発は、この分野のパイオニアたちの素晴らしい仕事とアイデアによってのみ可能でした。

基礎

前述したように、ゼロ知識証明は新しいものではありません。定義、基礎、重要な定理、そして重要なプロトコルさえも、1980年代半ばに確立されました。現代のSNARKsを構築するために使用する主要なアイデアとプロトコルのいくつかは、1990年代（sumcheckプロトコル）、あるいはビットコインの出現前（2007年のGKR）でさえ提案されていました。その採用における主な問題は、強力なユースケースの欠如（1990年代にはインターネットはそれほど発達していなかった）と、必要な計算能力の量に関連していました。

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

ゼロ知識証明の分野は、GoldwasserとMicali、Rackoffの論文で学術文献に登場しました。起源についての議論は、以下の動画で見ることができます。この論文は、完全性、健全性、ゼロ知識の概念を導入し、二次剰余と二次非剰余の構成を提供しました。

Sumcheckプロトコル（1992）

Sumcheckプロトコルは、1992年にLund、Fortnow、Karloff、Nisanによって提案されました。これは、簡潔な対話型証明のための最も重要な構成要素の1つです。これは、多変数多項式の評価の和に関する主張を、ランダムに選ばれた点での単一の評価に減らすのに役立ちます。

Goldwasser-Kalai-Rothblum（GKR）（2007）

GKRプロトコルは、回路のゲート数に対して線形に実行される証明者と、回路のサイズに対して準線形に実行される検証者を持つ対話型プロトコルです。このプロトコルでは、証明者と検証者は、有限体上のファンイン2の算術回路（深さdで、層dが入力層に対応し、層0が出力層）に合意します。プロトコルは回路の出力に関する主張から始まり、これは前の層の値に関する主張に還元されます。再帰を使用することで、これを回路の入力に関する主張に変換でき、簡単にチェックできます。これらの還元は、sumcheckプロトコルによって達成されます。

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

Kate、Zaverucha、Goldbergは2010年に、双線形ペアリング群を使用した多項式のコミットメントスキームを導入しました。コミットメントは単一の群要素で構成され、コミッターは多項式の任意の正しい評価に対してコミットメントを効率的に開くことができます。さらに、バッチング技術により、複数の評価に対する開示を行うことができます。KZGコミットメントは、Pinocchio、Groth16、Plonkなどのいくつかの効率的なSNARKsの基本的な構成要素の1つを提供しました。これはまた、EIP-4844の中核でもあります。バッチング技術の直感を得るには、Mina-Ethereumブリッジに関する私たちの投稿を参照してください。

楕円曲線を使用した実用的なSNARKs

SNARKsの最初の実用的な構造は2013年に登場しました。これらは、証明鍵と検証鍵を生成するための前処理ステップを必要とし、プログラム/回路に特化していました。これらの鍵はかなり大きくなる可能性があり、当事者に知られてはならない秘密のパラメータに依存していました。そうでなければ、証明を偽造できてしまいます。コードを証明可能なものに変換するには、コードを多項式制約のシステムにコンパイルする必要がありました。最初は、これは手動で行う必要があり、時間がかかり、エラーが発生しやすいものでした。この分野の進歩は、主な問題のいくつかを解決しようとしました：

  • より効率的な証明者を持つ
  • 前処理の量を減らす
  • 回路固有のセットアップではなく、普遍的なセットアップを持つ
  • 信頼されたセットアップを避ける
  • 多項式制約を手動で書く代わりに、高レベル言語を使用して回路を記述する方法を開発する

Pinocchio（2013）

Pinocchioは、最初の実用的で使用可能なzk-SNARKです。このSNARKは二次算術プログラム（QAP）に基づいています。証明サイズは当初288バイトでした。Pinocchioのツールチェーンは、Cコードから算術回路へのコンパイラを提供し、これがさらにQAPに変換されました。プロトコルは、検証者が回路固有の鍵を生成することを必要としました。これは楕円曲線ペアリングを使用して方程式をチェックしました。証明生成と鍵セットアップの漸近性は計算サイズに対して線形で、検証時間は公開入力と出力のサイズに対して線形でした。

Groth 16（2016）

Grothは、R1CSによって記述された問題に対して性能が向上した新しい知識の議論を導入しました。これは最小の証明サイズ（わずか3つの群要素）を持ち、3つのペアリングを含む高速な検証を行います。また、構造化された参照文字列を取得するための前処理ステップも含まれています。主な欠点は、証明したいプログラムごとに異なる信頼されたセットアップを必要とすることで、これは不便です。Groth16はZCashで使用されました。

Bulletproofs & IPA（2016）

KZG PCSの弱点の1つは、信頼されたセットアップを必要とすることです。Bootleらは、内積関係を満たすPedersenコミットメントの開示の効率的なゼロ知識議論システムを導入しました。内積議論は線形の証明者を持ち、対数的な通信と相互作用を持ちますが、線形時間の検証を持ちます。彼らはまた、信頼されたセットアップを必要としない多項式コミットメントスキームを開発しました。これらのアイデアを使用したPCSは、Halo 2とKimchiで使用されています。

Sonic、Marlin、およびPlonk（2019）

Sonic、Plonk、およびMarlinは、普遍的で更新可能な構造化された参照文字列を導入することで、Groth16で抱えていたプログラムごとの信頼されたセットアップの問題を解決します。MarlinはR1CSに基づく証明システムを提供し、Aleoの中核となっています。

Plonkは新しい算術化スキーム（後にPlonkishと呼ばれる）とコピー制約のためのグランドプロダクトチェックの使用を導入しました。Plonkishはまた、特定の操作のための特殊化されたゲート、いわゆるカスタムゲートの導入を可能にしました。Aztec、zkSync、Polygon ZKEVM、MinaのKimchi、Plonky2、Halo 2、Scrollなど、いくつかのプロジェクトがPlonkのカスタマイズバージョンを持っています。

ルックアップ（2018/2020）

GabizonとWilliamsonは2020年にplookupを導入し、グランドプロダクトチェックを使用して値が事前計算された値テーブルに含まれていることを証明しました。ルックアップ議論は以前にAryaで提示されましたが、その構造はルックアップの多重度の決定を必要とし、これにより構造の効率が低下します。PlonkUp論文は、plookup議論をPlonkに導入する方法を示しました。これらのルックアップ議論の問題は、ルックアップの数に関係なく、証明者に全テーブルの価格を支払わせることでした。これは大きなテーブルに対してかなりのコストを意味し、証明者のコストを使用するルックアップの数だけに減らすことに多くの努力が注がれてきました。

Haböckは、対数微分を使用してグランドプロダクトチェックを逆数の和に変換するLogUpを導入しました。LogUpはPolygon ZKEVMのパフォーマンスにとって重要です。ここでは、全テーブルをいくつかのSTARKモジュールに分割する必要があります。これらのモジュールは正しくリンクされる必要があり、クロステーブルルックアップがこれを強制します。LogUp-GKRの導入は、GKRプロトコルを使用してLogUpのパフォーマンスを向上させます。Caulkは、前処理時間O(NlogN)とストレージO(N)を使用することで、テーブルサイズに対して準線形の証明者時間を持つ最初のスキームでした（Nはテーブルサイズ）。Baloo、flookup、cq、caulk+などのいくつかの他のスキームが続きました。Lassoはいくつかの改善を提示し、テーブルが特定の構造を持っている場合、テーブルへのコミットを避けています。さらに、Lassoの証明者は、ルックアップ操作によってアクセスされるテーブルエントリにのみ対価を支払います。JoltはLassoを活用して、ルックアップを通じて仮想マシンの実行を証明します。

Spartan（2019）

SpartanはR1CSを使用して記述された回路のためのIOPを提供し、多変数多項式とsumcheckプロトコルの特性を活用します。適切な多項式コミットメントスキームを使用することで、線形時間の証明者を持つ透明なSNARKとなります。

HyperPlonk（2022）

HyperPlonkは多変数多項式を使用するPlonkのアイデアを基に構築されています。制約の施行を確認するための商の代わりに、sumcheckプロトコルに依存します。また、証明者の実行時間を損なうことなく、高次の制約をサポートします。多変数多項式に依存しているため、FFTを実行する必要はなく、証明者の実行時間は回路サイズに対して線形です。HyperPlonkは、より小さなフィールドに適した新しい置換IOPと、証明者の作業、証明サイズ、および検証者の時間を削減するsumcheckベースのバッチオープニングプロトコルを導入します。

折りたたみスキーム（2008/2021）

Novaは折りたたみスキームのアイデアを導入しました。これは、増分的に検証可能な計算（IVC）を達成するための新しいアプローチです。IVCの概念は、長さkの2つの証明を単一の長さkの証明にマージする方法を示したValiantまで遡ります。このアイデアは、ステップiからステップi+1への実行が正しいことを再帰的に証明し、ステップi-1からステップiへの遷移が正しかったことを示す証明を検証することで、任意の長時間の計算を証明できるというものです。Novaは均一な計算をうまく扱います。後にSupernovaの導入により、異なる種類の回路を処理できるように拡張されました。NovaはR1CSの緩和バージョンを使用し、親和的な楕円曲線上で動作します。親和的な曲線のサイクル（例えば、Pasta曲線）を使用してIVCを達成することは、簡潔な状態を達成するMinaの主要な構成要素であるPicklesでも使用されています。ただし、折りたたみのアイデアは、再帰的なSNARK検証とは異なります。アキュムレータのアイデアは、証明のバッチ処理の概念とより深く結びついています。Haloは、再帰的な証明の合成の代替としてアキュムレーションの概念を導入しました。Protostarは、高次のゲートとベクトルルックアップをサポートするPlonkの非均一IVCスキームを提供します。

衝突耐性ハッシュ関数の使用

Pinocchioが開発された頃、仮想マシンの実行の正しさを証明できる回路/算術化スキームを生成するいくつかのアイデアがありました。仮想マシンの算術化の開発は、一部のプログラムに対して専用の回路を書くよりも複雑または非効率的である可能性がありましたが、どんなに複雑なプログラムでも、仮想マシンで正しく実行されたことを示すことで証明できるという利点を提供しました。TinyRAMのアイデアは後にCairo vmの設計で改良され、その後の仮想マシン（zk-evmsや汎用zkvmsなど）にも影響を与えました。衝突耐性ハッシュ関数の使用により、より長い証明を代償として、信頼されたセットアップや楕円曲線演算の使用の必要性を排除しました。

TinyRAM（2013）

SNARKs for Cでは、Cプログラムの実行の正しさを証明するために、PCPに基づくSNARKを開発しました。このプログラムは、縮小命令セットコンピュータであるTinyRAMにコンパイルされます。このコンピュータはバイトレベルでアドレス可能なランダムアクセスメモリを持つハーバードアーキテクチャを使用しました。非決定性を活用することで、回路のサイズは計算のサイズに対して準線形となり、任意のデータ依存ループ、制御フロー、およびメモリアクセスを効率的に処理します。

STARKs（2018）

STARKsは2018年にBen Sassonらによって導入されました。これらは、O(log²n)の証明サイズを達成し、高速な証明者と検証者を持ち、信頼されたセットアップを必要とせず、ポスト量子安全であると予想されています。これらは最初にStarkware/Starknetで使用され、Cairo vmとともに使用されました。その主要な導入の中には、代数的中間表現（AIR）とFRIプロトコル（Fast Reed-Solomon Interactive Oracle Proof of Proximity）があります。また、他のプロジェクト（Polygon Miden、Risc0、Winterfell、Neptune）でも使用されているか、一部のコンポーネントが適応されています（zkSyncのBoojum、Plonky2、Starky）。

Ligero（2017）

Ligeroは、回路のサイズnに対してO(√n)の証明サイズを達成する証明システムを導入します。多項式係数を行列形式で配置し、線形コードを使用します。
Brakedownは、Ligeroを基に構築され、フィールドに依存しない多項式コミットメントスキームのアイデアを導入します。

新しい開発

異なる証明システムの実際の使用により、各アプローチの長所が示され、新しい開発につながりました。例えば、plonkish算術化はカスタムゲートとルックアップ引数を含める簡単な方法を提供します。FRIはPCSとして優れたパフォーマンスを示し、Plonkyにつながりました。同様に、AIRでのグランドプロダクトチェックの使用（前処理を伴うランダム化AIRにつながる）は、そのパフォーマンスを向上させ、メモリアクセス引数を簡素化しました。ハードウェアでのハッシュ関数の速度や新しいSNARK対応ハッシュ関数の導入に基づき、ハッシュ関数に基づくコミットメントが人気を集めています。

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

SpartanやHyperPlonkなどの多変数多項式に基づく効率的なSNARKsの出現により、この種の多項式に適したコミットメントスキームへの関心が高まっています。Binius、Zeromorph、Basefoldはすべて、多線形多項式へのコミットメントの新しい形式を提案しています。Biniusは、データ型を表現するためのオーバーヘッドがゼロであること（多くの証明システムは単一のビットを表現するために少なくとも32ビットのフィールド要素を使用する）という利点を提供し、二進フィールド上で動作します。このコミットメントは、フィールドに依存しないように設計されたbrakedownを適応させています。Basefoldは、FRIをReed-Solomon以外のコードに一般化し、フィールドに依存しないPCSにつながります。

カスタマイズ可能な制約システム（2023）

CCSはR1CSを一般化し、オーバーヘッドなしにR1CS、Plonkish、およびAIR算術化を捕捉します。CCSをSpartan IOPと組み合わせることで、SuperSpartanが生まれ、制約の次数に応じて暗号的コストがスケールする必要なく、高次の制約をサポートします。特に、SuperSpartanは線形時間の証明者を持つAIRのためのSNARKを生成します。

結論

この投稿では、1980年代半ばの導入以来のSNARKsの進歩について説明しました。コンピュータサイエンス、数学、ハードウェアの進歩と、ブロックチェーンの導入により、新しくより効率的なSNARKsが生まれ、私たちの社会を変革する可能性のある多くのアプリケーションへの道を開きました。研究者とエンジニアは、証明サイズ、メモリ使用、透明なセットアップ、ポスト量子安全性、証明者時間、および検証者時間に焦点を当て、彼らのニーズに応じてSNARKsの改善と適応を提案してきました。当初は2つの主要なライン（SNARKs vs STARKs）がありましたが、両者の境界は徐々に薄れ始め、異なる証明システムの利点を組み合わせようとしています。例えば、異なる算術化スキームと新しい多項式コミットメントスキームを組み合わせることなどです。新しい証明システムは、パフォーマンスの向上とともに継続的に登場すると予想され、一部の中核インフラを変更せずにこれらのツールを簡単に使用できない限り、これらの開発に追いつくには時間がかかるシステムもあるでしょう。