Bulletproof规模证明之优化
主页
微信大众号:暗码应用技能实战
博客园主页:https://www.cnblogs.com/informatics/
GIT地址:https://github.com/warm3snow
简介
Bulletproof将规模证明转换为二次多项式表达\(t(X) = t_0 + t_1 \cdot X + t_2 \cdot X^2\),并经过多项式许诺和内积许诺的验证,完成了规模证明。回忆《Bulletproof规模证明之原理》,咱们具体介绍了Bulletproof规模证明的结构和验证流程。本文将进一步介绍Bulletproof规模证明的优化技能 - 减半算法
本文安排如下:
- 术语界说
- Bulletproof复杂度剖析
- Bulletproof减半算法
- 总结
- 参考文献
术语界说
- \(p\)和\(q\):别离表明两个大素数
- \(Z_p\):表明模\(p\)的整数环
- \(Z_p^*\):表明模\(p\)的整数环中的一切与\(p\)互素的元素, 即非零元素
- \(G\):阶为\(p\)的循环群, 假如:\(g \in G, G = \{1, g, g^2, ..., g^{p-1}\} \equiv Z_p\), 则\(g\)是\(G\)的生成元
- \(G^n\)和\(Z_p^n\):别离表明群\(G\)上的n维向量空间和\(Z_p\)上的n维向量空间
- \(h^r \mathbf{g}^{\mathbf{x}}\) = \(h^r \cdot \prod_{i=1}^{n} g_i^{x_i} = h^r \cdot g_1^{x_1} \cdot g_2^{x_2} \cdot ... \cdot g_n^{x_n}\): 表明向量\(\mathbf{x}\)的Pedersen许诺值
- \(\mathbf{g}^{\mathbf{a}}{\mathbf{h}}^{\mathbf{b}} = \prod_{i=1}^{n} g_i^{a_i} \cdot h_i^{b_i}\): 表明向量\(\mathbf{a}\)和\(\mathbf{b}\)的Pedersen许诺值
- \(\langle \mathbf{a}, \mathbf{b} \rangle = \mathbf{a} \cdot \mathbf{b} = \sum_{i=1}^{n} a_i \cdot b_i\): 表明向量\(\mathbf{a}\)和\(\mathbf{b}\)的内积。
- \(\mathbf{a} \circ \mathbf{b} = (a_1 \cdot b_1, a_2 \cdot b_2, ..., a_n \cdot b_n)\): 表明向量\(\mathbf{a}\)和\(\mathbf{b}\)的哈达玛积。
- \(\mathbf{a_{[:n']}} = (a_1, a_2, ..., a_{n'}) \in F^{n'}\) 和 \(\mathbf{a_{[n':]}} = (a_{n'+1}, a_{n'+2}, ..., a_n) \in F^{n-n'}\): 表明向量\(\mathbf{a}\)的前\(n'\)个元素和后\(n-n'\)个元素。
- \(P\)和\(V\): 别离表明证明生成者Prover和证明验证者Verifier
Bulletproof复杂度剖析
在上一篇文章《Bulletproof规模证明之原理》中,咱们介绍了Bulletproof向量内积证明,Bulletproof运用向量内积证明来进行规模证明,流程如下:
剖析上图中的通讯数据包能够发现,交互式Bulletproof向量内积证明过程中,Prover和Verifier需求发送的数据包包含:
- 许诺\(C = (V, A, S, T_1, T_2)\), 其间\(V, A, S, T_1, T_2 \in G\), 复杂度为\(O(1)\)
- Verifier需求发送的数据包含:应战\((x, y, z)\), 其间\(x, y, z \in Z_p^*\), 复杂度为\(O(1)\)
- 呼应\((\tau_x, \mu, t, \mathbf{l}, \mathbf{r})\), 其间\(\tau_x, \mu, t \in Z_p\), \(\mathbf{l}, \mathbf{r} \in Z_p^n\), 复杂度为\(O(2n)\)
综上,未优化版别的Bulletproof向量内积证明通讯复杂度为\(O(2n)\)。复杂度首要来自于Prover发送的呼应\((\mathbf{l}, \mathbf{r})\),其间\(\mathbf{l}\)和\(\mathbf{r}\)是长度为\(n\)的向量。
Bulletproof减半算法
Bulletproof减半算法是Bulletproof的一种优化技木,首要用于削减Bulletproof规模证明的通讯复杂度,并完成了\(O(2\log_2{n})\)的通讯复杂度。Bulletproof减半算法的中心思维是经过递归的方法,不断将向量\(\mathbf{l}\)和\(\mathbf{r}\)减半,直到两个向量长度都为1,终究发送\(O(2\log_2{n})\)个长度为1的数据包,然后完成了数据的紧缩。
减半算法
Bulletproof减半算法根据改善的向量内积证明,下面咱们将具体介绍Bulletproof减半算法的优化原理。
改善的向量内积
假定\(\mathbf{g}\)和\(\mathbf{h}\)是两个独立的\(G\)生成元,标量\(c \in Z_p\),并有\(P \in G\),向量内积证明的方针是Prover向Verifier证明自己知道向量\(\mathbf{a}, \mathbf{b} \in Z_p^n\), 满意以下联系: