zk-SNARKs

protocol

前提

• クラスP, クラスNP
• NP Hard
  • Circuit-SAT
  • QAP

概要

非対話ゼロ知識証明(NIZK)の1つ.

Succinct Non-interactive ARgument Knowledge

• Succinct: 簡潔, 証明のサイズがステートメントに比べて小さい

• Non-interactive: 非対話型

• ARgument: 証明者の計算能力に限りがある

• Knowledge: 知識無しで証明を生成するのは不可能

• 完全性, 健全性, ゼロ知識性をもつ

アルゴリズム

• $\mathrm{Gen}(1^{\lambda },\mathcal{R})$

  • CRS= $\mathrm{pk},\mathrm{vk}$ が含まれている
    • 評価鍵, 検証鍵

• Prover $P(\mathrm{pk},x,w)$

  • x: ステートメント, w: 証拠を受け取り, 証明 $\pi$ を出力

• Verifier $V(\mathrm{vk},\pi ,x)$: 証明が正しいかをboolで返す

• CRSモデル: 信頼された第三者を介して証明される

検証

Circuit-SAT に対し, witness $w$ をproverに渡すことで
関係 $\mathcal{R}:=\{(x,w)\in {\mathbb{F}}^n\times {\mathbb{F}}^h\}$ に属していればpoly timeで出力が1かを判定できる
-> $w$ のサイズがとても大きく効率悪いので QAP に変換する.

「入出力が正しいか」を「ある多項式を知っているか」に変換

さらに, 多項式をverifierにわたすのはnon-succinctなので, $w$ に対して多項式が恒等的に0かを判定する.
-> 式を展開して係数を確認するのはexp timeなので
Schwartz-Zippleの補題 で評価点で判定することで簡潔性を保つ.

Encoding

多項式や評価点は明らかにしてはいけないので 離散対数問題 性を使ってblind

検証

双線型ペアリング
q-PKE 仮定の元で多項式評価の検証を行う

非対話へ変換

これで Pinocchio Protocol の元で zk-SNARKs の構成ができた.

• 特定条件下で, フィアットシャミア変換 により変換できる

2023-02-16

• Recursive SNARKs
  • GitHub - microsoft/Nova: Nova: Recursive SNARKs without trusted setup

参考文献

• zk-SNARKsの理論
• ゼロ知識証明はいいぞ