零知识证明 - zkHack V Puzzle 2 - Don't Lookup

接着看看zkHack V的第二道题。

https://zkhack.dev/zkhackV/puzzleV2.html

1. 题目

基于一个比较小的域，实现了一个Lookup协议。题目给定了一个从0～63的表，尝试证明2^15在表中。

2. Lookup协议

题目中实现的Lookup协议的理论基础是PROTOSTAR论文中的4.3小节：

如果想证明w列表在t表中，需要证明多项式6成立。

证明多项式成立的流程如下图：

第一步：证明者提供w列表，以及这个列表中的元素在表t中相应元素出现的次数m_i。

第二步：在接收到验证者随机挑战r后，计算h_i以及g_i，发送给验证者。验证者验证上图中右下角的三个等式。

协议本身并不复杂，论文也给出了可靠性误差的计算公式：

从可靠性误差的计算公式看出，如果l特别大的话，特别是大于等于|F|的情况下，协议已经失效。

3. l = |F|

仔细观察协议，如果l为|F|，并且witness为重复的元素的话，不论r的取值如何，h_i都相同。h_i的求和必为0。在这种情况下，等效于证明一个空列表是否在t表中。

4. 解决方案

解决方案相对简单，代码修改如下：

对题目感兴趣的小伙伴，可以进一步查看zkHack V网站上的详细分析。