Bulletproofs零知识证明:内积的零知识与简洁证明

  • RareSkills
  • 发布于 2024-11-03 15:12
  • 阅读 329

本文详细介绍了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)$。

Bulletproof ZK 算法

证明者生成随机标量 $\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} $$

之前...

剩余50%的内容订阅专栏后可查看

点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
RareSkills
RareSkills
https://www.rareskills.io/