AC4: Algebraic Computation Checker for Circuit Constraints in ZKPs
Hao Chen Minyu Chen Ruibang Liu Guoqiang Li
ZKP systems have surged attention and held a fundamental role in contemporary
cryptography. Zk-SNARK protocols dominate the ZKP usage, often implemented
through arithmetic circuit programming paradigm. However, underconstrained or
overconstrained circuits may lead to bugs. Underconstrained circuits refer to
circuits that lack the necessary constraints, resulting in unexpected solutions
in the circuit and causing the verifier to accept a bogus witness.
Overconstrained circuits refer to circuits that are constrained excessively,
resulting in the circuit lacking necessary solutions and causing the verifier
to accept no witness, rendering the circuit meaningless. This paper introduces
a novel approach for pinpointing two distinct types of bugs in ZKP circuits.
The method involves encoding the arithmetic circuit constraints to polynomial
equation systems and solving polynomial equation systems over a finite field by
algebraic computation. The classification of verification results is refined,
greatly enhancing the expressive power of the system. We proposed a tool, AC4,
to represent the implementation of this method. Experiments demonstrate that
AC4 represents a substantial 29% increase in the checked ratio compared to
prior work. Within a solvable range, the checking time of AC4 has also
exhibited noticeable improvement, demonstrating a magnitude increase compared
to previous efforts.