零知识证明: Plookup算法介绍

摘要:针对对电路描述不友好的操作(比如bit操作),Plookup给出了新的思路和证明方式。给定某个操作的真值表示(lookup table),证明某个操作的输入/输出是在真值表中。

举个例子,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函数的递归表示和边界。

免责声明

本文观点仅代表作者个人观点,不构成本平台的投资建议,本平台不对文章信息准确性、完整性和及时性作出任何保证,亦不对因使用或信赖文章信息引发的任何损失承担责任
上一篇

天眼深度 | 这次以太坊的“伦敦”升级为何很重要

下一篇

一文读懂Solana公链的稳定币布局