編集者注： a16z 暗号には、「銃」、私たちから ダオキャノン 昨年、私たちに NFTキヤノン 以前（そしてその前に私たちのオリジナル クリプトキャノン) — 必ずサインアップしてください web3 週刊ニュースレター より多くの更新情報やその他の精選されたリソースについては。
そうb以下に、すべてのものを理解し、深く掘り下げ、構築しようとしている人のために、一連のリソースを厳選しました。 ゼロ知識: ブロックチェーンのスケーラビリティの鍵を握る強力な基盤技術であり、将来のプライバシー保護アプリケーションや今後の無数のイノベーションを表しています。 追加する高品質の作品について提案がある場合は、@ でお知らせください。a16z暗号.
ゼロ知識証明システムは、何十年も前から存在しています。1985 年に Shafi Goldwasser、Silvio Micali、および Charles Rackoff によって導入されたゼロ知識証明システムは、暗号化の分野に変革をもたらしました。 2012. 理論から実践への移行、そして今日の crypto/web3 への応用を含め、この作業は何十年にもわたって行われてきました。 によって注釈が付けられた図書リスト ジャスティン・セイラー、以下のパート XNUMX に従います。
謝辞: Michael Blau、Sam Ragsdale、Tim Roughgarden にも感謝します。
基礎、背景、進化
これらの論文の一部は、一般的な暗号化 (すべてゼロ知識自体ではない) についても詳しく説明しており、今日のゼロ知識証明によって対処されている問題や重要な進歩の概要を説明しています: オープン ネットワークでプライバシーと認証を確保する方法.
暗号化の新しい方向性 (1976 年)
Whitfield Diffie および Martin Hellman 著
https://ee.stanford.edu/~hellman/publications/24.pdf
デジタル署名と公開鍵暗号システムを取得する方法
ロナルド・リベスト、アディ・シャミール、レナード・アデルマン
https://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=856E21BC2F75800D37FD611032C30B9C?doi=10.1.1.40.5588&rep=rep1&type=pdf
公開鍵暗号方式のプロトコル (1980 年)
ラルフ・マークル
http://www.merkle.com/papers/Protocols.pdf
安全でないチャネルを介した安全な通信 (1978 年)
ラルフ・マークル
https://www.merkle.com/1974/PuzzlesAsPublished.pdf
暗号における楕円曲線の使用 (1988)
ビクター・ミラー
https://link.springer.com/content/pdf/10.1007%2F3-540-39799-X_31.pdf
インタラクティブな証明システムの知識の複雑さ (1985)
Shafi Goldwasser, Silvio Micali, Charles Rackof 著
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.419.8132&rep=rep1&type=pdf
計算による健全な証明 (2000)
シルヴィオ・ミカリ
https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/Computationally_Sound_Proofs.pdf
抽出可能な衝突耐性から知識の簡潔で非対話的な議論 [SNARKs] まで、そして再び戻る (2011)
ニール・ビタンスキー、ラン・カネッティ、アレッサンドロ・キエーザ、エラン・トロマー
https://eprint.iacr.org/2011/443.pdf
シャッフルの正しさに関する効率的なゼロ知識の議論 (2012)
ステファニー・ベイヤーとイェンス・グロス著
http://www0.cs.ucl.ac.uk/staff/J.Groth/MinimalShuffle.pdf
フォン・ノイマン・アーキテクチャのための簡潔で非インタラクティブなゼロ知識 (2013)
Eli Ben-Sasson、Alessandro Chiesa、Eran Tromer、Madars Virza著
https://eprint.iacr.org/2013/879.pdf
スケーラブルで透過的で、ポスト量子の安全な計算整合性 (2018)
Eli Ben-Sasson、Iddo Bentov、Yinon Horesh、Michael Riabzev著
https://eprint.iacr.org/2018/046.pdf
（ほぼ）最小限の時間とスペースのオーバーヘッドを伴う公開コインのゼロ知識議論（2020年）
Alexander Block、Justin Holmgren、Alon Rosen、Ron Rothblum、および Pratik Soni 著
https://www.iacr.org/cryptodb/data/paper.php?pubkey=30645
概要と紹介
証明、議論、ゼロ知識 — 検証可能なコンピューティングとインタラクティブな証明と引数の概要、証明者が要求された計算を証明者が正しく実行したことを検証者に保証できるようにする暗号化プロトコル。 . Zk の引数には、暗号化における無数のアプリケーションがあり、過去 XNUMX 年間で理論から実践へと飛躍しました。
ジャスティン・セイラー
https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf
ゼロ知識証明のためのモデルの進化 — Meiklejohn (ユニバーシティ カレッジ ロンドン、Google) によるゼロ知識証明のレビューでは、開発を推進しているアプリケーション、これらの新しい相互作用を捉えるために出現したさまざまなモデル、達成できる構造、および作業について考察しています。やり残した。
サラ・メイクルジョン
https://www.youtube.com/watch?v=HO97kVMI3SE
ZK ホワイトボード セッション — 入門モジュール
ダン・ボネーらと
https://zkhack.dev/whiteboard/
zkps による暗号のセキュリティとプライバシー — 実際のゼロ知識証明の先駆者。 zkps とは何か、どのように機能するか…ライブ ステージの「デモ」を含む
ズーコ・ウィルコックス
https://a16z.com/2019/08/29/security-and-privacy-for-crypto-with-zero-knowledge-proofs/
主要な技術トピックの説明 — 一般的なゼロ知識の定義と含意を含む
ジョー・ボノー、ティム・ラフガーデン、スコット・コマイナーズ、アリ・ヤーヤ、クリス・ディクソン
https://web3-with-a16z.simplecast.com/episodes/hot-research-summer-blockchain-crypto-tech-topics-explainers-overviews-seminar-videos
来るべきプライバシーレイヤーが壊れたウェブをどのように修正するか
ハワード・ウー
https://future.com/a-privacy-layer-for-the-web-can-change-everything/
zkSNARKの紹介
ハワード・ウー、アンナ・ローズと
https://zeroknowledge.fm/38-2/
なぜ、どのように zk-SNARK が機能するのか: 決定的な説明
マクシム・ペトクス
https://arxiv.org/pdf/1906.07221.pdf
ゼロ知識証明の紹介
フレドリック・ハリーソンとアンナ・ローズ
https://www.zeroknowledge.fm/21 [+ 他の場所での要約の書き込み こちら]
Zk-SNARK: ボンネットの下
ヴィタリック・ブテリン
https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
一部1, 一部2, 一部3
分散化された速度 — ゼロ知識証明、分散型ハードウェアの進歩について
エレナ・バーガー
https://a16z.com/2022/04/15/zero-knowledge-proofs-hardware-decentralization-innovation/
最先端のzk研究 — Ethereum Foundation の zk 研究者と
メアリー・マラー、アンナ・ローズ、コビ・グルカンと
https://zeroknowledge.fm/232-2/
zk 研究の探索 — DFINITY の研究部長と。 Groth16のような進歩の背後にもあります
イェンス・グロス、アンナ・ローズ、コビ・グルカンと
https://zeroknowledge.fm/237-2/
SNARKの研究と教育学 — ZCash と Starkware の共同創設者の XNUMX 人と
with アレッサンドロ・キエーザ、アンナ・ローズ
https://zeroknowledge.fm/episode-200-snark-research-pedagogy-with-alessandro-chiesa/
詳細、ビルダー ガイド
確率論的証明の基礎 — インタラクティブプルーフなどからの 5 ユニットを含むコース
アレッサンドロ・キエーザ
https://www.youtube.com/playlist?list=PLGkwtcB-DfpzST-medFVvrKhinZisfluC
STARK — パート I、II、III
ヴィタリック・ブテリン
https://vitalik.ca/general/2017/11/09/starks_part_1.html
https://vitalik.ca/general/2017/11/22/starks_part_2.html
https://vitalik.ca/general/2018/07/21/starks_part_3.html
STARKの解剖学 — STARK プルーフ システムの仕組みを説明する XNUMX 部構成のチュートリアル
アラン・セピエニエク
https://aszepieniec.github.io/stark-anatomy/
SNARKデザイン、パート1 — 調査、ロールアップでの使用など
ジャスティン・セイラー
https://www.youtube.com/watch?v=tg6lKPdR_e4
SNARKデザイン、パート2 — ロールアップ、パフォーマンス、セキュリティ
ジャスティン・セイラー
https://www.youtube.com/watch?v=cMAI7g3UcoI
SNARK パフォーマンスの測定 — フロントエンド、バックエンドなど
ジャスティン・セイラー
https://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/
PLONKを理解する
https://vitalik.ca/general/2019/09/22/plonk.html
PLONKゼロ知識証明システム — PLONK の仕組みに関する 12 の短いビデオのシリーズ
デビッド・ウォン
https://www.youtube.com/playlist?list=PLBJMt6zV1c7Gh9Utg-Vng2V6EYVidTFCC
AIRからRAPへ — PLONK スタイルの算術演算のしくみ
アリエル・ガビゾン
https://hackmd.io/@aztec-network/plonk-arithmetiization-air
PLONK と Plookup でのマルチセット チェック
アリエル・ガビゾン
https://hackmd.io/@arielg/ByFgSDA7D
Halo2 デザイン — ECC から
https://zcash.github.io/halo2/design.html
ポンキー2
https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf
アプリケーションとチュートリアル: 概念実証、デモ、ツールなど
適用された zk — 学習リソース
0xPARCによる
https://learn.0xparc.org/materials/intro
zkSNARKs のオンライン開発環境 — zkREPL、ブラウザー内で Circom ツールスタックと対話するための新しいツール セット
ケビン・クォック
https://zkrepl.dev (+ 説明スレッド こちら)
ゼロからヒーローまでの二次算術プログラム
ヴィタリック・ブテリン
https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649
zkEVM で
アレックス・グルコウスキー、アンナ・ローズと
https://zeroknowledge.fm/175-2/
さまざまなタイプの zkEVM
ヴィタリック・ブテリン
https://vitalik.ca/general/2022/08/04/zkevm.html
ZK 機械学習 — ニューラルネットを SNARK に入れるためのチュートリアルとデモ
ホレス・パン、フランシス・ホー、アンリ・パラッチ著
https://0xparc.org/blog/zk-mnist
ZK言語について
アレックス・オズデミールとアンナ・ローズと
https://zeroknowledge.fm/172-2/
Dark Forest — zk 暗号をゲームに適用する — 完全に分散化された永続的な RTS (リアルタイム戦略) ゲーム
https://blog.zkga.me/announcing-darkforest
エンジニア向けZKP — ダーク フォレスト ZKP を見る
https://blog.zkga.me/df-init-circuit
ゼロ知識へのダイブ
エレナ・ナドリンクスキー、アンナ・ローズ、ジェームズ・プレストウィッチ
https://zeroknowledge.fm/182-2/
zkDocs: ゼロ知識情報共有
サム・ラグスデールとダン・ボネー著
https://a16zcrypto.com/zkdocs-zero-knowledge-information-sharing/
知識証明ゼロのプライバシー保護暗号エアドロップ
サム・ラグスデール
https://a16z.com/2022/03/27/crypto-airdrop-privacy-tool-zero-knowledge-proofs/
オンチェーンの信頼できるセットアップセレモニー -
ヴァレリア・ニコラエンコとサム・ラグスデール
https://a16zcrypto.com/on-chain-trusted-setup-ceremony/
暗号規制、違法金融、プライバシーなど – 規制/コンプライアンスのコンテキストにおけるゼロ知識に関するセクションを含む; 「プライバシー保護」技術と難読化技術の違い
ミケーレ・コーバー、ジャイ・ラマスワミー、ソナル・チョクシ
https://web3-with-a16z.simplecast.com/episodes/crypto-regulations-sanctions-compliance-aml-ofac-news-explained
その他の資料
zkMesh ニュースレター — 最新の分散型プライバシー保護技術、プライバシー プロトコル開発、およびゼロ知識システムを共有する月刊ニュースレター
https://zkmesh.substack.com/
ゼロ知識ポッドキャスト — 最新の zk リサーチと zk アプリケーション、および暗号化対応のプライバシー技術を構築する専門家について
アンナ・ローズと
https://zeroknowledge.fm/
…ジャスティン・セイラーによる、トピックと年表による注釈付きの読書リスト:
リニア PCP からの SNARK (別名、回路固有の設定による SNARK)
短い PCP を使用しない効率的な引数 (2007)
Yuval Ishai、Eyal Kushilevitz、Rafail Ostrovsky 著
2007 年頃までは、SNARK は主に キリアン–ミカリ パラダイム、「短い」確率的にチェック可能な証明 (PCP) を取り、それを「暗号的にコンパイル」して、マークルハッシュとフィアットシャミール変換を介して簡潔な議論にします。 残念ながら、短い PCP は複雑で、今日でも実用的ではありません。 この論文 (IKO) では、準同型暗号を使用して、「長いが構造化された」PCP から簡潔な (透過的ではない) インタラクティブな引数を取得する方法を示しました。 これらは短い PCP よりもはるかに単純であり、結果の SNARK は証明がはるかに短く、検証が高速です。 これらの議論は、実用的な効率の可能性があると最初に認識され、洗練され、実装されました。 コショウ. 残念ながら、IKO の引数には XNUMX 次時間の証明者と XNUMX 次サイズの構造化参照文字列があるため、大規模な計算には対応していません。
二次スパン プログラムと PCP を使用しない簡潔な NIZK (2012)
Rosario Gennaro、Craig Gentry、Bryan Parno、Mariana Raykova著
この画期的な論文 (GGPR) により、IKO のアプローチの証明者のコストが、回路のサイズが XNUMX 次から準線形に削減されました。 の以前の作業に基づいて構築 グロス & リプマー、それはまた、IKOのようなインタラクティブな議論ではなく、ペアリングベースの暗号化を介してSNARKを与えました. それは、算術回路充足可能性の一般化である、現在ランク 1 制約充足 (R1CS) 問題と呼ばれるもののコンテキストでその SNARK を説明しました。
この論文はまた、最初の SNARK の商業展開 (ZCash など) の理論的基礎としても機能し、今日でも人気のある SNARK (Groth16 など) に直接つながりました。 GGPR の引数の最初の実装が入ってきました ザアタール & ピノキオ、およびそれ以降のバリアントには次のものが含まれます C の SNARK & BCTV. BCIOP は、これらの線形 PCP から SNARK への変換を解明する一般的なフレームワークを提供しました (の付録 A も参照)。 ザアタール）およびそのさまざまなインスタンス化について説明します。
ペアリングベースの非対話型引数のサイズについて (2016)
イェンス・グロス
口語的に Groth16 と呼ばれるこの論文は、今日でも最先端の具体的な検証コストを達成する GGPR の SNARK の改良を提示しました (証明は 3 つのグループ要素であり、検証は XNUMX つのペアリング操作によって支配されます。入力が短い)。 セキュリティは、一般的なグループ モデルで証明されています。
普遍的な信頼できるセットアップを備えた SNARK
PlonK: エキュメニカルな非対話的な知識の議論のためのラグランジュ基底の順列 (2019)
アリエル・ガビゾン、ザカリー・ウィリアムソン、オアナ・チョボタル著
Marlin: ユニバーサルで更新可能な SRS を使用した zkSNARK の前処理 (2019)
Alessandro Chiesa、Yuncong Hu、Mary Maller、Pratyush Mishra、Psi Vesely、Nicholas Ward 著
PlonK と Marlin の両方が、Groth16 の回路固有の信頼できるセットアップをユニバーサルなセットアップに置き換えます。 これには、4 倍から 6 倍の大きなプルーフが必要です。 PlonK と Marlin は、Groth16 とその前任者の信頼できるセットアップ中に回路固有の作業を行い、それを発生する前処理フェーズに移動するものと考えることができます。 After SNARK プルーフ生成中と同様に、信頼できるセットアップ。
この方法で任意の回路と R1CS システムを処理する機能は、ホログラフィまたは計算コミットメントと呼ばれることもあり、 スパルタの (この編集の後半で説明します)。 証明の生成中に多くの作業が発生するため、PlonK と Marlin の証明者は、特定の回路または R16CS インスタンスに対して Groth1 よりも遅くなります。 ただし、Groth16 とは異なり、PlonK と Marlin は R1CS よりも一般的な中間表現で動作するようにすることができます。
多項式コミットメント スキーム、SNARK の主要な暗号プリミティブ
多項式とその応用に対する一定サイズのコミットメント (2010)
アニケット・ケイト、グレゴリー・ザヴェルチャ、イアン・ゴールドバーグ著
この論文では、多項式コミットメントスキームの概念を紹介しました。 それは、一定サイズのコミットメントと評価証明を伴う単変数多項式 (一般に KZG コミットメントと呼ばれる) のスキームを提供しました。 この方式では、信頼できる設定 (つまり、構造化された参照文字列) とペアリング ベースの暗号化が使用されます。 これは今日でも実際に非常に人気があり、前述の PlonK や Marlin などの SNARK で使用されています (Groth16 は非常に類似した暗号技術を使用しています)。
高速 Reed-Solomon Interactive Oracle Proofs of Proximity (2017)
イーライ・ベン＝サッソン、イド・ベントフ、イノン・ホレシュ、マイケル・リアブゼフ
リードソロモン テストの対話型オラクル証明 (IOP) を提供します。つまり、コミットされた文字列が XNUMX 変数多項式の評価テーブルに近いことを証明します。 マークル ハッシングと Fiat-Shamir 変換を組み合わせると、多対数サイズの評価証明を含む透明な多項式コミットメント スキームが得られます ( VP19 詳細については）。 今日、これはもっともらしいポスト量子多項式コミットメントスキームの中で最も短いままです。
Ligero: 信頼できるセットアップのない軽量のサブリニア引数 (2017)
Scott Ames、Carmit Hazay、Yuval Ishai、Muthuramakrishnan Venkitasubramaniam 著
FRI と同様に、この作業はリードソロモン テストの IOP を提供しますが、ポリログではなく平方根証明長を使用します。 理論的 作品 Reed-Solomon コードをより高速なエンコーディングを備えた別の誤り訂正コードに交換することにより、さらに任意のフィールドでネイティブに機能する線形時間証明器を取得できることを示しました。 このアプローチは洗練され、実装されています。 ブレーキダウン & オリオン、最先端の証明者のパフォーマンスをもたらします。
Bulletproofs: 機密取引の簡易証明など (2017)
Benedikt Bunz、Jonathan Bootle、Dan Boneh、Andrew Poelstra、Pieter Wuille、Greg Maxwell 著
前の仕事を洗練する BCCGP、Bulletproofsは、対数証明サイズであるが線形検証時間で離散対数を計算することの難しさに基づいて、透明な多項式コミットメントスキーム（実際、内積引数と呼ばれる一般化）を提供します。 このスキームは、その透明性と短い証拠 (たとえば、ZCash Orchard と Monero で使用されている) により、今日でも人気があります。
Dory: 一般化された内積と多項式コミットメントのための効率的で透過的な引数 (2020)
ジョナサン・リー
Dory は、透明性と対数サイズの証明 (Bulletproofs よりも具体的には大きいものの) と透明性を維持しながら、Bulletproofs の検証時間を線形から対数に短縮します。 ペアリングを使用し、SXDH の仮定に基づいています。
対話型証明、複数の証明者による対話型証明、および関連する SNARK
委任計算: マグルのためのインタラクティブな証明 (2008)
Shafi Goldwasser、Yael Tauman Kalai、Guy Rothblum著
この論文以前は、汎用の対話型証明には 超多項式時間 証明者。 この論文では、一般に GKR プロトコルと呼ばれる、効率的な並列アルゴリズムを持つ任意の問題に対して、多項式時間証明器と準線形時間検証器を備えた対話型証明プロトコルを提供します (同様に、対話型証明は深さの小さい任意の算術回路に適用されます)。
インタラクティブな証明のストリーミングによる実用的な検証済みの計算 (2011)
グラハム・コーモード、マイケル・ミッツェンマッハー、ジャスティン・セイラー
この論文（CMTと呼ばれることもあります）は、GKRプロトコルの証明者時間を、回路のサイズのXNUMX次から準線形に短縮しました。 汎用インタラクティブ証明の最初の実装を作成しました。 その後の一連の作品（オールスパイス, ターラー13, 麒麟, 天秤座) は、証明器の実行時間をさらに短縮し、回路のサイズが準線形から線形になりました。
vSQL: 動的外部委託データベースを介した任意の SQL クエリの検証 (2017)
Yupeng Zhang、Daniel Genkin、Jonathan Katz、Dimitrios Papadopoulos、Charalampos Papamanthou 著
タイトルは特定のアプリケーション領域 (データベース) に言及していますが、この論文の貢献はより一般的なものです。 具体的には、インタラクティブな証明を多項式コミットメント スキーム (多線形多項式の場合) と組み合わせることで、回路充足可能性に関する簡潔な議論を得ることができることが観察されました。
後で 作品 レンダリングされた 引数はゼロ知識であり、多線形多項式に異なるコミットメント スキームを導入しました。
Spartan: 信頼できるセットアップを必要としない効率的で汎用的な zkSNARK (2019)
スリナス・セティ
複数の証明者による対話型証明 (MIP) を多項式コミットメント スキームと組み合わせることで、回路充足可能性と R1CS の SNARK を取得します。 クローバー. その効果は、上記の GKR プロトコルなどのインタラクティブな証明から得られるものよりも短い証明で SNARK を取得することです。 PlonK や Marlin と同様に、Spartan は前処理と SNARK 証明生成を介して任意の回路と R1CS システムを処理する方法も示しています。
Spartan は、次の多項式コミットメント スキームを使用しました。 イワダヌキ. と呼ばれるその後の作品 ブレーキダウン & オリオン Spartan の MIP を他の多項式コミットメント スキームと組み合わせて、線形時間証明器で最初に実装された SNARK を生成します。
短い PCP と IOP
Polylog クエリの複雑さを伴う短い PCP (2005)
イーライ・ベン・サッソンとマドゥ・スーダン
この理論的作業により、検証される計算のサイズと多対数クエリ コスト (ただし線形検証時間) で準線形の証明長を持つ最初の確率的にチェック可能な証明 (PCP) が得られました。 PCP の SNARK への Kilian-Micali 変換に続いて、これは準線形時間証明器と多対数時間検証器を備えた SNARK への一歩でした。
その後の理論的研究 検証時間を多対数に短縮しました。 後続の 実際に焦点を当てた研究はこのアプローチを改良しましたが、短い PCP は今日でも実用的ではありません。 実用的な SNARK を取得するには、 後で 作品 回しました 〜へ と呼ばれる PCP のインタラクティブな一般化 インタラクティブなオラクル証明 (IOP)。 これらの取り組みは、その後の発展につながりました。 FREE、このコンパイルの多項式コミットメントセクションで説明されている一般的な多項式コミットメントスキーム。
このカテゴリの他の作品には、 ZKBoo とその子孫。 これらは簡潔な証明を達成しませんが、優れた定数因子を持っているため、小さなステートメントを証明するのに魅力的です。 それらは、次のようなポスト量子署名のファミリーにつながっています。 ピクニック その持っている き 最適化 in いくつかの 作品. ZKBoo は、 MPCインザヘッド、しかしそれはIOPをもたらします。
再帰的SNARK
漸進的に検証可能な計算または知識の証明は、時間/空間効率を意味します (2008)
ポール・ヴァリアント
この作業では、漸進的に検証可能な計算 (IVC) の基本的な概念が導入されました。IVC では、証明者が計算を実行し、これまでの計算が正しかったという証明を常に維持します。 SNARK の再帰的構成を介して IVC を構築しました。 ここで、 知識健全性 SNARK のプロパティは、再帰的に構成された非対話型引数の健全性を確立するために不可欠です。 この論文は、PCP 由来の SNARK に対する非常に効率的な知識抽出ツールも提供しました (Kilian-Micali パラダイムに従って)。
楕円曲線のサイクルによるスケーラブルなゼロ知識 (2014)
Eli Ben-Sasson、Alessandro Chiesa、Eran Tromer、Madars Virza著
フォロー 理論的な仕事、このペーパーでは、GGPR の SNARK のバリアントの再帰的適用を使用して、単純な仮想マシン (TinyRAM、から C の SNARK 紙）。
また、楕円曲線のサイクルの概念も導入されました。これは、楕円曲線暗号を利用する SNARK を再帰的に構成するのに役立ちます。
信頼できるセットアップのない再帰的証明合成 (2019)
ショーン・ボウ、ジャック・グリッグ、ダイラ・ホップウッド著
この作業 (Halo と呼ばれる) は、透過的な SNARK を再帰的に構成する方法を研究しています。 これは、透過的な SNARK での検証手順がはるかに高価になる可能性があるため、透過的でないものを構成するよりも困難です。
これはその後、 ライン of などのシステムで最高潮に達しました。 ノヴァ Groth16 などの不透明な SNARK の構成によって得られるものよりも優れた、最先端の IVC パフォーマンスを達成します。
アプリケーション
Zerocash: ビットコインによる分散型匿名決済 (2014)
Eli Ben Sasson、Alessandro Chiesa、Christina Garman、Matthew Green、Ian Miers、Eran Tromer、Madars Virza
以下を含む以前の作業に基づいて構築 ゼロコイン （と ピノキオコイン 並行作業として)、この論文では、GGPR から派生した SNARK を使用して、プライベート暗号通貨を設計します。 ZCashにつながりました。
Geppetto: 汎用性の高い検証可能な計算 (2014)
Craig Costello、Cedric Fournet、Jon Howell、Markulf Kohlweiss、Benjamin Kreuter、Michael Naehrig、Bryan Parno、Samee Zahur 著
Geppetto はおそらく、プライベート スマート コントラクトの実行への関心が爆発的に高まる前に作成されたものであり、イーサリアムの作成から約 XNUMX 年後に作成されました。 したがって、プライベート スマート コントラクトの実行のコンテキストでは表示されません。 ただし、SNARK の境界深さ再帰を使用して、実行中のプログラムや実行中のデータに関する情報を明らかにすることなく、信頼されていない証明者がプライベート データでプライベート (コミット済み/署名済み) コンピューター プログラムを実行できるようにします。 したがって、これはプライベート スマート コントラクト プラットフォームでの作業の前身です。 ゼセ [以下で説明します]。
検証可能な ASIC (2015)
Riad Wahby、Max Howald、Siddharth Garg、abhi shelat、Michael Walfish 著
このホワイト ペーパーでは、信頼されていないファウンドリで製造された ASIC を安全かつ効果的に使用する方法の問題について考察します (2015 年には、トップ エンドのファウンドリを持つ国は XNUMX つしかありませんでした)。 このアプローチは、高速だが信頼できない ASIC に、低速だが信頼できる ASIC で実行されるベリファイアに対して出力の正確性を証明させることです。 システムの合計実行時間 (つまり、証明者と検証者の実行時間とデータ転送コストの合計) が単純なベースラインよりも短い限り、ソリューションは興味深いものです。 -しかし、信頼できる ASIC。 GKR/CMT/Allspice のインタラクティブな証明の変形を使用して、この論文は、数論変換、パターン マッチング、楕円曲線演算など、多くの基本的な問題について単純なベースラインを実際に上回っています。 この作業は、一部の証明システムが他のシステムよりもハードウェア実装に適していることを示唆しています。 ハードウェア実装のための証明システムの最適化は現在受信中です かなりの 注意、しかし、まだ調査されていないことがたくさんあります。
検証可能 遅延機能 (2018)
Dan Boneh、Joseph Bonneau、Benedikt Bünz、Ben Fisch著
検証可能な遅延関数 (VDF) の表記法を導入しました。これは、ブロックチェーン アプリケーションで広く役立つ暗号化プリミティブです。たとえば、プルーフ オブ ステーク コンセンサス プロトコルの操作の可能性を軽減します。 SNARK (特にインクリメンタルに検証可能な計算用) は、最先端の VDF へのルートを提供します。
Zexe: 分散型プライベート コンピューティングの有効化 (2018)
Sean Bowe、Alessandro Chiesa、Matthew Green、Ian Miers、Pratyush Mishra、および Howard Wu 著
Zexe は、プライベート スマート コントラクト プラットフォームの設計です。 Zexe は Zerocash の拡張機能と見なすことができます (前述)。 Zerocash を使用すると、トークンの送信先、トークンの受信元、転送されるトークンの量などのユーザー データのプライバシーを保護しながら、単一のアプリケーションをオンチェーンで実行できます (ユーザーはトークンを転送できます)。異なるアプリケーション (スマート コントラクト) を同じブロックチェーン上で実行し、相互にやり取りします。 トランザクションはオフチェーンで実行され、正しい実行の証明がオンチェーンに投稿されます。 データのプライバシーが保護されるだけでなく、機能のプライバシーも保護されます。 これは、各トランザクションに関連付けられたプルーフでは、トランザクションがどのアプリケーションに関係するかさえ明らかにしないことを意味します。 Zexe のより一般的なエンジニアリングの貢献は、ペアリング ベースの SNARK の効率的な深さ 12 の構成に役立つ楕円曲線グループである BLS377-1 を導入したことです。
レプリケートされた実行のないレプリケートされたステート マシン (2020)
ジョナサン・リー、キリル・ニキチン、スリナス・セティ著
これは、ブロックチェーンのスケーラビリティのロールアップに関する数少ない学術論文の XNUMX つです。 ロールアップという用語は、学術文献の外で導入された概念より前または同時期に使用されるため、使用しません。
フロントエンド (コンピュータ プログラムから回路充足性、R1CS などの中間表現への効率的な変換)
RAM から委譲可能な簡潔制約充足問題への迅速な削減 (2012)
Eli Ben-Sasson、Alessandro Chiesa、Daniel Genkin、Eran Tromer著
現代の観点から見ると、これは仮想マシン (VM) の抽象化のための実用的なコンピューター プログラムから回路 SAT への変換に関する初期の作業です。 1970 年代後半から 1990 年代までの作品 (例: ロブソン) この論文では、T ステップの VM を実行することから、サイズ O(T*polylog(T)) の回路の充足可能性への決定論的な削減について詳しく説明しています。
その後の論文、例えば、 C の SNARK & BCTV、VM の抽象化によるフロントエンドの開発を続けており、最新のインスタンス化には次のようなプロジェクトが含まれます。 カイロ, RISCゼロ, ポリゴンミデン.
証明に基づいて検証された計算を実用化に数歩近づける (2012)
Srinath Setty、Victor Vu、Nikhil Panpalia、Benjamin Braun、Muqeet Ali、Andrew J. Blumberg、Michael Walfish 著
Ginger と呼ばれるこの論文は、実用的なフロントエンド技術へのもう 1 つの初期の貢献です。 Ginger は、条件文や論理式、ビット分割による比較とビット演算、プリミティブな浮動小数点演算などの一般的なプログラミング プリミティブ用のガジェットを導入しました。これらのガジェットを使用して、高水準言語から低次言語までの最初に実装されたフロントエンドを提供しました。算術制約 (現在 RXNUMXCS として知られているものと同様)、SNARK バックエンドを適用できる中間表現 (IR)。
一方、「Fast Reductions」論文とその子孫は、IR の生成に「CPU エミュレータ」アプローチを使用しています (つまり、IR は、指定されたステップ数に対して CPU の遷移関数を適用することによって、証明者が特定のプログラムを正しく実行したことを強制します)。 、Ginger およびその子孫はより ASIC に似たアプローチを採用し、証明者が正しく実行すると主張するコンピューター プログラムに合わせて調整された IR を生成します。
たとえば、 ビュッフェ このような制御フローを、実行中のプログラムに合わせて調整された有限状態マシンに変換することにより、ASIC モデルで複雑な制御フローを処理できること、およびこのアプローチが汎用 CPU エミュレーターを構築するよりもはるかに効率的であることを示しています。 xJスナーク 多精度演算の効率的な構築、RAM および ROM の最適化を提供し、Java のような高水準言語をプログラマーに公開します。これは今日でも人気があります。 CircC コンピューター プログラムを R1CS にコンパイルすることは、プログラム解析のよく知られた手法と密接に関連していることを観察し、両方のコミュニティのアイデアを組み込んだコンパイラ構築ツールキットを構築します (「回路のような表現のための LLVM」)。 ASIC スタイルのフロントエンドに貢献した初期の作品には、 ピノキオ & ジェペット.
「Fast-Reductions」論文は、いわゆる「ルーティング ネットワーク」と呼ばれる複雑で高価な構造を使用しました。 メモリチェック (つまり、信頼されていない証明者が、その正確性が証明されている VM の実行中、VM のランダム アクセス メモリを正しく維持していることを確認します)。 この選択は、このような初期の作品が PCP を取得しようとしていたために行われました。 両言語で 非インタラクティブで、情報理論的に安全です。 後に呼ばれる作品 パントリー (の前身 ビュッフェ 上記の作業) は、ルーティング ネットワークの代わりにマークル ツリーを使用し、代数的 (つまり、「SNARK に適した」) ハッシュ関数をコンパイルすることで効率を達成しました。 アジタイ、制約に。 これにより、「計算上安全な」フロントエンドが実現しました。 今日、SNARK に適したハッシュ関数に関する大規模な研究文献があり、例として次のようなものがあります。 ポセイドン, MiMC, 強化コンクリート, レスキュー用機材、 もっと。
証明者が RAM を正しく維持していることを確認するための最先端の技術は、少なくとも リプトン (1989) によってメモリチェックに使用されます。 ブルム等。 （1991）。 これらの手法は、本質的に証明者と検証者の間の相互作用を伴いますが、Fiat-Shamir 変換と非対話的にすることができます。 私たちが知る限り、それらは実用的なSNARKフロントエンドに関する文献に、と呼ばれるシステムによって紹介されました。 vRAM.
順列不変のフィンガープリンティング技術は現在、仮想マシンの抽象化のために多くのフロントエンドと SNARK で使用されています。 カイロ. 密接に関連するアイデアは、今日実際に広く使用されている以下の XNUMX つの作品の関連する文脈で再び現れました。
正しいプログラム実行のためのほぼ線形時間のゼロ知識証明 (2018)
Jonathan Bootle、Andrea Cerulli、Jens Groth、Sune Jakobsen、Mary Maller 著
Plookup: ルックアップ テーブルの簡略化された多項式プロトコル (2020)
アリエル・ガビゾンとザカリー・ウィリアムソン著
フロントエンドの初期の作業は、フィールド要素をビットに分割し、これらのビットに対して演算を実行し、次に「パッキング」することによって、回路および関連する IR 内の「非算術」演算 (範囲チェック、ビットごとの演算、整数比較など) を表していました。結果を単一のフィールド要素に戻します。 結果として得られる回路のサイズに関しては、これは操作ごとに対数のオーバーヘッドになります。
上記の XNUMX つの研究 (BCGJM と Plookup) は、償却された意味で回路内のこれらの操作をより効率的に表現するための (いわゆる「ルックアップ テーブル」に基づく) 影響力のある手法を提供します。 大まかに言えば、フロントエンドの設計者によって選択されたパラメータ B について、これらは回路内の各非算術演算を表すのに必要なゲートの数を B の対数係数だけ減らします。長さおよそ B の「アドバイス」ベクトル。
