Halo2 学习笔记——设计之Proving system之Circuit commitments（3）

1. 引言

在创建proof之前，Prover有a table of cell assignments that it claims satisfy the constraint system。该table具有 n = 2 k n=2^k n=2k行，可分为 advice columns、instance columns 以及 fixed columns。 将第 i i i个fixed column中的第 j j j行的assignment定义为 F i , j F_{i,j} Fi,j​，同理，定义advice 和 instance assignment为 A i , j A_{i,j} Ai,j​。 【注意，此处将fixed column assignment 与advice/instance column assignment区分的主要原因是：fixed columns由Verifier提供，而advice columns和instance columns 由Prover提供。实际上，instance column 和 fixed column的commitment均由Prover和Verifier计算，仅advice commitment会存储在proof中。】

为了对这些assignment进行commit，需为每列构建degree n − 1 n-1 n−1 Lagrange polynomials，基于的evaluation domain size 为 n n n（其中 ω \omega ω为 n n n-th primitive root of unity）：

• a i ( X ) a_i(X) ai​(X) interpolates such that a i ( ω j ) = A i , j a_i(\omega^j) = A_{i,j} ai​(ωj)=Ai,j​.
• f i ( X ) f_i(X) fi​(X) interpolates such that f i ( ω j ) = F i , j f_i(\omega^j) = F_{i,j} fi​(ωj)=Fi,j​.

然后为每列的polynomial创建blinding commitment： A = [ Commit ( a 0 ( X ) ) , … , Commit ( a i ( X ) ) ] \mathbf{A} = [\text{Commit}(a_0(X)), \dots, \text{Commit}(a_i(X))] A=[Commit(a0​(X)),…,Commit(ai​(X))] F = [ Commit ( f 0 ( X ) ) , … , Commit ( f i ( X ) ) ] \mathbf{F} = [\text{Commit}(f_0(X)), \dots, \text{Commit}(f_i(X))] F=[Commit(f0​(X)),…,Commit(fi​(X))]

F \mathbf{F} F会作为key generation的一部分生成，使用的blinding factor为 1 1 1。 A \mathbf{A} A由Prover构建并发送给Verifier。

2. Committing to the lookup permutations

1）首先，Verifier提供sampling challenge θ \theta θ 用于keep individual columns within lookups independent。

2）然后，Prover commits to the permutations for each lookup：

• 已知a lookup 具有 input column polynomials [ A 0 ( X ) , … , A m − 1 ( X ) ] [A_0(X), \dots, A_{m-1}(X)] [A0​(X),…,Am−1​(X)] 和 table column polynomials [ S 0 ( X ) , … , S m − 1 ( X ) ] [S_0(X), \dots, S_{m-1}(X)] [S0​(X),…,Sm−1​(X)]，Prover会构建2个压缩的多项式： A compressed ( X ) = θ m − 1 A 0 ( X ) + θ m − 2 A 1 ( X ) + ⋯ + θ A m − 2 ( X ) + A m − 1 ( X ) A_\text{compressed}(X) = \theta^{m-1} A_0(X) + \theta^{m-2} A_1(X) + \dots + \theta A_{m-2}(X) + A_{m-1}(X) Acompressed​(X)=θm−1A0​(X)+θm−2A1​(X)+⋯+θAm−2​(X)+Am−1​(X) S compressed ( X ) = θ m − 1 S 0 ( X ) + θ m − 2 S 1 ( X ) + ⋯ + θ S m − 2 ( X ) + S m − 1 ( X ) S_\text{compressed}(X) = \theta^{m-1} S_0(X) + \theta^{m-2} S_1(X) + \dots + \theta S_{m-2}(X) + S_{m-1}(X) Scompressed​(X)=θm−1S0​(X)+θm−2S1​(X)+⋯+θSm−2​(X)+Sm−1​(X)

• Prover会根据 lookup argument的rules 来 permutes A compressed ( X ) A_\text{compressed}(X) Acompressed​(X) 和 S compressed ( X ) S_\text{compressed}(X) Scompressed​(X)。

3）Prover为所有的lookups创建blinding commitments，并将相应的blinding commitments发送给Verifier。 L = [ ( Commit ( A ′ ( X ) ) ) , Commit ( S ′ ( X ) ) ) , …   ] \mathbf{L} = \left[ (\text{Commit}(A'(X))), \text{Commit}(S'(X))), \dots \right] L=[(Commit(A′(X))),Commit(S′(X))),…]

4）Verifier收到 A \mathbf{A} A， F \mathbf{F} F 和 L \mathbf{L} L之后，发送将用于permutation argument和lookup argument中的random challenges β , γ \beta,\gamma β,γ。（因为2个argument是独立的，因此可复用 β , γ \beta,\gamma β,γ。）

3. Committing to the equality constraint permutation

令 c c c为the number of columns that are enabled for equality constraints。

令 m m m为可容纳于column set 中的maximum number of columns，该值不会超过 PLONK配置的polynomial degree bound。

令 u u u为定义在 Permutation argument 中的 number of “usable” rows。

令 b = c e i l i n g ( c / m ) b = \mathsf{ceiling}(c/m) b=ceiling(c/m)。

1）Prover构建长度为 b u bu bu 的 vector P \mathbf{P} P，对于每一个column set 0 ≤ a < b 0\leq a