簡潔な非対話型アーギュメント

SNARGとSNARK

Succinct Non-Interactive Argument (SNARG)とは、簡潔性を持つ非対話型アーギュメントです。また、SNARG of Knowledge (SNARK)とは、簡潔性を持つ知識の非対話型アーギュメントです。簡潔性とは、生成される証明のサイズが短いという性質です。SNARKのうちゼロ知識性を持つものをzk-SNARKと呼びます。

簡潔性の嬉しさは、ブロックチェーンと相性が良いことであると前に述べました。ゼロ知識証明システムにブロックチェーンを利用する際、証明のサイズが一定のゼロ知識証明があればどれだけステートメントが複雑であろうとも、証明のサイズにかかる手数料が一定であることが保証されるからです。また、NP問題の検証に必要な計算量が、従来の計算量よりも少ない計算量で行えることができ、ブロックチェーンのスケーラビリティ向上策としても有用です。これらの有用性はブロックチェーンに限らず、SNARG研究においては証明サイズと検証時間の最小化が重視されています。

簡潔性の定義はいくつかあります。例えば、証明サイズがステートメントやウィットネスのサイズに依存する定義や、証明サイズがセキュリティパラメーター \(\lambda\) にのみ依存する定義などです。後者は証明のサイズが \(O(\operatorname{poly}(\lambda))\) になるということで、前者より強い定義です。証明サイズだけでなく、時間計算量を含む定義もあります。

Groth16では、アーギュメントが3つの群の元で構成されており、セキュリティパラメーター \(\lambda\) にのみ依存しています。

前処理型モデルと完全簡潔性

前処理型SNARK（preprocessing SNARK）と呼ばれるものがあります。前処理型SNARKとは、SNARKにおいて共通参照文字列の生成時に重い計算をすることを許すものです。逆に、前処理型SNARKでないSNARKは完全簡潔性がある（fully-succinct）と呼ばれることがあります。

前処理型SNARKにする利点は、検証時の計算効率が上がることです。つまり、前もって時間をかけて準備しておくか、検証時に時間をかけるかでトレードオフがあるということです。