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)}{k\,d + 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 \(d\) 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 \(k = n = 4\) and \(24 \le d \le 32\) \[ T_{\text{prov}}(S,d)=\Bigl(1+\frac{6.75}{d}\Bigr)S,\qquad |\pi|=(d^{2}+2d)(4d+1),\qquad \varepsilon_{\text{sound}}=\frac{4nd}{|\mathbb F|}. \] A 2.6-billion-gate trace at \(d = 32\) is proven in \(\approx 40\;\text{ms}\) on an RTX-4090 and verified on a smartphone in \(< 1\;\text{ms}\). 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