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

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

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

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

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

多集合检验（Multiset checks ）

多集合检验的问题是：
假如有两个集合a=a1,...,an, b=b1,...,bn,如何检验a,b集合相同，即元素相同。
直接的做法是循环比较，显然效率不高。引入plonk permutation的思路，采用“grand product reduction”，具体为：

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

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

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

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

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

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

plonk Permutation

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

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

对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

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