AC4: Algebraic Computation Checker for Circuit Constraints in ZKPs

ZKP系统在当代密码学中引起了广泛关注，并发挥着基础性作用。 Zk-SNARK协议主导了ZKP的使用，通常通过算术电路编程范式实现。然而，欠约束或过度约束的电路可能会导致错误。欠约束电路是指缺乏必要约束的电路，导致电路中出现意外解决方案，并导致验证者接受虚假证人。过度约束电路是指过度约束的电路，导致电路缺乏必要的解决方案，并导致验证者接受没有证人的情况，使电路无意义。本文介绍了一种用于确定ZKP电路中两种不同类型错误的新方法。该方法涉及将算术电路约束编码为多项式方程组，并通过代数计算在有限域上解决多项式方程组。验证结果的分类得到了改进，极大地增强了系统的表达能力。我们提出了一个名为AC4的工具来表示此方法的实现。实验证明，与以前的工作相比，AC4表示检查比率的实质性增加了29％。在可解范围内，AC4的检查时间也有明显的改善，与以前的努力相比，呈数量级增加的趋势。

检测ZKP电路中的错误

将算术电路约束编码为多项式方程系统，并通过代数计算在有限域上求解多项式方程系统，以检测ZKP电路中的错误。

提出了一个名为AC4的工具，用于实现该方法。实验结果显示，与以前的工作相比，AC4的检查比例增加了29％，检查时间也有所改善。

最近的相关研究包括：“Scalable Zero Knowledge via Cycles of Elliptic Curves”和“Bulletproofs: Short Proofs for Confidential Transactions and More”