Paper 2024/185

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

Alexandre Belling, Linea, Prover Team
Azam Soleimanian, Linea, Prover Team
Bogdan Ursu, Linea, Prover Team

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).

Available format(s)
Cryptographic protocols
Publication info
Polynomial CommitmentList Polynomial CommitmentSNARKZero-KnowledgeArgument of KnowledgeReed-Solomon Code
Contact author(s)
alexandre belling @ consensys net
azam soleimanian @ consensys net
bogdan ursu @ consensys net
2024-02-09: approved
2024-02-07: received
See all versions
Short URL
No rights reserved


      author = {Alexandre Belling and Azam Soleimanian and Bogdan Ursu},
      title = {Vortex: A List Polynomial Commitment and its Application to Arguments of Knowledge},
      howpublished = {Cryptology ePrint Archive, Paper 2024/185},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.