Introduction to Polynomial Commitments — Kimchi Series #2

5 min readJust now

At the core of blockchain networks lies cryptographic structures designed not for privacy, but for facilitating verifiability.

You can use the most powerful hardware to speed up the network, but if you can’t achieve fast verification, problems are inevitable.

With polynomial commitments, we can significantly accelerate verification processes. At the same time, we can achieve privacy, which isn’t inherently part of the blockchain’s design.

This is the second part of our content series diving deep into Mina’s Kimchi Proof system. You can find the first part of the series linked in the tweet below.

1. What are the Polynomial Commitments?

From the transactions you make to the signatures used in blockchains, everything is a commitment.

A 32-byte hash function output (e.g., SHA256, Keccak256) is written to the network, signed, and verified.

All addresses and the balances we hold on the blockchain are stored as commitments in the form of a 32-byte Merkle root as part of the post-state rule.

Polynomial commitments allow us to reduce the size of data written to the blockchain, speed up its verification, and thereby increase throughput.

Polynomial Commitments also find use in zkSNARKs, which is particularly crucial for Mina. Beyond Mina, Ethereum also utilizes KZG Commitments, a type of polynomial commitment in its sharding design.

Polynomial commitments come with two key features:

Binding:
It ensures that the sent data remains unchanged and can be proven in its committed form.
Hiding:
It ensures that the full content of the sent data is inaccessible to any individual or user, with the secret known only to the sender.

2. Merkle Tree

Merkle trees are a familiar type of commitment. Data is structured in a tree, aggregated in a single hash output that simplifies verifying the existence of specific data in the tree.

In this case, the commitment is the Merkle Root, representing the summary value at the top of the tree.

Transactions at the tree’s leaves are hashed to reduce their size. This way, proving a transaction’s validity or existence does not require downloading all transactions but instead relies on smaller hash outputs.

For instance, to verify the 8th transaction without a Merkle tree, one would need to download all 8 transactions (which could represent a large dataset), hash them, and rebuild the entire tree.

With a Merkle tree, however, a client possessing the 8th transaction only needs to download 4 hash outputs (assuming SHA256 is used, this equates to 4 x 32 = 128 bytes of data).

This approach saves storage, computation, and bandwidth.

The table and explanations below outline the time complexity of operations on a Merkle tree for developers seeking to optimize transaction speed and verification:

Space Complexity: How much memory the Merkle Tree needs as the input grows. “n” represents one input.
Search Complexity: How quickly you can find a particular element in the Merkle Tree. “n” represents one element.
Traversal Complexity: How quickly you can visit all elements in the Merkle Tree. “n” represents one element.
Insert Complexity: How quickly a new element can be added to the Merkle Tree. “n” represents one element.
Delete Complexity: How quickly an element can be removed from the Merkle Tree. “n” represents one element.

If you’re interested in blockchain and want to make the concept of time complexity more concrete, check out my content:

3. Elliptic Curve

Think of an elliptic curve as a special type of “smoothly curved” shape on a grid that has useful algebraic properties. These properties make it ideal for cryptography because:

Security with smaller keys: Elliptic curve cryptography (ECC) achieves strong security with fewer bits than older methods (like RSA).
Mathematically hard problems: The way you “add” or combine points on the curve (elliptic curve point arithmetic) ends up being a very difficult problem to invert, which underpins its security.

Mina uses the “Pasta Curves”.

The two curves pallas and vesta (pa(llas ve)sta) created by the Zcash team. Each curve’s scalar field is the other curve’s base field, which is practical for recursion.

Elliptic curves allow us to turn the “hard problem” of reversing point arithmetic on the curve into a secure cryptographic foundation.

Ethereum uses the elliptic curve called secp256k1, which is also used by Bitcoin. It’s well-established and widely implemented.

4. Polynomial Commitments

A polynomial commitment is a cryptographic way to promise (“commit to”) a polynomial p(x), imagine a black-box function, so that later you can:

-> Prove the value of that polynomial at some input “x” (e.g. prove p(5)=10).
-> No one can change what the polynomial was after the fact, yet you don’t have to reveal the entire polynomial.

This is important for scaling and privacy. Polynomial commitments are used in zero-knowledge proofs to show that large computations have been done correctly without revealing every step. Moreover, you can prove correctness without exposing private data.

4.1 Kate Commitments (KZG Commitments) vs. Bulletproof-Style Commitments

a) Kate Commitments (KZG)

KZG commitments use special “pairing-friendly” elliptic curves. The setup involves a structured randomness ceremony (a one-time, trusted process) to generate parameters. Once set up, anyone can create polynomial commitments and short proofs of correctness.

Ethereum uses KZG Commitments in its Danksharding design.

Kate Commitments offers extremely short proofs and very fast verification

b) Bulletproof-Style Commitments
Bulletproofs are based on more general elliptic curve assumptions (no special pairings). They can be used to create zero-knowledge proofs for various statements, including proving things about polynomials.

Mina overcomes the trusted setup limitation of PLONK by using a bulletproof-style polynomial commitment inside of the Kimchi Proof Protocol.

It is believed that zkSNARKs should be built with a trusted setup. But with Mina, we see that zkSNARKs do not always require a trusted setup.

Now that we understand the logic of Polynomial Commitments, we will get into the math.

In the next content, by using the same example we will learn how both KZG commitments and Bullet Proof work.

Thanks for reading..:)

X : blockofchain