用户: Guoh064/Bulletproofs

Bulletproofs 是一种无需信任基础设置的范围证明. 其特点在于零知识证明性、与 Pedersen 承诺的兼容性以及应用 Fiat–Shamir 后得到的非交互式证明.

1基础知识

以下, 我们约定 $(\mathbb{G},+)$ 是阶为 $p$ 的群, 那么群上有自然的数乘 ${\mathbb{Z}}_p\times \mathbb{G}\to \mathbb{G}:(a,G)\mapsto aG$. 我们要求在群 $\mathbb{G}$ 上离散对数问题是困难的 (一般采用椭圆曲线上的加法群) .

定义 1.1. 给定群 $\mathbb{G}$, 群的生成元 $G$ 和群中元素 $H$, 离散对数问题要求找到 $a\in {\mathbb{Z}}_p$, 使得 $H=aG$. (作为乘法群时为 $H=G^a$) 形式化地可以将等式改写为 $a={\log }_{G}H$, 离散对数因此得名.

注 1.2. 当 $\mathbb{G}={\mathbb{Z}}_p$ 时, 我们可以 “计算” 出 $a$ 的值, 这是因为 ${\mathbb{Z}}_p$ 不仅是一个群而且是一个域; 但对一般的加法群 $(\mathbb{G},+)$ 我们并没有这一结构.

离散对数问题困难性假设是指, 对于上述的离散对数问题, 不存在 (经典) 概率多项式算法求解. 使用 Shor 算法 (量子算法) 可以在多项式时间内处理这一问题, 但这超出了我们的篇幅.

以下, 我们均假设离散对数问题是困难的.

我们有推论:

推论 1.3. 给定群 $\mathbb{G}$, 群的生成元 $G_1,\dots ,G_n$ 和群中元素 $H$, 寻找一组解 $a_1,\dots ,a_n\in {\mathbb{Z}}_p$, 使得 $H={\sum }_{i=1}^n{a}_i{G}_i$, 是困难的.

承诺

定义 1.4 (Pedersen 承诺). 证明者需要向验证者证明其知道 $v\in {\mathbb{Z}}_p$. 利用群 $\mathbb{G}$ 中公开的生成元 $A,B$, 证明者随机选取致盲因子 $\tilde{v}\in {\mathbb{Z}}_p$, 计算 $V=vA+\tilde{v}B$ 并将 $V$ 发送给验证者. 当需要验证时, 证明者将 $v,\tilde{v}$ 发送给验证者, 验证者计算并证明等式是否成立.

Pedersen 承诺具有完全掩藏性和计算绑定性. 掩藏性指的是只有承诺 $V$ 的情况下无法直接得到 $v$ 的信息; 绑定性指的是给出承诺 $V$ 后证明者无法更改信息.

Pedersen 承诺具有同态性, 这是因为群 $\mathbb{G}$ 有 ${\mathbb{Z}}_p$-模的结构. 同态性的好处是在公开关于初始值的多项式时, 可以只发送致盲因子的多项式 (发送一个值) 达到打开承诺的目的. 比如说证明者生成了 $(v_1,\widetilde{v_1},V_1)$ 和 $(v_2,\widetilde{v_2},V_2)$ 两个承诺, 当其需要打开 $v_1+v_2$ 时, 其只需要发送 $v_1+v_2$ 和 $\widetilde{v_1}+\widetilde{v_2}$ 两个值即可, 这样不会单独暴露 $v_1$ 和 $v_2$ 的信息.

我们可以把 Pedersen 承诺推广到需要同时证明多个量 $v_i$,$i=1,\dots ,n$ 的情况. 此时我们利用公开的生成元 $A_i$, $i=1,\dots ,n$ 以及 $B$, 计算 $V={\sum }_i{v}_i{A}_i+\tilde{v}B$ 并将 $V$ 发送给验证者. 在离散对数困难性假设的前提下, 对于随机选取的 $A_i,B$, 在多项式时间内无法找到这些生成元之间的线性关系, 从而这一承诺是计算可靠的 (是绑定的) .

2内积论证

我们给出内积论证的定义:

定义 2.1 (内积论证). 给定公开的生成元 $\mathbf{C},\mathbf{D}$, 证明者发给验证者的 $P\in \mathbb{G}$, $c\in {\mathbb{Z}}_p$, 证明者需要向验证者证明其知道两个向量 $\mathbf{a},\mathbf{b}$, 使得 $⟨\mathbf{a},\mathbf{C}⟩+⟨\mathbf{b},\mathbf{D}⟩=P$ 且 $⟨\mathbf{a},\mathbf{b}⟩=c$

一种变种为:

定义 2.2. 给定公开的生成元 $B,\mathbf{C},\mathbf{D}$, 证明者发给验证者的 $P\in \mathbb{G}$, 证明者需要向验证者证明其知道两个向量 $\mathbf{a},\mathbf{b}$, 使得 $P=⟨\mathbf{a},\mathbf{C}⟩+⟨\mathbf{b},\mathbf{D}⟩+⟨\mathbf{a},\mathbf{b}⟩B$

3范围证明

对于 $y\in {\mathbb{Z}}_p$, 令 ${\mathbf{y}}^n=(1,y,\dots ,y^{n-1})\in {\mathbb{Z}}_p^n$. 特别地 $1=1^n=(1,\dots ,1)\in {\mathbb{Z}}_p^n$.

证明者需要在 Pedersen 承诺的基础上向验证者证明 $v\in [0,2^n-1]$, 其中 $n$ 一般取 2 的幂次. 令 ${\mathbf{a}}_L\in {\mathbb{Z}}_p^n$ 为 $v$ 在二进制表示下的各位构成的向量, 即 $⟨{\mathbf{a}}_L,2^n⟩=v$. 令 ${\mathbf{a}}_R={\mathbf{a}}_L-1$, 那么应当有 ${\mathbf{a}}_L\odot {\mathbf{a}}_R=0$.

当向量 $\mathbf{v}=0$ 时, 对任意的 $y$ 有 $⟨\mathbf{v},{\mathbf{y}}^n⟩=0$. 反过来对任意取定的 $v\ne 0$, 当 $y$ 随机选取时, $⟨\mathbf{v},{\mathbf{y}}^n⟩=0$ 的概率不超过 $\frac{n}{p}$ (考虑关于 $y$ 的不超过 $n$ 次多项式, 至多有 $n$ 个不重复的根) 对于较大的 $p$ (Bulletproofs 考虑 $p=2^{255}-19$) 这一情况可以忽略不计.

于是对于验证者提供的随机的 $y\in {\mathbb{Z}}_p$, 只需要验证$$\begin{array}{rl}⟨{\mathbf{a}}_L,2^n⟩& =v\\ ⟨{\mathbf{a}}_L,{\mathbf{y}}^n⟩-⟨1,{\mathbf{y}}^n\odot {\mathbf{a}}_R⟩& =⟨1,{\mathbf{y}}^n⟩\\ ⟨{\mathbf{a}}_L,{\mathbf{y}}^n\odot {\mathbf{a}}_R⟩& =0\end{array}$$

对于验证者提供的随机的 $z\in {\mathbb{Z}}_p$, 将上述式子组合得到$$z^{2}v+z⟨1,{\mathbf{y}}^n⟩=z^2⟨{\mathbf{a}}_L,2^n⟩+z⟨{\mathbf{a}}_L,{\mathbf{y}}^n⟩-z⟨1,{\mathbf{y}}^n\odot {\mathbf{a}}_R⟩+⟨{\mathbf{a}}_L,{\mathbf{y}}^n\odot {\mathbf{a}}_R⟩$$等号右边进行一些合并: $$\begin{array}{rl}& z^2⟨{\mathbf{a}}_L,2^n⟩+z⟨{\mathbf{a}}_L,{\mathbf{y}}^n⟩-z⟨1,{\mathbf{y}}^n\odot {\mathbf{a}}_R⟩+⟨{\mathbf{a}}_L,{\mathbf{y}}^n\odot {\mathbf{a}}_R⟩\\ & =⟨{\mathbf{a}}_L,z^2{2}^n+z{\mathbf{y}}^n⟩+⟨{\mathbf{a}}_L-z1,{\mathbf{y}}^n\odot {\mathbf{a}}_R⟩\\ & =⟨{\mathbf{a}}_L-z1,{\mathbf{y}}^n\odot ({\mathbf{a}}_R+z1)+z^2{2}^n⟩+z^3⟨1,2^n⟩+z^2⟨1,{\mathbf{y}}^n⟩\end{array}$$那么$$⟨{\mathbf{a}}_L-z1,{\mathbf{y}}^n\odot ({\mathbf{a}}_R+z1)+z^2{2}^n⟩=z^{2}v+\delta (y,z)$$(1)

其中$$\delta (y,z)=(z-z^2)⟨1,{\mathbf{y}}^n⟩-z^3⟨1,2^n⟩$$

注意到 $y,z$ 都由验证者提供, 所以 $\delta (y,z)$ 可以由验证者自行算出.

为了验证 (1) 成立, 一般需要将内积的两个向量发给验证者, 但这当然会暴露关于 $v$ 的信息 (想象一下不诚实的验证者使用了 $z=0$, 从而得到了 ${\mathbf{a}}_L$ 的信息) ;

这里采用的处理方法是证明者引入随机的掩盖向量 ${\mathbf{s}}_L,{\mathbf{s}}_R\in {\mathbb{Z}}_p^n$ 并承诺; 将原本内积中的 ${\mathbf{a}}_L,{\mathbf{a}}_R$ 变更为 ${\mathbf{a}}_L+\alpha {\mathbf{s}}_L,{\mathbf{a}}_R+\alpha {\mathbf{s}}_R$. 这样左边的内积记为 $t(\alpha )=⟨\mathbf{l}(\alpha ),\mathbf{r}(\alpha )⟩=t_0+t_1\alpha +t_2{\alpha }^2$, 其中 $\mathbf{l}(\alpha )={\mathbf{a}}_L-z1+\alpha {\mathbf{s}}_L$, $\mathbf{r}(\alpha )={\mathbf{y}}^n\odot ({\mathbf{a}}_R+z1)+z^2{2}^n+\alpha {\mathbf{y}}^n\odot {\mathbf{s}}_R$.

证明者将 $t_1,t_2$ 承诺给验证者 (因为这些系数都包含 ${\mathbf{s}}_L,{\mathbf{s}}_R$, 所以不会暴露关于 ${\mathbf{a}}_L,{\mathbf{a}}_R$ 的信息. 对于验证者随机选取的 $x\in {\mathbb{Z}}_p$, 证明者计算 ${\mathbf{l}}_x=\mathbf{l}(x)$, ${\mathbf{r}}_x=\mathbf{r}(x)$, $t_x=⟨\mathbf{l},\mathbf{r}⟩$, 将 $\mathbf{l},\mathbf{r}$ 发送给验证者, 将 $t_x$ 和 $\widetilde{t_x}=z^2\tilde{v}+\widetilde{t_1}x+\widetilde{t_2}{x}^2$ 发给验证者.

验证者得到 $t_x,t_1,t_2$ 的 Pedersen 承诺后利用同态可以算出 $t_0$ 的 Pedersen 承诺, 但仍然需要验证几件事情:

1.	${\mathbf{l}}_x={\mathbf{a}}_L-z1+x{\mathbf{s}}_L$, ${\mathbf{r}}_x={\mathbf{y}}^n\odot ({\mathbf{a}}_R+z1)+z^2{2}^n+x{\mathbf{y}}^n\odot {\mathbf{s}}_R$;
2.	$t_x=z^{2}v+\delta (y,z)+t_{1}x+t_2{x}^2$;
3.	$⟨{\mathbf{l}}_x,{\mathbf{r}}_x⟩=t_x$

为了验证 $t_x=z^{2}v+\delta (y,z)+t_{1}x+t_2{x}^2$, 利用 $v$ 的 Pedersen 承诺 $V=vA+\tilde{v}B$, 验证者计算等式$$t_{x}A+\widetilde{t_x}B=z^2(vA+\tilde{v}B)+\delta (y,z)A+x(t_{1}A+\widetilde{t_1}B)+x^2(t_{2}A+\widetilde{t_2}B)$$于是证明者需要保证$$\widetilde{t_x}=z^2\tilde{v}+x\widetilde{t_1}+x^2\widetilde{t_2}$$此时验证者只需验证$$t_{x}A+\widetilde{t_x}B=z^{2}V+\delta (y,z)A+x{T}_1+x^2{T}_2$$

为了验证 ${\mathbf{l}}_x={\mathbf{a}}_L+x{\mathbf{s}}_L-z1$, ${\mathbf{r}}_x={\mathbf{y}}^n\odot ({\mathbf{a}}_R+x{\mathbf{s}}_R+z1)+z^2{2}^n$, 我们利用已有的承诺 $E_a=⟨{\mathbf{a}}_L,\mathbf{C}⟩+⟨{\mathbf{a}}_R,\mathbf{D}⟩+u_{a}B$, $E_s=⟨{\mathbf{s}}_L,\mathbf{C}⟩+⟨{\mathbf{s}}_R,\mathbf{D}⟩+u_{s}B$. 那么$$E_a+x{E}_s=⟨{\mathbf{l}}_x+z1,\mathbf{C}⟩+⟨{\mathbf{y}}^{-n}\odot ({\mathbf{r}}_x-z^2{2}^n)-z1,\mathbf{D}⟩+(u_a+x{u}_s)B$$第一项很容易拆成 $⟨{\mathbf{l}}_x,\mathbf{C}⟩+z⟨1,\mathbf{C}⟩$. 第二项较为复杂: $$\begin{array}{rl}⟨{\mathbf{y}}^{-n}\odot ({\mathbf{r}}_x-z^2{2}^n)-z1,\mathbf{D}⟩& =⟨{\mathbf{y}}^{-n}\odot ({\mathbf{r}}_x-z^2{2}^n),\mathbf{D}⟩-z⟨1,\mathbf{D}⟩\\ & =⟨{\mathbf{r}}_x-z^2{2}^n,{\mathbf{y}}^{-n}\odot \mathbf{D}⟩-z⟨1,\mathbf{D}⟩\\ & =⟨{\mathbf{r}}_x,{\mathbf{y}}^{-n}\odot \mathbf{D}⟩-z^2⟨2^n,{\mathbf{y}}^{-n}\odot \mathbf{D}⟩-z⟨1,\mathbf{D}⟩\end{array}$$第三项中注意到 $u_a$ 与 $u_s$ 同时出现, 所以可以设 $u=u_a+x{u}_s$, 此时有$$⟨{\mathbf{l}}_x,\mathbf{C}⟩+⟨{\mathbf{r}}_x,{\mathbf{y}}^{-n}\odot \mathbf{D}⟩=Q(x,y,z)-uB$$(2)其中 $Q(x,y,z)=E_a+x{E}_s+z⟨1,\mathbf{D}-\mathbf{C}⟩+z^2⟨2^n,{\mathbf{y}}^{-n}\odot \mathbf{D}⟩$ 可以由验证者得到 $E_a,E_s$ 后自行计算, $u$ 需要由证明者发给验证者.

以下我们写出具体的协议步骤. (待整理) 记证明者为 $\mathcal{P}$, 验证者为 $\mathcal{V}$, 公开的生成元为 $A,B,\mathbf{C},\mathbf{D}$.

1.	$\mathcal{P}$: $\tilde{v}\leftarrow {\mathbb{Z}}_p$, $V=vA+\tilde{v}B$
2.	$\mathcal{P}\to \mathcal{V}$: $V$
3.	$\mathcal{P}$: ${\mathbf{s}}_L,{\mathbf{s}}_R\leftarrow {\mathbb{Z}}_p^n$
4.	$\mathcal{P}$: $u_a,u_s\leftarrow {\mathbb{Z}}_p$, $E_a=⟨{\mathbf{a}}_L,\mathbf{C}⟩+⟨{\mathbf{a}}_R,\mathbf{D}⟩+u_{a}B$, $E_s=⟨{\mathbf{s}}_L,\mathbf{C}⟩+⟨{\mathbf{s}}_R,\mathbf{D}⟩+u_{s}B$
5.	$\mathcal{P}\to \mathcal{V}$: $E_a,E_s$
6.	$\mathcal{V}$: $y,z\leftarrow {\mathbb{Z}}_p$
7.	$\mathcal{V}\to \mathcal{P}$: $y,z$
8.	$\mathcal{P}$: $t_1=⟨{\mathbf{s}}_L,{\mathbf{y}}^n\odot ({\mathbf{a}}_R+z1)+z^2{2}^n⟩+⟨{\mathbf{a}}_L-z1,{\mathbf{s}}_R⟩$, $t_2=⟨{\mathbf{s}}_L,{\mathbf{s}}_R⟩$
9.	$\mathcal{P}$: $\widetilde{t_1},\widetilde{t_2}\leftarrow {\mathbb{Z}}_p$, $T_1=t_{1}A+\widetilde{t_1}B$, $T_2=t_{2}A+\widetilde{t_2}B$.
10.	$\mathcal{P}\to \mathcal{V}$: $T_1,T_2$
11.	$\mathcal{V}$: $x\leftarrow {\mathbb{Z}}_p$
12.	$\mathcal{V}\to \mathcal{P}$: $x$
13.	$\mathcal{P}$: ${\mathbf{l}}_x={\mathbf{a}}_L-z1+x{\mathbf{s}}_L$, ${\mathbf{r}}_x={\mathbf{y}}^n\odot ({\mathbf{a}}_R+z1)+z^2{2}^n+x{\mathbf{y}}^n\odot {\mathbf{s}}_R$; $t_x=⟨{\mathbf{l}}_x,{\mathbf{r}}_x⟩$;
14.	$\mathcal{P}$: $\widetilde{t_x}=z^2\tilde{v}+x\widetilde{t_1}+x^2\widetilde{t_2}$, $u=u_a+x{u}_s$
15.	$\mathcal{P}\to \mathcal{V}$: $\widetilde{t_x},{\mathbf{l}}_x,{\mathbf{r}}_x,u,t_x$
16.	$\mathcal{V}$: $Q(x,y,z)=E_a+x{E}_s+z⟨1,\mathbf{D}-\mathbf{C}⟩+z^2⟨2^n,{\mathbf{y}}^{-n}\odot \mathbf{D}⟩$, $\delta (y,z)=(z-z^2)⟨1,{\mathbf{y}}^n⟩-z^3⟨1,2^n⟩$
17.	$\mathcal{V}$ 验证: $t_{x}A+\widetilde{t_x}B=z^{2}V+\delta (y,z)A+x{T}_1+x^2{T}_2$, $⟨{\mathbf{l}}_x,\mathbf{C}⟩+⟨{\mathbf{r}}_x,{\mathbf{y}}^{-n}\odot \mathbf{D}⟩=Q(x,y,z)-uB$, $⟨{\mathbf{l}}_x,{\mathbf{r}}_x⟩=t_x$

4基于对数内积证明的改进

注意到最后一步中后两个式子形同于在 $(\mathbf{C},{\mathbf{y}}^{-n}\odot \mathbf{D},Q(x,y,z)-uB,t_x)$ 处对 ${\mathbf{l}}_x,{\mathbf{r}}_x$ 的内积论证, 所以可以调用优化, 不直接发送 ${\mathbf{l}}_x,{\mathbf{r}}_x$, 将发送的元素个数从 $2n$ 降低到 $2{\log }_2(n)+2$.