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

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

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

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

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

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

本文介绍的这些知识点是理解plookup的基础

写在前面

上一篇介绍了环签名技术,环签名是群签名的一种,关于群签名,感兴趣可以自行查阅,了解更多!

我们之前有一系列的文章和视频围绕plonk的算法和工程代码,有些视频没有总结为文字blog,如果你感兴趣,我们欢迎你在看完视频后,整理出相应文字版本,“纸上得来终觉浅,绝知此事要躬行”,临渊羡鱼(听别人说)和退而结网(自己去做)是两个层面的事情,将自己的理解 –> 总结–> 讨论 –> 提高,结识志同道合的朋友,是我们一贯提倡并坚持的方法。

感兴趣的欢迎留言! 本文将介绍plonk中重要的一个优化方向—plookup思路!理解本文的最好了解plonk相关技术及术语。

多集合检验(Multiset checks )

多集合检验的问题是: 假如有两个集合$a = {a_1,…,a_n}$, $b = {b_1,…,b_n}$,如何检验a,b集合相同,即元素相同。 直接的做法是循环比较,显然效率不高。引入plonk permutation的思路,采用“grand product reduction”,具体为:

<a href=区块链blockchain中的数学 — MultiSet check&amp; Schwartz–Zippel lemma” />

如果a,b相等,那么各自元素的乘积也必然相等。反之呢,不一定!考虑a = {3, 4}, b= {2. 6}例子。 我们还需引入Schwartz–Zippel来解决这个问题。

Schwartz–Zippel lemma: 对于域F内的d次多项式f(x)。随机给x 赋值为F中的随机一个元素。为0 的几率为$frac{d}{F}$,当阶数d远小于域范围时,该概率可以忽略

看起来很简单,比较容易理解,往往越简单力量越大! 接下来往集合中每个元素都加入一个随机项r,

<a href=区块链blockchain中的数学 — MultiSet check&amp; Schwartz–Zippel lemma” />

这时候可以说,如果乘积相等,则集合相等,反之也成立。即是充分必要条件。 从Schwartz–Zippel lemma视角来看,等式两边是两个多项式 $fa(x)=prod^n{i=0}(a_i+x)$,$fb(x)=prod^n{i=0}(b_i+x)$ 当x随机取值r时, 如果 $f_a(r)=f_b(b)$,则$f_a(x)=f_b(x)$

这里隐式地将集合(或者称为向量vector)转化成多项式函数。我们认为二者一定范围内等同,零知识证明中大量使用多项式术语(多项式函数,承诺等),很多初学朋友问为什么要搞成多项式? 因为多项式可以实现简洁的验证,zksnark中s(Succinct)主要通过这种方式来实现,通过上面简单的例子可以窥探一二,如果你有不同理解,欢迎讨论!

关于Schwartz–Zippel lemma的更多应用,理解randomize的力量,值得慢慢体会,更多地可查阅本文参考资料。

plonk Permutation

Permutation这个思路,算法视频中已经讲得很清楚了。这里从Multiset checks角度来看, Permutation σ: [n]–>[n] ,a, b集合都有n个元素,检验满足$b_i=a_σ(i)$, 即下面两个集合相等:

<a href=区块链blockchain中的数学 — MultiSet check&amp; Schwartz–Zippel lemma” />

这是多元集合校验,把它约化成单项元素,然后可以使用多集合检验的方法了。 随机选择β,构造如下两个单元项集合:

<a href=区块链blockchain中的数学 — MultiSet check&amp; Schwartz–Zippel lemma” />

对a’, b’可直接使用Multiset checks方法了。 相关plonk系列视频

小结

本文介绍的这些知识点是理解plookup的基础,脚踏实地才能仰望星空,下一篇将继续介绍plookup算法!

参考: Plookup.pdf https://hackmd.io/@arielg/ByFgSDA7D https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma


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


相关阅读

相关plonk系列视频

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

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

区块链blockchain中的数学-sigma协议与Fiat-Shamir变换 sigma协议与Fiat-Shamir变换

区块链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/24330.html

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

提供最优质的资源集合

立即查看 了解详情