零知识证明 – Plookup算法介绍

这篇文章主要介绍了零知识证明 – Plookup算法介绍 ,文中通过代码以及文档配合进行讲解,很详细,它对在座的每个人的研究和工作具有很经典的参考价值。 如果需要,让我们与区块链资料网一起学习。

https://www.interchains.cc/23394.html

零知识证明 – Plookup算法介绍是很好的区块链资料,他说明了区块链当中的经典原理,可以给我们提供资料,零知识证明 – Plookup算法介绍学习起来其实是很简单的,

不多的几个较为抽象的概念也很容易理解,之所以很多人感觉零知识证明 – Plookup算法介绍比较复杂,一方面是因为大多数的文档没有做到由浅入深地讲解,概念上没有注意先后顺序,给读者的理解带来困难

零知识证明 – Plookup算法介绍

  • 零知识证明
  • Plookup

最近有空看了看Plookup的论文。针对对电路描述不友好的操作(比如bit操作),Plookup给出了新的思路和证明方式。给定某个操作的真值表示(lookup table),证明某个操作的输入/输出是在真值表中。这种方式,相对之前的bit计算约束方式,降低约束的个数,提高了电路效率。

最近有空看了看Plookup的论文。针对对电路描述不友好的操作(比如bit操作),Plookup给出了新的思路和证明方式。给定某个操作的真值表示(lookup table),证明某个操作的输入/输出是在真值表中。这种方式,相对之前的bit计算约束方式,降低约束的个数,提高了电路效率。

Plookup的论文下载地址如下:

https://eprint.iacr.org/2020/315.pdf

基本思想

Plookup尝试解决的问题是,给定两个集合,证明某个集合的元素在另外一个集合中。给定两个集合t和f,s是f排序后的结果。如果t中的元素最少在f中出现过一次。判别f中的元素是否包括在t中,只需要比较元素差的集合:

零知识证明 - Plookup算法介绍

举个例子,t是{1,4,8}的集合,元素的差异集合为{3, 4},分别是4-1,8-4。如果s只有t中的元素组成,并且每个元素最少出现一次,例如{1,1,4,8,8,8},元素的差异集合也为{3,4}。如果s中的元素并不完全是t中的元素,那即使在元素差异集合一样的情况下,也不能说明s中元素在t的集合中。例如s为{1,5,5,5,8,8},元素的差异集合也为{3,4},分别是8-5,5-1。

论文提出,可以引入一个随机因子,将前后两个元素相加的方法,确定两个集合的依赖关系。

定义多项式

在基本思想的基础上,论文在第三章定义了两个多项式F和G:

零知识证明 - Plookup算法介绍

如果F和G相互对等,有且如下的条件成立:

  • f集合属于t
  • s是(f,t)的并集,并且按照t中的元素排序

如果条件成立,可以推导出两个多项式相等。F多项式可以看成是两部分组成,分别是两个连乘。后面的连乘可以看成是t中的元素连乘。前面的连乘,可以看成是f中元素的连乘。因为f中的元素属于t,则f中的元素的连乘,可以想象成多个相同元素的连乘。反之,因为beta和gamma的随机因子,也能从F和G对等条件推出满足的两个条件。具体的证明过程,可以查看论文的第三章。

在定义多项式的基础上,问题可以转化成两个多项式相等。

Plookup协议

已知f和t,可以排序得到s。因为s由f和t合并而成,s可以由两个函数h1和h2表示。关键在于第4步,定义了Z函数:

  • Z(g) = 1 – 初始为1
  • Z(x) 是两种多项式表示的商
  • Z(g^(n+1)) = 1 – n+1元素的连乘,两种多项式表达式相等

零知识证明 - Plookup算法介绍

验证者,除了查看Z函数外,额外还要查看h1/h2连续性。

论文进一步将协议推广到更通用的情况,并给出了t中元素是连续情况下的优化协议。感兴趣的小伙伴可以自行查看。

总结:

Plookup提出了一种明确输入/输出的情况下,如何证明某个函数的运算正确的协议。输入输出定义成lookup表,计算的输入/结果只要在该lookup表中即表示运算正确。和Plonk采用同样的思路,Plookup定义了问题的多项式表示,证明了Z函数的递归表示和边界。

零知识证明 - Plookup算法介绍

本文首发于:https://mp.weixin.qq.com/s/e_hxq8e1lYjLvvEfzi4AoQ

部分转自网络,侵权联系删除www.interchains.cchttps://www.interchains.cc/23394.html

区块链毕设网(www.interchains.cc)全网最靠谱的原创区块链毕设代做网站 部分资料来自网络,侵权联系删除! 最全最大的区块链源码站 ! QQ3039046426
区块链知识分享网, 以太坊dapp资源网, 区块链教程, fabric教程下载, 区块链书籍下载, 区块链资料下载, 区块链视频教程下载, 区块链基础教程, 区块链入门教程, 区块链资源 » 零知识证明 – Plookup算法介绍

提供最优质的资源集合

立即查看 了解详情