Daily Hunting of The SNARK (12/31/22)

@Bobbin Threadbare：零知识证明系统中，递归证明验证就是一种临界魔法：它让我们可以将许多个证明压缩到一个证明的大小。 但它也并非没有代价， 递归验证证明可能会变得非常昂贵。一条了解如何在基于 STARK 的系统中降低一点点开销的快速🧵：验证 STARK 证明的很大一部分是要确保我们使用的多项式具有有界的次数。 为此，我们使用 FRI 协议。 FRI 通过“折叠”多项式来工作，直到我们得到 0 次多项式（即常数）。FRI验证者的主要工作是检查折叠是否正确的进行，以及我们最后得到的常数是否计算正确。但是，验证折叠是否正确进行非常昂贵，我们经常期望能减少下折叠次数。 一种方法是“提前停止”——即不要一直下降到一个常数。 这样我们最终会得到一个余数多项式，如果这个多项式足够小，验证者就可以直接检查它的次数。 此检查通常需要运行 iNTT 算法。 但是在证明系统中运行 iNTT 是昂贵的——因此我们似乎又回到了原点……等下，其实我们不必在证明系统之中实际运行 iNTT！ 相反，我们可以在证明系统之外运行 iNTT，非确定性地提供结果。 于是在证明系统内部，我们只需要验证 iNTT 的结果是否被正确的计算。 这可以以大约在一个随机点求值两个多项式的开销来进行。 有关如何完成此操作的更多信息，请访问：https://github.com/0xPolygonMiden/miden-vm/issues/568#issuecomment-1332298515

@Omer Shlomovits：HyperPlonk的硬件友好性 https://hackmd.io/@omershlo/rJhgKJPtj

@Justin Thaler：最近关于硬件加速和和校验协议（或更一般地说，通过将 Fiat-Shamir 应用于对数轮交互式协议得到的任何 SNARK）的一篇不错的帖子。 这是一些额外的内容。 已经有关于和校验的硬件实现的工作：Zebra (eprint.iacr.org/2015/1243) 和 Giraffe (eprint.iacr.org/2017/242)。 这些工作在每一轮中都大量利用了和校验证明者本质上完美的内存局部性。 在和校验的第 轮中，证明者可以使计算流通过大小为 的数据结构。 我不相信 FFT 具有相同程度的内存局部性，这就是为什么许多分布式 FFT 算法需要全方位通信的原因。 正如该帖子的结论中所指出的，FRI（除了需要 FFT外）具有与和校验相同的对数轮折叠结构，并且该帖子假定了这种折叠并非是使用 FRI 的 SNARK 的瓶颈。 除此之外，避免使用 FRI 和和校验的 SNARK（PlonK、Marlin、Groth16） 也是需要 FFT（和多指数）的，因此上述内存局部性问题也适用于这些 SNARK。 我自己的观点是，基于和校验的 SNARK 仍然是最小化证明者总工作量的最有希望的方法，且以后良好的硬件实现也会出现。

@Benedikt Bünz：关于和校验 (HyperPlonk) 对比NTTs (Plonk) 的硬件友好性的一篇有趣的博文。 @OmerShlomovits 提出的论点是和校验在每一轮中运行哈希函数，这需要将数据发送回 CPU（慢）。 而在 FFT中，你可以对10轮一起进行批处理。 这是一个有趣的观点，但我主要不同意 NTT （又名 FFT）相比和校验要对硬件更友好的结论。 在和校验中每轮多线性求值MLE的大小会减半。 所以在第二轮中，内存读取一半，计算完成一半。 而NTT 中，计算的大小在每一轮中保持不变。 因此即使我们只计算内存读取次数， 的 NTT 也需要 3 次大小为 的读取；而和校验需要 30 次读取，但总共只从内存读取 数据（...） 内存，即减少 50%。 其次，和校验非常局域化。 在每一轮中，它将两个元素直接相互组合，结果与其他项相加。 这意味着我们可以在芯片上流式传输数据、处理、返回结果，且只在芯片上保留一个小小的求和。这和需要批量处理数据的 NTT 形成了对比，我们需要等待计算完成才能返回内存。 第三：（正如@OmerShlomovits 所写）最后几轮（甚至可能是 18 轮）非常小，以至于可能把它们全部放入更快的内存中。 甚至可以将 fiat-shamir 哈希函数放在芯片上，这样根本就不需要内存了。 最后：和校验可以非常有效地进行批处理。 事实上，我们只需要两个大小为 MLE 的和校验，各用 轮。 另一方面，NTT 就不能这么容易地进行批处理，并且 NTT 的大小呈 的线性，其中 是自定义门的次数。 这就在完成的内存和计算量中增加了另一个因子。 在标准 Plonk 中， 约为 5，但在 Hyperplonk 中，由于该原因我们可以处理更大的次数。 总之，我认为思想争鸣是很棒的。 硬件中处理FS 是一个重要的话题。 但是 Hyperplonk 的总计算量和数据量比Plonk要少得多，如果这不能转化为更快的硬件实现，我会感到惊讶。