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.


Contains two algorithms:


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

Functional Commitments

committing to a function in family .

Steps followed:

  1. pp
  2. eval(Prover P, Verifier V): , s.t.
    1. succinct proof
    2. 0/1

Three main types of functional commitments possible:

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

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 , 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 time, where d is the degree of the polynomial and if you want to commit to d polynomials, it amounts to 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 which is linear in .
  • then comes evaluation proofs naively each evaluation proof takes time, and for polynomials this goes to

    • comes Feist-Khovartovich algorithm, which takes it in if domain is multiplicative subgroup.

KZG Commitments

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



  • Let and be two elliptic curves with a pairing .
  • Let be the order of and and is generator of and is generator of .
  • and where .

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 is created, using which its powers and for are created. In additive notation, it is represented as:

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:

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

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 such that . But the prover doesn’t know , so the best bet for prover to achieve is to make the polynomial pass through as many points as possible. But it’s computably inefficient to find the exact polynomial that passes through points where curve order as .

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 . Evaluation is done at a point and the claimed value is verified by the verifier.

Now, a value is chosen such that . This means that should have a factor . So, a quotient polynomial is computed and the evaluation proof becomes,

Prover sends this proof to verifier which verifiers this proof.

Verifying Evaluation

Now, verifier has following things:

  • Polynomial:
  • Commitment:
  • Evaluation point:
  • Claimed value:
  • Proof:

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:

Note: verifier has from the trusted setup and is computed through EC arithmetic.

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

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 .

For soundness, prover would have to compute incorrect proof,

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 , 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 will have elements, anyone can compute a commitment to a vector . Thus, using Merkle trees anyone can prove that element a_i is a member of a vector at position i using d hashes.


You can even make polynomial commitment out of Merkle trees. A polynomial is represented as , using , we can construct a polynomial of degree and computing merkle root of the coefficients. Now, the prover can prove the evaluation by sending all the and verifier verifying the evaluation by computation .

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


Let’s say we have a list of points that we want to prove, . We find a polynomial that goes through these points using Lagrange Interpolation:

For the evaluation proof, while in the single proof we compute , we will replace as single point with , and will be replaced with . Now, we replace our values and becomes

This is possible due to being divisible by all linear factors of and being divisible by whole . The multiproof for evaluation : . Now, our prover equation becomes

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 and . Cryptography really is cool.

      \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$}
      \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]$
        \State exchange $A[i]$ with $A[r]$