Paper 2023/1611

Power circuits: a new arithmetization for GKR-styled sumcheck

Abstract

Goldwasser-Kalai-Rothblum protocol (GKR) for layered circuits is a sumcheck-based argument of knowledge for layered circuits, running in $\sim 2\mu \ell$ amount of rounds, where $\ell$ is the amount of layers and $\mu$ is the average layer logsize. For a layer $i$ of size $2^{{\mu }_i}$ the main work consists of running a sumcheck protocol of the form $$\sum _{x,y}{\text{Add}}_i(x,y,z)(f(x)+f(y))+{\text{Mul}}_i(x,y,z)f(x)f(y)$$ over a $2^{2{\mu }_i}$-dimensional cube, where ${\text{Add}}_i(x,y,z)$ and ${\text{Mul}}_i(x,y,z)$ are (typically relatively sparse) polynomials called "wiring predicates". We present a different approach, based on the (trivial) observation that multiplication can be expressed through linear operations and squaring. This leads to the different wiring, which is marginally more efficient even in a worst-case scenario, and decreases the amount of communication $$ in the case where wiring predicates are sparse.