IT评测·应用市场-qidao123.com技术社区

标题: Bulletproof范围证明之优化 [打印本页]

---

作者: 民工心事    时间: 2024-11-8 10:31
标题: 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\), 满足以下关系：

\[P = {\mathbf{g}}^{\mathbf{a}}{\mathbf{h}}^{\mathbf{b}} \quad and \quad c = \langle \mathbf{a}, \mathbf{b} \rangle\]
此中：

• \(P\)是\(\mathbf{a}, \mathbf{b}\)的向量Pedersen承诺。
  
• \(c\)表现\(\mathbf{a}, \mathbf{b}\)的向量内积
  

以上的向量关系可以转换为下面的证明系统：

\[\{(\mathbf{g},\mathbf{h} \in G^n, P \in G, c \in Z_p; \mathbf{a}, \mathbf{b} \in Z_p^n): P = {\mathbf{g}}^{\mathbf{a}}{\mathbf{h}}^{\mathbf{b}} \land c = \langle \mathbf{a}, \mathbf{b} \rangle \}\]
在上述证明系统中：

• Prover可以直接将\(\mathbf{a}, \mathbf{b} \in Z_p^n\)发送给Verifier, Verifier重新盘算\(P\)并查抄是否正确，这种承诺的明文打开和验证方式显然是可以的。
  
• Prover必要向Verifier发送\(2n\)个元素。
  

在Bulletproof中，将以上证明系统转换为以劣等价的证明系统：

\[\{(\mathbf{g},\mathbf{h} \in G^n, u, P \in G, c \in Z_p; \mathbf{a}, \mathbf{b} \in Z_p^n): P = {\mathbf{g}}^{\mathbf{a}}{\mathbf{h}}^{\mathbf{b}} \cdot u^{\langle \mathbf{a}, \mathbf{b} \rangle} \}\]
此中\(u\)是\(G\)的独立且公开的生成元。
折半算法

H函数

在Bulletproof折半算法中，引入了一个特殊的功能函数\(H: Z_p^{2n+1} \rightarrow G\)

\[H(\mathbf{w}, \mathbf{x}, \mathbf{y}, \mathbf{z}, c) = {\mathbf{g}}_{[:n']}^{\mathbf{w}} \cdot {\mathbf{g}}_{[n':]}^{\mathbf{x}} \cdot {\mathbf{h}}_{[:n']}^{\mathbf{y}} \cdot {\mathbf{h}}_{[n':]}^{\mathbf{z}} \cdot u^c \in G\]
此中:

• \(n' = n/2\), 即\({\mathbf{g}}_{[:n']}\)表现向量\(\mathbf{g}\)的前\(n/2\)个元素，\({\mathbf{g}}_{[n':]}\)表现向量\(\mathbf{g}\)的后\(n/2\)个元素。\({\mathbf{h}}_{[:n']}, {\mathbf{h}}_{[n':]}\)同理
  
• 输入参数为五元组\(\{\mathbf{w}, \mathbf{x}, \mathbf{y}, \mathbf{z} \in Z_p^{n'}, c \in Z_p \}\)
  
• 输出为群\(G\)中的元素
  

上述\(H\)函数有一个重要性质: 加法同态。即：

\[H(\mathbf{w1}, \mathbf{x1}, \mathbf{y1}, \mathbf{z1}, c1) \cdot H(\mathbf{w2}, \mathbf{x2}, \mathbf{y2}, \mathbf{z2}, c2) = H(\mathbf{w1 + w2}, \mathbf{x1 + x2}, \mathbf{y1 + y2}, \mathbf{z1 + z2}, c1 + c2)\]
同态性证明：

\[H(\mathbf{w1}, \mathbf{x1}, \mathbf{y1}, \mathbf{z1}, c1) \cdot H(\mathbf{w2}, \mathbf{x2}, \mathbf{y2}, \mathbf{z2}, c2)\]

\[= {\mathbf{g}}_{[:n']}^{\mathbf{w1}} \cdot {\mathbf{g}}_{[n':]}^{\mathbf{x1}} \cdot {\mathbf{h}}_{[:n']}^{\mathbf{y1}} \cdot {\mathbf{h}}_{[n':]}^{\mathbf{z1}} \cdot u^{c1} \cdot {\mathbf{g}}_{[:n']}^{\mathbf{w2}} \cdot {\mathbf{g}}_{[n':]}^{\mathbf{x2}} \cdot {\mathbf{h}}_{[:n']}^{\mathbf{y2}} \cdot {\mathbf{h}}_{[n':]}^{\mathbf{z2}} \cdot u^{c2}\]

\[= {\mathbf{g}}_{[:n']}^{\mathbf{w1} + \mathbf{w2}} \cdot {\mathbf{g}}_{[n':]}^{\mathbf{x1} + \mathbf{x2}} \cdot {\mathbf{h}}_{[:n']}^{\mathbf{y1} + \mathbf{y2}} \cdot {\mathbf{h}}_{[n':]}^{\mathbf{z1} + \mathbf{z2}} \cdot u^{c1 + c2}\]

\[= H(\mathbf{w1 + w2}, \mathbf{x1 + x2}, \mathbf{y1 + y2}, \mathbf{z1 + z2}, c1 + c2)\]
等价转换

按照\(H\)函数的界说，我们可以将证明系统中的\(P\)重写为：

\[P = {\mathbf{g}}^{\mathbf{a}}{\mathbf{h}}^{\mathbf{b}} \cdot u^{\langle \mathbf{a}, \mathbf{b} \rangle} = H(\mathbf{a_{[:n']}}, \mathbf{a_{[n':]}}, \mathbf{b_{[:n']}, \mathbf{b_{[n':]}, \langle \mathbf{a}, \mathbf{b} \rangle} }) \in G\]
等式证明：

\[P =  {\mathbf{g}}^{\mathbf{a}}{\mathbf{h}}^{\mathbf{b}} \cdot u^{\langle \mathbf{a}, \mathbf{b} \rangle} = \prod g_i^{a_i} \cdot \prod h_i^{b_i} \cdot u^{\langle \mathbf{a}, \mathbf{b} \rangle}\]

\[= \prod_{i=1}^{n'} g_i^{a_i} \cdot \prod_{i=n'+1}^{n} g_i^{a_i} \cdot \prod_{i=1}^{n'} h_i^{b_i} \cdot \prod_{i=n'+1}^{n} h_i^{b_i} \cdot u^{\langle \mathbf{a}, \mathbf{b} \rangle}\]

\[=  {\mathbf{g}}_{[:n']}^{\mathbf{a_{[:n']}}} \cdot {\mathbf{g}}_{[n':]}^{\mathbf{a_{[n':]}}} \cdot {\mathbf{h}}_{[:n']}^{\mathbf{b_{[:n']}}} \cdot {\mathbf{h}}_{[n':]}^\mathbf{b_{[n':]}} \cdot u^{\langle \mathbf{a}, \mathbf{b} \rangle}\]

\[= H(\mathbf{a_{[:n']}}, \mathbf{a_{[n':]}}, \mathbf{b_{[:n']}, \mathbf{b_{[n':]}, \langle \mathbf{a}, \mathbf{b} \rangle} }) \in G\]
折半算法构造

Bulletproof折半算法的构造流程如下：

• Prover盘算\(L, R \in G\), 并发送给Verifier
  

\[L = H(\mathbf{0}^{n'}, \mathbf{a_{[:n']}}, \mathbf{b_{[n':]}},\mathbf{0}^{n'}, \langle \mathbf{a_{[:n']}}, \mathbf{b_{[n':]}} \rangle)\]

\[= {\mathbf{g}}_{[:n']}^{\mathbf{0}^{n'}} \cdot {\mathbf{g}}_{[n':]}^{\mathbf{a_{[:n']}}} \cdot {\mathbf{h}}_{[:n']}^{\mathbf{b_{[:n']}}} \cdot {\mathbf{h}}_{[n':]}^{\mathbf{0}^{n'}} \cdot u^{\langle \mathbf{a_{[:n']}}, \mathbf{b_{[n':]}} \rangle}\]

\[R = H(\mathbf{a_{[n':]}}, \mathbf{0}^{n'}, \mathbf{0}^{n'}, \mathbf{b_{[:n']}}, \langle \mathbf{a_{[n':]}}, \mathbf{b_{[:n']}} \rangle)\]

\[= {\mathbf{g}}_{[:n']}^{\mathbf{a_{[n']}}} \cdot {\mathbf{g}}_{[n':]}^{\mathbf{0}^{n'}} \cdot {\mathbf{h}}_{[:n']}^{\mathbf{0}^{n'}} \cdot {\mathbf{h}}_{[n':]}^{\mathbf{b_{[:n']}}}\cdot u^{\langle \mathbf{a_{[n':]}}, \mathbf{b_{[:n']}} \rangle}\]

• Verifier选择随机挑战\(x \in Z_p\), 并发送给Prover
  
• Prover盘算\(\mathbf{a'}, \mathbf{b'} \in Z_p^{n'}\), 并发送给Verifier
  

\[\mathbf{a'} = x\mathbf{a_{[:n']}} + x^{-1}\mathbb{a_{[n':]}} \in Z_p^{n'}\]

\[\mathbf{b'} = x^{-1}\mathbf{b_{[:n']}} + x\mathbf{b_{[n':]}} \in Z_p^{n'}\]

• 基于\(L, R, \mathbf{a'}, \mathbf{b'}\), Verifier验证以劣等式是否成立：
  

\[L^{x^2} \cdot P \cdot R^{x^{-2}} \stackrel{?}{=} H(x^{-1}\mathbf{a'}, x\mathbf{a'}, x^\mathbf{b'}, x^{-1}\mathbf{b'}, \langle \mathbf{a'}, \mathbf{b'} \rangle)\]

• 注：等式中的\(P\)是Prover发送的向量内积证明的承诺值
  

正确性验证

已知：

\[L = H(\mathbf{0}^{n'}, \mathbf{a_{[:n']}}, \mathbf{b_{[n':]}},\mathbf{0}^{n'}, \langle \mathbf{a_{[:n']}}, \mathbf{b_{[n':]}} \rangle)\]

\[P = H(\mathbf{a_{[:n']}}, \mathbf{a_{[n':]}}, \mathbf{b_{[:n']}, \mathbf{b_{[n':]}, \langle \mathbf{a}, \mathbf{b} \rangle}})\]

\[R = H(\mathbf{a_{[n':]}}, \mathbf{0}^{n'}, \mathbf{0}^{n'}, \mathbf{b_{[:n']}}, \langle \mathbf{a_{[n':]}}, \mathbf{b_{[:n']}} \rangle)\]
根据\(H\)函数的同态性质，容易盘算：

\[L^{x^2} \cdot P \cdot R^{x^{-2}}\]

\[= H(x^2\mathbf{0}^{n'} + \mathbf{a_{[:n']}} + x^{-2}\mathbf{a_{[n':]}}, x^2\mathbf{a_{[:n']}} + \mathbf{a_{[n':]}} + x^{-2}\mathbf{0}^{n'}, x^2\mathbf{b_{[n']}} + \mathbf{b_{[:n']} + x^{-2}\mathbf{0}^{n'}}, x^2\mathbf{0}^{n'}+\mathbf{b_{[n':]}}+x^{-2}\mathbf{b_{[:n']}}, x^2 \langle \mathbf{a_{[:n']}}, \mathbf{b_{[n':]}} \rangle + \langle \mathbf{a}, \mathbf{b} \rangle + x^{-2}\langle \mathbf{a_{[n':]}}, \mathbf{b_{[:n']}} \rangle)\]

\[= H(\mathbf{a_{[:n']}} + x^{-2}\mathbf{a_{[n':]}},  x^2\mathbf{a_{[:n']}} + \mathbf{a_{[n':]}}, x^2\mathbf{b_{[n']}} + \mathbf{b_{[:n']}}, \mathbf{b_{[n':]}}+x^{-2}\mathbf{b_{[:n']}}, x^2 \langle \mathbf{a_{[:n']}}, \mathbf{b_{[n':]}} \rangle + \langle \mathbf{a}, \mathbf{b} \rangle + x^{-2}\langle \mathbf{a_{[n':]}}, \mathbf{b_{[:n']}} \rangle)\]

\[= H(x^{-1}\mathbf{a'}, x\mathbf{a'}, x^\mathbf{b'}, x^{-1}\mathbf{b'},  x^2 \langle \mathbf{a_{[:n']}}, \mathbf{b_{[n':]}} \rangle + \langle \mathbf{a}, \mathbf{b} \rangle + x^{-2}\langle \mathbf{a_{[n':]}}, \mathbf{b_{[:n']}} \rangle)\]
由于：

\[\langle \mathbf{a'}, \mathbf{b'} \rangle = \langle x\mathbf{a_{[:n']}} + x^{-1}\mathbb{a_{[n':]}}, x^{-1}\mathbf{b_{[:n']}} + x\mathbf{b_{[n':]}} \rangle\]

\[= (x\mathbf{a_{[:n']}} + x^{-1}\mathbb{a_{[n':]}}) \cdot (x^{-1}\mathbf{b_{[:n']}} + x\mathbf{b_{[n':]}})\]

\[= x^2 \langle \mathbf{a_{[:n']}}, \mathbf{b_{[n':]}} \rangle + \mathbf{a_{[:n']}}\mathbf{b_{[:n']}} + \mathbf{a_{[n':]}}\mathbf{b_{[n':]}} + x^{-2}\langle \mathbf{a_{[n':]}}, \mathbf{b_{[:n']}}\rangle\]

\[= x^2 \langle \mathbf{a_{[:n']}}, \mathbf{b_{[n':]}} \rangle + \langle \mathbf{a}, \mathbf{b} \rangle + x^{-2}\langle \mathbf{a_{[n':]}}, \mathbf{b_{[:n']}} \rangle\]
因此，我们可以得出：

\[L^{x^2} \cdot P \cdot R^{x^{-2}} = H(x^{-1}\mathbf{a'}, x\mathbf{a'}, x^\mathbf{b'}, x^{-1}\mathbf{b'}, \langle \mathbf{a'}, \mathbf{b'} \rangle)\]
综上，verifier可以成功验证步骤4中的等式，即折半算法的正确性。
复杂度分析

通过折半算法，在通信过程中，Prover只发送了\((P, L, R, \mathbf{a'}, \mathbf{b'}\))， 此中

• \((P, L, R) \in G\)， 通信复杂度为\(O(1)\)
  
• \(\mathbf{a'}, \mathbf{b'}  \in Z_p^{n'}\), 通信复杂度为\(O(n') = O(n/2)\)
  

因此通过一轮折半算法，可以将直接发送\(\mathbf{a}, \mathbf{b} \in Z_p^{n}\)的复杂度减半。
递归折半算法

通过递归折半的方式，我们可以进一步降低复杂度：

• Prover可以在\((\mathbf{a}', \mathbf{b}')\)根本上继承执行折半算法
  
• 通过\(\log_2n\)次折半(即：向量长度每次减半），可以将\(\mathbf{a}, \mathbf{b} \in Z_p^{n}\)折半为两个元素\(a, b\in Z_p\)
  
• 每次执行折半算法，Prover必要重新生成\(L,R\)
  

由于交互式证明可以通过Fiat-Shamir方法转换为非交互式证明，因此在整个递归折半算法中，Prover仅必要发送以下消息给Verifier:

\[(L_1, R_1), ..., (L_{\log_2n}, R_{\log_2n}), a, b\]

• \((L_i, R_i), \forall i \in [1:\log_2n]\)表现第\(i\)次执行折半算法生成, 全部\((L, R)\)复杂度:\(2\log_2n\)
  
• \(a, b\)为两个元素，复杂度为\(O(1)\)
  

因此Bulletproof通过递归折半算法，成功将通信复杂度降低为\(2\log_2n\)。
结语

本文具体分析了Bulletproof范围证明的优化技能 - 折半算法。通过引入\(H\)函数和递归折半算法，Bulletproof成功将通信复杂度降低为\(O(2\log_2n)\)。折半算法的优化思想可以应用于其他范围证明系统，从而进一步提高范围证明的服从。除了以上优化技能外，Bulletproof的多个范围证明也可以通过批量验证等技能进一步提高服从。
本文未对Bulletproof递归折半算法构造进行具体证明，感兴趣的读者可以参考《Bulletproofs: Short Proofs for Confidential Transactions and More》进行深入学习。
参考文献

• 【1】Non-Interactive Zero-Knowledge Proof
  
• 【2】Bulletproofs: Short Proofs for Confidential Transactions and More
  
• 【3】Buuletproof范围证明之原理
  

转载请注明原文链接：https://www.cnblogs.com/informatics/p/18525971 本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须在文章页面给出原文连接，否则生存追究法律责任的权利。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/)

Powered by Discuz! X3.4