区块链中的数学–PLookup

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

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

区块链中的数学–PLookup是很好的区块链资料,他说明了区块链当中的经典原理,可以给我们提供资料,区块链中的数学–PLookup学习起来其实是很简单的,

不多的几个较为抽象的概念也很容易理解,之所以很多人感觉区块链中的数学–PLookup比较复杂,一方面是因为大多数的文档没有做到由浅入深地讲解,概念上没有注意先后顺序,给读者的理解带来困难

区块链blockchain中的数学–PLookup

本文主要介绍plookup算法的思路

写在前面

上一篇介绍了MultiSet check& Schwartz–Zippel lemma的应用,有了基础,可以进一步介绍plookup算法了。

首先看下Plookup的初心。

Plookup应用

使用zk snark去证明一些程式时,有一类操作不是很友好,比如AES-128 或者 SHA-256,它们包含了大量的位操作(异或,与等),这些位操作要表示成门约束,需要先把数分解成二进制位,然后检验二进制位正确性,然后在执行目标操作,所以传统方法约束较为复杂,直观体现门数量多。

以异或(XOR)操作为例: 假如有三个向量域元素,$a=(a_1,…,a_n),b=(b_1,…,b_n),c=(c_1,…,c_n)$,检验每个元素都是8比特位,而且$i ∈ [n],c_i=a_i bigoplus b_i$

使用lookup table来实现约束的思路比较直接,预计算出8比特位操作数所有的输入输出,构造查找表三项${t_1,t_2,t_3}$, 前两项是输入,后一项是XOR结果,检验t3是否是正确的操作结果,变成检验${t_1,t_2,t_3}$是否是预计算table中的一项(entry)。

检验元组$(a_i,b_i,c_i)$是表中的一项,首先把元组转化为单个元素 $f_i=a_i+rb_i+r^2c_i$, 相应地对table做类似处理,$ti=t{i1}+rt{i2}+r^2t{i3}$, 如果f属于t, 根据上篇说的Schwarz-Zippel Lemma 可以证实元组在table中。

现在问题转化为证明一个向量(集合)f包含在另一个向量(集合)t中,是plookup协议的核心。

plookup协议

如果向量f中每个元素都在t中,记为f ⊂ t,假设s是f||t,并且按照t中元素出现顺序排序,可以得出s中包含相同的相邻元素差值,反之亦然。

例如f = {2,2,1,1,5}, t = {1,2,5},那么s = {1,1,1,2,2,2,5,5}, 令$t’ =t_{i+1}-ti = {1,3}$, s相邻元素差值 $s’ = s{i+1}-s_i = {0,0,1,0,0,3,0}$, 对于f ⊂ t, s’与t’包含相同的非零元素(本例子中{1,3})。仔细观察s’,可以发现其中0元素的个数是等于f向量元素个数|f|,这是必然的。

randomness引入

验证f ⊂ t 进一步转化为s’, t’包含相同的非零元素,本质上在于验证s,t相邻元素非零差值相同。通过构造随机化差值向量可以实现检验。具体地,令$s’= si+βs{i+1}, t’ =ti+βt{i+1}$, 现在可以对s’, {(1 + β)f, t’}做多集合相等校验。根据上一节randomness的思想, 将β作为自变量,s’ 就是度为1的多项式。 当$si not= s{i+1}$ 不能对应(1 + β)f任一元素,会对应t’中某一元素$(tj+βt{j+1})$,因为二者系数结构相同(1,β),意味着s中新的不同元素包含在t中, s ⊂ t。 当$si=s{i+1}$, $s’= (1+β)s_i$, 一定对应于某个$f_j$, 可得f ⊂ s, 间接推出 f ⊂ t .

为什么一开始思路是相邻元素做减法,后面验证却用加法呢?二者本质相同,减法好理解直接对差值做随机化,加法略微有点回路: 假设相减差值集合 $delta =d_1,d_2,…,d_n , s’=si+ βs{i+1}=s_i+β(s_i+d_i)=(1+β)s_i+βd_i$, 可以看出也是对差值做的随机化。 所以说直接用减法结果做多集合校验也是没问题的!具体详细P,V多项式的构造与验证,可以查阅plookup的paper。

小结

本文主要介绍plookup算法的思路,本质上是用空间换时间的技巧,预计算一系列范围的值,构造table,验证时验证原始提供的元组(witness)是否在table内,之所以可以这么做的原因到此一目了然!感谢张博从第一性原理角度进行细节分析!


原文链接:https://mp.weixin.qq.com/s/_7LAvH-Rzat337YKL0aWpw 欢迎关注公众号:blocksight


相关阅读

区块链blockchain中的数学 — MultiSet check& Schwartz–Zippel lemma MultiSet check& Schwartz–Zippel lemma

相关plonk系列视频

区块链blockchain中的数学 -盲签名(Blind Signature) 盲签名原理

区块链blockchain中的数学 – sigma协议OR Proof&签名 sigma协议的扩展–OR proof

区块链blockchain中的数学 – 何谓零知识证明? 何谓零知识证明

区块链blockchain中的数学 – RSA累加器的非成员证明 RSA Accumulator非成员证明以及区块链blockchain应用

区块链blockchain中的数学 – Accumulator(累加器) 累加器与RSA Accumulator

区块链blockchain中的数学 – Kate承诺batch opening Kate承诺批量证明

区块链blockchain中的数学 – 多项式承诺 多项式知识和承诺

区块链blockchain中的数学 – Pedersen密钥共享 Pedersen 密钥分享

区块链blockchain中的数学 – Pedersen承诺 密码学承诺–Pedersen承诺

区块链blockchain中的数学 – 不经意传输 不经意传输协议

区块链blockchain中的数学 – RSA算法加解密过程及原理 RSA加解密算法

区块链blockchain中的数学 – BLS门限签名 BLS m of n门限签名

区块链blockchain中的数学 – BLS密钥聚合 BLS密钥聚合

Schorr 签名基础篇 Schorr签名与椭圆曲线

区块链blockchain中的数学-Uniwap自动化做市商核心算法解析 Uniwap核心算法解析(中)

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

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

提供最优质的资源集合

立即查看 了解详情