Commitment schemes in depth: Pedersen, KZG and IPA

Go beyond the sealed-envelope intuition and understand three concrete commitment schemes used in modern zero-knowledge — Pedersen, KZG and IPA — in terms of exactly what each one binds and hides, its homomorphism, its setup assumption, and the cost it pays at verification; and be able to say precisely which security property rests on which hardness assumption.

Track

Engineering

Module

12 · Applied Zero-Knowledge: commitments, proving systems & on-chain privacy

Prerequisites

Commitments and setup · Hash functions · Public-key cryptography

An earlier lesson introduced commitments as sealed envelopes: hiding stops the recipient reading the value early, binding stops you swapping it later. That intuition is correct but it is not enough to use these primitives safely. The three schemes below — Pedersen, KZG and IPA — are the commitment layer underneath almost every deployed SNARK, and they differ in what they commit to (a number, a vector, or an entire polynomial), in which of hiding and binding is perfect versus computational, in whether they are homomorphic, and above all in their setup: whether a secret trapdoor exists that must be destroyed.

The practical reason to know the difference: a system's trust model and its gas or bandwidth budget are largely decided by this one choice. "We use a polynomial commitment" tells you almost nothing; "we use KZG" tells you there is a trusted setup and that verification is a couple of pairings; "we use IPA" tells you there is no setup secret but verification is logarithmic work. This lesson makes each of those statements precise.

A Pedersen commitment lives in a cyclic group G of prime order q with two generators g and h, where nobody knows the discrete log of h relative to g. To commit to a value v you pick fresh randomness r and publish C = g^v · h^r. To open, you reveal (v, r) and anyone recomputes C.

synthetic — Pedersen commit, open, and why each property holds (illustrative)
Commit(v, r):  C = g^v * h^r        # r sampled fresh and uniformly

Perfectly hiding:
  for ANY target v', there is exactly one r' with C = g^v' * h^r'
  (namely r' solving the equation), so C leaks nothing about v.

Computationally binding:
  opening C to (v1,r1) AND (v2,r2) with v1 != v2 gives
      g^(v1-v2) = h^(r2-r1)   =>   log_g(h) = (v1-v2)/(r2-r1)
  i.e. it computes the discrete log of h — assumed hard.
  So binding holds exactly as long as discrete log is hard.

Pedersen is additively homomorphic: multiplying two commitments commits to the sum of the values. That single property is what lets a confidential-transaction system check that inputs equal outputs without ever seeing the amounts — the verifier multiplies the input commitments and the output commitments and checks they match. A vector Pedersen commitment generalises this to commit to a whole vector (m_1, …, m_n) in one group element using independent generators g_1, …, g_n, h; this is the commitment at the heart of Bulletproofs range proofs.

synthetic — homomorphic balance check without revealing amounts
# inputs: C1 = Commit(100, r1), C2 = Commit(50, r2)
# outputs: C3 = Commit(80, r3), C4 = Commit(70, r4)
#
# verifier checks:  C1 * C2  ==  C3 * C4
#   g^(100+50) * h^(r1+r2) == g^(80+70) * h^(r3+r4)
#   holds iff 150 == 150 AND r1+r2 == r3+r4
# the amounts stay hidden; only the SUM relation is checked.
# (a separate range proof is still needed so no amount is negative)

Pedersen commits to numbers; KZG commits to an entire polynomial. The setup samples a secret field element τ (the trapdoor, the "toxic waste") and publishes the structured reference string SRS = (g, g^τ, g^(τ²), …, g^(τ^d)) in G1 plus a couple of elements in G2. Nobody learns τ; the prover only ever uses the published powers. A commitment to p(x) is C = g^(p(τ)), computed from the SRS by taking the product of (g^(τ^i)) raised to each coefficient a_i.

synthetic — KZG commit and evaluation proof (illustrative, pairing-based)
Setup (TRUSTED): secret tau; publish SRS = (g, g^tau, g^(tau^2), ..., g^(tau^d))
                 then DESTROY tau.  # if tau leaks, the scheme is broken

Commit(p):  C = g^(p(tau))          # one group element, ~48 bytes on BLS12-381

Open "p(z) = y":
  1. quotient q(x) = (p(x) - y) / (x - z)      # exact division iff p(z)=y
  2. proof   pi   = g^(q(tau))                 # one group element

Verify(C, z, y, pi):
  e(C / g^y, h) == e(pi, h^tau / h^z)          # 2 pairings, CONSTANT time

The mechanism rests on a simple algebraic fact: p(z) = y if and only if (x − z) divides p(x) − y exactly, which means a quotient polynomial q(x) exists. The proof is a commitment to that quotient, and the pairing equation checks the divisibility relation at the secret point τ without anyone knowing τ. The payoff is remarkable: the commitment is one group element, the evaluation proof is one group element, and verification is two pairings — all constant size regardless of the polynomial's degree. Batch opening can even prove many evaluations with a single proof. This is why KZG is the commitment under PLONK and under Ethereum's EIP-4844 "blob" data.

An inner-product argument (IPA) proves that two vectors have a claimed inner product ⟨a, b⟩ = c without revealing them. The connection to polynomials is direct: a polynomial p(x) = Σ a_i x^i evaluated at z is exactly the inner product of its coefficient vector a with the public vector b = (1, z, z², …, z^d). So proving p(z) = y is proving an inner product, and IPA gives a polynomial commitment with no trusted setup — the generators are just public, verifiably-random group elements.

synthetic — IPA reduces vector length by half each round (illustrative)
Goal: prove <a, b> = c with public generators G, H, U; commitment
      P = <a,G> + <b,H> + c*U.

Each round (log n rounds total):
  prover sends L, R (cross-terms of the two halves)
  verifier sends a random challenge x
  both FOLD the vectors to half length:
      a' = a_lo + x   * a_hi
      b' = b_lo + x^-1* b_hi
  repeat until length 1.

Final proof: (L_1,R_1, ..., L_log n, R_log n, a, b)
Size: 2*log(n) group elements + 2 scalars  =>  O(log n), NO setup secret

IPA is the commitment scheme of Bulletproofs (range proofs about 600–700 bytes for a 64-bit range, with no trusted setup) and of Halo2, which uses IPA to get recursion without pairings — the path Zcash took in migrating its Orchard pool from Groth16 to Halo2. The trade is explicit: you remove the trapdoor entirely, but verification is linear (or amortised logarithmic with accumulation) rather than KZG's constant two pairings, and proofs are logarithmic rather than constant.

The three schemes are not interchangeable. They bind the same objects (polynomials, once you view a vector as coefficients) but buy completely different trust and cost profiles. This table orders them qualitatively; absolute numbers depend on curve, field and implementation and must be measured.

Read the table as a single sentence: smaller proofs and cheaper verification (KZG) buy a setup trust assumption; removing that assumption (IPA) costs proof size and verifier work. None is post-quantum — all three rest on discrete-log-type hardness; for post-quantum you move to hash-based commitments (FRI, covered with STARKs in the next lesson). The architectural lesson, and the reason modern systems separate the "polynomial IOP" from the "polynomial commitment", is that this choice can be swapped without rewriting the circuit.

For anyone auditing or reasoning about a ZK system, the commitment scheme is a load-bearing assumption you must name explicitly. If a system uses KZG, "the proof is valid" implicitly means "and the setup ceremony was honest"; if it uses IPA or FRI, that clause disappears but a different cost appears. A verifier checks a precise algebraic relation under the commitment's assumption — it does not certify that the assumption holds.

This is the RootRaven evidence model applied one layer down. A valid KZG opening proves the committed polynomial takes a specific value at a specific point, under discrete-log hardness and an honest setup. It does not prove the polynomial encodes the right computation, that the amounts are in range, or that the resulting decision is correct or safe. When you report on a ZK system, state the commitment scheme and the assumption it buys as part of the evidence, not as a footnote.

Expected direction: The balance check only proves inputs and outputs sum to the same field element. Field arithmetic is modular, so an attacker can craft an output amount that is effectively negative (a huge value that wraps mod q) to balance the equation while minting value — the classic missing-range-check inflation bug. The Pedersen commitment is additively homomorphic and perfectly hiding, so it faithfully proves the sum relation and reveals nothing, but it says nothing about each amount lying in a valid range; that requires a separate range proof (e.g. Bulletproofs). On the setup/trust change: moving from KZG to IPA removes the trusted-setup/toxic-waste assumption entirely (no secret τ to destroy, no ceremony to trust), at the cost of larger, logarithmic proofs and heavier (linear or amortised-logarithmic) verification instead of KZG's constant two pairings. Neither scheme is post-quantum.

For a Pedersen commitment, which property is perfect and which is computational, and what breaks the computational one?

Hiding is perfect (for any value there exists randomness producing the same commitment, so it leaks nothing); binding is computational and rests on the hardness of discrete log — being able to open one commitment to two different values would compute log_g(h).

What does a KZG commitment and its evaluation proof cost in size and verification, and what assumption pays for that?

The commitment is one group element and the evaluation proof is one group element (both constant size, ~48 bytes on BLS12-381), verified by two pairings in constant time. It pays for this with a trusted setup: a secret τ that must be destroyed, plus pairing/discrete-log (non-post-quantum) assumptions.

How does an inner-product argument give a polynomial commitment, and what is its headline trade-off versus KZG?

A polynomial evaluated at z is the inner product of its coefficient vector with (1, z, z², …), so IPA proves evaluations by proving that inner product. Versus KZG it removes the trusted setup entirely (transparent, public random generators) but pays with O(log n) proof size and O(n) (amortised O(log n)) verification instead of constant-size proofs and two pairings.

Why is "we use a polynomial commitment" an insufficient statement in an audit?

Because the specific scheme determines the trust model and cost: KZG implies a trusted setup and constant-time pairing verification; IPA/Bulletproofs imply no setup secret but logarithmic proofs and heavier verification; FRI implies hash-based, plausibly post-quantum but larger. A valid opening only proves the committed polynomial's value under that scheme's assumption, not that the assumption holds or that the computation is correct.