EUVIMEDObjevte EUVIMED
Crossref

AC4: Algebraic Computation Checker for Circuit Constraints in Zero-Knowledge Proofs

Qizhe Yang, Boxuan Liang, Hao Chen, Guoqiang Li

Formal Aspects of Computing · 2026-03-31 · 38 (1) · 1-20

DOI: 10.1145/3786607 ↗

At a glance

Journal article in Formal Aspects of Computing, published online on 2026-03-12. Written by Qizhe Yang and 3 co-authors. Cited 1 times so far (Crossref); 61 references. Funded by: National Natural Science Foundation of China.

AbstraktBibliografické údajeCiteRelated studies

Abstract (original language)

Zero-knowledge proof (ZKP) systems have surged attention and held a fundamental role in contemporary cryptography. Zero-knowledge succinct non-interactive argument of knowledge (zk-SNARK) protocols dominate the ZKP usage, implemented through arithmetic circuit programming paradigm. However, underconstrained or overconstrained circuits may lead to bugs. The former refers to circuits that lack the necessary constraints, resulting in unexpected solutions and causing the verifier to accept a bogus witness, and the latter refers to circuits that are constrained excessively, resulting in lacking necessary solutions and causing the verifier to accept no witness. This article 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 them over finite fields by the computer algebra system . The classification of verification results is refined, greatly enhancing the expressive power of the system. A tool, AC 4 , is proposed to represent the implementation of the method. Experiments show that AC 4 demonstrates an increase in the solved rate, showing a 36.7% improvement over Picus and CIVER, and a slight improvement over halo2-analyzer, a checker for halo2 circuits. Within a solvable range, the checking time has also exhibited noticeable improvement, demonstrating a magnitude increase compared to previous efforts.

Funding

  • National Natural Science Foundation of China

Cite

APA

Yang, Q., Liang, B., Chen, H., & Li, G. (2026). AC4: Algebraic Computation Checker for Circuit Constraints in Zero-Knowledge Proofs. Formal Aspects of Computing, 38(1), 1-20. https://doi.org/10.1145/3786607

Vancouver

Yang Q, Liang B, Chen H, Li G. AC4: Algebraic Computation Checker for Circuit Constraints in Zero-Knowledge Proofs. Formal Aspects of Computing. 2026;38(1):1-20. doi:10.1145/3786607

BibTeX
@article{Yang2026,
  author = {Yang, Qizhe and Liang, Boxuan and Chen, Hao and Li, Guoqiang},
  title = {AC4: Algebraic Computation Checker for Circuit Constraints in Zero-Knowledge Proofs},
  journal = {Formal Aspects of Computing},
  year = {2026},
  volume = {38},
  number = {1},
  pages = {1--20},
  doi = {10.1145/3786607}
}
Start for free →