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
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 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 , the messages between the prover and the verifier are of size . 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 (where is the list size and is the number of interactions between the prover and the verifier in the PIOP).

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Polynomial CommitmentList Polynomial CommitmentSNARKZero-KnowledgeArgument of KnowledgeReed-Solomon Code
Contact author(s)
alexandre belling @ consensys net
azam soleimanian @ consensys net
bogdan ursu @ consensys net
History
2024-02-09: approved
2024-02-07: received
See all versions
Short URL
https://ia.cr/2024/185
License
No rights reserved
CC0

BibTeX

@misc{cryptoeprint:2024/185,
      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},
      url = {https://eprint.iacr.org/2024/185}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.