Commitmentについて

証明者はcommitをを検証者に送り、commitとメッセージの対応を証明する

PCはある多項式Pに対するコミットメントとみなすことができ、証明者はある点zにおける多項式の値がP(z)＝aを満たすことを、多項式Pを明かすことなく証明することができる

Polynomial Commitment=PC

d次の多項式f(x)は高々d個の解しか持たない性質を利用したものであり、テキトーなsolution:sに対してf(s)=0となる確率は極めて低いと言える

つまり、f(s)=0ならば無視できる確率を除いてf≡0

これにより、多項式のチェックを一点で代用できる

KZG10,IPA,FRI,DARKSについて比較する

table:比較表

FRI KZG IPA DARK(RSA) DARK(Class)

----------------------- ---------------------------- ------------------------------------------- -------------------------------------------- ---------------------------------- ---------------------

Low lebel tech Hash function Paring group Discrete log group Unknown order group ditto

Setup - H hash function - G1,G2 groups - G elliptic curve g^n - N unknown order ditto

- w unity root - g1,g2 generators - independent elements in G - g random in N ditto

- e paring function - q large integer ditto

- s_k serect value in F

Commitment H(f(w^0),..,f(w^n)) (a_0s^0+..._a_ns^n)g_1 a_0g_0+...+a_ng_n (a_0q^0+..._a_dq^d)g

Transparent Yes No Yes No Yes

Sussient Yes Yes No Yes Yes

Post-Quantom Yes No No No No

Proof size O(log^2(d)) O(1) O(log(d)) O(log(d)) ditto

Proof time O(d*log^2(d)) O(d) O(d) O(d) ditto

Verify time O(log^2(d)) O(1) O(log(d)) O(d) ditto

Use case zk-STARKs Groth16,PLONK,Verkle tree Halo2 Supersonic

Pedersen、Bulletproof忘れてた

表から、KZGはProof sizeとVerify timeがともに一定であり、回路の規模が大きくなってもProof sizeが増加しないため、succinctの点で最も優れた方式であると結論づけることができる。

他のPC方式では、Proof sizeが回路規模に関係するため、回路規模が大きくなるとProof sizeも大きくなる

FRIが速いのはペアリング演算を必要とせずにハッシュ関数だけを使い、comptationが少なくて済むから

補足1: zk-STARKs

数学的な安全性の仮定にほとんど依存しない(ハッシュ関数を使うから)ため量子耐性を持つ

Trusted Setupが不要

補足2: Supersonic

RSAの場合、整数因数分解問題（IFP）の仮定に依存するため、Trusted Setupが必要

クラスグループの場合、クラスグループの要素数の計算の難しさに依存するため、trusted setupは不要

SNARKとSTARK

table:Type of computations

Circuit Comptations Machine Computations

Representration Arthmetic circuits Transaction functions

Airthmerization R1CS AIR

Use case SNARKs STARKs

https://scrapbox.io/files/62faf7a0a97a36001fee1819.png

https://scrapbox.io/files/62f5eefc44e6a00023e29272.png

多項式コミットメントの分類

* boundary compilers

* computer science to information theory—oracle encoding

* information theory to cryptographic—instantiation/materialisation

* internal compilers

* code => circuit/RAM program => R1CS => QAP

* within every bucket there are is significant massaging

プログラム(論理回路)を算術演算に落とし込んだ後で暗号学的に非対話性にするのがSNARK

プログラム(論理回路)を算術演算に落とし込んだ後で多項式コミットメントやハッシュ関数を使うのがSTARK

Fiat-Shamir変換はSNARKのNを提供し、多項式オラクルは、SNARKのSを提供する。

2枚目の青(oracleをインスタンス化するプリミティブ)の例

Set—RSA (and class group) accumulator, pairing-based accumulator

Vector—Merkle tree, vector commitment in groups of unknown order

Polynomial proximity—FRI, DEEP-FRI (Reed-Solomon codes)

Polynomial—KZG10, DARK

Inner product—non-universal Kate, bulletproof

コスト面では inner product(内積コミットメント?)が最適に見えるが、実用的ではないらしい

KZGコミットメントはペアリングが可能なので他のスキームに比べて証明も検証も高速だがTrusted Setupが必要

こうやって比較するとFRIがバランス取れてそう。

ここでは言及されてないけどAIRプロトコルはFRIの上位互換という認識でおけ？

λの寄与を明示的に示すことで、より公平に把握することができ、具体的な数値の由来を理解しやすくなる

証明サイズの具体的な数値は再利用が可能で、証明時間と検証時間に対するλの寄与を分解して示すことも可能

量子耐性あるのはFRIだけ

ただし量子オラクルモデルで128ビットの安全性を狙うには、ハッシュ出力を256ビットより大きくする必要がある

参考文献

https://www.youtube.com/watch?v=qUrA97TG2YU