本文详细介绍了Bulletproofs零知识证明算法,包括其在椭圆曲线上的内积证明实现。文章通过问题陈述、算法步骤以及非交互式证明等技术,系统地展示了如何在不泄露向量和内积的情况下进行高效证明。
Bulletproofs ZKPs 允许证明者以对数大小的证明来证明对内积的知识。Bulletproofs 不需要一个可信的设置。
在前面的章节中,我们展示了如何在不透露向量或内积的情况下证明对内积的知识,尽管这需要一个大小为 $\mathcal{O}(n)$ 的证明,其中 $n$ 是向量的长度。我们还展示了如何使用对数大小的数据来证明对内积的知识,但没有零知识属性。
在本章中,我们将这些算法结合在一起,以演示 Bulletproof ZK 算法。
(此工作是关于 ZK Bulletproofs 系列的一部分。)
证明者和验证者同意两个椭圆曲线基向量 $\mathbf{G}$ 和 $\mathbf{H}$ 的长度为 $n$,以及椭圆曲线点 $Q$ 和 $B$。所有这些点之间的离散对数关系都是未知的。
证明者有向量 $\mathbf{a}$ 和 $\mathbf{b}$,其内积为 $v$。证明者将 $\mathbf{a}$ 和 $\mathbf{b}$ 承诺为 $A$,即 $A =\langle\mathbf{a},\mathbf{G}\rangle + \langle\mathbf{b},\mathbf{H}\rangle + \alpha B$,其中 $\alpha$ 是盲项。证明者承诺 $V = \langle\mathbf{a},\mathbf{b}\rangle Q + \gamma B$。
证明者将 $(A, V)$ 发送给验证者,旨在证明 $\mathbf{a}$ 和 $\mathbf{b}$ 被承诺为 $A$,其内积被承诺为 $V$。验证者不学习向量或内积。
证明的大小必须为 $\mathcal{O}(\log n)$。
证明者生成随机标量 $\set{\alpha, \beta,\gamma,\tau_1,\tau_2}$ 和随机向量 $\set{\mathbf{s}_L,\mathbf{s}_R}$,并计算承诺
$$ \begin{align} A &= \langle\mathbf{a},\mathbf{G}\rangle + \langle\mathbf{b},\mathbf{H}\rangle+\alpha B\\ S &= \langle\mathbf{s}_L,\mathbf{G}\rangle + \langle\mathbf{s}_R,\mathbf{H}\rangle+\beta B\\ V &= vQ + \gamma B \\ \end{align} $$
证明者准备(但不发送)向量多项式
$$ \begin{align} \mathbf{l}(x) &= \mathbf{a} + \mathbf{s}_Lx\\ \mathbf{r}(x) &= \mathbf{b} + \mathbf{s}_Rx\\ t(x)&=\langle\mathbf{l}(x),\mathbf{r}(x)\rangle = \langle\mathbf{a},\mathbf{b}\rangle+(\langle\mathbf{a},\mathbf{s}_R\rangle + \langle\mathbf{b},\mathbf{s}_L\rangle) x+(\langle\mathbf{s}_L,\mathbf{s}_R\rangle)x^2 \end{align} $$
$A$ 是对向量多项式的常数项的承诺,$S$ 是对线性项的承诺,$V$ 是对内积的承诺。
证明者为了 $t(x)$ 的系数创建承诺如下
$$ \begin{align} T_1 &= (\langle\mathbf{a},\mathbf{s}_R\rangle + \langle\mathbf{b},\mathbf{s}_L\rangle)Q + \tau_1B\\ T_2 &= \langle\mathbf{s}_L,\mathbf{s}_R\rangle Q + \tau_2B \end{align} $$
注意 $V$ 是 $t(x)$ 的常数系数的承诺,$T_1$ 和 $T_2$ 分别是 $t(x)$ 的线性和二次系数的承诺。
证明者将 $(A, S, V, T_1, T_2)$ 发送给验证者。
验证者以随机值 $u$ 进行响应。
然后,证明者在 $u$ 处评估多项式,并创建它们被正确评估的证明:
$$ \begin{align} \mathbf{l}_u &= \mathbf{l}(u) = \mathbf{a} + \mathbf{s}_Lu \\ \mathbf{r}_u &= \mathbf{r}(u) = \mathbf{b} + \mathbf{s}_Ru \\ t_u &= t(u) =v + (\langle\mathbf{a},\mathbf{s}_R\rangle + \langle\mathbf{b},\mathbf{s}_L\rangle)u + \langle\mathbf{s}_L,\mathbf{s}R\rangle u^2\\ \pi{lr} &=\alpha+\beta u\\ \pi_t &= \gamma + \tau_1u + \tau_2u^2\\ \end{align} $$
之前...
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!