This is a really informal post of my understanding of polynomial commitments. I am in no way a professional in cryptography and is just learning this for fun. Most of the excerpts in these notes are borrowed from the amazing article by Dankrad and Alinush.

My pain

Is self-chosen

At least

So The Prophet says

Now, another song for you to listen along for this ride that you’re embarking on with me. River of Deceit by Mad Season. This was a total random song found while listening to my Daily Mix playlist. Anyways, I like it.

Commitments

Contains two algorithms:

$co mmi t (m, r) \to co m$
$v er i f y (m, co m, r) \to 0/1$

Properties:

Binding: can’t produce two valid openings for one commitment
Hiding: com doesn’t reveal about committed data.

Functional Commitments

committing to a function $f$ in family $F = f : X \to Y$ .

Steps followed:

$se t u p ()$ → pp
$co mmi t (f, pp, r)$ → $co m$
eval(Prover P, Verifier V): $x \in X$ , $y \in Y$ s.t. $f (x) = y$
1. $P (f, pp, x, y, r)$ → succinct proof $p i$
2. $V (pp, co m, x, y, π)$ → 0/1

Three main types of functional commitments possible:

Polynomial commitments: Univariate polynomial of at most degree d
Multilinear commitments: Multivariate polynomial
Linear commitments: Linear functions $f_\vec{v}(\vec{u}) = <\vec{u},\vec{v}>=\sum^{i=1}_{n}u_{i}v_{i}$

Different types of PCS:

Basic Elliptic curves: Bulletproofs

Bilinear groups: KZG

Groups of unknown order: DARK

Hash functions: FRI

More info about comparison between these schemes here.

Polynomial Commitment Scheme (PCS)

what properties are desirable for an efficient PCS? :: commitment time is fast and proof is small, verify/eval time is fast
what do you mean by small and fast? :: small means few bytes, for ex: in KZG, it’s just one group element and BN254 is just 32 bytes. By fast, i mean in quasilinear time. for ex: verification in KZG takes $O (l o g d)$ , where d is degree of polynomial.
see, commitment to a polynomial is just evaluation of that polynomial at a point and brute force method takes $O (d)$ time, where d is the degree of the polynomial and if you want to commit to d polynomials, it amounts to $O (d^{2})$ time.
- there’s a better method than that, i.e. NTT Number theory transform which can do this in O(d logd).
  - implement this
- even better than this → use lagrange interpolation to find $f (τ)$ which is linear in $d$ .
then comes evaluation proofs $π_{a}$ → naively each evaluation proof takes $O (d)$ time, and for $d$ polynomials this goes to $O (d^{2})$
- comes Feist-Khovartovich algorithm, which takes it in $O (d l o g d)$ if $\Upomega$ domain is multiplicative subgroup.

KZG Commitments

A polynomial commitment scheme allows anyone to commit to a polynomial $p (X)$ with the properties that this commitment $C$ (an elliptic curve point) can later be verified by anyone at any position $z$ on that polynomial. The prover proves at a position the value of the polynomial known as proof $π$ versus the claimed value known as evaluation $p (z)$ and this is only possible when prover actually has provided proof for that one polynomial that it committed to.

kzg-steps

Notation

Let $G_{1}$ and $G_{2}$ be two elliptic curves with a pairing $e : G_{1} \times G_{2} \to G_{T}$ .
Let $p$ be the order of $G_{1}$ and $G_{2}$ and $G$ is generator of $G_{1}$ and $H$ is generator of $G_{2}$ .
$[x]_{1} = x G \in G_{1}$ and $[x]_{2} = x H \in G_{2}$ where $x \in F_{p}$ .

Trusted Setup

You might’ve read multiple times in twitter threads that there is a trusted ceremony that is associated with DAS, SNARKs or words like KZG Ceremony. They are usually talking about this trusted setup. Also known as Powers of tau.

In this ceremony, a random secret $τ \in F_{p}$ is created, using which its powers $[τ^{i}]_{1}$ and $[τ^{i}]_{2}$ for $i = 0, \dots, n - 1$ are created. In additive notation, it is represented as:

$[τ^{i}]_{1} = (G, τ G, τ^{2} G, \dots, τ^{n - 1} G) \in G_{1}$ $[τ^{i}]_{2} = (H, τ H, τ^{2} H, \dots, τ^{n - 1} H) \in G_{2}$

These elements which are just elliptic curve points are made public but the secret has to be destroyed otherwise this ceremony has no meaning as anyone will be able to forge invalid proofs later. In practice this is usually implemented via a secure multiparty computation (MPC), which uses multiple participants to derive these elements and require all participants together to know secret $τ$ . Thus, this has a nice 1-to-N security assumption, basically only 1 honest participant is required which is easy to obtain.

Now, you must be thinking what are they used for? We know that a polynomial is represented as:

$P o l y n o mia l : p (X) = \sum_{i = 0}^{n} p_{i} X^{i}$

Now, the prover can compute the commitment to the polynomial as:

$C o mmi t m e n t : C = [p (τ)]_{1}$

$= [\sum_{i = 0}^{n} p_{i} τ^{i}] = \sum_{i = 0}^{n} p_{i} [τ^{i}]$

This is a really interesting output, as prover is able to evaluate polynomial at point $τ$ , even when he doesn’t know the secret and this becomes the commitment of prover of the polynomial.

Now, you might be wondering if a malicious prover find another polynomial $q (X) \neq = p (X)$ such that $[q (τ)]_{1} = [p (τ)]_{1}$ . But the prover doesn’t know $τ$ , so the best bet for prover to achieve $p (τ) = q (τ)$ is to make the polynomial pass through as many points $n$ as possible. But it’s computably inefficient to find the exact polynomial that passes through $n$ points where curve order $p \approx 2^{256}$ as $n <<< p$ .

Proof Evaluation

We need a mechanism so that prover could verify its commitment on the polynomial and this is done through evaluations on the polynomial $p (X)$ . Evaluation is done at a point $z$ and the claimed value $p (z)$ is verified by the verifier.

Now, a value $z$ is chosen such that $p (z) = y$ . This means that $p (X) - y$ should have a factor $X - z$ . So, a quotient polynomial $q (X) = \frac{p ( X ) - y}{X - z}$ is computed and the evaluation proof becomes,

$π = [q (τ)]_{1}$

$= \sum_{i = 0}^{n} [τ^{i}] \cdot q_{i}$

Prover sends this proof to verifier which verifiers this proof.

Verifying Evaluation

Now, verifier has following things:

Polynomial: $p (X) = \sum_{i = 0}^{n} p_{i} X^{i}$
Commitment: $C = \sum_{i = 0}^{n} p_{i} [τ^{i}]$
Evaluation point: $z$
Claimed value: $y$
Proof: $π = [q (τ)]_{1}$

Now verifier wants to verify that claimed value is indeed correct using the proof. That’s where pairings come into play. Pairings allow us to multiply two polynomials in different curves and get the output in a target curve. This unfortunately is not possible in a single curve which is a property called Fully Homomorphic Encryption for elliptic curves. ECs are only homomorphic additively.

Verifier checks the following equation:

$e (π, [τ]_{2} - [z]_{2}) = e (C - [y]_{1}, H)$

Note: verifier has $[τ]_{2}$ from the trusted setup and $[τ - z]_{2}$ is computed through EC arithmetic.

This convinces verifier that claimed value is indeed the evaluation of the committed polynomial at the point $z$ . How? Let’s unroll the equation,

$e (π, [τ]_{2} - [z]_{2}) = e (C - [y]_{1}, H)$ $e (π, [τ - z]_{2}) = e (p [τ]_{1} - [y]_{1}, H)$ $[q (τ) \cdot (τ - z)]_{T} = [p (τ) - y]_{T}$

We need two properties from this equation:

Correctness: If prover followed right steps, then proof is correct.
Soundness: if they produce incorrect proof, verifier won’t be convinced.

Correctness checks out as this equation is similar to what we defined in the quotient polynomial $q (X) (X - z) = p (X) - y$ .

For soundness, prover would have to compute incorrect proof,

$π^{'} = (C - [y^{'}]_{1})^{\frac{1}{τ - z}}$

But it’s not possible to do this as $τ$ is not known to prover and if they can forge this proof, then they can convince verifier for anything. Or it would have to forge a fake proof with fake evaluation $ω$ which somehow has $τ$ as root of $\frac{P - ω}{X - z}$ , whose probability is negligible due to Schwartz Zippel Lemma.

Comparison to Merkle Trees

Merkle trees are a form of vector commitments, i.e. Using a merkle tree of depth $d$ will have $2^{d} - 1$ elements, anyone can compute a commitment to a vector $(a_{0}, a_{1}, a_{2}, \dots, a_{2^{d} - 1})$ . Thus, using Merkle trees anyone can prove that element a_i is a member of a vector at position i using d hashes.

merkle-tree

You can even make polynomial commitment out of Merkle trees. A polynomial is represented as $p (X) = \sum_{i = 0}^{n} p_{i} X^{i}$ , using $a_{i} = p_{i}$ , we can construct a polynomial of degree $n = 2^{d} - 1$ and computing merkle root of the coefficients. Now, the prover can prove the evaluation by sending all the $p_{i}$ and verifier verifying the evaluation by computation $p (z) = y$ .

This is a very simple polynomial commitment that is inefficient to its core but will help to understand the marvel KZG commitment is.

Prover has to send all the $p_{i}$ to verifier in order to commence verification. So, proof size is linear with the degree of the polynomial. While in Kate Commitments, commitment and proof size is just one group element of an elliptic group. Commonly used pairing curve is BLS12-381, that would make proof size to be 48 bytes.
The verifier need to do linear work to compute $z$ . While in KZG, verification is constant as only two multiplications and pairings are required to verify proof.
commitments using merkle trees makes the polynomial public and doesn’t hide anything. While it’s mostly hidden in Kate commitments.

Now, the best part about Kate proofs are it can create one proof for multiple evaluation, i.e. only one group element for multiple proofs.

Multiproofs

Let’s say we have a list of $k$ points that we want to prove, $(z_{0}, y_{0}), (z_{1}, y_{1}), \dots, (z_{k}, y_{k})$ . We find a polynomial $I (X)$ that goes through these points using Lagrange Interpolation:

$I (X) = \sum_{i = 0}^{k - 1} y_{i} \prod_{j \neq = i j = 0}^{k - 1} \frac{X - z _{j}}{z _{i} - z _{j}}$

For the evaluation proof, while in the single proof we compute $q (x) = \frac{p ( x ) - y}{x - z}$ , we will replace $y$ as single point with $I (x)$ , and $x - z$ will be replaced with $Z (x) = \prod_{i = 0}^{k} x - z_{i}$ . Now, we replace our values and $q (x)$ becomes

$q (x) = \frac{p ( x ) - I ( x )}{Z ( x )}$

This is possible due to $p (x) - I (x)$ being divisible by all linear factors of $Z (x)$ and being divisible by whole $Z (x)$ . The multiproof for evaluation $(z_{0}, y_{0}), (z_{1}, y_{1}), \dots, (z_{k}, y_{k})$ : $π = [q (s)]_{1}$ . Now, our prover equation becomes

$e (π, [Z (s)]_{2}) = e (C - [I (s)]_{1}, H)$

$[q (s) \cdot Z (s)]_{T} = [p (s) - I (s)]_{T}$

This really blew my mind when I was first studying them. You can have a million proofs batch together in one single 48 bytes proof which anyone can verify by just computing $I (x)$ and $Z (x)$ . Cryptography really is cool.

    \begin{algorithm}
    \caption{Quicksort}
    \begin{algorithmic}
      \Procedure{Quicksort}{$A, p, r$}
        \If{$p < r$}
          \State $q \gets $ \Call{Partition}{$A, p, r$}
          \State \Call{Quicksort}{$A, p, q - 1$}
          \State \Call{Quicksort}{$A, q + 1, r$}
        \EndIf
      \EndProcedure
      \Procedure{Partition}{$A, p, r$}
        \State $x \gets A[r]$
        \State $i \gets p - 1$
        \For{$j \gets p$ \To $r - 1$}
          \If{$A[j] < x$}
            \State $i \gets i + 1$
            \State exchange
            $A[i]$ with $A[j]$
          \EndIf
        \State exchange $A[i]$ with $A[r]$
        \EndFor
      \EndProcedure
      \end{algorithmic}
    \end{algorithm}

lonerapier.xyz

Explorer

Polynomial Commitments

Commitments

Functional Commitments

Polynomial Commitment Scheme (PCS)

KZG Commitments

Notation

Trusted Setup

Proof Evaluation

Verifying Evaluation

Comparison to Merkle Trees

Multiproofs

Resources

Graph View

Table of Contents

Backlinks