At the technical heart of verifiable computation, decentralized rollups, and zero-knowledge arguments lies the Commitment Scheme: the digital analogue of placing a secret message inside a locked safe, handing the safe to a verifier, and subsequently revealing the key. In modern proof systems, scalar commitments have evolved into Polynomial Commitment Schemes (PCS), enabling a prover to commit to an entire algebraic polynomial (P(X)) of degree (d) using a single 48-byte group element and prove arbitrary evaluations (P(z) = y) with constant-size proofs.
1. Formal Definition: Hiding & Binding Properties
A commitment scheme consists of three algorithms (( ext{Setup}, ext{Commit}, ext{Open})). To be cryptographically sound, it must satisfy two conflicting guarantees:
- Hiding (Secrecy): The commitment (C = ext{Commit}(m; r)) reveals zero information about message (m). In perfect hiding, distributions ( ext{Commit}(m_0)) and ( ext{Commit}(m_1)) are statistically identical. In computational hiding, distinguishing them requires super-polynomial time.
- Binding (Integrity): The committer cannot open (C) to any alternate message (m’
eq m). In strict binding, it is computationally impossible to output ((m, r)) and ((m’, r’)) such that ( ext{Commit}(m; r) = ext{Commit}(m’; r’)).
By information theory, a commitment scheme can be statistically hiding and computationally binding, or computationally hiding and strictly binding, but never both simultaneously.
2. The Pedersen Commitment Scheme
In 1991, Torben Pedersen introduced an algebraically elegant commitment over an elliptic curve group (G) of prime order (q) with generators (g, h in G) whose discrete log relation (log_g h) is unknown. To commit to secret (m in mathbb{Z}_q), the committer samples uniform blinding factor (r leftarrow mathbb{Z}_q):
[
C = [m]g + [r]h in G
]
Pedersen commitments possess remarkable mathematical properties:
- Perfect Hiding: For any message (m), as (r) varies uniformly over (mathbb{Z}_q), the group element (C) takes every value in (G) with equal probability (1/q). An adversary with infinite computational power learns nothing about (m).
- Computational Binding: If an adversary could produce ((m, r)) and ((m’, r’)) with (m
eq m’) such that ([m]g + [r]h = [m’]g + [r’]h), then ([m – m’]g = [r’ – r]h). Inverting gives (log_g h = (m – m’)(r’ – r)^{-1} pmod q), directly breaking the Discrete Logarithm Problem. - Additive Homomorphism: The sum of commitments commits to the sum of messages:
[
C_1 + C_2 = ([m_1]g + [r_1]h) + ([m_2]g + [r_2]h) = [m_1 + m_2]g + [r_1 + r_2]h
]
This linearity is the engine powering confidential transactions in privacy cryptocurrencies (e.g., Monero, Mimblewimble).
3. Polynomial Commitments: The KZG (Kate-Zaverucha-Goldberg) Scheme
While Pedersen commits to single scalars, modern zk-SNARKs require committing to vectors of thousands of coefficients represented as polynomials (P(X) in mathbb{F}_p[X]) of degree (d). In 2010, Kate, Zaverucha, and Goldberg introduced KZG using bilinear pairings:
- Trusted Setup: Sample secret toxic waste ( au leftarrow mathbb{F}_p^*) and compute Structured Reference String (SRS):
[
ext{SRS} = Big( {[ au^i]_1}_{i=0}^d, [ au]_2 Big) = Big( g_1, [ au]g_1, [ au^2]g_1, dots, [ au^d]g_1, g_2, [ au]g_2 Big)
]
The secret scalar ( au) is subsequently permanently destroyed. - Commitment: For polynomial (P(X) = sum_{i=0}^d c_i X^i), the commitment (C in G_1) is computed via multi-scalar multiplication (MSM) without knowing ( au):
[
C = [P( au)]_1 = sum_{i=0}^d c_i [ au^i]_1 in G_1
] - Evaluation Proof (Opening): The prover claims (P(z) = y). By the polynomial remainder theorem, (P(X) – y) has a root at (X = z), meaning it is divisible by ((X – z)):
[
Q(X) = rac{P(X) – y}{X – z}
]
The prover computes evaluation proof (pi = [Q( au)]_1 in G_1). - Verification: The verifier checks whether (P( au) – y = Q( au)( au – z)) using a single bilinear pairing:
[
eleft( C – [y]_1, g_2
ight) stackrel{?}{=} eleft( pi, [ au]_2 – [z]_2
ight)
]
Crucially, both the commitment (C) and proof (pi) consist of exactly one single (G_1) group element (48 bytes on BLS12-381), and verification executes in constant (mathcal{O}(1)) time with two pairings, regardless of whether (P(X)) has degree 10 or 10,000,000.
