Paper 2024/185

Vortex: A List Polynomial Commitment and its Application to Arguments of Knowledge

Abstract

A list polynomial commitment scheme (LPC) is a polynomial commitment scheme with a relaxed binding property. Namely, in an LPC setting, a commitment to a function $f(X)$ can be opened to a list of low-degree polynomials close to $f(X)$ (w.r.t. the relative Hamming distance and over a domain $D$). The scheme also allows opening one of the polynomials of the list at an arbitrary point $x$ and convincing a verifier that one of the polynomials in the list evaluates to the purported value. Vortex is a list polynomial commitment, obtained through a modification of Ligero (CCS 2017), inspired by the schemes of Brakedown (Crypto 2023), batch-FRI (FOCS 2020), and RedShift (CCS 2022). Concerning one application of Vortex, for a witness of size $N$, the messages between the prover and the verifier are of size $O(N^{1/2})$. Vortex is a core component of the SNARK used by the prover of Linea (Consensys). This paper provides a complete security analysis for Vortex. We use a general compiler to build an Argument of Knowledge (AoK) by combining our list polynomial commitment and a polynomial-IOP (PIOP). The approach is similar to combining a PIOP with a polynomial commitment scheme and has a soundness loss only linear in the list size. This overcomes a previous limitation in the standard compiler from a generic PIOP and a list polynomial commitment scheme to an interactive argument of knowledge, which suffers from a soundness loss of $\mathcal{O}(|L|^r)$ (where $|L|$ is the list size and $r$ is the number of interactions between the prover and the verifier in the PIOP).