Welcome to the resource topic for 2025/1850
Title:
Linear*-Time Permutation Check
Authors: Benedikt Bünz, Jessica Chen, Zachary DeStefano
Abstract:Permutation and lookup arguments are at the core of most deployed SNARK protocols today. Most modern techniques for performing them require a grand product check. This requires either committing to large field elements (E.g. in Plonk) or using GKR (E.g. in Spartan) which has worse verifier cost and proof size. Sadly, both have a soundness error that grows linearly with the input size.
We present two permutation arguments that have \text{polylog}(n)/|\mathbb{F}| soundness error – for reasonable input size n=2^{32} and field size |\mathbb{F}|=2^{128}, the soundness error improves significantly from 2^{-96} to 2^{-120}. Moreover, the arguments achieve \log(n) verification cost and proof size without ever needing to commit to anything beyond the witness.
\mathsf{BiPerm} only requires the prover to perform O(n) field operations on top of committing to the witness, but at the cost of limiting the choices of PCS.
We show a stronger construction, \mathsf{MulPerm}, which has no restriction on the PCS choice and its prover performs essentially linear field operations, n\cdot \tilde O(\sqrt{\log(n)}).
Our permutation arguments generalize to lookups.
We demonstrate how our arguments can be used to improve SNARK systems such as HyperPlonk and Spartan, and build a GKR-based protocol for proving non-uniform circuits.
ePrint: https://eprint.iacr.org/2025/1850
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .