Commit-and-Prove ZKs(CnP ZK)

モチベーション

証明者の計算量と通信量の複雑さを緩和するモチベで研究されている。

CnPで構築されたZKは、回路を証明する際に、どの値を忘れ、どの値を保持するかについて柔軟性を提供します。

2つ目の要素は、コミットメントを使ってメモリを「再利用」するという考え方である。 コミットメントスキームと計算回路が与えられた場合、各ゲートに対して、証明者は常にワイヤ値にコミットし、すべてのコミットメントが正しくオープンできることを証明し、オープンされた値が特定の関係を満たすことを証明することができる。すべてのZKプロトコルはCnP ZKにすることもできるが、これには余分なコストがかかる。 特に、この一般的なアプローチはゲートごとに行われるため、計算コストがかかる。

https://scrapbox.io/files/67553fdfb4f94358980ebd6a.png

CnPのアイデアはこの計算コストを抑えるためにリサイクルする点にある。あるワイヤが計算で不要になれば、パーティはそのワイヤのコミットメントをメモリから削除することができる。 これが、CnPスキームがメモリをリサイクルできる理由である。

BineingとHidingに加えてコミットメントのもう1つの暗黙の特性は、コミットメントが不要になった場合、例えば、コミットメントがオープンされたり、この値に関連する計算が検証されたりした場合、当事者は、コミットメント値を格納するために使用される空間を割り当て解除できることである。 これは、ゼロ知識証明（ZKP）スキームの空間複雑度を改善するために重要である。

CnP ZKはコミットメントを備えたゼロ知識証明である。 通常のZKプロトコルでは、証明者がwitness wを入力し、両者が関数fと公開入力xを入力すると、プロトコルは検証者にf(x, w)を明らかにする。 対照的に、CnP ZKでは、プロトコルで使われる前に、証明者はそのwitnessにコミットする。プロトコル全体を通して、回路の計算をゲート1つずつ証明していく。

このプロトコルは、ゲートの計算を証明するとき、その入力ワイヤーはすでにコミットされ、正しいことが証明されているという不変性を維持する。 これは通常の証明に比べて余分なステップのように見えるが、ZKプロトコルの実行において、どの配線を「記憶」し、どの配線を「忘却」するかを決めることができる。

次のゲートに進むには、証明者はゲートの出力ワイヤーにコミットし、小さなZKPプロトコルを実行して、コミットされた入力値を参照して、コミットされた出力値が正しいことを証明しなければならない。 コミットされたワイヤの値が不要になれば、今後ゲートがこのワイヤを入力として使用することはないため、その値と関連するコミットを忘れることができる。

コミットされたワイヤを忘れることができるため、不要になったワイヤのための空間を再利用しながら、回路計算を証明することができる。 コミットして証明するZKプロトコルは、基礎となるコミットメントが "deallocation "を許可している限り、これをサポートする。

例

https://scrapbox.io/files/67554a5a111dc6acb0c69c34.png

Circuit representation of an ℓ-bit adder and a full adder

例えばl=3の時の処理は以下のようになる。

code:l=3

% s{1…4} <- 3-bit–adder(x{1…3}, y{1…3},c1) :

t1 = XOR(x1, c1)

t2 = XOR(y1, c1)

t3 = AND(t1, t2)

c2 = XOR(t3, c1)

s1 = XOR(x1, t2)

t4 = XOR(x2, c2)

t5 = XOR(y2, c2)

t6 = AND(t4, t5)

c3 = XOR(t6, c2)

s2 = XOR(x2, t3)

t7 = XOR(x3, c3)<

t8 = XOR(y3, c3)

t9 = AND(t7, t8)

c4 = XOR(t9, c4)

s3 = XOR(x3, t4)

中間値を保持するために9つのwireが必要となる。回路を評価する場合、どの配線もいつでも必要になる可能性があるため、回路サイズに線形なメモリが必要となりうる。

メモリが入力文のゲート/制約の数に線形であることである。 これは通常、これらのプロトコルが計算全体を平坦化回路にエンコードし、それらを少数のコミットメントに置く必要があるためである。IOPのようなスキームでは不要な値を削除できると考えられる

以下に、すべてのコミットメントを保持せずに回路のすべてのゲートを証明する表を示す。 特に、右の列には、覚えておく必要がある、アクティブでコミットされたワイヤをすべて示している。

随所にForgetが入ってる

table:adder(l=2)

% s{1…3} <- 2-bit–adder (x1, x2, y1, y2, c1 ): Commitments

1st adder

(x1, x2, y1, y2, c1)

Prove t1 = XOR(x1, c1) (x1, x2, y1, y2, c1, t1)

Prove t2 = XOR(y1, c1) (x1, x2, y1, y2, c1, t1, t2)

Forget commitment y1 (x1, x2, y2, c1, t1, t2)

Prove t3 = AND(t1, t2) (x1, x2, y2, c1, t1, t2, t3)

Forget commitment t1 (x1, x2, y2, c1, t2, t3)

Prove c2 = XOR(t3, c1) (x1, x2, y2, c1, t2, t3, c2)

Forget commitments t3, c1 (x1, x2, y2, t2, c2)

Prove s1 = XOR(x1, t2) (x1, x2, y2, t2, c2, s1)

Forget commitments x1, t2 (x2, y2, c2, s1)

2nd adder

Prove t4 = XOR(x2, c2) (x2, y2, c2, s1, t4)

Prove t5 = XOR(y2, c2) (x2, y2, c2, s1, t4, t5)

Forget commitment y2 (x2, c2, s1, t4, t5)

Prove t6 = AND(t4, t5) (x2, c2, s1, t4, t5, t6)

Forget commitments t4, t5 (x2, c2, s1, t6)

Prove s3 = XOR(t6, c2) (x2, c2, s1, t6, s3)

Forget commitments t6, c2 (x2, s1, s3)

Prove s2 = XOR(x2, t3) (x2, s1, s3, s2)

Forget commitment x2 (x2, s1, s3, s2)

非効率ではあるものの、任意のzk protocolにCnPを適応させることが可能らしい

参考