Halo2

2022-01-09 本文已影响0人雪落无留痕

Halo2是Zcash协议在Orchard升级中将要采用的零知识证明系统，无需可信设置，可以实现递归证明。

基本概念

证明系统

证明公开输入和隐私输入满足关系 $R$

private inputs: 隐私输入
advice value：中间输入
public input: 公开输入

private input 和 advice value 统称为 witness。

PLONKish

Halo2 基于PLONK实现，支持 custom gate 和 lookup argument，称为Plonkish.

UPA电路定了一个矩阵，包括rows, columns 和 cells等元素。

cell的值定义在有限域 $\mathbb{F}$ 上；
columns可分为fixed, advice, instance。fixed 对应着固定的列，advice 对应着 witness 值，instance 主要用作公开输入；
域 $F$ 上的多变量多项式在每一行值为0.
由input expressions 和 table columns定义的lookup arguments

通过电路的描述，可以生成 proving key 和 verification key.

电路门包括 standard gate （支持通用操作）和 custom gates（支持专用的操作）。

Cores

Cores 可以用来实现一些密码组件，例如hash 算法，标量乘或双线性对等。

Chips

可以将多个cores的功能整合在一起，形成chip。

Gadgets

相比Chips, 能提供更上层的抽象。

用户文档

开发工具

MockProver: 可以用于调试电路，并验证电路的正确性；

dev-graph: 创建电路的图形化表示；

circuit_dot_graph: 用于构建电路的DOT图表示。

cost-model: 用于评估验证的消耗和proof大小。

查找表

以空间换时间，通过查找表提升性能。

证明系统

门电路
$A(X)\cdot q_A(X) + B(X)\cdot q_B(X) + A(X)\cdot B(X)\cdot q_M(X)+C(X)\cdot q_C(X)=0$
Halo2证明系统可以分解为五步：

对电路的主要组件生成多项式承诺；
构造 vanishing argument 限制所有的电路关系为0;
有一些必要的点对上面的多项式进行估值；
构建 multipoint opening argument 验证估值和承诺一致；
利用inner product argument 构建 polynomial commitment opening proof.

halo2协议

$\bf Prover$		$\bf Verifier$
	$\leftarrow$	$t(X)=(X^n-1)$
	$\leftarrow$	$F=[F_0,F_1,\cdots,F_{m-1}]$
$A=[A_0,A_1,\cdots,A_{m-1}]$	$\rightarrow$
	$\leftarrow$	$\theta$
$\mathbf{L}=[(A_0^{'},S_0^{'}),\cdots, (A_{m-1}^{'},S_{m-1}^{'})]$	$\rightarrow$
	$\leftarrow$	$\beta, \gamma$
$\mathbf{Z_P}= [Z_{P,0},Z_{P,1},\cdots]$	$\rightarrow$
$\mathbf{Z_L}=[Z_{L,0},Z_{L,1},\cdots]$	$\rightarrow$
	$\leftarrow$	$y$
$h(X)=\frac{gate_0(x)+\cdots+y^i\cdot gate_i(x)}{t(X)}$
$h(X)=h_0(X)+\cdots+X^{n(d-1)}h_{d-1}(X)$
$\mathbf{H}=[H_0,H_1,\cdots,H_{d-1}]$	$\rightarrow$
	$\leftarrow$	$x$
$evals=[A_0(x),\cdots,H_{d-1}(x)]$	$\rightarrow$
		检查 $h(x)$
	$\leftarrow$	$x_1,x_2$
构造 $h'(x)$
$U=Commit(h'(x))$	$\rightarrow$
	$\leftarrow$	$x_3$
$\mathbf{q}_{evals}=[Q_0(x_3),Q_1(x_3),\cdots]$	$\rightarrow$
$u_{eval}=U(x_3)$	$\rightarrow$
	$\leftarrow$	$x_4$

然后证明者和验证者执行：

构造 $finalPoly(X)$ ;
构造 $finalPolyEval$ ;
执行 $InnerProduct(finalPoly(X),x_3, finalPolyEval)$

Lookup argument

halo2采用查找表技术，比Plookup更简单。

$Z(X)$ 为 grand product argument polynomial

技术描述

对于长度为 $2^k$ 的两个列 $A$ 和 $S$ ，查找表主要实现：确何 $A$ 中的每个元素在 $S$ 中存在。

其中 $S$ 的值可以固定的，也可能是变化的；
$A$ 和 $S$ 都可以包含重复的值。

给定 $A$ 和 $S$ 置换分别为 $A'$ 和 $S'$ , 它们之间可以采用 permutaion argument 进行约束。
$Z(\omega X)\cdot (A'(X) + \beta)(S'(X) + \gamma)- Z(X)\cdot (A(X)+ \beta)\cdot (S(X) + \gamma) = 0 \\ l_0(X)\cdot (1-Z(X))=0$
对于所有的 $i \in [0, 2^k)$ :
$Z_{i+1}=Z_i\cdot \frac{(A_i+\beta)(S_i+\gamma)}{(A_i^{'}+\beta)(S_i^{'}+\gamma)}$
上述只是指定了置换关系，但未指明具体的置换。

需要注意的点：

$A'$ 由 $A$ 排序得到，并且相同的值连接排列；
$S'$ 中与 $A'$ 中相同连续值的第一个对应行保持相等，其它的值可以为任意置换。

相应地，约束 $A_i^{'}=S_i^{'}$ 或 $A_i^{'} = A_{i+1}^{'}$ 条件为：

$(A'(X) - S'(x))\cdot (A'(x) - A'(\omega ^ {-1}x) )=0$
另外，需要限制 $A_0^{'}=S_0^{'}$ ，采用以下规则：
$l_0(X)\cdot (A'(X)-S'(X))=0$
通过上述规则可以保证 $A$ 中的每个元素存在于 $S$ 中。

Permuation argument

置换为一对一的映射，一个置换可以分解为多个cycles , 例如 $(a,b,c)$ 表示 $a$ 映射 $b$ , $b$ 映射到 $c$ , $c$ 映射到 $a$ 。

设 $w$ 为 $2^k$ 次本原根， $\delta$ 为 $T$ 次本原根，其中 $T\cdot 2^S + 1 = p$ ， $T$ 为奇数， $k\leq S$ . 用 $\delta ^i\cdot \omega ^j$ 表示 $j$ 行 $i$ 列。

用 $\sigma$ 表示 $m$ 个多项式 $s_i(X)$ 的向量置换，使得 $s_i(\omega^j)=\delta^{i'}\cdot w^{j'}$

恒等置换为： $ID_i(\omega^j)=\delta^i\cdot \omega^j$

置换可以表示：
$\prod_{i=0}^{m-1}\prod_{j=0}^{n-1}(\frac{v_i(\omega^j)+\beta\cdot \delta^i\omega^j+\gamma}{v_i(\omega^j)+\beta\cdot s_i(\omega^j)+\gamma})=1$
定义 $Z_P$ 为： $Z_P(\omega^0)=Z_P(\omega^n)=1$ ，对于 $0\leq j < n$ ：
$Z_P(\omega^{j+1})=Z_P(\omega^j)\prod_{i=0}^{m-1}\frac{v_i(\omega^j)+\beta\cdot \delta^i\omega^j+\gamma}{v_i(\omega^j)+\beta\cdot s_i(\omega^j)+\gamma}$

可以有效进行约束：
$Z_P(\omega X)\cdot \prod_{i=0}^{m-1}(v_i(X)+\beta\cdot s_i(X)+\gamma)-Z_P(X)\cdot\prod_{i=0}^{m-1}(v_i(X)+\beta\cdot\delta^i\cdot X + \gamma)=0 \\ l_0\cdot (1-Z_P(X))=0$

列的个数可以进行任意扩展，具体不再进行介绍。

Circuit commitments

Committing to the circuit assignments

对于长度为 $n=2^k$ 的表，可以分解为 advice, instance, fixed 列，用 $F_{i,j}$ 表示固定列 $j$ 行 $i$ 列的赋值，相似地， $A_{i,j}$ 表示advice和instance列的赋值。

为了对赋值进行承诺，构造次数为 $n-1$ 次的多项式，满足：

$a_i(X)$ 插值得到： $a_i(\omega^j)=A_{i,j}$
$f_i(X)$ 插值得到： $f_i(\omega^j)=F_{i,j}$

然后构建每一列多项式的承诺：
$\mathbf{A}=[Commit(a_0(X)),\cdots, Commit(a_i(X))] \\ \mathbf{F}=[Commit(f_0(X)),\cdots, Commits(f_i(X))]$
$\mathbf{F}$ 是密钥生成的一部分，盲化因子为1。 $\mathbf{A}$ 由证明者构造，发送给验证者。

Committing to the lookup permutaions

验证者随机生成 $\theta$ ，用于保证查找表各列相互独立，证明者对置换承诺的过程如下：

对于输入的列多项式 $[A_0(X),\cdots, A_{m-1}(X)]$ 和表的列多项式 $[S_0(X),\cdots, S_{m-1}(X)]$ ，证明者可以构造两个压缩多项式：

$A_{compressed}(X)=\theta^{m-1}A_0(X)+\theta^{m-2}A_1(X)+\cdots+\theta A_{m-2}(X)+A_{m-1}(X) \\ S_{compressed}(X)=\theta^{m-1}S_0(X)+\theta^{m-2}S_1(X)+\cdots+\theta S_{m-2}(X)+S_{m-1}(X)$

证明者再得到 $A_{compressed}(X)$ 和 $S_{compressed}(X)$ 的置换 $A'(X)$ 和 $S'(X)$

然后证明者得到lookup 的盲承若：
$\mathbf{L} = [(Commit(A'(X))), Commit(S'(X)),\cdots]$
并将其发送给验证者。

验证者得到 $A, F, L$ 后，生成随机挑战 $\beta$ 和 $\gamma$ , 可以用于 permutation argument 和 lookup argument中。

Committing to the quality constraint permutation

定义 $c$ 为等式约束的列数， $m$ 为最大的列数， $u$ 为 Permuation argument 中可用的行数， $b= ceiling(c/m)$

证明者构建向量 $\mathbf{P}$ , 其长度为 $bu$ , 对于列集 $0\leq a < b$ , 对于每一行 $0\leq j < u$ ：
$\mathbf{P}_{au+j}=\prod_{i=am}^{min(c, (a+1)m)-1}\frac{v_i(\omega^j)+\beta\cdot \delta^i\cdot \omega^j + \gamma}{v_i(\omega^j)+\beta\cdot s_i(\omega^j)+\gamma}$
然后证明者构建 $Z_{P,a}$ 多项式的盲承若：
$\mathbf{Z_P}=[Commit(Z_{P,0}(X)),\cdots, Commit(Z_{P,b-1}(X))]$
并将基发送给验证者。

Committing to the lookup permuation product columns

对于查找表，证明者需要构建置换的承诺：

证明构建向量 $P$ , 满足：
$P_j=\frac{(A_{compressed}(\omega^j)+\beta)(S_{compressed}(\omega^j)+\gamma)}{(A'(\omega^j)+ \beta)(S'(\omega^j)+ \gamma)}$
证明者构建多项式 $Z_L$ , 采用Lagrange 基表示, 且 $Z_L(1)=1$

然后，证明者构造 $Z_L$ 多项式的盲承诺：
$\mathbf{Z_L} = [Commits(Z_L(X))]$

Vanishing argument

在对电路赋值承诺之后，证明者需要保证电路关系满足：

定制电路门，由 $gate_i(X)$ 表示
查找表的规则；
等式约束置换的规则；

每列的次数为 $n-1$ , relation 由次数为 $d(n-1)$ ，其中 $d$ 表示列多项式的次数。

例如，对于下述门电路多项式，其次数为： $3n-3$

$gate_0(X)=a_0(X)\cdot a_1(X)\cdot a_2(X\omega^{-1})-a_3(X)$
$gate_1(X) = f_0(X\omega^{-1})\cdot a_2(X)$
$gate_2(X)=f_0(X)\cdot a_3(X)\cdot a_0(X)$

若多项式值为0，表示relation 关系满足，可以通过vanishing polynomial $t(X)= (X^n-1)$ 实现。若relation 多项式可以被 $t(X)$ 整除，则表示它在domain上的所有值为0.

可以对每一个多项式关系构造一个承诺，也可以对所有关系多项式同时进行承诺，验证者生成随机挑战 $y$ , 然后证明者构造商多项式：
$h(X)=\frac{gate_0(X)+y\cdot gate_1(X)+\cdots+ y^i\cdot gate_i(X)+\cdots}{t(X)}$
其中分子是电路关系的随机线性组合。

Committing to $h(X)$

$h(X)$ 次数为 $(d-1)n-d$ ， halo2 中的多项式承诺最多支持次数 $n-1$ , 因此需要对 $h(X)$ 多项式进行拆分，即：
$h_0(X)+ X^nh_1(X)+\cdots+X^{n(d-1)}h_{d-1}(X)$
然后生成每个部分的盲多项式承诺：
$\mathbf{H} = [Commit(h_0(X)), Commit(h_1(X)),\cdots, Commit(h_{d-1}(X))]$
Evaluating the polynomials

目前所有多项式都被承诺了，验证需要知道 $h(x)$ 的承诺是否正确，验证者生成 $x$ , 证明者生成多项式在 $x$ 的值：

本例中，多项式值包括：
$$
a_0(x) \
a_1(x) \
a_2(x), a_2(x\omega^{-1}) \
a_3(x) \
f_0(x), f_0(x\omega^{-1}) \
h_0(x),\cdots, h_{d-1}(x)

验证者检查 $h(X)$ 的值满足以下形式：
$\frac{gate_0(x)+\cdots+ y^i\cdot gate_i(x)+\cdots}{t(x)}=h_0(x)+\cdots+x^{n(d-1)}h_{d-1}(x)$
通过检查估值，验证者可以验证电路约束关系满足。因此验证者需要验证所有多项式在 $x$ 处的值和它们的承诺对应，这通过 multipoit opening argument 实现。

Multipoint opening argument

multipoint opening的输入包含：

由验证者随机生成的 $x$ , 在其上计算多项式 $a(X),b(X),c(X),d(X)$ 的值；
由证明者提供多项式的值： $a(x),b(x),c(x),d(x),c(\omega x), d(\omega x)$

优化过程如下：

随机选取 $x_1$ , 使 $a, b, c,d$ 线性无关。
累加多项式和其对应的值：
$q_1(X) =a(X)+x_1b(X) \\ q_2(X)=c(X) + x_1d(X)$
插值值的集合：
$r_1(X)\ \ s.t. \ \ \ r_1(x)=a(x)+x_1b(x) \\ r_2(X)\ \ s.t. \ \ \ r_2(x)=c(x)+x_1d(x) \\ r_2(\omega x)= c(\omega x) + x_1d(\omega x)$

构造 f_polys, 并检查其正确性：
$f_1(X)=\frac{q_1(X)-r_1(X)}{X-x} \\ f_2(X)=\frac{q_2(X)-r_2(x)}{(X-x)(X-\omega x)}$
随机选取 $x_2$ , 构造 $f(X)=f_1(X)+x_2f_2(X)$

随机选取 $x_3$ , 估计值 $f(X)$ :
$f(x_3)& = &f_1(x_3)+x_2f_2(x_3) \\ &= &\frac{q_1(x_3)-r_1(x_3)}{x_3-x} + \frac{q_2(x_3)-r_2(x_3)}{(x_3-x)(x_3-\omega x)}$
随机选取 $x_3$ , 构造 $final\_poly(X)=f(X)+x_3q_1(X)+x_4^2q_2(X)$ , 即为最终进行内积证明承诺的多项式。

Inner product argument

Halo2 内积证明类似 BCMS20.

协议描述

采用 $\lambda$ 作为安全参数。

cryptographic groups

用 $\mathbb{G}$ 表示素数阶为 $p$ 的循环群，单位元为 $\mathbb{O}$ . 标量域 $\mathbb{F}$ , 阶为 $p$ . 用 $\langle \mathbf{a}, \mathbf{b} \rangle$ 表示两个向量的内积，其中 $\mathbf{a,b}\in \mathbb{F}^n$ . $\langle \mathbf{a}, \mathbf{G} \rangle$ 表示群元素的线性组合，其中 $\mathbf{a} \in \mathbb{F}^n, \mathbf{G} \in \mathbb{G}^n$

离散对数关系问题：采用的度量为：
$\bf{Adv}_{\mathbb{G},n}^{dl-rel}(\mathcal{A}, \lambda)=Pr[G_{\mathbb{G},n}^{dl-rel}(\mathcal{A}, \lambda)]$
由以下游戏定义：
$$
\begin{array}{ll}

&\underline{\bf{Game}\ \ G_{\mathbb{G},n}^{dl-rel}(\mathcal{A}, \lambda):} \
& \mathbf{G}\leftarrow \mathbb{G}_{\lambda}^n \
& a \leftarrow \mathcal{A}(\mathbf{G}) \
& Return\ (\langle \mathbf{a}, \mathbf{G} \rangle = \and\ \mathbf{a}\neq \mathbf{0}^n)
\end{array}
$$

Interactive proofs

交互式证明是一个三元的算法： $IP=(Setup, P, V)$ , $Setup(1^{\lambda})$ 生成公开的参数 $pp$ , 证明者 $\mathcal{P}$ 和验证者 $\mathcal{V}$ 采用 $\langle \mathcal{P}(x), \mathcal{V}(x) \rangle$ 表示，其输入分别为 $x$ 和 $y$ 。

零知识证明具体有以下属性：

Completeness
Soundness
Knowledge soundness
Zero knowledge

协议

定义 $\omega \in \mathbb{F}$ 为 $n=2^k$ 次本原根，定义域为 $D=(\omega^0, \omega^1, \cdots, \omega^{n-1})$ , $t(X)= X^n-1$ 为定义域上的vanishing 多项式，设 $k, n_g, n_a$ 为正整数。对于交互式证明 $\bf{Halo}=(Setup, \mathcal{P},\mathcal{V})$ , 其关系为：
$\mathcal{R} =\left\{ \begin{array}{ll} & \left( \begin{array}{ll} \left( g(X, C_0, C_1, ..., C_{n_a - 1}) \right); \\ \left( a_0(X), a_1(X, C_0), ..., a_{n_a - 1}(X, C_0, C_1, ..., C_{n_a - 1}) \right) \end{array} \right): \\ & g(\omega^i, C_0, C_1, ..., C_{n_a - 1}) = 0 \, \, \, \, \forall i \in [0, 2^k) \end{array} \right\}$
其中 $a_0, a_1, ..., a_{n_a - 1}$ 为多变量多项式，次数 $n-1$ , $g$ 次数为 $n_g(n-1)$ .

$Setup(\lambda)$ 返回参数为： $\bf{pp}=(\mathbb{G}, \mathbb{F}, \mathbf{G}\in \mathbb{G}^n, U, W \in \mathbb{G} )$

$\mathcal{P}$ 和 $\mathcal{V}$ 进行以下 $n_a$ 轮交互：

$\mathcal{P}$ 设定 $a_j'(X)=a_j(X,c_0,\cdots, c_{j-1})$ ;
$\mathcal{P}$ 发送承诺 $A_j=\langle \mathbf{a'}, \mathbf{G} \rangle + [\cdot]W$ ，其中 $\mathbf{a'}$ 为 $a_j'(X)$ 的系数。
$\mathcal{V}$ 响应挑战 $c_j$

$\mathcal{P}$ 和 $\mathcal{V}$ 设定多项式 $g'(X)=g(X,c_0,c_1,\cdots,c_{n_a-1})$
$\mathcal{P}$ 发送承诺 $R=\langle \mathbf{r}, \mathbf{G} \rangle + [\cdot]W$ ，其中 $\mathbf{r} \in \mathbb{F}^n$ 随机抽样的系数，单变量多项式 $r(X)$ 的次数为 $n-1$
$\mathcal{P}$ 计算单变量多项式 $h(X)=\frac{g'(X)}{t(X)}$ , 其次数为 $n_g(n-1)-n$
$\mathcal{P}$ 计算至多度数为 $n-1$ 的多项式： $h_0(X),h_1(X),\cdots, h_{n_g-2}(X)$ 使得 $h(X)=\prod_{i=0}^{n_g-2} X^{ni}h_i(X)$
$\mathcal{P}$ 发送承诺 $H_i = \langle \mathbf{h_i}, \mathbf{G} \rangle + [\cdot]W$ , 对于所有 $i$ , $\mathbf{h_i}$ 表示 $h_i(x)$ 的系数
$\mathcal{V}$ 响应挑战 $x$ , 并计算 $H'= \sum_{i=0}^{n_g-2}[x^{ni}]H_i$
$\mathcal{P}$ 设置 $h'(X)=\sum_{i=0}^{n_g-2}x^{ni}h_i(X)$
$\mathcal{P}$ 发送 $r=r(x)$ , 对于所有 $i\in [0, n_a)$ , 发送 $\mathbf{a_i}$ ，使得 $(\mathbf{a}_i)_j=a'(\omega^{(p_i)_j}x)$ , $j \in [0, n_e]$
对于所有的 $i \in [0, n_a)$ $\mathcal{P}$ 和 $\mathcal{V}$ 设定 $s_i(X)$ 为次数最低的单变量多项式，定义为： $s_i(\omega^{(p_i)_j}x)= (\mathbf{a}_i)_j$ , $j \in [0, n_e)$
$\mathcal{V}$ 响应挑战 $x_1, x_2$ ，并初始化 $Q_0, Q_1,\cdots, Q_{n_q-1}=\mathcal{O}$

从 $i=0$ 到 $n_a-1$ , $\mathcal{V}$ 设定 $Q_{\sigma(i)}:= [x_1]Q_{\sigma(i)}+ A_i$
$\mathcal{V}$ 最终设定 $Q_0:= [x_1^2]Q_i+[x_1]H'+R$

$\mathcal{P}$ 初始化 $q_0(X), q_1(X),\cdots, q_{n_q-1}(X)=0$

从 $i=0$ 到 $n_a-1$ , $\mathcal{P}$ 设定 $q_{\sigma(i)}:= x_1q_{\sigma(i)}+a'(X)$
$\mathcal{P}$ 最终设定 $q_0(X):= x_1^2q_0(X) + x_1h'(X)+r(X)$

$\mathcal{P}$ 和 $\mathcal{V}$ 初始化 $r_0(X),r_1(X),\cdots, r_{n_q-1}(X)=0$

从 $i=0$ 到 $n_a - 1$ ， $\mathcal{P}$ 和 $\mathcal{V}$ 设定 $r_{\sigma(i)}(X) := x_1 r_{\sigma(i)}(X) + s_i(X)$ .
$\mathcal{P}$ 和 $\mathcal{V}$ 设定 $r_0 := x_1^2 r_0 + x_1 h + r$ ，其中 $h$ is由 $\mathcal{V}$ 通过 $\frac{g'(x)}{t(x)}$ 计算， $\mathbf{a}$ 由证明者 $\mathcal{V}$ 提供。

$\mathcal{P}$ 发送 $Q' = \langle \mathbf{q'}, \mathbf{G} \rangle + [\cdot] W$ ，其中 $\mathbf{q'}$ 定义了多项式的系数：
$$
q'(X) = \sum\limits_{i=0}^{n_q - 1}

x_2^i
\left(
\frac
{q_i(X) - r_i(X)}
{\prod\limits_{j=0}^{n_e - 1}
\left(
X - \omega^{\left(
\mathbf{q_i}
\right)_j} x
\right)
}
\right)
$$

$\mathcal{V}$ 响应挑战 $x_3$ .
$\mathcal{P}$ 发送 $\mathbf{u} \in \mathbb{F}^{n_q}$ 使得 $\mathbf{u}_i = q_i(x_3)$ ， $i \in [0, n_q)$ .
$\mathcal{V}$ 响应挑战 $x_4$ .
$\mathcal{P}$ 和 $\mathcal{V}$ 设定 $P = Q' + x_4 \sum\limits_{i=0}^{n_q - 1} [x_4^i] Q_i$ ，其中 $v =$
$$
\sum\limits_{i=0}^{n_q - 1}
\left(
x_2^i
\left(
\frac
{ \mathbf{u}i - r_i(x_3) }
{\prod\limits{j=0}^{n_e - 1}
\left(
x_3 - \omega^{\left(
\mathbf{q_i}
\right)_j} x
\right)
}
\right)
\right)

x_4 \sum\limits_{i=0}^{n_q - 1} x_4 \mathbf{u}_i
$$

$\mathcal{P}$ 设定 $p(X) = q'(X) + [x_4] \sum\limits_{i=0}^{n_q - 1} x_4^i q_i(X)$ .
$\mathcal{P}$ 选取次数为 $n-1$ 的多项式s(X) ，其中一个根为 $x_3$ , 并发送承诺 $S = \langle \mathbf{s}, \mathbf{G} \rangle + [\cdot] W$ , 其中 $\mathbf{s}$ 定义了多项式 $s(X)$ 系数。.
$\mathcal{V}$ 响应挑战 $\xi, z$ .
$\mathcal{P}$ 和 $\mathcal{V}$ 设定 $P' = P - [v] \mathbf{G}_0 + [\xi] S$ .
$\mathcal{P}$ 设定 $p'(X) = p(X) - v + \xi s(X)$ .
初始化 $\mathbf{p'}$ 作为 $p'(X)$ 的系数， $\mathbf{G'} = \mathbf{G}$ ， $\mathbf{b} = (x_3^0, x_3^1, ..., x_3^{n - 1})$ . $\mathcal{P}$ 和 $\mathcal{V}$ 将在以下 $k$ 中交互，对于 $j\in [0, k-1]$ :

$\mathcal{P}$ 发送 $L_j = \langle \mathbf{p'}_{hi}, \mathbf{G'}_{lo} \rangle + [z \langle \mathbf{p'}_{hi}, \mathbf{b}_{lo}] U\rangle + [\cdot] W$ 和 $R_j = \langle \mathbf{p'}_{lo}, \mathbf{G'}_{hi} \rangle + [z \langle \mathbf{p'}_{lo}, \mathbf{b}_{hi}] U\rangle + [\cdot] W$
$\mathcal{V}$ 响应挑战 $u_j$ .
$\mathcal{P}$ 和 $\mathcal{V}$ 设定 $\mathbf{G'} := \mathbf{G'}_{lo }+ u_j \mathbf{G'}_{hi}$ and $\mathbf{b} = \mathbf{b}_{lo} + u_j \mathbf{b}_{hi}$ .
$\mathcal{P}$ 设定 $\mathbf{p'} := \mathbf{p'}_{lo} + u_j^{-1} \mathbf{p'}_{hi}$ .

$\mathcal{P}$ 发送 $c = \mathbf{p'}_0$ 和盲化因子 $f$ .
$\mathcal{V}$ 验证 $\sum_{j=0}^{k - 1} [u_j^{-1}] L_j + P' + \sum_{j=0}^{k - 1} [u_j] R_j = [c] \mathbf{G'}_0 + [c \mathbf{b}_0 z] U + [f] W$ 是否成立。