Welcome to the resource topic for 2024/185
Title:
Vortex: A List Polynomial Commitment and its Application to Arguments of Knowledge
Authors: Alexandre Belling, Azam Soleimanian, Bogdan Ursu
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).
ePrint: https://eprint.iacr.org/2024/185
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 .