Daily Hunting of The SNARK (01/03/23)

@Bobbin Threadbare：在 Polygon，我们不断致力于推动最先进的技术向前发展。 最近的一个例子是我们与@Alan Szepieniec、@Tomerashur 和 @Willi Meier 合作开发的一种新的和改进的 Rescue Prime Optimized (RPO) 哈希函数。 eprint.iacr.org/2022/1577 退一步说：算术化友好的哈希函数对于零知识证明来说非常重要。 这使我们能够在基于 FRI 的证明系统中拥有超快的递归证明。 但是，尽管它们在证明系统中非常友好，但它们在普通 CPU 上的运行速度非常慢。 为了解决这个问题，@0xPolygonZero 的优秀成员构造了迄今为止最快的 Poseidon 哈希函数实现。 这种实现速度非常快，已经可接近于 SHA2 和 SHA3 等传统哈希函数的性能。 算术化友好哈希的另一个缺点是它们相对较新。 也就是说，它们不像其传统对手那样经过了实战检验。 因此，为了用着放心，我们希望能有多种选择； 这就是 RPO 的用武之地。 顾名思义，RPO 基于 Rescue Prime 哈希函数。 但与大多数其他算术化友好的哈希不同，RPO 不是一个哈希函数族，而是专门针对 Goldilocks 域 () 的一个具体的哈希函数。RPO 在零知识证明系统内外都比原来的 Rescue Prime 更快。 与 Poseidon 的最快实现相比，RPO 的零知识证明系统外性能仅差约 4 倍。 在证明系统之外，我们使用了一个新的 MDS 矩阵，该矩阵旨在使矩阵向量乘法的性能提高多达 40%，这要归功于@0xPolygonZero 开发的技术。在证明系统内部，我们改变了运算顺序并避免乘以逆 MDS 矩阵。 此外，我们还有一个更高效的吸收阶段和一个简化的填充规则。 此处提供了 RPO 的纯 Rust 高性能实现：https://github.com/0xPolygonMiden/crypto/tree/main/src/hash/rpo

@Srinath Setty：SuperNova来了，扩展 Nova 以支持多指令虚拟机执行的递归证明而无需为通用电路引入额外开销（即，证明一个程序步骤的成本仅与调用指令的电路大小成正比）！ia.cr/2022/1758

@Georgios Konstantopoulos：这样说是否正确，先前的证明者开销为单个“子电路”证明占据了整个电路规模，以使其可递归？ 你在这里解除这个，意味着每个子证明不再由系统中最大的电路支配？

是的。 Nova 每一步只支持一次计算。 因此，为了证明机器的执行，必须构建一个可以执行任何受支持指令的电路。 然后证明者也需要为“未调用的”指令付出开销。

@Ariel Gabizon：也许可以和@0xPolygonMiden的 MAST 设计进行比较，例如在不为两个分支付出开销的情况下进行条件判断

https://youtube.com/watch?v=GRFPGJW0hic&t=1614s

https://wiki.polygon.technology/docs/miden/design/decoder/main/

@Weikeng Chen：我必须补充一点：基于拉格朗日基，由于稀疏性，在 Plonk 中使用大量选择子多项式可能不会导致高开销（即电路永远不会是通用的，即使看起来像）。

我不确定是否理解正确。 如果电路可以执行任何支持的指令，则每步证明成本与所有指令的电路大小之和成正比。 一些先前的工作避免了这一点（参加我们论文第一节），但它们与递归证明不兼容

我们只关注 MSM，不一定要 Plonk。 当一个指令集复杂时，更多的选择子多项式通常是稀疏的。 它们对相同的数据进行操作。 这就是 Scroll 有这么多多项式的原因。

我不确定。 商多项式所需的 MSM 又如何呢？

仅与 max（线数 * 门数，商多项式中的最大次数）呈线性关系。 选择子多项式的数量在这里不是问题。

@Remco Bloemen：通过更有效地使用 SIMD 和内存层次结构（缓存、RAM、SSD），是存在优化空间的。 我们可以推动 CPU 实现在达到域大小限制（即 ）时表现良好，至少对于 Goldilocks-FRI 是这样，这方面我很乐观。一个很大的瓶颈将是内存大小和带宽。 定制硬件在这里没有优势，它只能缓解计算瓶颈。 所以问题在于我们能让 CPU 实现多接近带宽限制。

@Santiago Palladino：关于零知识电路开发的一个问题：在编写单元测试时，如何捕获见证生成过程中隐藏在约束中的错误？https://twitter.com/smpalladino/status/1607483400021241856