ゼロ知識証明プロトコルLigero

Ligeroは、証明者が秘密の値を知っていることを、その秘密の値を明らかにすることなく検証者に納得させるゼロ知識証明プロトコルの一種↓

eprint.iacr.org

スキームの仕組みについて、SHA-256のプリイメージを知っていることを証明するユースケースで見ていく。証明者はy = SHA256(x)となるプリイメージxを知っていることをxを明かさずに検証者に納得させる。

セットアップ

まず、SHA256を加算ゲートと乗算ゲートで構成される算術回路として表現する（SHA256自体はビット演算が主体なので、本来ブール回路の方が適している*1、*2）。

セットアップした回路の定義は検証者と共有する。回路化して共有するのは他のゼロ知識証明プロトコルでも同様。尚、LigeroはTrusted Setupが不要なスキーム。

証明プロセス

実際に証明をする場合、証明者はプリイメージxをビット列として扱い回路に入力し、witnessを得る。witnessは、プリメージxに加えて、すべての中間計算値と最終出力が含まれるデータ。つまり計算が正しく行われたことの証拠となるSHA256計算の完全な実行トレース。

続いて、witnessをリード・ソロモン符号でエンコードする。 ${witness = (w_0, ..., w_n)}$ とすると、 witnessの各値を有限体上で定義された多項式の係数として表現する。つまり ${f(X) = w_0 + w_1X + w_2X^{2} + ... + w_nX^{n}}$ のような多項式。

そして、多項式を8n個*3の評価点 ${\alpha_1, \alpha_2, ..., \alpha_{8n}}$ で評価し、評価値 ${f(\alpha_1), f(\alpha_2), ..., f(\alpha_{8n})}$ を得る。

ただ、回路のゲート数は何万個にもなり、それを次数とするような巨大な多項式を構成すると計算コストが非常に高くなるため、次数nを次数が ${\sqrt{n}}$ となる ${\sqrt{n}}$ 個のブロックの多項式に分割する。たとえば、n = 25,000, ${\sqrt{n} = 158}$ の場合は、

${f_0(X) = w_0 + w_1X + ... + w_{157}X^{157}}$
${f_1(X) = w_{158} + w_{159}X + ... + w_{315}X^{157}}$
...

のような多項式に変換する。このように大きなwitnessを複数の小さな多項式に分割する（複数のリードソロモン符号の組み合わせた）構造をインターリーブド構造と呼んでいる。インターリーブドというのは、

多項式\評価点	${\alpha_1}$	${\alpha_2}$	...	${\alpha_{1264}}$
${f_0}$	${f_0(\alpha_{1})}$	${f_0(\alpha_{2})}$	...	${f_0(\alpha_{1264})}$
${f_1}$	${f_1(\alpha_{1})}$	${f_1(\alpha_{2})}$	...	${f_1(\alpha_{1264})}$
${f_2}$	${f_2(\alpha_{1})}$	${f_2(\alpha_{2})}$	...	${f_2(\alpha_{1264})}$
...	...	...	...	...
${f_{157}}$	${f_{157}(\alpha_{1})}$	${f_{157}(\alpha_{2})}$	...	${f_{157}(\alpha_{1264})}$

のように、評価点 ${\alpha_i}$ に対する各評価値を織り交ぜて配置し、検証時に列単位でアクセスすることが由来みたい。

このように多項式を分割することで、並列計算が可能になるので、実際の計算時間を短縮できる。

エンコードができたら、続いて各評価値を使ってマークルツリーを構成する。リーフは評価点 ${\alpha_i}$ を使って各多項式を評価した値 ${(f_0(\alpha_i), f_1(\alpha_i), ..., f_{157}(\alpha_i))}$ を連結してハッシュした値。

        root
       /    \
      /      \
   hash₁    hash₂
   /  \     /  \
  /    \   /    \
f(α₁) f(α₂) f(α₃) f(α₄) ...

証明者はこのマークルルートを検証者に送信する。

マークルルートを受け取った検証者は、証明者との対話的なやりとりを通じて証明の正しさを確認していく。

線形結合チャレンジ

検証者は回路内の各ゲートにより正しく計算された結果であることを検証する。

回路には数万個の加算、乗算ゲートがあるが、これにはそれぞれ以下の制約がある。a、bを入力、cを出力とした場合、

加算ゲート：a + b - c = 0
乗算ゲート：a * b - c = 0

回路の情報は予め検証者に共有されているので、回路内の各制約については検証者にとっても既知だが、その制約を満たす具体的な値は知らず、制約の構造に基づいて証明者に対してランダムチャレンジを行う。

その際に、これらの制約がすべて成立しているかを個別にチェックするのは非効率的なので、線型結合を使って1つの制約に圧縮する。例えば、3つの制約をそれぞれ ${C_1, C_2, C_3}$ とすると、ランダムな係数 ${r_1, r_2, r_3}$ を選択した場合、 ${LC = r_1 \times C_1 + r_2 \times C_2 + r_3 \times C_3}$ と圧縮し、LC = 0となることを示す。

ただ、Ligeroでは、線型結合はインターリーブド・リード・ソロモン符号と組み合わされる。ここでは、検証者はランダムな係数 ${(r_1, ..., r_{158})}$ を生成し、証明者に送信する。これらの値の個数は、↑の行列の行数に相当する。

証明者は、受け取った係数を使って、各評価点 ${\alpha_i}$ について線形結合する。これは、例えば ${\alpha_1}$ については、 ${r_1 \times f_0(\alpha_1) + r_2 \times f_1(\alpha_1) + r_3 \times f_2(\alpha_1) + ... + r_{158} \times f_{157}(\alpha_1)}$ を計算することを意味する。これを全評価点分計算し、検証者に送信する。

※ ただ、上記の各多項式はwitnessの値を係数として埋め込んだ状態なので、上記のような制約を直接検証することができない。そこで制約を検証できるように元のwitnessの行列の射影行列を別途用意し、証明者もそれらに追加でコミットする必要があり、検証者もその射影行列を用いた制約の検証を行う必要がある。この辺りまだよく分かってない。

ランダムチャレンジ

検証者は、マークツリー内のランダムなリーフの位置をt個*4選択する。

証明者は選択された各位置のリーフiに対して、

各評価点での評価値 ${f_0(\alpha_i), f_1(\alpha_i), ..., f_{157}(\alpha_i)}$ と
それが以前送信したマークルルートに含まれていることを証明するマークルプルーフ

を検証者に送信する。

検証者は、

開示された評価値がコミットされたデータかどうか、マークルプルーフを検証し、
開示された値を使って、線型結合を計算し、証明者が送信した値と一致するか検証する。これはt個のリーフiに対して、 ${r_1 \times f_0(\alpha_i) + ... + r_{158} \times f_{157}(\alpha_i)}$ を計算し、それが線形結合チャレンジで証明者が送信した値と一致するか検証することを意味する。この線型結合の一致をチェックすることで、評価値が低次多項式の評価値として妥当かどうかも多項式を復元することなくチェックできるみたい。
最後に最終的な出力がハッシュ値と一致することを確認する。これは、検証者のランダムなチャレンジとは別に明示的に証明者が対象の評価値を開示することで行われるものと思われる。

すべてのチェックをパスすれば、証明者が正しいwitness（つまり、SHA256のプリイメージ）を知っていることを高い確率で確信できる。

というのがざっくりとしたLigeroのスキーム。↑は対話型の記述になってるけど、Fiat-Shamir変換により非対話型になる。

ゼロ知識性

証明者が提供するのは、

回路の実行トレース（witness）から生成したインターリーブド・リード・ソロモン符号のコミットメント（マークルルート）
ランダムに選択された位置の評価値のリストと
それがコミットしたツリー内に含まれていることのマークルプルーフ

証明者が嘘つく場合、正しい実行トレースが作れず、リード・ソロモン符号の性質により多くの位置で不整合が発生し、検証者によるランダムチェックで高確率で補足される。

一方、検証者は、ランダムな位置の評価値（全体の中のごく一部）しか確認できず、そのデータから元の多項式（witness）を復元することはできないため、その途中の値からプリイメージを逆算することはできない。また個々の制約もランダムな係数による線形結合によりマスキングされており、制約の情報も隠蔽される。

特徴

Trusted Setupが不要
証明のサイズは、回路のサイズnに対して ${O(\sqrt{n})}$
（ ${2^{-40}}$ の健全性を担保するSHA256のプリイメージの検証だと約35KB）
証明コストは、O(n)。ただ、zk-SNARKsとかと比較すると、ハッシュ関数やリード・ソロモン符号などの軽量な処理で済む分速いとか。
検証コストは、 ${O(\sqrt{n})}$
ハッシュ関数の安全性にのみ依存しているため、量子安全