README.md

lambdaworks Polynomial Commitment Schemes

This folder contains lambdaworks polynomial commitment schemes (PCS). The following commitment schemes are supported:

• KZG10
• IPA (Inner Product Argument)

Introduction to KZG commitment scheme

The Kate, Zaverucha, Goldberg (KZG) commitment is a polynomial commitment scheme that works over pairing-friendly elliptic curves, such as BN-254 and BLS12-381. It is important to have the following notation in mind:

• $\mathbb{F_p }$ is the base field of the curve, defined by the prime $p$.
• $\mathbb{F_r }$ is the scalar field associated with the curve, defined by the prime $r$.
• $G_1$ is the largest subgroup/group of prime order of the elliptic curve (the number of elements in the subgroup/group is $r$).
• $G_2$ is the subgroup/group of prime order (equal to $r$) of the twist curve.
• $G_t$ is the multiplicative subgroup of the $r$-th roots of unity of an extension field. For BN-254 and BLS12-381, the extension field is $\mathbb{F_{p^{12} }}$ (a degree twelve extension) and each element of $x \in G_t$ satisfies that $x^r = 1$.

Throughout, we will use the additive notation for the groups $G_1$ and $G_2$ and multiplicative notation for $G_t$. So, given elements $x , y \in G_1$, we will write $x + y = z$, but if $x , y \in G_t$, we have $x \times y = z$.

An elliptic curve is given by the pairs of points $(x , y)$ in $\mathbb{F_p } \times \mathbb{F_p }$, satisfying the equation $y^2 = x^3 + a x + b$. We can find a cyclic group/subgroup of order $r$ that satisfy the equation. This is the group $G_1$.

In a similar way, the group $G_2$ is given by a cyclic group of prime order $r$ that satisfied the twisted curve's equation $y^2 = x^3 + a^\prime x + b^\prime$, where $x, y$ live in an extension field of $\mathbb{F_p }$, typically $\mathbb{F_{p^2 } }$.

Given that both $G_1$, $G_2$ and $G_t$ are cyclic groups, we have elements $g_1$, $g_2$ and $g_t$, called generators, such that when we apply the group operation repeatedly, we span all the elements in the group. For notation purposes, we will denote $[a]_1 = a g_1 = g_1 + g_1 + g_1 + g_1 + ... + g_1$, where we add $a$ copies of $g_1$. Similarly, $[a]_2 = a g_2$ and $[a]_t = g_t^{a}$. More concretely, ${ g_1 , 2g_1 , 3g_1 , 4g_1 , \dots (r - 1)g_1 } = G_1$. Note that if we do $m g_1$, and $m \geq r$, then this will yield the same as $s g_1$ where $s \equiv m \pmod{r}$ and $0 \leq s \leq r - 1$.

The whole scheme depends on a pairing function (also known as bilinear map) $e: G_1 \times G_2 \rightarrow G_t$ which satisfies the following properties:

• $e(x , y) \neq 1$ if $x \neq \mathcal{O}$ and $y \neq \mathcal{O}$ (non-degeneracy).
• $e([a]_1 , [b]_2 ) = \left( e(g_1 , g_2 ) \right)^{a b} = {g_t }^{ab}$ (bilinearity).

There are two parties, prover and verifier. They share a public Structured Reference String (SRS) or trusted setup, given by:

• ${ g_1 , [\tau]_1 , [\tau^2 ]_1 , \dots , [\tau^{n - 1} ]_1 }$ consisting of the powers of a random, yet secret number $\tau$, with degree bounded by $n - 1$, hidden inside $G_1$
• ${ g_2 , [\tau]_2 }$ = ${ g_2 , \tau g_2 }$ contains the generator and $\tau$ hidden inside $G_2$ (for practical purposes, we don't need additional powers).

Knowing these sets of points does not allow recovering the secret $\tau$ or any of its powers (security under the algebraic model).

A polynomial of degree bound by $n - 1$ is an expression $p(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_{n - 1} x^{n - 1}$. The coefficient $a_k \neq 0$ accompanying the largest power is called the degree of the polynomial $\mathrm{deg} (p)$. The coefficients of the polynomial belong to the field $\mathbb{F_r }$. We can commit to a polynomial of degree at most $n - 1$ by performing the following multiscalar multiplication (MSM):

$\mathrm{cm} (p) = a_0 g_1 + a_1 [\tau]_1 + a_2 [\tau^2]1 + \dots + a{n - 1} [\tau^{n - 1}]_1 = P$

This operation works, since we have points over an elliptic curve, and multiplication by a scalar and addition are defined properly. The commitment to $P$ is a point on the elliptic curve, which is equal to $p(\tau ) g_1 = P$. This commitment achieves the two properties we need:

• Hiding
• Binding

Given a commitment to $p$, we can prove evaluations of $p$ at points $z$. We will focus on the simplest case, where we want to show that $p(z) = y$, where $z$ and $y$ live in $\mathbb{F_r}$. The following fact will help us prove the evaluation (it is called the polynomial remainder theorem):

If $p(z) = y$ then $p^\prime = p(x) - y$ is divisible by $x - z$. Another way to state this is that there exists a polynomial $q(x)$ of degree $\mathrm{deg} (p) - 1$ such that $p(x) - y = p^\prime (x) = (x - z) q(x)$.

Providing the quotient would allow the verifier to check the evaluation, but the problem is that the verifier does not know $p(x)$ in full. Given that $\tau$ is a secret point at random, we could check the previous equality in just one point, $\tau$, that is:

$p(\tau ) - y = (\tau - z) q(\tau )$

Due to the Schwartz-Zippel lemma, if the equality above holds, then, with high probability $p(x) - y = p^\prime (x) = (x - z) q(x)$. We could send, therefore $Q = \mathrm{cm} (q) = q(\tau ) g_1$ using the MSM. If $q(x) = b_0 + b_1 x + b_2 x^2 + \dots + b_{n - 1} x^{n - 2}$,

$\mathrm{cm} (q) = b_0 g_1 + b_1 [\tau]1 + \dots b{n - 2} [\tau^{n - 2}]_1 = Q$

In the context of EIP-4844, $P$ is called the commitment and $Q$ is the evaluation proof. We can use the pairing to check the equality at $\tau$. We compute the following:

• $e( P - y g_1 , g_2 ) = \left( e(g_1 , g_2 ) \right)^{ p(\tau ) - y }$
• $e( Q , [\tau]_2 - z g_2 ) = \left( e(g_1 , g_2 ) \right)^{ q(\tau ) (\tau - z)}$

If the two pairings are equal, this means that $p(\tau ) - y \equiv q(\tau ) (\tau - z) \pmod{r}$. In practice, we use an alternative formulation,

$e( P - y g_1 , - g_2 ) \times e( Q , [\tau]_2 - z g_2 ) \equiv 1 \pmod{r}$

This is more efficient, since we can compute the pairing using two Miller loops but just one final exponentiation.

Implementation

The implementation in this codebase includes:

• StructuredReferenceString: Stores the powers of a secret value in both G1 and G2 groups
• KateZaveruchaGoldberg: The main implementation of the KZG commitment scheme
• Support for both single and batch openings/verifications

API Usage

KZG commitments can be used to commit to polynomials and later prove evaluations at specific points. Here's how to use the KZG implementation in lambdaworks:

Creating a KZG Instance

First, you need to load or create a Structured Reference String (SRS) and initialize the KZG instance:

use lambdaworks_crypto::commitments::kzg::{KateZaveruchaGoldberg, StructuredReferenceString};
use lambdaworks_crypto::commitments::traits::IsCommitmentScheme;
use lambdaworks_math::elliptic_curve::short_weierstrass::curves::bls12_381::{
    curve::BLS12381Curve,
    default_types::{FrElement, FrField},
    pairing::BLS12381AtePairing,
    twist::BLS12381TwistCurve,
};
use lambdaworks_math::elliptic_curve::short_weierstrass::point::ShortWeierstrassProjectivePoint;

// Load SRS from a file
let srs_file = "path/to/srs.bin";
let srs = StructuredReferenceString::from_file(srs_file).unwrap();

// Create a KZG instance
let kzg = KateZaveruchaGoldberg::<FrField, BLS12381AtePairing>::new(srs);

Committing to a Polynomial

To commit to a polynomial, you first create the polynomial and then use the commit method:

use lambdaworks_math::field::element::FieldElement;
use lambdaworks_math::polynomial::Polynomial;

// Create a polynomial p(x) = x + 1
let p = Polynomial::<FrElement>::new(&[FieldElement::one(), FieldElement::one()]);

// Commit to the polynomial
let commitment = kzg.commit(&p);

Generating and Verifying Proofs

To prove that a polynomial evaluates to a specific value at a specific point:

// Choose a point to evaluate the polynomial
let x = -FieldElement::one();

// Compute the evaluation
let y = p.evaluate(&x);  // Should be 0 for p(x) = x + 1 when x = -1

// Generate a proof for this evaluation
let proof = kzg.open(&x, &y, &p);

// Verify the proof
let is_valid = kzg.verify(&x, &y, &commitment, &proof);
assert!(is_valid, "Proof verification failed");

Batch Operations

KZG supports batch operations for more efficient verification of multiple polynomial evaluations:

// Create polynomials
let p0 = Polynomial::<FrElement>::new(&[FieldElement::from(9000)]);  // Constant polynomial
let p1 = Polynomial::<FrElement>::new(&[
    FieldElement::from(1),
    FieldElement::from(2),
    -FieldElement::from(1),
]);  // p(x) = 1 + 2x - x²

// Commit to the polynomials
let p0_commitment = kzg.commit(&p0);
let p1_commitment = kzg.commit(&p1);

// Choose a point to evaluate the polynomials
let x = FieldElement::from(3);

// Compute the evaluations
let y0 = p0.evaluate(&x);  // 9000
let y1 = p1.evaluate(&x);  // 1 + 2*3 - 3² = 1 + 6 - 9 = -2

// Generate a random field element for the batch proof
let upsilon = &FieldElement::from(1);  // In practice, use a random value

// Generate batch proof
let proof = kzg.open_batch(&x, &[y0.clone(), y1.clone()], &[p0, p1], upsilon);

// Verify batch proof
let is_valid = kzg.verify_batch(
    &x,
    &[y0, y1],
    &[p0_commitment, p1_commitment],
    &proof,
    upsilon
);
assert!(is_valid, "Batch proof verification failed");

Serialization and Deserialization

The SRS can be serialized and deserialized for storage and transmission:

// Serialize the SRS
let bytes = srs.as_bytes();

// Deserialize the SRS
let deserialized_srs = StructuredReferenceString::<
    ShortWeierstrassProjectivePoint<BLS12381Curve>,
    ShortWeierstrassProjectivePoint<BLS12381TwistCurve>,
>::deserialize(&bytes).unwrap();

References

• Constantine
• EIP-4844
• KZG proof verification
• Multiproofs KZG
• Fast amortized KZG proofs

---

Introduction to IPA commitment scheme

The Inner Product Argument (IPA) is a transparent polynomial commitment scheme — it requires no trusted setup. Security relies only on the discrete logarithm assumption over any prime-order group. It produces $O(\log n)$ sized proofs with $O(n)$ verification time (dominated by a single multi-scalar multiplication).

The IPA folding protocol originates from Bulletproofs (Bünz et al., 2017) and is used in protocols like Halo, Halo 2, and Spartan. It complements KZG for scenarios where transparency is preferred over the smaller proof sizes that pairings enable.

Setup

The setup is public and deterministic — no secret ceremony required:

• A vector of $n$ group generators $G_0, G_1, \dots, G_{n-1} \in \mathbb{G}$, where $n$ is a power of two
• An independent generator $U \in \mathbb{G}$ used to bind the inner product

These can be derived deterministically (e.g., by hashing indices to curve points).

Commitment

A polynomial $p(x) = a_0 + a_1 x + \dots + a_{n-1} x^{n-1}$ is committed by a multi-scalar multiplication:

$$C = \sum_{i=0}^{n-1} a_i \cdot G_i$$

Opening Protocol

To prove that $p(z) = y$, the prover and verifier engage in $k = \log_2(n)$ rounds of folding:

1. Define the evaluation vector $\mathbf{b} = (1, z, z^2, \dots, z^{n-1})$ so that $\langle \mathbf{a}, \mathbf{b} \rangle = p(z) = y$.
2. The prover maintains the invariant: $P = \text{MSM}(\mathbf{a}, \mathbf{G}) + \langle \mathbf{a}, \mathbf{b} \rangle \cdot U$

In each round $j$, the prover:

• Splits vectors $\mathbf{a}$, $\mathbf{b}$, $\mathbf{G}$ into left and right halves
• Computes cross-terms $L_j = \text{MSM}(\mathbf{a}_L, \mathbf{G}_R) + \langle \mathbf{a}_L, \mathbf{b}_R \rangle \cdot U$ and $R_j = \text{MSM}(\mathbf{a}_R, \mathbf{G}_L) + \langle \mathbf{a}_R, \mathbf{b}_L \rangle \cdot U$
• Receives a random challenge $x_j$ (derived via Fiat-Shamir)
• Folds: $\mathbf{a}' = x_j \mathbf{a}_L + x_j^{-1} \mathbf{a}_R$, $\mathbf{b}' = x_j^{-1} \mathbf{b}_L + x_j \mathbf{b}_R$, $\mathbf{G}' = x_j^{-1} \mathbf{G}_L + x_j \mathbf{G}_R$

After $k$ rounds, the prover sends the final scalar $a_{\text{final}}$.

Verification

The verifier reconstructs the folded commitment:

$$P_{\text{final}} = C + y \cdot U + \sum_{j=1}^{k} \left( x_j^2 \cdot L_j + x_j^{-2} \cdot R_j \right)$$

Then computes:

• $\mathbf{s}$: the tensor product of challenges (used to derive $G_{\text{final}} = \text{MSM}(\mathbf{s}, \mathbf{G})$)
• $b_{\text{final}} = \prod_{j=1}^{k} \left( x_j^{-1} + x_j \cdot z^{2^{k-j}} \right)$ in $O(\log n)$ time

And checks: $P_{\text{final}} = a_{\text{final}} \cdot G_{\text{final}} + (a_{\text{final}} \cdot b_{\text{final}}) \cdot U$

Proof Size

For a polynomial of degree $n - 1$:

• $2 \log_2(n)$ group elements ($L_j$ and $R_j$ points)
• 1 scalar ($a_{\text{final}}$)

IPA Implementation

The implementation includes:

• IpaSetup: Transparent setup containing generators and the inner product binding point $U$
• IpaProof: Proof structure with $L/R$ points and the final scalar
• Ipa: The main IPA polynomial commitment scheme, generic over any group implementing IsGroup + AsBytes

The current implementation is non-hiding (binding but not hiding). Blinding can be added in the future for zero-knowledge applications.

IPA API Usage

Creating an IPA Instance

use lambdaworks_crypto::commitments::ipa::{Ipa, IpaSetup};
use lambdaworks_math::{
    elliptic_curve::short_weierstrass::curves::pallas::curve::PallasCurve,
    elliptic_curve::traits::IsEllipticCurve,
    field::element::FieldElement,
    field::fields::vesta_field::Vesta255PrimeField,
    polynomial::Polynomial,
};

type F = Vesta255PrimeField;
type FE = FieldElement<F>;
type G = <PallasCurve as IsEllipticCurve>::PointRepresentation;

// Create generators deterministically
let g = PallasCurve::generator();
let n = 8; // must be a power of two
let generators: Vec<G> = (1..=n as u64)
    .map(|i| g.operate_with_self(i))
    .collect();
let u = g.operate_with_self(n as u64 + 1337);

let setup = IpaSetup { generators, u };
let ipa = Ipa::<4, F, G>::new(setup);

Committing and Proving

use lambdaworks_crypto::fiat_shamir::default_transcript::DefaultTranscript;

// Create a polynomial p(x) = 1 + 2x + 3x^2 + ... + 8x^7
let coeffs: Vec<FE> = (1..=8).map(FE::from).collect();
let p = Polynomial::new(&coeffs);

// Commit
let commitment = ipa.commit(&p);

// Prove evaluation at z = 5
let z = FE::from(5);
let y = p.evaluate(&z);

let mut prover_transcript = DefaultTranscript::new(b"my-protocol");
let proof = ipa.open(&commitment, &p, &z, &mut prover_transcript);

Verifying

let mut verifier_transcript = DefaultTranscript::new(b"my-protocol");
let valid = ipa.verify(&commitment, &z, &y, &proof, &mut verifier_transcript);
assert!(valid);

Important: Prover and verifier must use transcripts initialized with the same label.

IPA References

• Bulletproofs (original IPA)
• Halo: Recursive Proof Composition without a Trusted Setup
• Halo 2 Book
• Proofs for Inner Pairing Products (BMMTV)