零知识证明 - zkHack V Puzzle 1 - zeitgeist

zkHack的Puzzle是我比较喜欢的活动。通过实例编码深入理解零知识证明的细节是比较高效的学习方式。zkHack V前几天已经开始了。这篇文章分析一下第一道题目：

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

1. 题目

有一个验证电路，证明者需要证明在知道“私钥”的同时，提供一个Nullifier。但是，验证服务故意让证明者多次（64次）提交证明，从而获取证明者的私钥信息。题目重现了整个场景，要求找出验证服务找出私钥信息的方法。

2. 电路和证明系统

这条题目使用的是修改过的“Halo2”证明系统。Halo2证明系统的介绍，可以参考之前的文章：

零知识证明 - Halo2电路构建源代码导读

通过查看MyCircuit结构的configure函数，整个验证电路的芯片结构如下：

整个验证电路由三块芯片组成：一块Input芯片以及两块Pow5芯片。Pow5芯片用来计算hash值。两块Pow5芯片分别输出commitment和nullifier。表面上看，电路业务本身比较简单，没有什么问题。

3. 深入Halo2

仔细查看题目实现的Halo2的证明系统，在advice列盲化填充时采用了固定值。打印所有advice列信息后发现：

• 整个电路由9列advice列

• 每一列由64个cell组成

• 在计算commitment的Pow5芯片的第一个advice列数据使用不变，并且第二到第四个cell都是private key信息

Halo2是基于IOP的证明系统。电路中的每一列都需要“承诺”以及“打开”，通过打开信息的约束关系保证电路约束。到此，基本的思路就有了：找出第一个advice列的“打开”的64个(point, eval)信息，通过拉格朗日插值恢复原始advice列数据。

4. 解决方案

基于上述的思路，细化后的解决方案如下：

1/ 从Proof中找出Evaluation: Proof的第640开始的32个字节。

2/ 并重现验证过程，从Transcript中恢复出挑战X。

3/ 使用halo2_proofs::arithmetic::lagrange_interpolate进行拉格朗日插值。注意的是，因为原始的advice列是在特定域上转换为多项式形式，为了获取原始的advice列数据，需要采用best_ftt函数将多项式从系数表示转换为值表示。

let mut coeffs = lagrange_interpolate(points.as_slice(), evals.as_slice());                              
  best_fft(coeffs.as_mut_slice(), domain.get_omega(), K);
  let secret = coeffs[2];

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