Paper 2025/728

SNAIL: Verifiable Computation within 30% of Native Speed

Abstract

SNAIL (Succinct, Non-interactive, Alon-compressed, Instant argument for Layered circuits) turns any depth-$d$ arithmetic circuit into a non-interactive argument whose prover runs within $1+c(d,k,n)$ of plain circuit execution, where $c(d,k,n)=\frac{3(k+n+1)}{kd+n+1}$. For the representative choice $k=n=4$ and $24\le d\le 32$ this means only 21–28 % overhead. Core idea: A constant-round zerocheck based on a difference-driven Alon decomposition compresses all $$ layers into one multivariate identity. Fiat–Shamir in the random-oracle model yields a transparent argument whose hot loop uses only field additions and multiplications (no MSMs, FFTs, or Merkle trees). Cost summary: with $$ and $$ $$ A 2.6-billion-gate trace at $$ is proven in $$ on an RTX-4090 and verified on a smartphone in $$. Width scalability: Proof size depends only on depth, so widening to billions of parallel gates leaves the verifier unchanged—ideal for ultra-wide workloads such as live-audited VM traces. Security: The six-round interactive core is statistically sound; the Fiat–Shamir variant is computationally sound in the random-oracle model and needs no trusted setup. Implications: SNAIL shows that a prover can run near real-time on commodity GPUs while emitting proofs small enough for mobile light clients, enabling applications such as live-streamed provable gaming, pay-per-cycle cloud nodes, and always-on verifiable CPUs.

Note: Remove unnecessary P