Skip to article frontmatterSkip to article content

缺失的协议 PH23-PCS（三）

本文给 PH23-KZG10 协议加上对 Zero-knowledge 的支持。

1. 如何支持 ZK

为了让 PH23-KZG10 协议支持 ZK，我们需要修改两个部分的协议，一是要在 KZG10 子协议中支持 Hiding，即在任何一次 Evaluation 证明中，都不会泄漏除了求值之外的信息；二是确保在 PH23 协议中，不会泄漏 Witness 向量，即 a⃗\vec{a} 的信息。

首先我们需要一个 Perfect Hiding KZG10 协议，它可以保证多项式在每一次打开后，都不会泄漏多项式除多项式求值之外的其它信息。下面是 [KT23] 中的的 KZG10 协议，其主要思想来源于 [PST13]，[ZGKPP17]，与 [XZZPS19]。

Hiding KZG10

SRS=([1]1,[τ]1,[τ2]1,[τ3]1,…,[τD]1,[γ]1,[1]2,[τ]2,[γ]2)SRS = ([1]_1, [\tau]_1, [\tau^2]_1, [\tau^3]_1, \ldots, [\tau^D]_1, {\color{red}[\gamma]_1}, [1]_2, [\tau]_2, {\color{red}[\gamma]_2})
(1)

一个多项式 f(X)∈F[X]f(X)\in\mathbb{F}[X] 的承诺定义为：

Cf=KZG.Commit(f(X);ρf)=f0⋅[1]1+f1⋅[τ]1+⋯+fd⋅[τd]1+ρf⋅[γ]1C_f=\mathsf{KZG.Commit}(f(X);\rho_f) = f_0 \cdot [1]_1 + f_1 \cdot [\tau]_1 + \cdots + f_d \cdot [\tau^d]_1 + {\color{blue}\rho_f} \cdot {\color{red}[\gamma]_1}
(2)

根据多项式环的性质，f(X)f(X) 可以分解为：

f(X)=q(X)⋅(X−z)+f(z)f(X) = q(X)\cdot(X-z) + f(z)
(3)

那么商多项式的承诺计算如下，同样需要一个 Blinding Factor ρq{\color{blue}\rho_q} 来保护 q(X)q(X) 的承诺。

Q=KZG.Commit(q(X);ρq)=q0⋅[1]1+q1⋅[τ]1+⋯+qd⋅[τd−1]1+ρq⋅[γ]1=[q(τ)]1+ρq⋅[γ]1\begin{aligned} Q = \mathsf{KZG.Commit}(q(X); {\color{blue}\rho_q}) & = q_0 \cdot [1]_1 + q_1 \cdot [\tau]_1 + \cdots + q_d \cdot [\tau^{d-1}]_1 + {\color{blue}\rho_q} \cdot {\color{red}[\gamma]_1} \\ & = [q(\tau)]_1 + {\color{blue}\rho_q}\cdot{\color{red}[\gamma}]_1 \end{aligned}
(4)

同时 Prover 还要计算下面一个额外的 G1\mathbb{G}_1 元素，用来配平验证公式：

E=ρf⋅[1]1−ρq⋅[τ]1+(ρq⋅z)⋅[1]1\color{blue}E = \rho_f \cdot [1]_1 - \rho_q \cdot [\tau]_1 + (\rho_q\cdot z)\cdot [1]_1
(5)

那么 Evaluation 证明由两个 G1\mathbb{G}_1 元素组成：

π=(Q,E)\pi = (Q, {\color{blue}E})
(6)

于是，Verifier 可以通过下面的公式来验证：

e(Cf−f(z)⋅[1]1, [1]2)=e(Q, [τ]2−z⋅[1]2)+e(E, [γ]2)e\Big(C_f - f(z)\cdot[1]_1,\ [1]_2\Big) = e\Big(Q,\ [\tau]_2 - z\cdot[1]_2\Big) + {\color{blue}e\Big(E,\ {\color{red}[\gamma]_2}\Big)}
(7)

求和证明的 ZK

在 Prover 采用累加多项式 z(X)z(X) 来证明求和值的过程中，也会泄漏 z⃗\vec{z} 向量的信息，其中也包括了 Witness a⃗\vec{a} 的信息。因此，我们需要一个 ZK 版本的求和证明协议。

我们有一个阶为 NN 的乘法子群 H⊂FH\subset\mathbb{F}：

H=(1,ω,ω2,…,ωN−1)H=(1, \omega, \omega^2, \ldots, \omega^{N-1})
(8)

我们记 {Li(X)}i=0N−1\{L_i(X)\}_{i=0}^{N-1} 关于 HH 的 Lagrange 多项式， vH(X)=XN−1v_H(X)=X^N-1 是 HH 上的消失多项式。

假设有一个 NN 个元素的向量 a⃗=(a0,a1,…,aN−1)\vec{a}=(a_0, a_1, \ldots, a_{N-1})，我们希望证明 ∑iai=v\sum_i a_i = v。Prover 实现计算了 a⃗\vec{a} 的承诺，记为 CaC_a。

Ca=KZG10.Commit(a(X);ρa)=[a(τ)]1+ρa⋅[γ]1C_a = \mathsf{KZG10.Commit}(a(X); {\color{blue}\rho_a}) = [a(\tau)]_1 + {\color{blue}\rho_a\cdot[\gamma]_1}
(9)

Round 1

首先，我们要确定在 z(X)z(X) 会被打开几次，比如，z(X)z(X) 会被在 ζ\zeta 和 ω−1⋅ζ\omega^{-1}\cdot\zeta 两处打开。那么我们引入一个随机的多项式：r(X)r(X)，

r(X)=r0⋅L0(X)+r1⋅L1(X)+r2⋅L2(X)+r3⋅L3(X)r(X) = r_0\cdot L_0(X) + r_1\cdot L_1(X) + r_2\cdot L_2(X) + r_3\cdot L_3(X)
(10)

这个多项式包含四个随机因子。为什么是四个？我们后面会看到。

Prover 然后计算 r(X)r(X) 的承诺，并引入一个额外的 Blinding Factor ρr{\color{blue}\rho_r} ：

Cr=KZG10.Commit(r(X);ρr)=[r(τ)]1+ρr⋅[γ]1C_r = \mathsf{KZG10.Commit}(r(X); {\color{blue}\rho_r}) = [r(\tau)]_1 + {\color{blue}\rho_r\cdot[\gamma]_1}
(11)

Prover 计算一个新的求和 ∑iri\sum_i r_i:

vr=r0+r1+r2+r3v_r = r_0 + r_1 + r_2 + r_3
(12)

Prover 发送 CrC_r 与 vrv_r 给 Verifier。

Round 2

Verifier 发送一个随机挑战数 β←$F\beta\leftarrow_{\$}\mathbb{F} 给 Prover。

Prover 构造一个新的多项式 a′(X)a'(X)，满足

a′(X)=a(X)+β⋅r(X){\color{blue}a'(X) = a(X) + \beta\cdot r(X)}
(13)

Prover 发送给 Verifier一个混合的求和值 v′v':

v′=vr+β⋅v{\color{blue}v' = v_r + \beta\cdot v}
(14)

这时，Prover 和 Verifier 把求和证明的目标 ∑iai=v\sum_i a_i=v 转换成 ∑i(ai+β⋅ri)=v+β⋅vr\sum_i (a_i + \beta\cdot r_i) = v + \beta\cdot v_r。

Round 3

Verifier 再发送一个随机数 α←$F\alpha\leftarrow_{\$}\mathbb{F} 给 Prover。

Prover 构造约束多项式 h0(X),h1(X),h2(X)h_0(X), h_1(X), h_2(X)，满足

h0(X)=L0(X)⋅(z(X)−a(X))h1(X)=(X−1)⋅(z(X)−z(ω−1⋅X)−a(X))h2(X)=LN−1(X)⋅(z(X)−v)\begin{split} h_0(X) &= L_0(X)\cdot\big(z(X) - a(X) \big) \\ h_1(X) &= (X-1)\cdot\big(z(X)-z(\omega^{-1}\cdot X)-a(X)\big) \\ h_2(X) & = L_{N-1}(X)\cdot\big( z(X) - v \big) \\ \end{split}
(15)

Prover 构造多项式 h(X)h(X)，满足

h(X)=h0(X)+α⋅h1(X)+α2⋅h2(X)\begin{split} h(X) &= h_0(X) + \alpha \cdot h_1(X) + \alpha^2 \cdot h_2(X) \end{split}
(16)

Prover 计算商多项式 t(X)t(X)，满足

h(X)=t(X)⋅vH(X)h(X) =t(X)\cdot v_H(X)
(17)

Prover 计算 z(X)z(X) 的承诺 CzC_z，并发送 CzC_z

Cz=KZG10.Commit(z(X);ρz)=[z(τ)]1+ρz⋅[γ]1C_z = \mathsf{KZG10.Commit}(z(X); \rho_z) = [z(\tau)]_1 + {\color{blue}\rho_z\cdot[\gamma]_1}
(18)

Prover 计算 t(X)t(X) 的承诺 CtC_t，并发送 CtC_t

Ct=KZG10.Commit(t(X);ρt)=[t(τ)]1+ρt⋅[γ]1C_t = \mathsf{KZG10.Commit}(t(X); \rho_t) = [t(\tau)]_1 + {\color{blue}\rho_t\cdot[\gamma]_1}
(19)

Round 4

Verifier 发送随机求值点 ζ←$F\zeta\leftarrow_{\$}\mathbb{F}

Prover 构造 商多项式 qa(X)q_{a}(X), qz(X)q_z(X), qt(X)q_t(X) 与 qz′(X)q'_z(X), 满足

qa(X)=a′(X)−a′(ζ)X−ζq_{a}(X) = \frac{a'(X) - a'(\zeta)}{X-\zeta}
(20)
qt(X)=t(X)−t(ζ)X−ζq_t(X) = \frac{t(X) - t(\zeta)}{X-\zeta}
(21)
qz(X)=z(X)−z(ζ)X−ζq_z(X) = \frac{z(X) - z(\zeta)}{X-\zeta}
(22)
qz′(X)=z(X)−z(ω−1⋅ζ)X−ω−1⋅ζq'_z(X) = \frac{z(X) - z(\omega^{-1}\cdot\zeta)}{X-\omega^{-1}\cdot\zeta}
(23)

Prover 计算四个商多项式的承诺，并引入相应的 Blinding Factor ρqa,ρqz,ρqt,ρqz′{\color{blue}\rho_{q_a}}, {\color{blue}\rho_{q_z}}, {\color{blue}\rho_{q_t}}, {\color{blue}\rho_{q'_z}}

Qa=KZG10.Commit(qa(X);ρqa)=[qa(τ)]1+ρqa⋅[γ]1Qz=KZG10.Commit(qz(X);ρqz)=[qz(τ)]1+ρqz⋅[γ]1Qt=KZG10.Commit(qt(X);ρqt)=[qt(τ)]1+ρqt⋅[γ]1Qz′=KZG10.Commit(qz′(X);ρqz′)=[qz′(τ)]1+ρqz′⋅[γ]1\begin{split} Q_{a} &= \mathsf{KZG10.Commit}(q_{a}(X); {\color{blue}\rho_{q_{a}}}) = [q_{a}(\tau)]_1 + {\color{blue}\rho_{q_{a}}\cdot[\gamma]_1} \\ Q_z &= \mathsf{KZG10.Commit}(q_z(X); {\color{blue}\rho_{q_z}}) = [q_z(\tau)]_1 + {\color{blue}\rho_{q_z}\cdot[\gamma]_1} \\ Q_t &= \mathsf{KZG10.Commit}(q_t(X); {\color{blue}\rho_{q_t}}) = [q_t(\tau)]_1 + {\color{blue}\rho_{q_t}\cdot[\gamma]_1} \\ Q'_z &= \mathsf{KZG10.Commit}(q'_z(X); {\color{blue}\rho_{q'_z}}) = [q'_z(\tau)]_1 + {\color{blue}\rho_{q'_z}\cdot[\gamma]_1} \\ \end{split}
(24)

Prover 还要构造四个相应的 Blinding Factor 的承诺，并发送给 Verifier：

Ea=(ρa+β⋅ρr)⋅[1]1−ρqa⋅[τ]1+(ρqa⋅ζ)⋅[1]1Ez=ρz⋅[1]1−ρqz⋅[τ]1+(ρqz⋅ζ)⋅[1]1Et=ρt⋅[1]1−ρqt⋅[τ]1+(ρqt⋅ζ)⋅[1]1Ez′=ρz⋅[1]1−ρqz′⋅[τ]1+(ρqz′⋅ω−1⋅ζ)⋅[1]1\begin{split} E_a &= (\rho_{a} + \beta\cdot\rho_{r})\cdot[1]_1 - \rho_{q_a}\cdot[\tau]_1 + (\rho_{q_a}\cdot\zeta)\cdot[1]_1 \\ E_z &= \rho_{z}\cdot[1]_1 - \rho_{q_z}\cdot[\tau]_1 + (\rho_{q_z}\cdot\zeta)\cdot[1]_1 \\ E_t &= \rho_{t}\cdot[1]_1 - \rho_{q_t}\cdot[\tau]_1 + (\rho_{q_t}\cdot\zeta)\cdot[1]_1 \\ E'_z &= \rho_{z}\cdot[1]_1 - \rho_{q'_z}\cdot[\tau]_1 + (\rho_{q'_z}\cdot\omega^{-1}\cdot\zeta)\cdot[1]_1 \\ \end{split}
(25)

这里可以看到，在证明过程中，Prover 需要在四个多项式上进行求值，并且这四个多项式的求值都会泄漏 a⃗\vec{a} 的信息，因此 Prover 在 Round 1 增加一个包含两个额外随机因子的随机多项式 r(X)r(X)。这样证明过程中的多项式求值都在 a′(X)a'(X) 上进行，而非直接对 a(X)a(X) 运算求值。

Proof

π=(Cr,vr,Cz,Ct,a′(ζ),z(ζ),t(ζ),z(ω−1⋅ζ),Qa,Qz,Qt,Qz′,Ea,Ez,Et,Ez′)\pi = (C_r, v_r, C_z, C_t, a'(\zeta), z(\zeta), t(\zeta), z(\omega^{-1}\cdot\zeta), Q_a, Q_z, Q_t, Q'_z, E_a, E_z, E_t, E'_z)
(26)

Verification

Verifier 首先验证下面的等式：

h(ζ)=t(ζ)⋅vH(ζ)h(\zeta) = t(\zeta)\cdot v_H(\zeta)
(27)

其中 vH(ζ)v_H(\zeta) 由 Verifier 计算，h(ζ)h(\zeta) 由下面的等式计算：

h(ζ)=L0(ζ)⋅(z(ζ)−a′(ζ))+α⋅(ζ−1)⋅(z(ζ)−z(ω−1⋅ζ)−a′(ζ))+α2⋅LN−1(ζ)⋅(z(ζ)−(vr+β⋅v))\begin{aligned} h(\zeta) &= L_0(\zeta)\cdot\big(z(\zeta) - a'(\zeta) \big) \\ &+ \alpha\cdot(\zeta-1)\cdot\big(z(\zeta)-z(\omega^{-1}\cdot\zeta)-a'(\zeta)\big) \\ &+ \alpha^2\cdot L_{N-1}(\zeta)\cdot\big( z(\zeta) - (v_r + \beta\cdot v) \big) \end{aligned}
(28)

然后 Verifier 验证 a′(ζ),z(ζ),t(ζ),z(ω−1⋅ζ)a'(\zeta), z(\zeta), t(\zeta), z(\omega^{-1}\cdot\zeta) 正确性：

e(Ca′−a′(ζ)⋅[1]1, [1]2)=e(Qa, [τ]2−ζ⋅[1]2)+e(Ea, [γ]2)e(Cz−z(ζ)⋅[1]1, [1]2)=e(Qz, [τ]2−ζ⋅[1]2)+e(Ez, [γ]2)e(Ct−t(ζ)⋅[1]1, [1]2)=e(Qt, [τ]2−ζ⋅[1]2)+e(Et, [γ]2)e(Cz−(ω−1⋅ζ)⋅[1]1, [1]2)=e(Qz′, [τ]2−ω−1⋅ζ⋅[1]2)+e(Ez′, [γ]2)\begin{aligned} e\Big(C_{a'} - a'(\zeta)\cdot[1]_1,\ [1]_2\Big) &= e\Big(Q_a,\ [\tau]_2 - \zeta\cdot[1]_2\Big) + e\Big(E_a,\ [\gamma]_2\Big) \\ e\Big(C_z - z(\zeta)\cdot[1]_1,\ [1]_2\Big) &= e\Big(Q_z,\ [\tau]_2 - \zeta\cdot[1]_2\Big) + e\Big(E_z,\ [\gamma]_2\Big) \\ e\Big(C_t - t(\zeta)\cdot[1]_1,\ [1]_2\Big) &= e\Big(Q_t,\ [\tau]_2 - \zeta\cdot[1]_2\Big) + e\Big(E_t,\ [\gamma]_2\Big) \\ e\Big(C_z - (\omega^{-1}\cdot\zeta)\cdot[1]_1,\ [1]_2\Big) &= e\Big(Q'_z,\ [\tau]_2 - \omega^{-1}\cdot\zeta\cdot[1]_2\Big) + e\Big(E'_z,\ [\gamma]_2\Big) \\ \end{aligned}
(29)

2. ZK-PH23-KZG10 协议（优化版）

下面是完整的支持 Zero-knowledge 的 PH23-KZG10 协议。

Precomputation

  1. 预计算 s0(X),…,sn−1(X)s_0(X),\ldots, s_{n-1}(X) and vH(X)v_H(X)
vH(X)=XN−1v_H(X) = X^N -1
(30)
si(X)=vH(X)vHi(X)=XN−1X2i−1s_i(X) = \frac{v_H(X)}{v_{H_i}(X)} = \frac{X^N-1}{X^{2^i}-1}
(31)
  1. 预计算 D=(1,ω,ω2,…,ω2n−1)D=(1, \omega, \omega^2, \ldots, \omega^{2^{n-1}}) 上的 Bary-Centric Weights {w^i}\{\hat{w}_i\}。这个可以加速
w^j=∏l≠j1ω2j−ω2l\hat{w}_j = \prod_{l\neq j} \frac{1}{\omega^{2^j} - \omega^{2^l}}
(32)
  1. 预计算 Lagrange Basis 的 KZG10 SRS A0=[L0(τ)]1,A1=[L1(τ)]1,A2=[L2(τ)]1,…,AN−1=[L2n−1(τ)]1A_0 =[L_0(\tau)]_1, A_1= [L_1(\tau)]_1, A_2=[L_2(\tau)]_1, \ldots, A_{N-1} = [L_{2^{n-1}}(\tau)]_1

Commit 计算过程

  1. Prover 构造一元多项式 a(X)a(X)，使其 Evaluation form 等于 a⃗=(a0,a1,…,aN−1)\vec{a}=(a_0, a_1, \ldots, a_{N-1})，其中 ai=f~(bits(i))a_i = \tilde{f}(\mathsf{bits}(i)), 为 f~\tilde{f} 在 Boolean Hypercube {0,1}n\{0,1\}^n 上的取值。
a(X)=a0⋅L0(X)+a1⋅L1(X)+a2⋅L2(X)+⋯+aN−1⋅LN−1(X)a(X) = a_0\cdot L_0(X) + a_1\cdot L_1(X) + a_2\cdot L_2(X) + \cdots + a_{N-1}\cdot L_{N-1}(X)
(33)

  1. Prover 抽样一个随机数 ρa←$F\rho_a\leftarrow_{\$}\mathbb{F}，用来保护 a⃗\vec{a} 的承诺。

  2. Prover 计算 f^(X)\hat{f}(X) 的承诺 CaC_a，并发送 CaC_a

Ca=a0⋅A0+a1⋅A1+a2⋅A2+⋯+aN−1⋅AN−1+ρa⋅[γ]1=[f^(τ)]1+ρa⋅[γ]1C_{a} = a_0\cdot A_0 + a_1\cdot A_1 + a_2\cdot A_2 + \cdots + a_{N-1}\cdot A_{N-1} + {\color{blue}\rho_a\cdot[\gamma]_1} = [\hat{f}(\tau)]_1 + {\color{blue}\rho_a\cdot[\gamma]_1}
(34)

其中 A0=[L0(τ)]1,A1=[L1(τ)]1,A2=[L2(τ)]1,…,AN−1=[L2n−1(τ)]1A_0 =[L_0(\tau)]_1, A_1= [L_1(\tau)]_1, A_2=[L_2(\tau)]_1, \ldots, A_{N-1} = [L_{2^{n-1}}(\tau)]_1 ，在预计算过程中已经得到。

Evaluation 证明协议

Common inputs

  1. Ca=[f^(τ)]1C_a=[\hat{f}(\tau)]_1: the (uni-variate) commitment of f~(X0,X1,…,Xn−1)\tilde{f}(X_0, X_1, \ldots, X_{n-1})
  2. u⃗=(u0,u1,…,un−1)\vec{u}=(u_0, u_1, \ldots, u_{n-1}): 求值点
  3. v=f~(u0,u1,…,un−1)v=\tilde{f}(u_0,u_1,\ldots, u_{n-1}): MLE 多项式 f~\tilde{f} 在 X⃗=u⃗\vec{X}=\vec{u} 处的运算值。

回忆下证明的多项式运算的约束：

f~(u0,u1,u2,…,un−1)=v\tilde{f}(u_0, u_1, u_2, \ldots, u_{n-1}) = v
(35)

这里 u⃗=(u0,u1,u2,…,un−1)\vec{u}=(u_0, u_1, u_2, \ldots, u_{n-1}) 是一个公开的挑战点。

Round 1.

Prover:

  1. 计算向量 c⃗\vec{c}，其中每个元素 ci=eq∼(bits(i),u⃗)c_i=\overset{\sim}{eq}(\mathsf{bits}(i), \vec{u})

  2. 构造多项式 c(X)c(X)，其在 HH 上的运算结果恰好是 c⃗\vec{c} 。

c(X)=∑i=0N−1ci⋅Li(X)c(X) = \sum_{i=0}^{N-1} c_i \cdot L_i(X)
(36)
  1. 计算 c(X)c(X) 的承诺 Cc=[c(τ)]1C_c= [c(\tau)]_1，并发送 CcC_c
Cc=KZG10.Commit(c⃗)=[c(τ)]1C_c = \mathsf{KZG10.Commit}(\vec{c}) = [c(\tau)]_1
(37)

  1. 构造一个 Blinding 多项式 r(X)=r0⋅L0(X)+r1⋅L1(X)\color{blue}r(X) = r_0\cdot L_0(X) + r_1\cdot L_{1}(X)，其中 {r0,r1}←$F2\{r_0, r_1\}\leftarrow_{\$}\mathbb{F}^2 是随机抽样的 Blinding Factor。

  2. 计算 r(X)\color{blue}r(X) 的承诺 Cr=[r(τ)]1C_r = [\color{blue}r(\tau)]_1，并发送 CrC_r

Cr=KZG10.Commit(r(X);ρr)=[r(τ)]1+ρr⋅[γ]1C_r = \mathsf{KZG10.Commit}({\color{blue}r(X)}; \rho_r) = [\color{blue}r(\tau)]_1 + \rho_r\cdot[\gamma]_1
(38)
  1. 计算 vr=⟨r⃗,c⃗⟩\color{blue} v_r = \langle \vec{r}, \vec{c}\rangle，并发送 vrv_r，其中 r⃗\vec{r} 定义如下：
r⃗∈FN=(r0,r1,0,⋯ ,0)\vec{r}\in\mathbb{F}^{N} = (r_0, r_1, 0, \cdots, 0)
(39)

Round 2.

Verifier: 发送挑战数 α,β←$Fp2\alpha, {\color{blue}\beta}\leftarrow_{\$}\mathbb{F}^2_p

Prover:

  1. 构造关于 c⃗\vec{c} 的约束多项式 p0(X),…,pn(X)p_0(X),\ldots, p_{n}(X)
p0(X)=s0(X)⋅(c(X)−(1−u0)(1−u1)...(1−un−1))pk(X)=sk−1(X)⋅(un−k⋅c(X)−(1−un−k)⋅c(ω2n−k⋅X)),k=1…n\begin{split} p_0(X) &= s_0(X) \cdot \Big( c(X) - (1-u_0)(1-u_1)...(1-u_{n-1}) \Big) \\ p_k(X) &= s_{k-1}(X) \cdot \Big( u_{n-k}\cdot c(X) - (1-u_{n-k})\cdot c(\omega^{2^{n-k}}\cdot X)\Big) , \quad k=1\ldots n \end{split}
(40)
  1. 把 {pi(X)}\{p_i(X)\} 聚合为一个多项式 p(X)p(X)
p(X)=p0(X)+α⋅p1(X)+α2⋅p2(X)+⋯+αn⋅pn(X)p(X) = p_0(X) + \alpha\cdot p_1(X) + \alpha^2\cdot p_2(X) + \cdots + \alpha^{n}\cdot p_{n}(X)
(41)
  1. 构造 a′(X)\color{blue}a'(X) ，并计算 ⟨a⃗′,c⃗⟩=v′\color{blue}\langle \vec{a}', \vec{c}\rangle=v'
a′(X)=a(X)+β⋅r(X)\color{blue}a'(X) = a(X) + \beta\cdot r(X)
(42)
  1. 构造累加多项式 z(X)z(X)，满足
z(1)=a0′⋅c0z(ωi)−z(ωi−1)=a′(ωi)⋅c(ωi),i=1,…,N−1z(ωN−1)=v′\begin{split} z(1) &= {\color{blue}a'_0}\cdot c_0 \\ z(\omega_{i}) - z(\omega_{i-1}) &= {\color{blue}a'(\omega_{i})}\cdot c(\omega_{i}), \quad i=1,\ldots, N-1 \\ z(\omega^{N-1}) &= {\color{blue}v'} \\ \end{split}
(43)
  1. 构造约束多项式 h0(X),h1(X),h2(X)h_0(X), h_1(X), h_2(X)，满足
h0(X)=L0(X)⋅(z(X)−c0⋅a′(X))h1(X)=(X−1)⋅(z(X)−z(ω−1⋅X)−a′(X)⋅c(X))h2(X)=LN−1(X)⋅(z(X)−v′)\begin{split} h_0(X) &= L_0(X)\cdot\big(z(X) - c_0\cdot {\color{blue}a'(X)} \big) \\ h_1(X) &= (X-1)\cdot\big(z(X)-z(\omega^{-1}\cdot X)- {\color{blue}a'(X)}\cdot c(X)) \\ h_2(X) & = L_{N-1}(X)\cdot\big( z(X) - {\color{blue}v'} \big) \\ \end{split}
(44)
  1. 把 p(X)p(X) 和 h0(X),h1(X),h2(X)h_0(X), h_1(X), h_2(X) 聚合为一个多项式 h(X)h(X)，满足
h(X)=p(X)+αn+1⋅h0(X)+αn+2⋅h1(X)+αn+3⋅h2(X)\begin{split} h(X) &= p(X) + \alpha^{n+1} \cdot h_0(X) + \alpha^{n+2} \cdot h_1(X) + \alpha^{n+3} \cdot h_2(X) \end{split}
(45)
  1. 计算 Quotient 多项式 t(X)t(X)，满足
h(X)=t(X)⋅vH(X)h(X) =t(X)\cdot v_H(X)
(46)
  1. 抽样 ρt,ρz←$Fp2\rho_t, \rho_z\leftarrow_{\$}\mathbb{F}^2_p，计算 Ct=[t(τ)]1+ρt⋅[γ]1C_t=[t(\tau)]_1+{\color{blue}\rho_t\cdot[\gamma]_1}， Cz=[z(τ)]1+ρz⋅[γ]1C_z=[z(\tau)]_1+{\color{blue}\rho_z\cdot[\gamma]_1}，并发送 CtC_t 和 CzC_z
Ct=KZG10.Commit(t(X);ρt)=[t(τ)]1+ρt⋅[γ]1Cz=KZG10.Commit(z(X);ρz)=[z(τ)]1+ρz⋅[γ]1\begin{split} C_t &= \mathsf{KZG10.Commit}(t(X); {\color{blue}\rho_t}) = [t(\tau)]_1 + {\color{blue}\rho_t\cdot[\gamma]_1} \\ C_z &= \mathsf{KZG10.Commit}(z(X); {\color{blue}\rho_z}) = [z(\tau)]_1 + {\color{blue}\rho_z\cdot[\gamma]_1} \end{split}
(47)

Round 3.

Verifier: 发送随机求值点 ζ←$F\zeta\leftarrow_{\$}\mathbb{F}

Prover:

  1. 计算 si(X)s_i(X) 在 ζ\zeta 处的取值：
s0(ζ),s1(ζ),…,sn−1(ζ)s_0(\zeta), s_1(\zeta), \ldots, s_{n-1}(\zeta)
(48)

这里 Prover 可以快速计算 si(ζ)s_i(\zeta) ，由 si(X)s_i(X) 的公式得

si(ζ)=ζN−1ζ2i−1=(ζN−1)(ζ2i+1)(ζ2i−1)(ζ2i+1)=ζN−1ζ2i+1−1⋅(ζ2i+1)=si+1(ζ)⋅(ζ2i+1)\begin{aligned} s_i(\zeta) & = \frac{\zeta^N - 1}{\zeta^{2^i} - 1} \\ & = \frac{(\zeta^N - 1)(\zeta^{2^i} +1)}{(\zeta^{2^i} - 1)(\zeta^{2^i} +1)} \\ & = \frac{\zeta^N - 1}{\zeta^{2^{i + 1}} - 1} \cdot (\zeta^{2^i} +1) \\ & = s_{i + 1}(\zeta) \cdot (\zeta^{2^i} +1) \end{aligned}
(49)

因此 si(ζ)s_i(\zeta) 的值可以通过 si+1(ζ)s_{i + 1}(\zeta) 计算得到，而

sn−1(ζ)=ζN−1ζ2n−1−1=ζ2n−1+1s_{n-1}(\zeta) = \frac{\zeta^N - 1}{\zeta^{2^{n-1}} - 1} = \zeta^{2^{n-1}} + 1
(50)

因此可以得到一个 O(n)O(n) 的算法来计算 si(ζ)s_i(\zeta) ，并且这里不含除法运算。计算过程是：sn−1(ζ)→sn−2(ζ)→⋯→s0(ζ)s_{n-1}(\zeta) \rightarrow s_{n-2}(\zeta) \rightarrow \cdots \rightarrow s_0(\zeta) 。

  1. 定义求值 Domain D′D', 包含 n+1n+1 个元素：
D′=Dζ={ζ,ωζ,ω2ζ,ω4ζ,…,ω2n−1ζ}D'=D\zeta = \{\zeta, \omega\zeta, \omega^2\zeta,\omega^4\zeta, \ldots, \omega^{2^{n-1}}\zeta\}
(51)
  1. 计算并发送 c(X)c(X) 在 D′D' 上的取值
c(ζ),c(ζ⋅ω),c(ζ⋅ω2),c(ζ⋅ω4),…,c(ζ⋅ω2n−1)c(\zeta), c(\zeta\cdot\omega), c(\zeta\cdot\omega^2), c(\zeta\cdot\omega^4), \ldots, c(\zeta\cdot\omega^{2^{n-1}})
(52)

  1. 计算并发送 z(ω−1⋅ζ)z(\omega^{-1}\cdot\zeta)

  2. 计算 Linearized Polynomial lζ(X)l_\zeta(X)

lζ(X)=(s0(ζ)⋅(c(ζ)−c0)+α⋅s0(ζ)⋅(un−1⋅c(ζ)−(1−un−1)⋅c(ω2n−1⋅ζ))+α2⋅s1(ζ)⋅(un−2⋅c(ζ)−(1−un−2)⋅c(ω2n−2⋅ζ))+⋯+αn−1⋅sn−2(ζ)⋅(u1⋅c(ζ)−(1−u1)⋅c(ω2⋅ζ))+αn⋅sn−1(ζ)⋅(u0⋅c(ζ)−(1−u0)⋅c(ω⋅ζ))+αn+1⋅(L0(ζ)⋅(z(X)−c0⋅a′(X))+αn+2⋅(ζ−1)⋅(z(X)−z(ω−1⋅ζ)−c(ζ)⋅a′(X))+αn+3⋅LN−1(ζ)⋅(z(X)−v′)−vH(ζ)⋅t(X) )\begin{split} l_\zeta(X) =& \Big(s_0(\zeta) \cdot (c(\zeta) - c_0) \\ & + \alpha\cdot s_0(\zeta) \cdot (u_{n-1}\cdot c(\zeta) - (1-u_{n-1})\cdot c(\omega^{2^{n-1}}\cdot\zeta))\\ & + \alpha^2\cdot s_1(\zeta) \cdot (u_{n-2}\cdot c(\zeta) - (1-u_{n-2})\cdot c(\omega^{2^{n-2}}\cdot\zeta)) \\ & + \cdots \\ & + \alpha^{n-1}\cdot s_{n-2}(\zeta)\cdot (u_{1}\cdot c(\zeta) - (1-u_{1})\cdot c(\omega^2\cdot\zeta))\\ & + \alpha^n\cdot s_{n-1}(\zeta)\cdot (u_{0}\cdot c(\zeta) - (1-u_{0})\cdot c(\omega\cdot\zeta)) \\ & + \alpha^{n+1}\cdot (L_0(\zeta)\cdot\big(z(X) - c_0\cdot {\color{blue}a'(X)})\\ & + \alpha^{n+2}\cdot (\zeta - 1)\cdot\big(z(X)-z(\omega^{-1}\cdot\zeta)-c(\zeta)\cdot {\color{blue}a'(X)} ) \\ & + \alpha^{n+3}\cdot L_{N-1}(\zeta)\cdot(z(X) - {\color{blue}v'}) \\ & - v_H(\zeta)\cdot t(X)\ \Big) \end{split}
(53)

显然，rζ(ζ)=0r_\zeta(\zeta)= 0，因此这个运算值不需要发给 Verifier，并且 [rζ(τ)]1[r_\zeta(\tau)]_1 可以由 Verifier 自行构造。

  1. 构造多项式 c∗(X)c^*(X)，它是下面向量在 DζD\zeta 上的插值多项式
αn+1L0(ζ)(ρz−c0⋅ρa)+αn+2(ζ−1)(ρz−c(ζ)⋅ρa)+αn+3LN−1(ζ)⋅ρz−vH(ζ)⋅ρt\alpha^{n+1}L_0(\zeta)(\rho_z - c_0\cdot\rho_a) \\ +\alpha^{n+2}(\zeta-1)(\rho_z - c(\zeta)\cdot\rho_a) \\ + \alpha^{n+3}L_{N-1}(\zeta)\cdot \rho_z \\ - v_H(\zeta)\cdot\rho_t
(54)
c∗⃗=(c(ω⋅ζ),c(ω2⋅ζ),c(ω4⋅ζ),…,c(ω2n−1⋅ζ),c(ζ))\vec{c^*}= \Big(c(\omega\cdot\zeta), c(\omega^2\cdot\zeta), c(\omega^4\cdot\zeta), \ldots, c(\omega^{2^{n-1}}\cdot\zeta), c(\zeta)\Big)
(55)

Prover 可以利用事先预计算的 DD 上的Bary-Centric Weights {w^i}\{\hat{w}_i\} 来快速计算 c∗(X)c^*(X)，

c∗(X)=c0∗⋅w^0X−ωζ+c1∗⋅w^1X−ω2ζ+⋯+cn∗⋅w^nX−ω2nζw^0X−ωζ+w^1X−ω2ζ+⋯+w^nX−ω2nζc^*(X) = \frac{c^*_0 \cdot \frac{\hat{w}_0}{X-\omega\zeta} + c^*_1 \cdot \frac{\hat{w}_1}{X-\omega^{2}\zeta} + \cdots + c^*_n \cdot \frac{\hat{w}_n}{X-\omega^{2^n}\zeta}}{ \frac{\hat{w}_0}{X-\omega\zeta} + \frac{\hat{w}_1}{X-\omega^2\zeta} + \cdots + \frac{\hat{w}_n}{X-\omega^{2^n}\zeta} }
(56)

这里 w^j\hat{w}_j 为预计算的值：

w^j=∏l≠j1ω2j−ω2l\hat{w}_j = \prod_{l\neq j} \frac{1}{\omega^{2^j} - \omega^{2^l}}
(57)
  1. 因为 lζ(ζ)=0l_\zeta(\zeta)= 0，所以存在 Quotient 多项式 qζ(X)q_\zeta(X) 满足
qζ(X)=1X−ζ⋅lζ(X)q_\zeta(X) = \frac{1}{X-\zeta}\cdot l_\zeta(X)
(58)
  1. 计算 qζ(X)q_\zeta(X) 的承诺 QζQ_\zeta，并同时抽样一个随机数 ρq←$F{\color{blue}\rho_q}\leftarrow_{\$}\mathbb{F} 作为承诺的 Blinding Factor：
Qζ=KZG10.Commit(qζ(X);ρq)=[qζ(τ)]1+ρq⋅[γ]1Q_\zeta = \mathsf{KZG10.Commit}(q_\zeta(X); {\color{blue}\rho_q}) = [q_\zeta(\tau)]_1 + {\color{blue}\rho_q\cdot[\gamma]_1}
(59)
Eζ=(αn+1L0(ζ)(ρz−c0⋅(ρa+β⋅ρr))+αn+2(ζ−1)(ρz−c(ζ)⋅(ρa+β⋅ρr))+αn+3LN−1(ζ)⋅ρz−vH(ζ)⋅ρt)⋅[1]1−ρq⋅[τ]1+(ζ⋅ρq)⋅[1]1{\color{blue} \begin{split} E_\zeta &= \big(\alpha^{n+1}L_0(\zeta)(\rho_z - c_0\cdot(\rho_a + \beta\cdot\rho_r)) \\ & \quad +\alpha^{n+2}(\zeta-1)(\rho_z - c(\zeta)\cdot(\rho_a + \beta\cdot\rho_r)) \\ & \quad + \alpha^{n+3}L_{N-1}(\zeta)\cdot \rho_z - v_H(\zeta)\cdot\rho_t\big)\cdot [1]_1 \\ &- \rho_q\cdot[\tau]_1 + (\zeta\cdot\rho_q)\cdot[1]_1 \\ \end{split}}
(60)
  1. 构造 DζD\zeta 上的消失多项式 zDζ(X)z_{D_{\zeta}}(X)
zDζ(X)=(X−ζω)⋯(X−ζω2n−1)(X−ζ)z_{D_{\zeta}}(X) = (X-\zeta\omega)\cdots (X-\zeta\omega^{2^{n-1}})(X-\zeta)
(61)
  1. 构造 Quotient 多项式 qc(X)q_c(X) :
qc(X)=(c(X)−c∗(X))(X−ζ)(X−ωζ)(X−ω2ζ)⋯(X−ω2n−1ζ)q_c(X) = \frac{(c(X) - c^*(X))}{(X-\zeta)(X-\omega\zeta)(X-\omega^2\zeta)\cdots(X-\omega^{2^{n-1}}\zeta)}
(62)
  1. 计算 qc(X)q_c(X) 的承诺 QcQ_c 与 EcE_c，由于 c(X)c(X) 中不含有任何私有信息，所以不需要添加 Blinding Factor:
Qc=KZG10.Commit(qc(X))=[qc(τ)]1Q_c = \mathsf{KZG10.Commit}(q_c(X)) = [q_c(\tau)]_1
(63)
  1. 构造 Quotient 多项式 qωζ(X)q_{\omega\zeta}(X)，用来证明 z(X)z(X) 在 ω−1⋅ζ\omega^{-1}\cdot\zeta 处的取值：
qωζ(X)=z(X)−z(ω−1⋅ζ)X−ω−1⋅ζq_{\omega\zeta}(X) = \frac{z(X) - z(\omega^{-1}\cdot\zeta)}{X - \omega^{-1}\cdot\zeta}
(64)
  1. 计算 qωζ(X)q_{\omega\zeta}(X) 的承诺 QωζQ_{\omega\zeta}，并同时抽样一个随机数 ρq′←$F{\color{blue}\rho_{q}'}\leftarrow_{\$}\mathbb{F} 作为承诺的 Blinding Factor：
Qωζ=KZG10.Commit(qωζ(X);ρq′)=[qωζ(τ)]1+ρq′⋅[γ]1Q_{\omega\zeta} = \mathsf{KZG10.Commit}(q_{\omega\zeta}(X); {\color{blue}\rho_{q}'}) = [q_{\omega\zeta}(\tau)]_1 + {\color{blue}\rho_{q}'\cdot[\gamma]_1}
(65)
Eωζ=ρz⋅[1]1−ρq′⋅[τ]1+(ω−1⋅ζ⋅ρq′)⋅[1]1{\color{blue}E_{\omega\zeta} = \rho_z\cdot[1]_1 - \rho_{q}'\cdot[\tau]_1 + (\omega^{-1}\cdot\zeta\cdot\rho_{q}')\cdot[1]_1}
(66)
  1. 发送 (Qc,Qζ,Eζ,Qωζ,Eωζ)\big(Q_c, Q_\zeta, {\color{blue}E_\zeta}, Q_{\omega\zeta}, {\color{blue}E_{\omega\zeta}} \big)

Round 4.

  1. Verifier 发送第二个随机挑战点 ξ←$F\xi\leftarrow_{\$}\mathbb{F}

  2. Prover 构造第三个 Quotient 多项式 qξ(X)q_\xi(X)

    qξ(X)=c(X)−c∗(ξ)−zDζ(ξ)⋅qc(X)X−ξq_\xi(X) = \frac{c(X) - c^*(\xi) - z_{D_\zeta}(\xi)\cdot q_c(X)}{X-\xi}
    (67)

  3. Prover 计算并发送 qξ(X)q_\xi(X) 的承诺 QξQ_\xi

    Qξ=KZG10.Commit(qξ(X))=[qξ(τ)]1Q_\xi = \mathsf{KZG10.Commit}(q_\xi(X)) = [q_\xi(\tau)]_1
    (68)

证明表示

9⋅G19\cdot\mathbb{G}_1, (n+1)⋅F(n+1)\cdot\mathbb{F}

πeval=(z(ω−1⋅ζ),c(ζ),c(ω⋅ζ),c(ω2⋅ζ),c(ω4⋅ζ),…,c(ω2n−1⋅ζ),Cc,Ct,Cz,Qc,Qζ,Eζ,Qξ,Qωζ,Eωζ)\begin{split} \pi_{eval} &= \big(z(\omega^{-1}\cdot\zeta), c(\zeta), c(\omega\cdot\zeta), c(\omega^2\cdot\zeta), c(\omega^4\cdot\zeta), \ldots, c(\omega^{2^{n-1}}\cdot\zeta), \\ & C_{c}, C_{t}, C_{z}, Q_c, Q_\zeta, {\color{blue}E_\zeta}, Q_\xi, Q_{\omega\zeta}, {\color{blue}E_{\omega\zeta}}\big) \end{split}
(69)

验证过程

  1. Verifier 计算 Ca′\color{blue}C'_a 与 v′\color{blue} v'
    Ca′=Ca+β⋅Cb\color{blue}C'_a = C_a + \beta \cdot C_b
    (70)
v′=v+β⋅vb\color{blue} v' = v + \beta \cdot v_b
(71)
  1. Verifier 计算 c∗(ξ)c^*(\xi) 使用预计算的 Barycentric Weights {w^i}\{\hat{w}_i\}
    c∗(ξ)=∑iciwiξ−xi∑iwiξ−xic^*(\xi)=\frac{\sum_i c_i\frac{w_i}{\xi-x_i}}{\sum_i \frac{w_i}{\xi-x_i}}
    (72)
  2. Verifier 计算 vH(ζ),L0(ζ),LN−1(ζ)v_H(\zeta), L_0(\zeta), L_{N-1}(\zeta)
    vH(ζ)=ζN−1v_H(\zeta) = \zeta^N - 1
    (73)
L0(ζ)=1N⋅zH(ζ)ζ−1L_0(\zeta) = \frac{1}{N}\cdot \frac{z_{H}(\zeta)}{\zeta-1}
(74)
LN−1(ζ)=ωN−1N⋅zH(ζ)ζ−ωN−1L_{N-1}(\zeta) = \frac{\omega^{N-1}}{N}\cdot \frac{z_{H}(\zeta)}{\zeta-\omega^{N-1}}
(75)

  1. Verifier 计算 s0(ζ),…,sn−1(ζ)s_0(\zeta), \ldots, s_{n-1}(\zeta) ，其计算方法可以采用前文提到的递推方式进行计算。

  2. Verifier 计算线性化多项式的承诺 ClC_l

    Cl=((c(ζ)−c0)s0(ζ)+α⋅(un−1⋅c(ζ)−(1−un−1)⋅c(ω2n−1⋅ζ))⋅s0(ζ)+α2⋅(un−2⋅c(ζ)−(1−un−2)⋅c(ω2n−2⋅ζ))⋅s1(ζ)+⋯+αn−1⋅(u1⋅c(ζ)−(1−u1)⋅c(ω2⋅ζ))⋅sn−2(ζ)+αn⋅(u0⋅c(ζ)−(1−u0)⋅c(ω⋅ζ))⋅sn−1(ζ)+αn+1⋅L0(ζ)⋅(Cz−c0⋅Ca)+αn+2⋅(ζ−1)⋅(Cz−z(ω−1⋅ζ)−c(ζ)⋅Ca)+αn+3⋅LN−1(ζ)⋅(Cz−v′)−vH(ζ)⋅Ct)\begin{split} C_l & = \Big( (c(\zeta) - c_0)s_0(\zeta) \\ & + \alpha \cdot (u_{n-1}\cdot c(\zeta) - (1-u_{n-1})\cdot c(\omega^{2^{n-1}}\cdot\zeta))\cdot s_0(\zeta)\\ & + \alpha^2\cdot (u_{n-2}\cdot c(\zeta) - (1-u_{n-2})\cdot c(\omega^{2^{n-2}}\cdot\zeta))\cdot s_1(\zeta) \\ & + \cdots \\ & + \alpha^{n-1}\cdot (u_{1}\cdot c(\zeta) - (1-u_{1})\cdot c(\omega^2\cdot\zeta))\cdot s_{n-2}(\zeta)\\ & + \alpha^n\cdot (u_{0}\cdot c(\zeta) - (1-u_{0})\cdot c(\omega\cdot\zeta))\cdot s_{n-1}(\zeta) \\ & + \alpha^{n+1}\cdot L_0(\zeta)\cdot(C_z - c_0\cdot C_a)\\ & + \alpha^{n+2}\cdot (\zeta-1)\cdot\big(C_z - z(\omega^{-1}\cdot \zeta)-c(\zeta)\cdot C_{a} ) \\ & + \alpha^{n+3}\cdot L_{N-1}(\zeta)\cdot(C_z - {\color{blue}v'}) \\ & - v_H(\zeta)\cdot C_t \Big) \end{split}
    (76)

  3. Verifier 产生随机数 η\eta 来合并下面的 Pairing 验证：

    e(Cl+ζ⋅Qζ,[1]2)=?e(Qζ,[τ]2)+e(Eζ,[γ]2)e(C−C∗(ξ)−zDζ(ξ)⋅Qc+ξ⋅Qξ,[1]2)=?e(Qξ,[τ]2)e(Z+ζ⋅Qωζ−z(ω−1⋅ζ)⋅[1]1,[1]2)=?e(Qωζ,[τ]2)+e(Eωζ,[γ]2)\begin{aligned} e(C_l + \zeta\cdot Q_\zeta, [1]_2) & \overset{?}{=} e(Q_\zeta, [\tau]_2) + {\color{blue}e(E_\zeta, [\gamma]_2)}\\ e(C - C^*(\xi) - z_{D_\zeta}(\xi)\cdot Q_c + \xi\cdot Q_\xi, [1]_2) & \overset{?}{=} e(Q_\xi, [\tau]_2)\\ e(Z + \zeta\cdot Q_{\omega\zeta} - z(\omega^{-1}\cdot\zeta)\cdot[1]_1, [1]_2) &\overset{?}{=} e(Q_{\omega\zeta}, [\tau]_2) + {\color{blue}e(E_{\omega\zeta}, [\gamma]_2)}\\ \end{aligned}
    (77)

    合并后的验证只需要两个 Pairing 运算：

    P=(Cl+ζ⋅Qζ)+η⋅(C−C∗−zDζ(ξ)⋅Qc+ξ⋅Qξ)+η2⋅(Cz+ζ⋅Qωζ−z(ω−1⋅ζ)⋅[1]1)\begin{aligned} P &= \Big(C_l + \zeta\cdot Q_\zeta\Big) \\ &+ \eta\cdot \Big(C - C^* - z_{D_\zeta}(\xi)\cdot Q_c + \xi\cdot Q_\xi\Big) \\ &+ \eta^2\cdot\Big(C_z + \zeta\cdot Q_{\omega\zeta} - z(\omega^{-1}\cdot\zeta)\cdot[1]_1\Big) \end{aligned}
    (78)
e(P,[1]2)=?e(Qζ+η⋅Qξ+η2⋅Qωζ,[τ]2)+e(Eζ+η2⋅Eωζ,[γ]2)e\Big(P, [1]_2\Big) \overset{?}{=} e\Big(Q_\zeta + \eta\cdot Q_\xi + \eta^2\cdot Q_{\omega\zeta}, [\tau]_2\Big) + {\color{blue}e\Big(E_\zeta + \eta^2\cdot E_{\omega\zeta}, [\gamma]_2\Big)}
(79)

3. 优化性能分析

Proof size: 9 G1+(n+1) F9~\mathbb{G}_1 + (n+1)~\mathbb{F}

Verifier: 4 F+O(n) F+3 G1+2 P4~\mathbb{F} + O(n)~\mathbb{F}+ 3~\mathbb{G}_1 + 2~P

References

PH23
缺失的协议 PH23-PCS（二）
PH23
缺失的协议 PH23-PCS（四）