区块链中的数学--PLookup
source link: https://learnblockchain.cn/article/2732
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
本文主要介绍plookup算法的思路
上一篇介绍了MultiSet check& Schwartz–Zippel lemma的应用，有了基础，可以进一步介绍plookup算法了。
首先看下Plookup的初心。
Plookup应用
使用zk snark去证明一些程式时，有一类操作不是很友好，比如AES-128 或者 SHA-256，它们包含了大量的位操作（异或，与等），这些位操作要表示成门约束，需要先把数分解成二进制位，然后检验二进制位正确性，然后在执行目标操作，所以传统方法约束较为复杂，直观体现门数量多。
以异或（XOR）操作为例：
假如有三个向量域元素，a=(a1,...,an),b=(b1,...,bn),c=(c1,...,cn)，检验每个元素都是8比特位，而且i∈[n],ci=ai⨁bi
使用lookup table来实现约束的思路比较直接，预计算出8比特位操作数所有的输入输出，构造查找表三项t1,t2,t3， 前两项是输入，后一项是XOR结果，检验t3是否是正确的操作结果，变成检验t1,t2,t3是否是预计算table中的一项(entry)。
检验元组(ai,bi,ci)是表中的一项，首先把元组转化为单个元素 fi=ai+rbi+r2ci, 相应地对table做类似处理，ti=ti1+rti2+r2ti3, 如果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′=ti+1−ti={1,3}, s相邻元素差值 s′=si+1−si={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+βsi+1,t′=ti+βti+1,
现在可以对s', {(1 + β)f, t'}做多集合相等校验。根据上一节randomness的思想， 将β作为自变量，s' 就是度为1的多项式。
当si=si+1 不能对应(1 + β)f任一元素，会对应t'中某一元素(tj+βtj+1)，因为二者系数结构相同（1，β），意味着s中新的不同元素包含在t中, s ⊂ t。
当si=si+1， s′=(1+β)si， 一定对应于某个fj, 可得f ⊂ s, 间接推出 f ⊂ t .
为什么一开始思路是相邻元素做减法，后面验证却用加法呢？二者本质相同，减法好理解直接对差值做随机化，加法略微有点回路：
假设相减差值集合 delta=d1,d2,...,dn,s′=si+βsi+1=si+β(si+di)=(1+β)si+βdi, 可以看出也是对差值做的随机化。
所以说直接用减法结果做多集合校验也是没问题的！具体详细P，V多项式的构造与验证，可以查阅plookup的paper。
本文主要介绍plookup算法的思路，本质上是用空间换时间的技巧，预计算一系列范围的值，构造table，验证时验证原始提供的元组（witness）是否在table内，之所以可以这么做的原因到此一目了然！感谢张博从第一性原理角度进行细节分析！
原文链接：https://mp.weixin.qq.com/s/_7LAvH-Rzat337YKL0aWpw
欢迎关注公众号：blocksight
区块链中的数学 -- MultiSet check& Schwartz–Zippel lemma MultiSet check& Schwartz–Zippel lemma
区块链中的数学 -盲签名（Blind Signature） 盲签名原理
区块链中的数学 - sigma协议OR Proof&签名 sigma协议的扩展--OR proof
区块链中的数学 - 何谓零知识证明? 何谓零知识证明
区块链中的数学 - RSA累加器的非成员证明 RSA Accumulator非成员证明以及区块链应用
区块链中的数学 - Accumulator(累加器) 累加器与RSA Accumulator
区块链中的数学 - Kate承诺batch opening Kate承诺批量证明
区块链中的数学 - 多项式承诺 多项式知识和承诺
区块链中的数学 - Pedersen密钥共享 Pedersen 密钥分享
区块链中的数学 - Pedersen承诺 密码学承诺--Pedersen承诺
区块链中的数学 - 不经意传输 不经意传输协议
区块链中的数学 - RSA算法加解密过程及原理 RSA加解密算法
区块链中的数学 - BLS门限签名 BLS m of n门限签名
区块链中的数学 - BLS密钥聚合 BLS密钥聚合
Schorr 签名基础篇 Schorr签名与椭圆曲线
区块链中的数学-Uniwap自动化做市商核心算法解析 Uniwap核心算法解析（中）
本文参与登链社区写作激励计划 ，好文好收益，欢迎正在阅读的你也加入。
- 发表于 2天前
- 阅读 ( 35 )
- 学分 ( 2 )
- 分类：入门/理论
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK