无ZKP计算的简洁验证

Question

当你的证明被允许泄露知识时，产生快速可验证的正确计算证明的最新进展是什么？

对于上下文，我受到米登VM承诺的启发：

对于在Miden上执行的任何程序，都会自动生成一个基于斯塔克的执行证明。然后，任何人都可以使用此证明来验证程序是否正确执行，而不需要重新执行程序，甚至不需要知道程序的内容。

然而，我想知道，如果我们放弃零知识要求，我们是否能做得更好(例如减少验证时间或空间要求等)。

Answer 1

我不相信ZKP能够证明程序已经正确运行，这意味着验证器可以确认f(x)=y是真的，只知道x和y。

从逻辑上说，我们可以想象，恶意参与者可以生成两个程序f(x)=y和f'(x)=y'，其中f'是f的损坏版本。如果不了解f或f'的任何细节，就不可能区分y或y'是否是正确运行的程序f的“正确”结果。

可以构造一种更有效的f形式，将相同的输入映射到相同的输出，但运行速度更快。然而，这是一个更特定于编译器的问题--你永远不能保证长度较短的“电路”(程序)的行为也是一样的。

至于问题的第二部分，这在很大程度上取决于所使用的具体ZKP算法。在大多数算法中，计算开销最大的部分是将需要证明的所有内容转换为可证明的格式(即将x=25转换为某种程度的多项式方程)。

因此，你需要转换的越少，证明就越有效率。这意味着您可以通过隐藏更少的信息来产生更有效的操作(尽管如上所述，我不认为这在Miden的例子中会有帮助)。