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

@Ariel Gabizon： 一个古怪的问题 - 即使我们还没有计算下一轮的fiat shamir挑战，和校验轮数是否可以部分并行化！？ 如果是这样，那将增强与 FFT 的对比优势。

@Justin Thaler：我认为这不可能。 Fiat-Shamir 的全部要点是，在知道证明者的下一条消息之前，下一个验证者的挑战应该是不可预测的，并且需要该验证者挑战来更新和校验证明者的数据结构。但我认为，出于多种原因，将这点作为和校验的可能瓶颈是会误导的。这不是 Zebra 和 Giraffe 中的证明者瓶颈。 这些实际上是交互式的，但是等待来自芯片外的下一个验证者挑战只会比对证明者的（短）消息进行哈希慢。如果它真的是一个瓶颈，我们可以以更多的证明者工作为代价来降低轮数复杂性。 例如，可以将轮数减少 4 倍，同时将证明者域操作总数增加约 倍。这也会将证明者数据结构的大小每轮减少 16 倍，而不是原来的 2 倍，于是数据结构将仅在几轮之后就可放入内存。 （标准）技巧是对 而不是 求和。同样的对数轮数问题出现在 FRI 和 Bulletproofs/IPA 中，而且我并没有遇到过关于这是关键瓶颈的说法。

@Weikeng Chen：我认为问题在于，如果我们着眼于实际成本而不是计算复杂性，并且如果我们假设电路处于可工作范围内（较大的电路将进行递归），那么 FFT 永远不会占主导地位。 这在学术界和工业界是非常不同的。

@Justin Thaler：如果 FFT 不是瓶颈（比如说是默克尔哈希，或多指数，或和校验无关的域操作），那么和校验也不应该是。此外，递归带来了开销和不完全理解的安全性，尤其是在使用新的 SNARK 友好哈希函数时。 仅仅因为今天人们严重依赖它来控制电路规模并不意味着将永远如此。

@Brendan：我认为使用像 blake 这样对SNARK 不友好的哈希函数进行递归可能比证明巨大的语句 () 还要更高效效些。恕我直言，这里的悲观主义是没有根据的，因为我们很快就会拥有更快的哈希函数，并且依赖于更保守的分析。

递归非常强大。 我的评论不应被视为悲观主义（尽管我对安全性保持谨慎，尤其是在大深度时），而是乐观地认为非递归技术在许多情况下会被证明更好

好的，很好奇你认为的优势是什么 - 对我来说，证明更大的语句 () 似乎不是最优的，因为它需要更昂贵/非商用的硬件，更复杂，并引入更高的延迟。

@Justin Thaler：这里有几点。 首先，一些关键应用更适用于完全避免电路或其他中间表示的超高效协议，这将导致夜以继日的证明者性能改进。我认为我们很快就会看到的是神经网络训练/推理，其中的瓶颈通常是小整数的重复矩阵乘法。 我也正在研究其他的一些希望人们会觉得有吸引力的东西。顺便说一句，像 Bulletproofs/IPA 这样已经普遍存在的协议可以被视为专用目的的一体化的（基于和校验的！）SNARKs，如果你观察足够仔细的话，请参见，例如，和校验论证（https://eprint.iacr.org /2021/333.pdf，附录 A）。这些已经应用于表示为电路巨大的语句。 我不是在推动这个观点，但认为它有助于传达为什么“专用一体化 SNARK”并不会被递归所包含。 其次，我不相信人们想要证明的所有语句都可以很容易地分解成大小为 ~ 的电路表示的片段，而不会引入重大开销。 但我同意rollups是可行的——根据定义，它们压缩了许多简单的语句/交易。 第三，我不会完全取消安全方面的考虑。 我希望你是对的，SNARK 友好的哈希函数的情况很快就会好转。 但是，虽然项目正在部署具有最多 95 位安全性的 Poseidon，但现在就放松这一点还为时过早。即使使用标准哈希，我认为也有一些实体在安全方面比较保守，并且根据我们的理解不会使用这种技术。 所有实现的组合 SNARK 都具有启发式安全性，或者至少不能排除具体安全性方面的巨大损失。

@abdel.stark：我们做到了！ @KakarotZkEvm 100% EVM 操作码兼容性！ https://github.com/sayajin-labs/kakarot 2个月零20天...没有资金，没有公司，只有一个充满热情的建设者社区 我太激动了。 在投入生产之前还有很长的路要走，但这太棒了🔥