当前位置:首页 > 其他 > 正文内容

Bulletproof规模证明之优化

邻居的猫1个月前 (12-09)其他1052

主页

微信大众号:暗码应用技能实战
博客园主页: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运用向量内积证明来进行规模证明,流程如下:

image

剖析上图中的通讯数据包能够发现,交互式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 \]

扫描二维码推送至手机访问。

版权声明:本文由51Blog发布,如需转载请注明出处。

本文链接:https://www.51blog.vip/?id=756

分享给朋友:

“Bulletproof规模证明之优化” 的相关文章

【DreamQuest Mod之旅 01】建立制造mod的环境

【DreamQuest Mod之旅 01】建立制造mod的环境

在我今日正式开端之前,我从前测验给《雪居之地》里边一个比较大的mod叫做《snow fall》做汉化mod。因而我了解到一个关键词叫做“Harmony”,并测验搭建了一下汉化环境。可是我发现snow fall 或许说雪居之地好像不是很支撑中文mod,所以终究抛弃了做汉化mod的主意。 今日在b站测验...

SQL注入中二阶注入原理

SQL注入中二阶注入原理

1.sql注入中二阶注入原理?. 二阶注入是用户输入被存储后(如数据库或文件),再次被读取并输入到sql查询语句中,然后导致注入进犯。 1.刺进歹意数据,进行数据库刺进数据时,对特别字符进行了转义处理,在写入数据库时保留了本来的数据。 2.引证歹意数据,开发者默许存入数据库的数据都是安全的,进行查询...

USACO 竞赛辅导建议和常见问题

USACO 竞赛辅导建议和常见问题

USACO 竞赛辅导主张和常见问题 在学习信息学奥赛(信奥)的过程中,许多人会接触到 CSP、NOIP 等国内赛事。但是,USACO(美国核算机奥林匹克竞赛)作为一项世界性赛事,也是一个十分值得参与的竞赛,特别关于提高算法才能和请求国内外顶尖大学具有重要价值。 什么是 USACO? USACO 的中...

开源节流,企业稳健发展的双引擎

开源节流,企业稳健发展的双引擎

“开源节流”是一个经济管理术语,指的是通过增加收入来源(开源)和减少支出(节流)来提高经济效益的一种方法。这个概念可以应用于个人、企业或政府等多个层面。1. 开源:增加收入来源。对于个人来说,可以通过提高自己的技能、增加工作时间、寻找兼职等方式来增加收入。对于企业来说,可以通过扩大市场份额、开发新产...

云计算的基本特征,云计算的基本概念

云计算的基本特征,云计算的基本概念

云计算是一种基于互联网的计算方式,通过这种方式,共享的软硬件资源和信息可以按需提供给计算机和其他设备。云计算的基本特征包括:1. 按需自助服务:用户可以根据自己的需求,随时获取计算资源,无需与供应商交互。2. 广泛的网络访问:云计算资源可以通过标准的网络设备访问,如计算机、手机等。3. 资源池化:云...

北京云计算,引领科技浪潮,赋能产业升级

北京云计算,引领科技浪潮,赋能产业升级

北京超级云计算中心是由北京市人民政府主导的国家重要信息化基础平台,成立于2011年,现坐落于北京市怀柔综合性国家科学中心怀柔科学城。该中心由北京市人民政府和中科院计算机网络信息中心共同建设,旨在为科学计算、工业仿真、气象海洋、新能源、生物医药、人工智能等重点行业提供高效、精准的云计算服务。北京超级云...