2025-07-24  2025-07-24    7692 字  16 分钟
- 论文笔记

区间证明（BulletProof）

这里简单记一下BulletProof 论文的笔记，以便于后续用到时能够快速回想起来。这是一篇关于区间证明的文章，用于证明承诺的值属于某个区间。区间证明的目标可以描述为：证明者持有 $v \in \mathbb{Z}_p$ 及其 Pedersen 承诺：$V = h^\gamma g^v$，他想要向验证者证明 $V$ 中承诺的数据 $v \in [0, 2^n-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 群相关记号

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

  • $G^n$ 与 $\mathbb{Z}_p^n$ 分别表示定义在 $G$ 与 $\mathbb{Z}_p$ 上的长度为 $n$ 的向量空间。

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

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

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

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

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

1.2 内积和Hadamard积

  • 对于标量 $c \in \mathbb{Z}_p$ 和向量 $\mathbf{a} \in \mathbb{Z}_p^n$，用 $\mathbf{b} = c \cdot \mathbf{a}$ 表示 $b_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) = \sum_{i=0}^d \mathbf{p}_i X^i \in \mathbb{Z}_p^n[X]$；
  • 对于两个向量多项式 $\mathbf{l}(X), \mathbf{r}(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) := \langle \mathbf{l}(X), \mathbf{r}(X) \rangle$，则对任意 $x \in \mathbb{Z}_p$ 有： $t(x) = \langle \mathbf{l}(x), \mathbf{r}(x) \rangle$

1.4 向量承诺与变换

  • 给定 $\mathbf{g} = (g_1, \ldots, g_n) \in G^n$ 和向量 $\mathbf{a} \in \mathbb{Z}_p^n$，则向量 $\mathbf{a}$ 的承诺为：

$$ C = \mathbf{g}^\mathbf{a} = \prod_{i=1}^n g_i^{a_i} $$

  • 该承诺是对向量 $\mathbf{a}$ 的绑定承诺（但非隐藏）。 若已知另一个向量 $\mathbf{b} \in \mathbb{Z}_p^n$（元素均非零），可定义 $g’_i = g_i^{b_i^{-1}}$，以构造一个新的对 $\mathbf{a} \circ \mathbf{b}$ 的承诺：

$$ C = \prod_{i=1}^n (g’_i)^{a_i \cdot b_i} $$

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

  • 若 $\mathbf{a} \in \mathbb{Z}_p^n$，$\mathbf{b} \in \mathbb{Z}_p^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 \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} 表示一个指定公开输入和证明者见证的关系。

  • 例如：证明者想证明自己知道向量 $\mathbf{a}, \mathbf{b} \in \mathbb{Z}_p^n$，使得它们满足内积等于某个标量 $c$，并且两者的 Pedersen 向量承诺为 $P = \mathbf{g}^\mathbf{a} \mathbf{h}^\mathbf{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 内积论证: 设有两个生成元向量 $\mathbf{g}, \mathbf{h} \in G^n$，以及对待承诺向量 $\mathbf{a}, \mathbf{b} \in \mathbb{Z}_p^n$ 的绑定不隐藏向量承诺$P = \mathbf{g}^{\mathbf{a}} \cdot \mathbf{h}^{\mathbf{b}} \in G$，以及一个标量 $c \in \mathbb{Z}_p$。内积论证是为了向验证者证明以下关系同时成立：

$$ \{ (\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 \} $$

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

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

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

设有两个生成元向量 $\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 \in G$ 是一个额外的生成元，$\mathbf{a}, \mathbf{b} \in \mathbb{Z}_p^n$ 是证明者的私有向量。该改进型内积论证的目标是向验证者证明：

$$ \{ (\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} \} $$

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

2.3 如何将通信复杂度降至 $2 \log_2 n$

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

2.3.1 对待原始关系进行转化

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

$$ \{(\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 \} $$

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

$$ \{(\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} \} $$

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

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

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

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

  2. 构造中间承诺：计算中间承诺 $L$ 和 $R$ 如下，用于绑定 $\langle \mathbf{a}_L, \mathbf{b}_R \rangle$ 和 $\langle \mathbf{a}_R, \mathbf{b}_L \rangle$： $$ 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. 挑战生成：验证者从 $\mathbb{Z}_p$ 中随机选择一个挑战 $x$ 并发送给证明者。

  4. 向量与生成元压缩：证明者根据挑战 $x$ 构造压缩后的新向量和生成元： $$ \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 $$ $$ \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}} $ 此时，新的关系为： $$ \{(\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. 递归进行下一轮：以 $(\mathbf{g}’, \mathbf{h}’, \mathbf{a}’, \mathbf{b}’, P’)$ 为新的输入，进入下一轮，直到向量长度为 1。

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

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

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

首先，对新承诺 $P’$ 进行展开。根据定义有： $ P’ = L^{x^2} \cdot P \cdot R^{x^{-2}} $ 其中： $$ 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 = \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} $$

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

$$ 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} $$

$$ 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 = \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} $$

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

$$ \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 $ 因此：

$$ \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}}$ , 因此： $$ \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’} \cdot h’^{b’} \cdot u^{\langle a,b \rangle}$ 化简得到结果：

$$ \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. 若 $P$ 并非以上述形式生成，即 $ P \neq \mathbf{g}^{\mathbf{a}} \cdot \mathbf{h}^{\mathbf{b}} \cdot u^{\langle \mathbf{a}, \mathbf{b} \rangle} , . $ 无论证明者如何伪造 $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} $ 基本不可能成立。这意味着如果承诺 $P$ 的结构错误，将无法通过验证。

  2. 如果证明者不知道原始向量 $\mathbf{a}, \mathbf{b}$，那么他无法计算中间承诺 $L, 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 = \mathbf{g}^{\mathbf{a}} \cdot \mathbf{h}^{\mathbf{b}} \cdot u^{\langle \mathbf{a}, \mathbf{b} \rangle}$ 确实是对向量 $\mathbf{a}, \mathbf{b}$ 的承诺，并且证明者确实知道对应的 $\mathbf{a}, \mathbf{b}$。

  4. 本质上，上述方案的安全性来源于 承诺结构的绑定性 和 离散对数困难性。 因此，如果上述递归过程中的等式 $ P’ = \mathbf{g}’^{\mathbf{a}’} \cdot \mathbf{h}’^{\mathbf{b}’} \cdot u^{\langle \mathbf{a}’, \mathbf{b}’ \rangle} $ 成立，事实上也代表最初要证明的如下关系成立。 $$ \{(\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’ \stackrel{?}{=} (g’)^{a’} \cdot (h’)^{b’} \cdot u^{a’\cdot b’}$ 是否成立，从而验证要证明的关系是否成立。但是当要证明的向量本来就是1维向量时，这种方法会暴露a,b的值，无法达到零知识性。此时可以用下面的方法证明。

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

$$ \{(g, h, P, c;\ a, b) : P = g^a \cdot h^b \land \ c = a\cdot b \} $$

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

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

  3. 证明者 根据首先使用原始承诺和向量 $a,b$ 计算 $$ 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}} $$ 然后根据挑战 $x$ 计算响应 $a’ = a \cdot x + b \cdot x^{-1}$。并将 $(L,R,a’)$ 发送给验证者。

  4. 验证者 首先根据自己选择的挑战和证明者发来的 $L,R$ 计算 $$ g’ = g^{x^{-1}} \cdot h^{x} \quad ; \quad P’ = L^{x^2} \cdot P \cdot R^{x^{-2}} $$ 然后检查等式 $P’ \stackrel{?}{=} (g’)^{a’}$ 是否成立，若成立，验证者接受；否则拒绝。

2.7 通讯成本分析：

通过上述递归算法可知：每次递归需要发送 2 个群元素 $(L_i, R_i)$，当向量的维度为n时，共 $2\ log_2 n$ 个群元素。而最后一轮发送两个标量 $a, b$，因此证明两个 n 维向量 $\mathbf{a},\mathbf{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 \log_2 n)× \mathbb{G} + 2 × \mathbb{Z}_p$ 相比原始发送向量方案的 $2n$，优势明显。

2.8 零知识与可验证性

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

区间证明

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

三、区间证明思路分析

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

3.1 区间证明思路分析

区间证明的目标可以描述为：证明者持有 $v \in \mathbb{Z}_p$ 及其 Pedersen 承诺：$V = h^\gamma g^v$，他想要向验证者证明 $V$ 中承诺的数据 $v \in [0, 2^n-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. 可以将 $v$ 的二进制展开写作向量：$\mathbf{a}_L \in {0,1}^n$, 那么我们有 $v = \langle \mathbf{a}_L, 2^n \rangle$
  2. 为了使证明者相信 $a_L$ 确实只有 $\{0,1\}$组成, 定义 $ \mathbf{a}_R = \mathbf{a}_L - \mathbf{1}^n $ 并保证：$\mathbf{a}_L \circ \mathbf{a}_R = 0^n$。如果上面的式子均满足，那么 $\mathbf{a}_L$ 的每个分量只能是 0 或 1。
    \\ 证明如下：由定义 $\mathbf{a}_R = \mathbf{a}_L - \mathbf{1}^n$和 $\mathbf{a}_L \circ \mathbf{a}_R = 0^n$ 可得,对于向量 $a_L$中的每个分量 $a_i$ 有等式 $a_i(a_i - 1) = 0$成立。因此我们有 $a_i = 0$ 或 $a_i = 1$。因此可得 $\mathbf{a}_L \in \{0,1\}^n$。
  3. 我们可将证明 $(1)$ 中的关系转化为证明下面的关系：

$$ \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中证明的约束关系可以进一步转化为：

$$ \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 的形式，是因为我们利用了 随机线性组合技术。具体地，验证者从 $\mathbb{Z}_p$ 中随机选择一个挑战 $y$，并要求证明者证明下式成立： $$ \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 中的原始约束没有全部满足，那么上述等式在随机 $y$ 下成立的概率至多为 $\frac{n}{p}$，可忽略不计。因此，只要在随机挑战下等式成立，我们就能认为原始约束关系也成立。
    这样就把原来的 $2n+1$ 个约束条件压缩成了少量内积形式，从而可以在后续应用 改进的内积论证来高效验证。

3.4 将约束转化为内积

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

$$ 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 $$

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

$$ \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} $$

$$ \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 $$

此时事实上已经可以直接发送向量 $\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$ 给验证者，从而证明 $(1)$ 成立了。但是这么做会暴露 $a_L$ 的信息，为此作者引入多项式对两个向量进行盲化。

3.5 构造多项式盲化

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

$$ l(X) = (\mathbf{a}_L - z \cdot \mathbf{1}^n) + \mathbf{s}_L \cdot X , $$

$$ 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) = \langle l(X), r(X) \rangle = t_0 + t_1 \cdot X + t_2 \cdot X^2 $$

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

说明：

  • 容易看出 $l(0) = \mathbf{a}_L - z \cdot \mathbf{1}^n$, 并且 $r(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=x$ 不等于 0 时，向量 $l(x)$ 和 $r(x)$ 是使用 $s_L$ 和 $s_R$ 以及 $x$ 对向量 $\mathbf{a}$ 和 $\mathbf{b}$ 随机化之后得到的向量。此时敌手不能从中得到任何关于 向量 $\mathbf{a}$ 和 $\mathbf{b}$ 的信息。
  • 将 $t(x)$ 展开可以得到常数项刚好等于式 $(4)$, 也就是 $t_0 = v \cdot z^2 + \delta(y,z)$。而 $t(x)$ 的另外两个系数 $t_1$ 和 $t_2$ 也可以很容易的计算出来，这里不在写出来。

3.6 总结

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

四、区间证明完整流程

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

4.1、交互式的流程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. 首先计算在挑战 $x$ 下，盲化后的向量如下：
    $$ \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. 针对验证者的挑战 $x$ , 计算响应： $\tau_x = \tau_2 \cdot x^2 + \tau_1 \cdot x + z^2 \cdot \gamma \quad ; \quad \mu = \alpha + \rho \cdot x$

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

说明：

  • 实际上， 响应 $\tau_x$ 证明了证明者拥有 承诺 $T_1, T_2, V$ 中使用的随机数 $t_1, t_2, \gamma$
  • 响应 $\mu$ 则证明证明者拥有 原始向量和盲化向量承诺 $A,S$ 中使用的随机数 $\alpha,\rho$

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

  1. 首先验证：证明者对挑战 $x$ 的响应 $\hat{t}=t(x)$ 是否是用承诺的多项式 $t(x)=t_0 + t_1x+t_2x^2$ 计算得到的，这可以通过验证以下的等式来完成：

$$ 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)$ 的构造中，我们引入了 $\mathbf{a_R} \circ \mathbf{y^n}$ 和 $\mathbf{s_R} \circ \mathbf{y^n}$ 。因此，为了构造 $r(x)$ 的承诺，需要首先构造出 $\mathbf{a_R} \circ \mathbf{y^n}$ 和 $\mathbf{s_R} \circ \mathbf{y^n}$ 的向量承诺。为此，首先计算 $h_i’ = h_i^{(y^{-i+1})}, \ \forall i \in [1,n]$，然后即可使用已有的承诺 $A,S$ 构造出 $l(x)$ 和 $r(x)$ 的承诺如下：

$$ P = A \cdot S^x \cdot \mathbf{g}^{-z} \cdot (h’)^{z \cdot \mathbf{y^n} + z^2\cdot \mathbf{2^n}} $$

  1. 接着，即可通过以下的等式验证 $\mathbf{l}$ 和 $\mathbf{r}$ 是否是使用承诺的 $l(x)$ 和 $r(x)$ 计算得到的。

$$ P \stackrel{?}{=} h^\mu \cdot \mathbf{g}^{\mathbf{l}} \cdot (\mathbf{h}’)^{\mathbf{r}} \tag{5} $$

  1. 最终，证明 $\hat{t}$ 是通过 $\hat{t} = \langle \mathbf{l},\mathbf{r} \rangle$ 计算得来的，这可以通过验证下面的等式实现。

$$ \hat{t} \stackrel{?}{=} \langle \mathbf{l},\mathbf{r} \rangle \tag{6} $$

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

  • 证明者给出得响应 $\mathbf{l}$,$\mathbf{r}$ 是通过实现承诺的多项式 $l(x),r(x)$ 生成的。
  • 证明者给出的响应 $\hat{t}$ 确实是通过 $\langle\mathbf{l}$,$\mathbf{r} \rangle$ 计算得到的，即 $\hat{t} = \langle\mathbf{l}$,$\mathbf{r} \rangle$
  • 证明者给出的响应 $\hat{t}$ 确实是承诺的二次多项式 $t(x) = t_0 + t_1X + t_2 X^2$ 在挑战 $x$ 处的取值，即 $\hat{t} = t_0 + t_1x + t_2 x^2$, 并且这里的常数项 $t_0$ 满足： $$ 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)$ 成立，也即是最初的区间证明成立。我们在整个证明过程中没有泄露任何 $\mathbf{a_L},\mathbf{a_R}$的信息，也即是没有泄露 $v$ 的信息。故，我们证明了：

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

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

$$ 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 $$

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

$$ \{ (\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,z$ 使用哈希函数代替即可。如：可以让 $y=H(st,A,S)$ , $z=H(A,S,y)$, $x=H(T_1,T_2,x,y)$。

Websocketpp库 →