SNARKと前処理

2024年10月20日 21:10

　今回は、SNARKにはどのような特徴があるのかを前回確認した証明プロトコルに則って確認します。そして前処理の種類と性能について見た後、SNARKを使用するソフトウェアシステムについて大まかな流れをチェックしていきます。

SNARKの特徴

概要の振り返り

No.1の記事の冒頭でも触れた通り、SNARKとは
・Succinct (簡潔)
・Non-interactive (非対話型) $${\to}$$前回のテーマ
・ARgument (証明者の計算能力は有限である)
・Knowledge (知識なしでは証明を生成することは不可能)
の頭文字をとったものです。
これらのなかでもSNARKの特徴でもある簡潔さについて、非対話型証明プロトコルにおいてどのステップが簡潔さに寄与するのでしょうか？

　まずは、前回も登場した非対話型証明プロトコルにおける3つのステップを確認します。

① 前処理：$${S(C) \to (S_p, S_v)}$$
② 証明の生成：$${P(S_p, x, w) \to {\pi}}$$
③ 真偽の判定：$${V(S_v, x, \pi) \to Accept or Reject}$$

この中で簡潔さ(Succinct)に寄与するステップは、主に①です。

回路の圧縮

① 回路$${C}$$を圧縮すること
　公開パラメーター$${S_p, S_v}$$を生成するのは、この前処理の段階で回路Cを要約する意味合いがあります。回路が大規模になったとしても、ここで圧縮しているため、証明$${\pi}$$や検証時間に与える影響は小さくなります。

(参考)
これは以下の式でも確認できます。
・証明$${\pi}$$の計算量：$${|\pi| = o(log(|C|), \lambda)}$$
　$${\lambda}$$はセキュリティパラメーターなので、与える影響は無視できます。回路Cを圧縮したことで、$${|C|}$$ではなく、$${log(|C|)}$$となっているので、回路のサイズが大きくなっても証明の生成に与える影響は比較的小さく抑えられます。このことから、$${\pi}$$は短い証明であることがわかります。
・検証時間$${time(V)}$$の計算量：$${time(V) = o(|x|, log(|C|), {\lambda})}$$
　$${\lambda}$$はセキュリティパラメーターなので、与える影響は無視できます。先ほどと同様、回路Cを圧縮したことで$${log(|C|)}$$となっているので、回路のサイズが大きくなっても検証時間に与える影響は比較的小さく抑えられます。一方入力の$${x}$$については、大きくなると線形で増加し検証時間に与える影響は大きいため、入力データのサイズを小さくすることは必要です。
　　
　前処理がSNARKには不可欠であることを確認しましたが、どのような種類があるのでしょうか？

前処理の種類

　前処理は、大きく3つに分類できます。ここではそれらを、Trusted Setupが必要かどうか、そして回路ごとに生成するかどうかの4象限で整理しています。
　Trusted Setupとは、必要なデータを生成する際に使用した秘密のパラメータが外部に漏れないような仕組みです。ここに関しては、次回以降1本の記事で詳しく解説しますが、今は「多数の参加者で1人だけでも正直に行動すれば全体の秘密が外に漏れることがないような仕組み」と捉えてください。

それぞれの特徴と使用する場面についてみていきます。

3つのSetup

① Trusted setup per circuits
$${S(C ; r) \to public parametes (S_p, S_v)}$$
ここで、使用したrは証明者から秘密にしておくべき値です。もし証明者がrを知ってしまうと、公開パラメータ$${S_p, S_v}$$を生成できてしまい、生合成を崩さずに不正な命題を証明することが可能になってしまうからです。

② Trusted but universal setup
Step1 : $${S_{init}(\lambda ; r) \to pp}$$
Step2 : $${S_{index}(pp, C) \to (S_p, S_v)}$$

　Step1 : 初期セットアップ$${S_{init}}$$
　$${S_{init}(\lambda ; r) \to pp}$$
　ここで使用した$${r}$$は、使用する回路Cから独立したランダムなビットです。この$${r}$$も①同様、証明者から秘密にしておくべき値です。初期セットアップは1度だけ行い、$${pp}$$は複数の異なる回路で使い回します。

　Step2 : インデックスセットアップ$${S_{index}}$$
　$${S_{index}(pp, C) \to (S_p, S_v)}$$
　ここで使用した$${pp}$$は、Step1で生成した値です。ここで使用するのは回路$${C}$$とStep1で生成した$${pp}$$なので、Step1においてランダムビットrの秘密が適切に管理されていれば、Step2では安全な処理が可能になります。またStep1とは異なり、Step2は回路ごとに行います。

③ Transparent setup
$${S(C) \to (S_p, S_v)}$$
①,②と違い、証明者には秘密にしておく値rを使用することなく、公開パラメータを生成します。

　証明者に秘密にする値を使用する回数に注目し、安全性を整理すると以下のようになります。

代表例

ここでは代表的な前処理と、その証明サイズ、検証時間、Trusted Setupの有無についてみていきます。

・$${\pi}$$のサイズについて
　Groth'16とPlonk/Marlinでは回路の規模に依存しない一方、BulletproofsとDARKでは回路の規模の影響は小さいことがわかります。
・$${S_p}$$のサイズについて
　BulletproofsとDARKでは、回路の規模に依存しない一方、Groth'16とPlonk/Marlinでは回路の規模の影響を大きく受けることがわかります。
・検証時間について
　Groth'16とPlonk/Marlinでは回路の規模に依存しない一方、DARKでは回路の規模の影響は小さく、Bulletproofsは回路の規模の影響を大きく受けることがわかります。
・証明時間について
　全て共通して、回路の規模の影響を大きく受けることがわかります。

ここまでSNARKの前処理についてみてきましたが、これらはSNARKのソフトウェアシステムにおいてどの部分に位置する工程なのでしょうか？
次は、SNARKの全体像について見ていきます。

SNARKのソフトウェアシステムの概要

　以下の図では、SNARKのソフトウェアシステムの大きな流れを示しています。

それぞれのステップを見ていきます。
① DSL(ドメイン固有言語)で書かれたプログラム
　SNARKでは、ドメイン固有言語を用いてプログラムが書かれます。2本目の記事で見た算術回路は、このプログラムで表現するものです。
② コンパイル
　①のDSLプログラムをコンパイルすることで、回路$${C}$$の構造を多項式に変換し、SNARKに適した形式として出力します。
③ $${S_p, S_v}$$の生成
　②で得た多項式を用いて、効率的に公開パラメータを生成します。今まで見てきた前処理は、この③に該当します。$${S_p, S_v}$$には、多項式を特定の点で評価するためのデータやラグランジュ係数などが含まれることが多いです。
④ 証明者による証明の生成
　③で生成した公開パラメータ、公開情報$${x}$$、秘密情報$${w}$$を使用して、証明$${\pi}$$を生成します。これには、高い計算コストがかかるため、適切なバックエンドで実行することが求められます。3本目の記事で見た証明プロトコルは、この④に該当します。

　SNARKの大きな特徴の1つに、算術回路を変換した多項式というプロセスがあります。しかし数学的な要素も深く関わるので、次回以降の記事で解説します！

最後に

　今回は、前処理の種類とその特徴、そしてSNARKソフトウェアの流れについて見てきました。また、最後に登場した概略図で、これまで登場した算術回路や証明プロトコル、前処理の3つが、それぞれ全体のどこに位置するかを整理しました。
　次回以降もぜひチェックしてください！

[参照]

　この記事は、『ZK Hack Whiteboard Session1 Module1: What is a SNARK?』の動画の内容を編集し、図や説明を加えたものです。
　ZK Hackとは、ZKに関するビデオやニュースレターの発信や、イベントを開催するコミュニティです。今回のビデオは、Stanford大学のDan Boneh教授によるSNARKの入門動画になります。