区间证明（BulletProof）

这里简单记一下BulletProof 论文的笔记，以便于后续用到时能够快速回想起来。这是一篇关于区间证明的文章，用于证明承诺的值属于某个区间。区间证明的目标可以描述为：证明者持有 v∈Zpv \in \mathbb{Z}_p 及其 Pedersen 承诺：V=hγgvV = h^\gamma g^v，他想要向验证者证明 VV 中承诺的数据 v∈[0,2n−1]v \in [0, 2^n-1]。把它写成一个正式的零知识证明如下：

{(g,h∈G,V,n ; v,γ∈Zp):V=hγgv∧v∈[0,2n−1]} \{ (g,h \in \mathbb{G}, V, n \ ;\ v,\gamma \in \mathbb{Z}_p) : V = h^\gamma g^v \wedge v \in [0,2^n - 1] \}

论文首先对以前的内积论证进行改进，随后基于改正后的内积论证构造了一个区间证明方案。本文首先介绍他们引入的改进的内积论证，然后在介绍区间证明。

改进的内积论证

一、记号说明（Notation）

1.1 群相关记号

  • 设 GG 是一个素数阶为 pp 的循环群（cyclic group），Zp\mathbb{Z}_p 是模 pp 的整数环。

  • GnG^n 与 Zpn\mathbb{Z}_p^n 分别表示定义在 GG 与 Zp\mathbb{Z}_p 上的长度为 nn 的向量空间。

  • Zp∗\mathbb{Z}_p^\ast 表示去除 00 的有限域元素集合。

  • 群生成元通常记作 g,h,u∈Gg, h, u \in G。

  • 表示承诺的群元素使用大写字母，如 CC，而用于随机性的标量则用希腊字母，如 α\alpha。

例如，使用 Pedersen 承诺对 aa 进行承诺结果为: C=gahα∈GC = g^a h^\alpha \in G。

  • x←$Zp∗x \xleftarrow{\$} \mathbb{Z}_p^\ast 表示从集合 Zp∗\mathbb{Z}_p^\ast 中均匀随机抽取一个元素。
  • 向量使用加粗小写字母表示，如 a∈Fn\mathbf{a} \in \mathbb{F}^n；
  • 矩阵使用加粗大写字母，如 A∈Fn×m\mathbf{A} \in \mathbb{F}^{n \times m}；
  • 若 A=(ai,j)\mathbf{A} = (a_{i,j})，则 ai,ja_{i,j} 表示第 ii 行第 jj 列的元素。

1.2 内积和Hadamard积

  • 对于标量 c∈Zpc \in \mathbb{Z}_p 和向量 a∈Zpn\mathbf{a} \in \mathbb{Z}_p^n，用 b=c⋅a\mathbf{b} = c \cdot \mathbf{a} 表示 bi=c⋅aib_i = c \cdot a_i。

  • 向量内积定义为： $ \langle \mathbf{a}, \mathbf{b} \rangle := \sum_{i=1}^n a_i \cdot b_i $

  • Hadamard 积（即逐项乘法）定义为： $ \mathbf{a} \circ \mathbf{b} := (a_1 \cdot b_1, \ldots, a_n \cdot b_n) $

1.3 多项式向量和内积

  • 向量多项式 p(X)=∑i=0dpiXi∈Zpn[X]p(X) = \sum_{i=0}^d \mathbf{p}_i X^i \in \mathbb{Z}_p^n[X]；
  • 对于两个向量多项式 l(X),r(X)\mathbf{l}(X), \mathbf{r}(X)，定义其内积为：
⟨l(X),r(X)⟩:=∑i=0d∑j=0i⟨li,rj⟩⋅Xi+j∈Zp[X] \langle \mathbf{l}(X), \mathbf{r}(X) \rangle := \sum_{i=0}^d \sum_{j=0}^i \langle \mathbf{l}_i, \mathbf{r}_j \rangle \cdot X^{i+j} \in \mathbb{Z}_p[X]

记 t(X):=⟨l(X),r(X)⟩t(X) := \langle \mathbf{l}(X), \mathbf{r}(X) \rangle，则对任意 x∈Zpx \in \mathbb{Z}_p 有： t(x)=⟨l(x),r(x)⟩t(x) = \langle \mathbf{l}(x), \mathbf{r}(x) \rangle

1.4 向量承诺与变换

  • 给定 g=(g1,…,gn)∈Gn\mathbf{g} = (g_1, \ldots, g_n) \in G^n 和向量 a∈Zpn\mathbf{a} \in \mathbb{Z}_p^n，则向量 a\mathbf{a} 的承诺为：
C=ga=∏i=1ngiai C = \mathbf{g}^\mathbf{a} = \prod_{i=1}^n g_i^{a_i}
  • 该承诺是对向量 a\mathbf{a} 的绑定承诺（但非隐藏）。 若已知另一个向量 b∈Zpn\mathbf{b} \in \mathbb{Z}_p^n（元素均非零），可定义 gi′=gibi−1g'_i = g_i^{b_i^{-1}}，以构造一个新的对 a∘b\mathbf{a} \circ \mathbf{b} 的承诺：
C=∏i=1n(gi′)ai⋅bi C = \prod_{i=1}^n (g'_i)^{a_i \cdot b_i}

1.5 Python 风格切片和幂次向量记号

  • 若 a∈Zpn\mathbf{a} \in \mathbb{Z}_p^n，b∈Zpm\mathbf{b} \in \mathbb{Z}_p^m，其拼接写作：a∥∥b∈Zpn+m\mathbf{a} \|\| \mathbf{b} \in \mathbb{Z}_p^{n+m}；

  • 切片符号： $ \mathbf{a}[:\ell] = (a_1, \ldots, a_\ell), \quad \mathbf{a}[\ell:] = (a_{\ell+1}, \ldots, a_n) $

  • 对 k∈Zp∗k \in \mathbb{Z}_p^\ast，定义其幂向量为： $ \mathbf{k}^n = (1, k, k^2, \ldots, k^{n-1}) \in (\mathbb{Z}_p^\ast)^n $

1.6 零知识证明的表示：

我们使用 {(public input; witness) : relation} 表示一个指定公开输入和证明者见证的关系。

  • 例如：证明者想证明自己知道向量 a,b∈Zpn\mathbf{a}, \mathbf{b} \in \mathbb{Z}_p^n，使得它们满足内积等于某个标量 cc，并且两者的 Pedersen 向量承诺为 P=gahbP = \mathbf{g}^\mathbf{a} \mathbf{h}^\mathbf{b}。该关系可写作：
{(g,h,P,c;a,b):P=gahb∧c=⟨a,b⟩} \{(\mathbf{g}, \mathbf{h}, P, c; \mathbf{a}, \mathbf{b}) : P = \mathbf{g}^\mathbf{a} \mathbf{h}^\mathbf{b} \land c = \langle \mathbf{a}, \mathbf{b} \rangle \}

二、改进的内积论证

为了构造区间证明，论文首先介绍了 Bootle 等人提出的内积论证方法 [1]，随后引出其在原始基础上经过作者改进后的版本。

2.1 内积论证: 设有两个生成元向量 g,h∈Gn\mathbf{g}, \mathbf{h} \in G^n，以及对待承诺向量 a,b∈Zpn\mathbf{a}, \mathbf{b} \in \mathbb{Z}_p^n 的绑定不隐藏向量承诺P=ga⋅hb∈GP = \mathbf{g}^{\mathbf{a}} \cdot \mathbf{h}^{\mathbf{b}} \in G，以及一个标量 c∈Zpc \in \mathbb{Z}_p。内积论证是为了向验证者证明以下关系同时成立：

{(g,h,P,c;a,b):P=ga⋅hb∧c=⟨a,b⟩} \{ (\mathbf{g}, \mathbf{h}, P, c; \mathbf{a}, \mathbf{b}) : P = \mathbf{g}^{\mathbf{a}} \cdot \mathbf{h}^{\mathbf{b}} \land c = \langle \mathbf{a}, \mathbf{b} \rangle \}

即承诺 PP 确实是 a,b\mathbf{a}, \mathbf{b} 的组合结果，且两者的内积为 cc，而无需泄露向量的具体内容。

  • 最简单的，可以直接将向量 a,b\mathbf{a}, \mathbf{b} 发给验证者，验证者重新计算 P′=ga⋅hbP' = \mathbf{g}^{\mathbf{a}} \cdot \mathbf{h}^{\mathbf{b}} 和 v′=⟨a,b⟩v'=\langle a,b\rangle , 然后验证 P′=PP'=P 和 v′=vv'=v 是否相等来验证要证明的关系是否成立。但是这样需要发送给 2n2n 个元素给验证者，通信开销较大。并且需要暴露两个向量 a,b\mathbf{a}, \mathbf{b}，无法保证零知识性。
  • 为了降低通信开销，并实现零知识性，Bootle等人 给出了一种算术电路可满足性的零知识论证方案，将通信复杂度降低到了6log2(n)6log_2(n)。这部分不是本文的重点，这里不予讨论。

2.2 改进的内积论证: 在介绍了 Bootle 等人提出的基本内积论证方案之后，Bulletproofs 所采用的改进版本进一步降低了通信复杂度，并提升了整体效率。

设有两个生成元向量 g,h∈Gn\mathbf{g}, \mathbf{h} \in G^n，以及向量承诺： $ P = \mathbf{g}^{\mathbf{a}} \cdot \mathbf{h}^{\mathbf{b}} \cdot u^{\langle \mathbf{a}, \mathbf{b} \rangle} $， 其中 u∈Gu \in G 是一个额外的生成元，a,b∈Zpn\mathbf{a}, \mathbf{b} \in \mathbb{Z}_p^n 是证明者的私有向量。该改进型内积论证的目标是向验证者证明：

{(g,h∈Gn, u,P∈G ; a,b∈Zpn): P=gahb⋅u⟨a,b⟩} \{ (\mathbf{g}, \mathbf{h} \in G^n,\ u, P \in G\ ;\ \mathbf{a}, \mathbf{b} \in \mathbb{Z}_p^n) :\ P = \mathbf{g}^{\mathbf{a}} \mathbf{h}^{\mathbf{b}} \cdot u^{\langle \mathbf{a}, \mathbf{b} \rangle} \}

即证明者知道向量 a,b\mathbf{a}, \mathbf{b}，使得该等式成立，但不泄露 a,b\mathbf{a}, \mathbf{b} 的具体内容。

2.3 如何将通信复杂度降至 2log⁡2n2 \log_2 n

在基本的内积论证中，若直接将向量 a,b∈Zpn\mathbf{a}, \mathbf{b} \in \mathbb{Z}_p^n 发送给验证者，需要传输 2n2n 个标量，通信成本高且不具备零知识性。为此，Bulletproofs 利用递归技术设计了两个协议：协议 1 和 协议 2，将通信复杂度降低至 2log⁡2n2 \log_2 n 个群元素加两个标量。

2.3.1 对待原始关系进行转化

为了简单，我们可以将待证明的内积约束转化为一个特殊的向量承诺形式。具体来说，如果引入一个公共生成元 u∈Gu \in G，那么证明 c=⟨a,b⟩c = \langle \mathbf{a}, \mathbf{b} \rangle 相当于证明 uc=u⟨a,b⟩u^c = u^{\langle \mathbf{a}, \mathbf{b} \rangle}。因此可以将原始关系：

{(g,h,P,c; a,b):P=ga⋅hb∧ c=⟨a,b⟩} \{(\mathbf{g}, \mathbf{h}, P, c;\ \mathbf{a}, \mathbf{b}) : P = \mathbf{g}^{\mathbf{a}} \cdot \mathbf{h}^{\mathbf{b}} \land \ c = \langle \mathbf{a}, \mathbf{b} \rangle \}

转化为证明一个新的关系：

{(g,h,u,P,c; a,b):P=ga⋅hb⋅u⟨a,b⟩} \{(\mathbf{g}, \mathbf{h}, u, P, c;\ \mathbf{a}, \mathbf{b}) : P = \mathbf{g}^{\mathbf{a}} \cdot \mathbf{h}^{\mathbf{b}}\cdot u^{\langle \mathbf{a}, \mathbf{b} \rangle} \}

前面提到，直接将两个向量 a,b\mathbf{a}, \mathbf{b} 发给验证者进行证明，会导致这两个向量的泄露，并且证明的长度是 2n2n。实际上，Bulletproofs 提出了一种改进的内积论证方法，基于二分法的思想实现在零知识的情况下证明一个向量承诺 P=ga⋅hb⋅u⟨a,b⟩P = \mathbf{g}^{\mathbf{a}} \cdot \mathbf{h}^{\mathbf{b}} \cdot u^{\langle \mathbf{a}, \mathbf{b} \rangle} 是正确的，且通信复杂度仅为 O(log⁡n)\mathcal{O}(\log n)。

2.3.2 通过二分法压缩证明长度

该协议采用递归方式将向量长度从 nn 缩减至 1，整个过程共进行 log⁡2n\log_2 n 轮。在每一轮中：

  1. 向量分解：将向量 a,b\mathbf{a}, \mathbf{b} 分为左右两半： $ \mathbf{a} = (\mathbf{a}_L, \mathbf{a}_R), \quad \mathbf{b} = (\mathbf{b}_L, \mathbf{b}_R) $

  2. 构造中间承诺：计算中间承诺 LL 和 RR 如下，用于绑定 ⟨aL,bR⟩\langle \mathbf{a}_L, \mathbf{b}_R \rangle 和 ⟨aR,bL⟩\langle \mathbf{a}_R, \mathbf{b}_L \rangle：

    L=gRaL⋅hLbR⋅u⟨aL,bR⟩;R=gLaR⋅hRbL⋅u⟨aR,bL⟩ L = \mathbf{g}_R^{\mathbf{a}_L} \cdot \mathbf{h}_L^{\mathbf{b}_R} \cdot u^{\langle \mathbf{a}_L, \mathbf{b}_R \rangle} \quad ; \quad R = \mathbf{g}_L^{\mathbf{a}_R} \cdot \mathbf{h}_R^{\mathbf{b}_L} \cdot u^{\langle \mathbf{a}_R, \mathbf{b}_L \rangle}

  3. 挑战生成：验证者从 Zp\mathbb{Z}_p 中随机选择一个挑战 xx 并发送给证明者。

  4. 向量与生成元压缩：证明者根据挑战 xx 构造压缩后的新向量和生成元：

    a′=x⋅aL+x−1⋅aR;b′=x−1⋅bL+x⋅bR \mathbf{a}' = x \cdot \mathbf{a}_L + x^{-1} \cdot \mathbf{a}_R \quad ; \quad \mathbf{b}' = x^{-1} \cdot \mathbf{b}_L + x \cdot \mathbf{b}_R
    g′=gLx∘gRx−1;h′=hLx−1∘hRx \mathbf{g}' = \mathbf{g}_L^x \circ \mathbf{g}_R^{x^{-1}} \quad ; \quad \mathbf{h}' = \mathbf{h}_L^{x^{-1}} \circ \mathbf{h}_R^x

  5. 更新承诺：令新的承诺为： $ P’ = L^{x^2} \cdot P \cdot R^{x^{-2}} $ 此时，新的关系为：

    {(g′,h′,u,P′; a′,b′):P′=g′a′⋅h′b′⋅u⟨a′,b′⟩} \{(\mathbf{g}', \mathbf{h}', u, P';\ \mathbf{a}', \mathbf{b}') : P' = \mathbf{g}'^{\mathbf{a}'} \cdot \mathbf{h}'^{\mathbf{b}'} \cdot u^{\langle \mathbf{a}', \mathbf{b}' \rangle} \}

  6. 递归进行下一轮：以 (g′,h′,a′,b′,P′)(\mathbf{g}', \mathbf{h}', \mathbf{a}', \mathbf{b}', P') 为新的输入，进入下一轮，直到向量长度为 1。

  7. 终止条件（长度为 1 的特殊情况）: 当递归至最后一轮时，向量长度缩减为 n=1n = 1，此时验证者检查最终关系是否成立： P′=?(g′)a′⋅(h′)b′⋅ua′⋅b′P' \stackrel{?}{=} (g')^{a'} \cdot (h')^{b'} \cdot u^{a'\cdot b'}。 若等式成立，则验证通过；否则拒绝该证明。 [ 实际上，我们下面的分析会知道，证明最初的关系成立，也就相当于证明迭代中第5步的等式成立。而在两个向量长度都是1的情况下，可以直接通过最简单的验证方式（直接将承诺向量a,b代入的方式）验证P′=?(g′)a′⋅(h′)b′⋅ua′⋅b′P' \stackrel{?}{=} (g')^{a'} \cdot (h')^{b'} \cdot u^{a'\cdot b'}是否成立，从而验证最初的关系是否成立。这里也不用担心向量a,b暴露的问题，因为他们已经是盲化后的向量了。 ]

2.4 为什么可以将证明进行折半拆分

在 Bulletproofs 的协议 2 中，每一轮都将向量长度从 nn 压缩为 n/2n/2。这是通过将向量 a,b\mathbf{a}, \mathbf{b} 拆分为左右两半，并引入中间承诺 L,RL, R 来实现的。下面给出折半拆分的正确性证明。

首先，对新承诺 P′P' 进行展开。根据定义有： $ P’ = L^{x^2} \cdot P \cdot R^{x^{-2}} $ 其中：

L=gRaL⋅hLbR⋅u⟨aL,bR⟩,R=gLaR⋅hRbL⋅u⟨aR,bL⟩ L = \mathbf{g}_R^{\mathbf{a}_L} \cdot \mathbf{h}_L^{\mathbf{b}_R} \cdot u^{\langle \mathbf{a}_L, \mathbf{b}_R \rangle}, \quad R = \mathbf{g}_L^{\mathbf{a}_R} \cdot \mathbf{h}_R^{\mathbf{b}_L} \cdot u^{\langle \mathbf{a}_R, \mathbf{b}_L \rangle}

P=gLaL⋅gRaR⋅hLbL⋅hRbR⋅u⟨aL,bL⟩+⟨aR,bR⟩ P = \mathbf{g}_L^{\mathbf{a}_L} \cdot \mathbf{g}_R^{\mathbf{a}_R} \cdot \mathbf{h}_L^{\mathbf{b}_L} \cdot \mathbf{h}_R^{\mathbf{b}_R} \cdot u^{\langle \mathbf{a}_L,\mathbf{b}_L \rangle + \langle \mathbf{a}_R,\mathbf{b}_R \rangle}

对于等式左边，我们将每一项进行展开可得：

Lx2=(gRaL)x2⋅(hLbR)x2⋅ux2⟨aL,bR⟩=gRx2aL⋅hLx2bR⋅ux2⟨aL,bR⟩ L^{x^2} = \big(\mathbf{g}_R^{\mathbf{a}_L}\big)^{x^2} \cdot \big(\mathbf{h}_L^{\mathbf{b}_R}\big)^{x^2} \cdot u^{x^2 \langle \mathbf{a}_L, \mathbf{b}_R \rangle} = \mathbf{g}_R^{x^2 \mathbf{a}_L} \cdot \mathbf{h}_L^{x^2 \mathbf{b}_R} \cdot u^{x^2 \langle \mathbf{a}_L, \mathbf{b}_R \rangle}
Rx−2=(gLaR)x−2⋅(hRbL)x−2⋅ux−2⟨aR,bL⟩=gLx−2aR⋅hRx−2bL⋅ux−2⟨aR,bL⟩ R^{x^{-2}} = \big(\mathbf{g}_L^{\mathbf{a}_R}\big)^{x^{-2}} \cdot \big(\mathbf{h}_R^{\mathbf{b}_L}\big)^{x^{-2}} \cdot u^{x^{-2} \langle \mathbf{a}_R, \mathbf{b}_L \rangle} = \mathbf{g}_L^{x^{-2} \mathbf{a}_R} \cdot \mathbf{h}_R^{x^{-2} \mathbf{b}_L} \cdot u^{x^{-2} \langle \mathbf{a}_R, \mathbf{b}_L \rangle}
P=gLaL⋅gRaR⋅hLbL⋅hRbR⋅u⟨aL,bL⟩+⟨aR,bR⟩ P = \mathbf{g}_L^{\mathbf{a}_L} \cdot \mathbf{g}_R^{\mathbf{a}_R} \cdot \mathbf{h}_L^{\mathbf{b}_L} \cdot \mathbf{h}_R^{\mathbf{b}_R} \cdot u^{\langle \mathbf{a}_L,\mathbf{b}_L \rangle + \langle \mathbf{a}_R,\mathbf{b}_R \rangle}

故，将 Lx2⋅P⋅Rx−2L^{x^2} \cdot P \cdot R^{x^{-2}} 化简得到结果：

gLaL+x−2aR⋅gRx2aL+aR⋅hLbL+x2bR⋅hRbR+x−2bL⋅u⟨aL,bL⟩+⟨aR,bR⟩+x2⟨aL,bR⟩+x−2⟨aR,bL⟩ \boxed{ \mathbf{g}_L^{\mathbf{a}_L + x^{-2} \mathbf{a}_R} \cdot \mathbf{g}_R^{x^2 \mathbf{a}_L + \mathbf{a}_R} \cdot \mathbf{h}_L^{\mathbf{b}_L + x^2 \mathbf{b}_R} \cdot \mathbf{h}_R^{\mathbf{b}_R + x^{-2} \mathbf{b}_L} \cdot u^{\langle \mathbf{a}_L, \mathbf{b}_L \rangle + \langle \mathbf{a}_R, \mathbf{b}_R \rangle + x^2 \langle \mathbf{a}_L, \mathbf{b}_R \rangle + x^{-2} \langle \mathbf{a}_R, \mathbf{b}_L \rangle} }

对于等式右边，由于压缩后 $ \mathbf{a}’ = x \cdot \mathbf{a}_L + x^{-1} \cdot \mathbf{a}_R \ ;\ \mathbf{b}’ = x^{-1} \cdot \mathbf{b}_L + x \cdot \mathbf{b}_R $ 因此：

⟨a′,b′⟩=⟨xaL+x−1aR , x−1bL+xbR⟩=⟨aL,bL⟩+⟨aR,bR⟩+x2⟨aL,bR⟩+x−2⟨aR,bL⟩ \begin{aligned} \langle \mathbf{a}', \mathbf{b}' \rangle &= \langle x \mathbf{a}_L + x^{-1} \mathbf{a}_R \ ,\ x^{-1} \mathbf{b}_L + x \mathbf{b}_R \rangle \\ &= \langle \mathbf{a}_L, \mathbf{b}_L \rangle + \langle \mathbf{a}_R, \mathbf{b}_R \rangle + x^2 \langle \mathbf{a}_L, \mathbf{b}_R \rangle + x^{-2} \langle \mathbf{a}_R, \mathbf{b}_L \rangle \end{aligned}

压缩后的生成元为： $ \mathbf{g}’ = \mathbf{g}_L^{x^{-1}} \circ \mathbf{g}_R^{x}, \quad \mathbf{h}’ = \mathbf{h}_L^{x} \circ \mathbf{h}_R^{x^{-1}}$ , 因此：

g′a′=gLaL+x−2aR⋅gRx2aL+aR,h′b′=hLbL+x2bR⋅hRbR+x−2bL. \mathbf{g}'^{\mathbf{a}'} = \mathbf{g}_L^{a_L + x^{-2} a_R} \cdot \mathbf{g}_R^{x^2 a_L + a_R}, \qquad \mathbf{h}'^{\mathbf{b}'} = \mathbf{h}_L^{b_L + x^2 b_R} \cdot \mathbf{h}_R^{b_R + x^{-2} b_L}.

故，将 g′a′⋅h′b′⋅u⟨a,b⟩g'^{a'} \cdot h'^{b'} \cdot u^{\langle a,b \rangle} 化简得到结果：

(gLx2aL+aR⋅gRaL+x−2aR)⋅(hLbL+x2bR⋅hRbR+x−2bL)⋅(u⟨aL,bL⟩+⟨aR,bR⟩+x2⟨aL,bR⟩+x−2⟨aR,bL⟩) \boxed{ (\mathbf{g}_L^{x^2 a_L + a_R} \cdot \mathbf{g}_R^{a_L + x^{-2} a_R}) \cdot (\mathbf{h}_L^{b_L + x^2 b_R} \cdot \mathbf{h}_R^{b_R + x^{-2} b_L}) \cdot (u^{\langle \mathbf{a}_L, \mathbf{b}_L \rangle + \langle \mathbf{a}_R, \mathbf{b}_R \rangle + x^2 \langle \mathbf{a}_L, \mathbf{b}_R \rangle + x^{-2} \langle \mathbf{a}_R, \mathbf{b}_L \rangle} ) }

通过对比可以看出，等式左右两边完全相同。需要注意的是

2.5 简单的说明

  1. 若 PP 并非以上述形式生成，即 $ P \neq \mathbf{g}^{\mathbf{a}} \cdot \mathbf{h}^{\mathbf{b}} \cdot u^{\langle \mathbf{a}, \mathbf{b} \rangle} , . $ 无论证明者如何伪造 L,R,a′,b′L, R, \mathbf{a}', \mathbf{b}'，更新验证公式 $ P’ = L^{x^2} \cdot P \cdot R^{x^{-2}} \stackrel{?}{=} \mathbf{g}‘^{\mathbf{a}’} \cdot \mathbf{h}‘^{\mathbf{b}’} \cdot u^{\langle \mathbf{a}‘, \mathbf{b}’ \rangle} $ 基本不可能成立。这意味着如果承诺 PP 的结构错误，将无法通过验证。

  2. 如果证明者不知道原始向量 a,b\mathbf{a}, \mathbf{b}，那么他无法计算中间承诺 L,RL, R，也无法计算正确的压缩向量 $ \mathbf{a}’ = x \cdot \mathbf{a}_L + x^{-1} \cdot \mathbf{a}_R \ ,\quad \mathbf{b}’ = x^{-1} \cdot \mathbf{b}_L + x \cdot \mathbf{b}_R , . $ 去回复验证者的挑战 x 。

  3. 因此，在上述压缩后的证明中，如果最后的验证等式成立，那么可以确定 P=ga⋅hb⋅u⟨a,b⟩P = \mathbf{g}^{\mathbf{a}} \cdot \mathbf{h}^{\mathbf{b}} \cdot u^{\langle \mathbf{a}, \mathbf{b} \rangle} 确实是对向量 a,b\mathbf{a}, \mathbf{b} 的承诺，并且证明者确实知道对应的 a,b\mathbf{a}, \mathbf{b}。

  4. 本质上，上述方案的安全性来源于 承诺结构的绑定性 和 离散对数困难性。 因此，如果上述递归过程中的等式 $ P’ = \mathbf{g}‘^{\mathbf{a}’} \cdot \mathbf{h}‘^{\mathbf{b}’} \cdot u^{\langle \mathbf{a}‘, \mathbf{b}’ \rangle} $ 成立，事实上也代表最初要证明的如下关系成立。

    {(g,h,P,c; a,b):P=ga⋅hb∧ c=⟨a,b⟩} \{(\mathbf{g}, \mathbf{h}, P, c;\ \mathbf{a}, \mathbf{b}) : P = \mathbf{g}^{\mathbf{a}} \cdot \mathbf{h}^{\mathbf{b}} \land \ c = \langle \mathbf{a}, \mathbf{b} \rangle \}

2.6 如何证明两个1维向量的承诺成立

我们知道，在上述递归的终止条件中，直接判断P′=?(g′)a′⋅(h′)b′⋅ua′⋅b′P' \stackrel{?}{=} (g')^{a'} \cdot (h')^{b'} \cdot u^{a'\cdot b'} 是否成立，从而验证要证明的关系是否成立。但是当要证明的向量本来就是1维向量时，这种方法会暴露a,b的值，无法达到零知识性。此时可以用下面的方法证明。

验证者拥有生成元 g,h∈Gg, h \in G，以及一个绑定承诺： $ P = g^{a} \cdot h^{b} \cdot u^{a\cdot b} $, 证明者想向验证者证明自己知道 (a,b)(a, b) 且 c=a⋅bc=a\cdot b，但又不直接暴露它们，即证明下列关系成立：

{(g,h,P,c; a,b):P=ga⋅hb∧ c=a⋅b} \{(g, h, P, c;\ a, b) : P = g^a \cdot h^b \land \ c = a\cdot b \}

  1. 证明者 首先将公共参数 (g,h)(g,h) 和承诺及内积 (P,c)(P,c) 发给验证者。(也可约定双方事先知道这些)

  2. 验证者 随机生成 x∈Zp∗x \in \mathbb{Z}_p^\ast 并发送给证明者。

  3. 证明者 根据首先使用原始承诺和向量 a,ba,b 计算

    L=ha,R=gb;g′=gx−1⋅hx;P′=Lx2⋅P⋅Rx−2 L = h^{a}, \quad R = g^{b} \quad ; \quad g' = g^{x^{-1}} \cdot h^{x} \quad ; \quad P' = L^{x^2} \cdot P \cdot R^{x^{-2}}
    然后根据挑战 xx 计算响应 a′=a⋅x+b⋅x−1a' = a \cdot x + b \cdot x^{-1}。并将 (L,R,a′)(L,R,a') 发送给验证者。

  4. 验证者 首先根据自己选择的挑战和证明者发来的 L,RL,R 计算

    g′=gx−1⋅hx;P′=Lx2⋅P⋅Rx−2 g' = g^{x^{-1}} \cdot h^{x} \quad ; \quad P' = L^{x^2} \cdot P \cdot R^{x^{-2}}
    然后检查等式 P′=?(g′)a′P' \stackrel{?}{=} (g')^{a'} 是否成立，若成立，验证者接受；否则拒绝。

2.7 通讯成本分析：

通过上述递归算法可知：每次递归需要发送 2 个群元素 (Li,Ri)(L_i, R_i)，当向量的维度为n时，共 2 log2n2\ log_2 n 个群元素。而最后一轮发送两个标量 a,ba, b，因此证明两个 n 维向量 a,b\mathbf{a},\mathbf{b} 满足关系：

{(g,h,P,c; a,b):P=ga⋅hb∧ c=⟨a,b⟩} \{(\mathbf{g}, \mathbf{h}, P, c;\ \mathbf{a}, \mathbf{b}) : P = \mathbf{g}^{\mathbf{a}} \cdot \mathbf{h}^{\mathbf{b}} \land \ c = \langle \mathbf{a}, \mathbf{b} \rangle \}

所需要的总通信为： (2log⁡2n)×G+2×Zp(2 \log_2 n)× \mathbb{G} + 2 × \mathbb{Z}_p 相比原始发送向量方案的 2n2n，优势明显。

2.8 零知识与可验证性

作者在原文中证明，该协议构成一个 Sigma 协议，满足Completeness、Special Honest-Verifier Zero-Knowledge(HVZK) 以及 Special Soundness。同时，作者给出了相应的模拟器与提取器的构造方法，并利用 forking lemma 将协议的安全性归约到离散对数困难问题。在此基础上，该协议还可以通过 Fiat–Shamir 变换转化为非交互形式。

区间证明

介绍上述改进的内积论证作为基础知识之后，下面可以开始介绍区间证明的内容了。

三、区间证明思路分析

在这一节中，作者提出了一种基于改进内积论证的区间证明方法，用于证明承诺值 VV 对应的秘密数 vv 落在区间 [0,2n−1][0, 2^n - 1] 内，而不泄露 vv 的具体数值。

3.1 区间证明思路分析

区间证明的目标可以描述为：证明者持有 v∈Zpv \in \mathbb{Z}_p 及其 Pedersen 承诺：V=hγgvV = h^\gamma g^v，他想要向验证者证明 VV 中承诺的数据 v∈[0,2n−1]v \in [0, 2^n-1]。把它写成一个正式的零知识证明如下：

{(g,h∈G,V,n ; v,γ∈Zp):V=hγgv∧v∈[0,2n−1]}(1) \{ (g,h \in \mathbb{G}, V, n \ ;\ v,\gamma \in \mathbb{Z}_p) : V = h^\gamma g^v \wedge v \in [0,2^n - 1] \} \tag{1}

3.2 上述关系可等价为下面的关系

想要证明 (1)(1) 中的关系，有点无从下手的感觉，为此作者将这个证明进行了转换如下：

  1. 可以将 vv 的二进制展开写作向量：aL∈{0,1}n\mathbf{a}_L \in \{0,1\}^n, 那么我们有 v=⟨aL,2n⟩v = \langle \mathbf{a}_L, 2^n \rangle
  2. 为了使证明者相信 aLa_L 确实只有 {0,1}\{0,1\}组成, 定义 $ \mathbf{a}_R = \mathbf{a}_L - \mathbf{1}^n $ 并保证：aL∘aR=0n\mathbf{a}_L \circ \mathbf{a}_R = 0^n。如果上面的式子均满足，那么 aL\mathbf{a}_L 的每个分量只能是 0 或 1。

    证明如下：由定义 aR=aL−1n\mathbf{a}_R = \mathbf{a}_L - \mathbf{1}^n和 aL∘aR=0n\mathbf{a}_L \circ \mathbf{a}_R = 0^n 可得,对于向量 aLa_L中的每个分量 aia_i 有等式 ai(ai−1)=0a_i(a_i - 1) = 0成立。因此我们有 ai=0a_i = 0 或 ai=1a_i = 1。因此可得 aL∈{0,1}n\mathbf{a}_L \in \{0,1\}^n。
  3. 我们可将证明 (1)(1) 中的关系转化为证明下面的关系：
⟨aL,2n⟩=v∧aL∘aR=0n∧aR=aL−1n(2) \langle \mathbf{a}_L, \mathbf{2}^n \rangle = v \quad \land \quad \mathbf{a}_L \circ \mathbf{a}_R = \mathbf{0}^n \quad \land \quad \mathbf{a}_R = \mathbf{a}_L - \mathbf{1}^n \tag{2}

3.3 对约束进行变形

  1. 上述3.2中证明的约束关系可以进一步转化为：
⟨aL,2n⟩=v∧⟨aL,aR∘yn⟩=0∧⟨aL−1n−aR,yn⟩=0(3) \langle \mathbf{a}_L, \mathbf{2}^n \rangle = v \quad \land \quad \langle \mathbf{a}_L, \mathbf{a}_R \circ \mathbf{y}^n \rangle = 0 \quad \land \quad \langle \mathbf{a}_L - \mathbf{1}^n - \mathbf{a}_R , \mathbf{y}^n \rangle = 0 \tag{3}
  1. 之所以能将 3.2 中的多个约束转化为 3.3 的形式，是因为我们利用了 随机线性组合技术。具体地，验证者从 Zp\mathbb{Z}_p 中随机选择一个挑战 yy，并要求证明者证明下式成立：
    ⟨aL,aR∘yn⟩=0,⟨aL−1n−aR,yn⟩=0. \langle \mathbf{a}_L, \mathbf{a}_R \circ \mathbf{y}^n \rangle = 0, \qquad \langle \mathbf{a}_L - \mathbf{1}^n - \mathbf{a}_R , \mathbf{y}^n \rangle = 0.
  2. 如果 3.2 中的原始约束没有全部满足，那么上述等式在随机 yy 下成立的概率至多为 np\frac{n}{p}，可忽略不计。因此，只要在随机挑战下等式成立，我们就能认为原始约束关系也成立。
    这样就把原来的 2n+12n+1 个约束条件压缩成了少量内积形式，从而可以在后续应用 改进的内积论证来高效验证。

3.4 将约束转化为内积

上述3.2中证明的约束关系转化为内积，这可以通过随机线性组合的技巧来做。具体来说，三个约束关系 ⟨aL,2n⟩=v\langle \mathbf{a}_L, 2^n \rangle = v、aL∘aR=0n\mathbf{a}_L \circ \mathbf{a}_R = 0^n 和 aR=aL−1n\mathbf{a}_R = \mathbf{a}_L - \mathbf{1}^n 可以转化为：

z2⋅⟨aL,2n⟩+z⋅⟨aL−1n−aR,yn⟩+⟨aL,aR∘yn⟩=z2⋅v z^2 \cdot \langle \mathbf{a}_L, \mathbf{2}^n \rangle + z \cdot \langle \mathbf{a}_L - \mathbf{1}^n - \mathbf{a}_R , \mathbf{y}^n \rangle + \langle \mathbf{a}_L , \mathbf{a}_R \circ \mathbf{y}^n \rangle = z^2 \cdot v

其中，zz 是一个随机数。若原始约束不成立，则新关系成立的概率可忽略。为了利用内积论证，作者将上述关系进一步写成：

⟨aL−z⋅1n , yn∘(aR+z⋅1n)+z2⋅2n⟩=z2⋅v+δ(y,z)(4) \left\langle \mathbf{a}_L - z \cdot \mathbf{1}^n \ ,\ \mathbf{y}^n \circ (\mathbf{a}_R + z \cdot \mathbf{1}^n) + z^2 \cdot \mathbf{2}^n \right\rangle = z^2 \cdot v + \delta(y,z) \tag{4}
δ(y,z)=(z−z2)⋅⟨1n,yn⟩−z3⋅⟨1n,2n⟩∈Zp \delta(y,z) = (z - z^2)\cdot \langle \mathbf{1}^n, \mathbf{y}^n \rangle - z^3 \cdot \langle \mathbf{1}^n, \mathbf{2}^n \rangle \in \mathbb{Z}_p

此时事实上已经可以直接发送向量 aL−z⋅1n\mathbf{a}_L - z \cdot \mathbf{1}^n 和 yn∘(aR+z⋅1n)+z2⋅2n\mathbf{y}^n \circ (\mathbf{a}_R + z \cdot \mathbf{1}^n) + z^2 \cdot \mathbf{2}^n 给验证者，从而证明 (1)(1) 成立了。但是这么做会暴露 aLa_L 的信息，为此作者引入多项式对两个向量进行盲化。

3.5 构造多项式盲化

为避免泄露秘密，作者引入了盲化向量 sL,sR∈Zpn\mathbf{s}_L, \mathbf{s}_R \in \mathbb{Z}_p^n，并构造多项式 l(x),r(x)l(x),r(x) 并计算 t(x)t(x)：

l(X)=(aL−z⋅1n)+sL⋅X, l(X) = (\mathbf{a}_L - z \cdot \mathbf{1}^n) + \mathbf{s}_L \cdot X ,
r(X)=yn∘(aR+z⋅1n+sR⋅X)+z2⋅2n r(X) = \mathbf{y}^n \circ (\mathbf{a}_R + z \cdot \mathbf{1}^n + \mathbf{s}_R \cdot X) + z^2 \cdot \mathbf{2}^n
t(X)=⟨l(X),r(X)⟩=t0+t1⋅X+t2⋅X2 t(X) = \langle l(X), r(X) \rangle = t_0 + t_1 \cdot X + t_2 \cdot X^2

其中t0t_0 对应 (4)(4) 的常数项： $ t_0 = v \cdot z^2 + \delta(y,z) $ 证明者仅需对 t(X)t(X) 的系数 (t0,t1,t2)(t_0,t_1,t_2) 进行承诺，并在验证者随机给定 x∈Zp∗x \in \mathbb{Z}_p^\ast 时公开 l(x),r(x)l(x), r(x)，即可在不泄露 aL,aR\mathbf{a}_L, \mathbf{a}_R 的前提下完成验证。

说明：

  • 容易看出 l(0)=aL−z⋅1nl(0) = \mathbf{a}_L - z \cdot \mathbf{1}^n, 并且 r(0)=yn∘(aR+z⋅1n+sR⋅X)+z2⋅2nr(0)=\mathbf{y}^n \circ (\mathbf{a}_R + z \cdot \mathbf{1}^n + \mathbf{s}_R \cdot X) + z^2 \cdot \mathbf{2}^n。
  • 当证明者给出的 X=xX=x 不等于 0 时，向量 l(x)l(x) 和 r(x)r(x) 是使用 sLs_L 和 sRs_R 以及 xx 对向量 a\mathbf{a} 和 b\mathbf{b} 随机化之后得到的向量。此时敌手不能从中得到任何关于 向量 a\mathbf{a} 和 b\mathbf{b} 的信息。
  • 将 t(x)t(x) 展开可以得到常数项刚好等于式 (4)(4), 也就是 t0=v⋅z2+δ(y,z)t_0 = v \cdot z^2 + \delta(y,z)。而 t(x)t(x) 的另外两个系数 t1t_1 和 t2t_2 也可以很容易的计算出来，这里不在写出来。

3.6 总结

到了这里，我们已经将 “证明一个Pederson承诺中的承诺的值 v 属于某区间” 转换成了 “证明两个向量的内积等于某个值”，并且通过对向量进行盲化，防止了对承诺值 v 的信息泄泄露。下面我们将介绍区间证明的整个证明过程。

四、区间证明完整流程

下面描述了证明者 PIP\mathcal{P}_{IP} 和验证者 V\mathcal{V} 在区间证明中的交互过程。

4.1、交互式的流程

证明者 PIP\mathcal{P}_{IP} 执行：

  1. 选择向量 aL∈{0,1}n\mathbf{a}_L \in \{0,1\}^n，满足 ⟨aL,2n⟩=v\langle \mathbf{a}_L, \mathbf{2}^n \rangle = v, 并计算 aR=aL−1n\mathbf{a}_R = \mathbf{a}_L - \mathbf{1}^n

  2. 随机选择 α←$Zp\alpha \xleftarrow{\$} \mathbb{Z}_p 以计算向量 aL\mathbf{a}_L 和 aR\mathbf{a}_R 的承诺 A=hα⋅gaL⋅haRA = h^\alpha \cdot \mathbf{g}^{\mathbf{a}_L} \cdot \mathbf{h}^{\mathbf{a}_R}。

  3. 随机选择盲化向量 sL,sR←$Zpn\mathbf{s}_L, \mathbf{s}_R \xleftarrow{\$} \mathbb{Z}_p^n，和 ρ←$Zp\rho \xleftarrow{\$} \mathbb{Z}_p。计算盲化向量的承诺 S=hρ⋅gsL⋅hsRS = h^\rho \cdot \mathbf{g}^{\mathbf{s}_L} \cdot \mathbf{h}^{\mathbf{s}_R}

  4. 将原始向量的承诺和盲化向量的承诺 A,SA, S 发送给验证者 V\mathcal{V}。

验证者 V\mathcal{V} 执行：

  1. 验证者选择 y,z←$Zp∗y, z \xleftarrow{\$} \mathbb{Z}_p^\ast

  2. 将 y,zy, z 发送给证明者

证明者 PIP\mathcal{P}_{IP} 执行：

  1. 构造盲化多项式 l(x),r(x)l(x),r(x) 并计算 t(x)t(x) 以得到三个系数 t0,t1,t2t_0,t_1,t_2。为了证明 t0=v⋅z2+δ(y,z)t_0 = v \cdot z^2 + \delta(y,z)，首先对 t1,t2t_1,t_2 进行承诺。

  2. 选择随机数 τ1,τ2←$Zp\tau_1, \tau_2 \xleftarrow{\$} \mathbb{Z}_p 并计算 Ti=gτi⋅hti,i=1,2T_i = g^{\tau_i} \cdot h^{t_i}, \quad i=1,2，并将 T1,T2T_1, T_2 发送给验证者。

验证者 V\mathcal{V} 执行：

  1. 验证者选择 x←$Zp∗x \xleftarrow{\$} \mathbb{Z}_p^\ast 作为挑战发送给证明者。

证明者 PIP\mathcal{P}_{IP} 执行：

  1. 首先计算在挑战 xx 下，盲化后的向量如下：

    l=aL−z⋅1n+sL⋅x;r=yn∘(aR+z⋅1n+sR⋅x)+z2⋅2n;t^=⟨l,r⟩ \mathbf{l} = \mathbf{a}_L - z \cdot \mathbf{1}^n + \mathbf{s}_L \cdot x \quad ; \quad \mathbf{r} = \mathbf{y}^n \circ (\mathbf{a}_R + z \cdot \mathbf{1}^n + \mathbf{s}_R \cdot x) + z^2 \cdot \mathbf{2}^n \quad ; \quad \hat{t} = \langle \mathbf{l}, \mathbf{r} \rangle

  2. 针对验证者的挑战 xx , 计算响应： $\tau_x = \tau_2 \cdot x^2 + \tau_1 \cdot x + z^2 \cdot \gamma \quad ; \quad \mu = \alpha + \rho \cdot x$

  3. 最终将 (τx,μ,t^,l,r)(\tau_x, \mu, \hat{t}, \mathbf{l}, \mathbf{r}) 发送给验证者。

说明：

  • 实际上， 响应 τx\tau_x 证明了证明者拥有 承诺 T1,T2,VT_1, T_2, V 中使用的随机数 t1,t2,γt_1, t_2, \gamma
  • 响应 μ\mu 则证明证明者拥有 原始向量和盲化向量承诺 A,SA,S 中使用的随机数 α,ρ\alpha,\rho

验证者 V\mathcal{V} 执行：

  1. 首先验证：证明者对挑战 xx 的响应 t^=t(x)\hat{t}=t(x) 是否是用承诺的多项式 t(x)=t0+t1x+t2x2t(x)=t_0 + t_1x+t_2x^2 计算得到的，这可以通过验证以下的等式来完成：
gt^⋅hτx=?Vz2⋅gδ(y,z)⋅T1x⋅T2x2 g^{\hat{t}} \cdot h^{\tau_x} \stackrel{?}{=} V^{z^2} \cdot g^{\delta(y,z)} \cdot T_1^x \cdot T_2^{x^2}
  1. 在 r(x)r(x) 的构造中，我们引入了 aR∘yn\mathbf{a_R} \circ \mathbf{y^n} 和 sR∘yn\mathbf{s_R} \circ \mathbf{y^n} 。因此，为了构造 r(x)r(x) 的承诺，需要首先构造出 aR∘yn\mathbf{a_R} \circ \mathbf{y^n} 和 sR∘yn\mathbf{s_R} \circ \mathbf{y^n} 的向量承诺。为此，首先计算 hi′=hi(y−i+1), ∀i∈[1,n]h_i' = h_i^{(y^{-i+1})}, \ \forall i \in [1,n]，然后即可使用已有的承诺 A,SA,S 构造出 l(x)l(x) 和 r(x)r(x) 的承诺如下：
P=A⋅Sx⋅g−z⋅(h′)z⋅yn+z2⋅2n P = A \cdot S^x \cdot \mathbf{g}^{-z} \cdot (h')^{z \cdot \mathbf{y^n} + z^2\cdot \mathbf{2^n}}
  1. 接着，即可通过以下的等式验证 l\mathbf{l} 和 r\mathbf{r} 是否是使用承诺的 l(x)l(x) 和 r(x)r(x) 计算得到的。
P=?hμ⋅gl⋅(h′)r(5) P \stackrel{?}{=} h^\mu \cdot \mathbf{g}^{\mathbf{l}} \cdot (\mathbf{h}')^{\mathbf{r}} \tag{5}
  1. 最终，证明 t^\hat{t} 是通过 t^=⟨l,r⟩\hat{t} = \langle \mathbf{l},\mathbf{r} \rangle 计算得来的，这可以通过验证下面的等式实现。
t^=?⟨l,r⟩(6) \hat{t} \stackrel{?}{=} \langle \mathbf{l},\mathbf{r} \rangle \tag{6}

说明，上述验证过程验证了：

  • 证明者给出得响应 l\mathbf{l},r\mathbf{r} 是通过实现承诺的多项式 l(x),r(x)l(x),r(x) 生成的。
  • 证明者给出的响应 t^\hat{t} 确实是通过 ⟨l\langle\mathbf{l},r⟩\mathbf{r} \rangle 计算得到的，即 t^=⟨l\hat{t} = \langle\mathbf{l},r⟩\mathbf{r} \rangle
  • 证明者给出的响应 t^\hat{t} 确实是承诺的二次多项式 t(x)=t0+t1X+t2X2t(x) = t_0 + t_1X + t_2 X^2 在挑战 xx 处的取值，即 t^=t0+t1x+t2x2\hat{t} = t_0 + t_1x + t_2 x^2, 并且这里的常数项 t0t_0 满足：
    t0=⟨aL−z⋅1n , yn∘(aR+z⋅1n)+z2⋅2n⟩=z2⋅v+δ(y,z) t_0 = \left\langle \mathbf{a}_L - z \cdot \mathbf{1}^n \ ,\ \mathbf{y}^n \circ (\mathbf{a}_R + z \cdot \mathbf{1}^n) + z^2 \cdot \mathbf{2}^n \right\rangle = z^2 \cdot v + \delta(y,z)

综上所述，上述验证如果全部通过，则可证明等式 (4)(4) 成立，也即是最初的区间证明成立。我们在整个证明过程中没有泄露任何 aL,aR\mathbf{a_L},\mathbf{a_R}的信息，也即是没有泄露 vv 的信息。故，我们证明了：

{(g,h∈G,V,n ; v,γ∈Zp):V=hγgv∧v∈[0,2n−1]} \{ (g,h \in \mathbb{G}, V, n \ ;\ v,\gamma \in \mathbb{Z}_p) : V = h^\gamma g^v \wedge v \in [0,2^n - 1] \}

4.2、引入改进的内积论证优化证明大小

在 4.1 节中，证明者需要直接发送向量 l,r∈Zpn\mathbf{l}, \mathbf{r} \in \mathbb{Z}_p^n，其通信量为 2n2n 个元素，规模是线性的。为了降低通信开销，4.2 节引入上面介绍的 改进的内积论证 来把证明大小降低为对数级别。

在 (5)(5) 和 (6)(6) 中，验证者需要检查的条件是：

P=?hμ⋅gl⋅(h′)r;t^=?⟨l,r⟩ P \stackrel{?}{=} h^\mu \cdot \mathbf{g}^{\mathbf{l}} \cdot (\mathbf{h}')^{\mathbf{r}} \quad ; \quad \hat{t} \stackrel{?}{=} \langle \mathbf{l}, \mathbf{r} \rangle

这正好就是一个 内积关系, 可以把要验证的关系重新表述为：

{(g,h′,Ph−μ,t^); l,r∈Zpn:Ph−μ=gl⋅h′r∧t^=⟨l,r⟩} \{ (\mathbf{g}, \mathbf{h}', P h^{-\mu}, \hat{t}); \ \mathbf{l}, \mathbf{r} \in \mathbb{Z}_p^n : P h^{-\mu} = \mathbf{g}^{\mathbf{l}}\cdot \mathbf{h'}^{\mathbf{r}} \land \hat{t} = \langle \mathbf{l}, \mathbf{r} \rangle \}

这就把原始的检验条件转化为了内积论证问题，使用前面的改进内积论证即可压缩证明大小。

4.2、非交互式的证明

将上述协议转换为非交互式的协议是非常简单，直接使用 Fiat-Shamir 变换将三个挑战 x,y,zx,y,z 使用哈希函数代替即可。如：可以让 y=H(st,A,S)y=H(st,A,S) , z=H(A,S,y)z=H(A,S,y), x=H(T1,T2,x,y)x=H(T_1,T_2,x,y)。