A New Zero Knowledge Argument for General Circuits and Its Application

Abstract

Verifying the correctness of computation without revealing the input is a critical issue intensively studied in real-world applications. The recent surge of zero knowledge arguments has been focusing on its efficiency and practicality. Among them, GKR-based arguments have received wide attention and become the foundation of many zero-knowledge proof protocols. However, GKR-based protocols are restricted to layered arithmetic circuits. We proposeTerrace, a new, efficient zero-knowledge argument system for general circuits, based on GKR. By dynamically patching cross-layer claims to the original circuit for verification instead of verifying those claims separately,Terraceis able to reduce the total circuit size and thus enjoys a logarithmic factor less verification time and proof size.Terraceis further extended to include the verification of non-arithmetic operations by rewriting those claims in the multilinear extension form. Experimental results demonstrate that Terrace enjoys a competitive performance on efficiency, and shows great promise in enabling low-cost verification of neural networks.