举个例子,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:

验证者,除了查看Z函数外,额外还要查看h1/h2连续性。
论文进一步将协议推广到更通用的情况,并给出了t中元素是连续情况下的优化协议。感兴趣的小伙伴可以自行查看。
总结Plookup提出了一种明确输入/输出的情况下,如何证明某个函数的运算正确的协议。输入输出定义成lookup表,计算的输入/结果只要在该lookup表中即表示运算正确。和Plonk采用同样的思路,Plookup定义了问题的多项式表示,证明了Z函数的递归表示和边界。

