commitments-in-zk-proofs.ipynb

Kernel: SageMath 10.0

Connect: Commitments as Building Blocks for ZK Proofs

Module 09 | Real-World Connections

Pedersen commitments from this module appear inside every major zero-knowledge proof system. Here is where and how.

Introduction

The Pedersen commitment from 09b, $C = g^m h^r$, looks like a simple cryptographic primitive. Commit to a value, reveal it later. But this humble construction is a universal building block for zero-knowledge proof systems.

It appears in:

Proof System	How Pedersen commitments are used
Bulletproofs	Commit to individual bits for range proofs
Groth16	Commit to witness elements in the proof
KZG (Kate) commitments	Generalize Pedersen to polynomials via pairings
Confidential Transactions	Hide transaction amounts on-chain

In this notebook, we trace the common pattern: commit, challenge, respond, the sigma protocol structure from 09c, scaled up to prove complex statements.

Pedersen Commitments: Quick Review

Let us set up Pedersen parameters and recall the key properties we will need:

• Perfectly hiding: $C$ reveals nothing about $m$ (even to unbounded adversaries)

• Computationally binding: cannot open to two different values (under DLP)

• Homomorphic: $\text{Commit}(m_1, r_1) \cdot \text{Commit}(m_2, r_2) = \text{Commit}(m_1 + m_2, r_1 + r_2)$

# === Pedersen Setup ===

def find_safe_prime(bits=20):
    """Find a safe prime p = 2q + 1 where q is also prime."""
    while True:
        q = random_prime(2^bits, lbound=2^(bits-1))
        p = 2 * q + 1
        if is_prime(p):
            return p, q

p, q = find_safe_prime(20)

def find_generator(p, q):
    """Find a generator of the order-q subgroup of Z_p*."""
    while True:
        h = power_mod(randint(2, p - 2), 2, p)
        if h != 1:
            return h

g = find_generator(p, q)
h = find_generator(p, q)
while h == g:
    h = find_generator(p, q)

def pedersen_commit(m, r, g, h, p):
    return (power_mod(g, m, p) * power_mod(h, r, p)) % p

def pedersen_verify(C, m, r, g, h, p):
    return C == pedersen_commit(m, r, g, h, p)

# Quick test
m_test, r_test = 42, randint(1, q - 1)
C_test = pedersen_commit(m_test, r_test, g, h, p)
print(f"Setup: p={p}, q={q}")
print(f"Generators: g={g}, h={h}")
print(f"Test: Commit({m_test}) = {C_test}, verify = {pedersen_verify(C_test, m_test, r_test, g, h, p)}")

# Demonstrate homomorphic property
m1, r1 = 10, randint(1, q-1)
m2, r2 = 25, randint(1, q-1)
C1 = pedersen_commit(m1, r1, g, h, p)
C2 = pedersen_commit(m2, r2, g, h, p)
C_sum = (C1 * C2) % p
C_direct = pedersen_commit(m1 + m2, (r1 + r2) % q, g, h, p)
print(f"\nHomomorphic: Commit({m1}) * Commit({m2}) = Commit({m1+m2})? {C_sum == C_direct}")

In Bulletproofs: Range Proofs from Bit Commitments

Bulletproofs (Bunz et al., 2018) prove that a committed value lies in a range $[0, 2^n)$ without revealing the value. They are used in Monero and Mimblewimble for confidential transactions.

The core idea:

1. To prove $v \in [0, 2^n)$, decompose $v$ into its $n$ bits: $v = \sum_{i=0}^{n-1} b_i \cdot 2^i$

2. Commit to each bit $b_i$ using a Pedersen commitment

3. Prove each $b_i \in \{0, 1\}$ using a sigma protocol

4. Prove the bit commitments are consistent with the value commitment

The homomorphic property is essential: we can check that the weighted sum of bit commitments equals the value commitment, without opening any of them.

Let's build a simplified version.

# === Simplified Bulletproofs-style Range Proof ===

def range_proof_commit(v, n_bits, g, h, p, q):
    """Commit to each bit of v, plus a commitment to v itself.
    Returns (C_v, bit_commitments, bit_randomness, bits)."""
    bits = [(v >> i) & 1 for i in range(n_bits)]
    
    # Commit to each bit
    bit_randomness = [randint(1, q - 1) for _ in range(n_bits)]
    bit_commitments = [pedersen_commit(bits[i], bit_randomness[i], g, h, p) 
                       for i in range(n_bits)]
    
    # Commitment to v with combined randomness
    r_v = sum(bit_randomness[i] * pow(2, i) for i in range(n_bits)) % q
    C_v = pedersen_commit(v, r_v, g, h, p)
    
    return C_v, bit_commitments, bit_randomness, bits, r_v

# Prove that v = 42 is in [0, 256) (8-bit range)
v = 42
n_bits = 8
C_v, bit_comms, bit_rands, bits, r_v = range_proof_commit(v, n_bits, g, h, p, q)

print(f"Value: v = {v}")
print(f"Binary: {bits} (LSB first)")
print(f"Value commitment: C_v = {C_v}")
print(f"\nBit commitments:")
for i, (b, C_b) in enumerate(zip(bits, bit_comms)):
    print(f"  bit {i}: b_{i} = {b}, C_{i} = {C_b}")

# Verify: product of C_i^(2^i) should equal C_v (homomorphic check)
C_reconstructed = 1
for i in range(n_bits):
    C_reconstructed = (C_reconstructed * power_mod(bit_comms[i], pow(2, i), p)) % p

print(f"\n--- Homomorphic Consistency Check ---")
print(f"Product of C_i^(2^i) = {C_reconstructed}")
print(f"C_v                  = {C_v}")
print(f"Match? {C_reconstructed == C_v}")
print(f"\nThe verifier checks this WITHOUT seeing any bits or randomness!")

# === Proving Each Bit is 0 or 1 (Sigma Protocol) ===
# For each bit commitment C_i = g^b_i * h^r_i, we prove b_i in {0, 1}.
#
# Key insight: b in {0,1} iff b*(b-1) = 0 iff b = b^2.
# Equivalently: C_i commits to 0 OR C_i / g commits to 0.
#
# We use a simplified OR-proof (disjunction of two Schnorr-style proofs).

import hashlib

def prove_bit(b, r, g, h, p, q):
    """Prove that commitment C = g^b * h^r has b in {0, 1}.
    Uses a simplified sigma protocol for OR proofs."""
    C = pedersen_commit(b, r, g, h, p)
    
    if b == 0:
        # Real proof for b=0: C = h^r, prove knowledge of r
        k = randint(1, q - 1)
        R_real = power_mod(h, k, p)
        
        # Simulate proof for b=1: C/g = h^r, simulate
        s_sim = randint(0, q - 1)
        c_sim = randint(0, q - 1)
        C_over_g = (C * power_mod(g, q - 1, p)) % p  # C * g^(-1)
        R_sim = (power_mod(h, s_sim, p) * power_mod(C_over_g, q - c_sim, p)) % p
        
        # Combined challenge
        data = f"{C}:{R_real}:{R_sim}".encode()
        c_total = int(hashlib.sha256(data).hexdigest(), 16) % q
        c_real = (c_total - c_sim) % q
        s_real = (k + c_real * r) % q  # s = k + c*r (prove knowledge of r)
        
        return (C, R_real, R_sim, c_real, c_sim, s_real, s_sim)
    else:
        # Real proof for b=1: C/g = h^r, prove knowledge of r
        C_over_g = (C * power_mod(g, q - 1, p)) % p
        k = randint(1, q - 1)
        R_real = power_mod(h, k, p)
        
        # Simulate proof for b=0: C = h^r, simulate
        s_sim = randint(0, q - 1)
        c_sim = randint(0, q - 1)
        R_sim = (power_mod(h, s_sim, p) * power_mod(C, q - c_sim, p)) % p
        
        # Combined challenge
        data = f"{C}:{R_sim}:{R_real}".encode()
        c_total = int(hashlib.sha256(data).hexdigest(), 16) % q
        c_real = (c_total - c_sim) % q
        s_real = (k + c_real * r) % q
        
        return (C, R_sim, R_real, c_sim, c_real, s_sim, s_real)

def verify_bit_proof(proof, g, h, p, q):
    """Verify that the commitment in the proof has bit value 0 or 1."""
    C, R0, R1, c0, c1, s0, s1 = proof
    C_over_g = (C * power_mod(g, q - 1, p)) % p
    
    # Check both proof branches
    check0 = (power_mod(h, s0, p) == (R0 * power_mod(C, c0, p)) % p)
    check1 = (power_mod(h, s1, p) == (R1 * power_mod(C_over_g, c1, p)) % p)
    
    # Check challenge consistency
    data = f"{C}:{R0}:{R1}".encode()
    c_total = int(hashlib.sha256(data).hexdigest(), 16) % q
    check_c = ((c0 + c1) % q == c_total)
    
    return check0 and check1 and check_c

# Prove each bit of our range proof
print(f"Proving each bit of v = {v} is in {{0, 1}}:")
print("Bit  Value  Proof Valid")for i in range(n_bits):
    proof = prove_bit(bits[i], bit_rands[i], g, h, p, q)
    valid = verify_bit_proof(proof, g, h, p, q)
    print(f"{i}  {bits[i]}  {str(valid)}")

print(f"\nAll bits proven to be 0 or 1, without revealing which is which!")
print(f"Combined with the homomorphic check, this proves v in [0, 2^{n_bits}).")

In Groth16: Committing to the Witness

Groth16 (2016) is the most widely deployed SNARK, used in Zcash and many other systems. The prover proves knowledge of a witness $w$ satisfying a circuit, without revealing $w$.

At a high level, the proof contains commitments to witness elements that are structured like Pedersen commitments but use elliptic curve pairings instead of discrete-log groups:

$$A = \alpha G_1 + \sum_i a_i \cdot U_i$$

where $a_i$ are witness elements and $U_i$ are public curve points from the trusted setup.

The key structural parallel:

• Pedersen: $C = g^m \cdot h^r$, commit with one generator per value

• Groth16: $A = \sum a_i U_i$, commit with one curve point per witness element

Both achieve hiding (the commitment reveals nothing about the inputs) and both are verified using algebraic checks rather than opening.

Polynomial Commitments: From Values to Polynomials

KZG commitments (Kate, Zaverucha, Goldberg, 2010) generalize Pedersen commitments from single values to entire polynomials.

A Pedersen commitment commits to a scalar $m$: $C = g^m h^r$.

A KZG commitment commits to a polynomial $f(x) = a_0 + a_1 x + \ldots + a_d x^d$:

$$C = a_0 G + a_1 [\tau] G + a_2 [\tau^2] G + \ldots + a_d [\tau^d] G$$

where $[\tau^i] G$ are points from a trusted setup (nobody knows $\tau$).

This is a vector Pedersen commitment to the coefficient vector $(a_0, a_1, \ldots, a_d)$, with generators $G, [\tau]G, [\tau^2]G, \ldots$ KZG adds the ability to prove evaluations: "I committed to $f$, and $f(z) = y$" with a short proof.

KZG is the core commitment scheme in PLONK, Marlin, and Ethereum's EIP-4844 (proto-danksharding).

Let's demonstrate the analogy with a toy vector commitment.

# === Polynomial Commitment as Vector Pedersen ===
# We commit to a polynomial f(x) = a0 + a1*x + a2*x^2 by committing
# to its coefficient vector [a0, a1, a2] using vector Pedersen.

# Generate independent generators (analogous to [tau^i]*G in KZG)
degree = 3
generators = []
seen = set()
while len(generators) < degree + 1:
    candidate = power_mod(randint(2, p - 2), 2, p)
    if candidate != 1 and power_mod(candidate, q, p) == 1 and candidate not in seen:
        generators.append(candidate)
        seen.add(candidate)

h_blind = find_generator(p, q)  # blinding generator

# Polynomial: f(x) = 3 + 5x + 2x^2 + 7x^3
coeffs = [3, 5, 2, 7]
R_poly = ZZ['x']
x_var = R_poly.gen()
f = sum(c * x_var^i for i, c in enumerate(coeffs))

print(f"Polynomial: f(x) = {f}")
print(f"Coefficients: {coeffs}")
print(f"Generators (analogous to [tau^i]*G): {generators}")
print()

# Commit to the coefficient vector
r_poly = randint(1, q - 1)
C_poly = power_mod(h_blind, r_poly, p)
for i, (c_i, g_i) in enumerate(zip(coeffs, generators)):
    C_poly = (C_poly * power_mod(g_i, c_i, p)) % p

print(f"Polynomial commitment: C = {C_poly}")
print(f"\nThis single group element commits to the ENTIRE polynomial.")

# Evaluate the polynomial at a point
z = 4
f_z = sum(c * z^i for i, c in enumerate(coeffs)) % q
print(f"\nf({z}) = {f_z}")
print(f"Verify: 3 + 5*{z} + 2*{z}^2 + 7*{z}^3 = {3 + 5*z + 2*z^2 + 7*z^3}")
print(f"\nIn KZG, the prover can produce a short proof that f({z}) = {f_z}")
print(f"without revealing any of the coefficients. This is the power")
print(f"of polynomial commitments, and the foundation of modern SNARKs.")

The Common Pattern: Commit, Challenge, Respond

Look at the structure of every proof system we have discussed:

Phase	Schnorr (09d)	Bulletproofs	Groth16	PLONK/KZG
Commit	$R = g^k$	Bit commitments	$A, B, C$ (witness commitments)	Polynomial commitments
Challenge	Random $c$	Fiat-Shamir hash	Fiat-Shamir hash	Fiat-Shamir hash
Respond	$s = k + cx$	Inner-product argument	Pairing check values	Evaluation proofs

The sigma protocol from 09c is the DNA of all these systems. What changes is the complexity of the statement being proved, but the three-phase structure remains the same.

And at the commitment layer, Pedersen's construction (or its generalizations) provides the hiding and homomorphic properties that make the proofs zero-knowledge and composable.

# === The Commit-Challenge-Respond Pattern in Action ===
# Let's demonstrate how multiple Pedersen commitments compose with
# sigma protocols to prove a more complex statement.
#
# Statement: "I know m1 and m2 such that C1 = Commit(m1) and
#             C2 = Commit(m2) and m1 + m2 = target."
#
# This is a simplified version of what happens in confidential
# transactions: prove inputs equal outputs without revealing amounts.

import hashlib

# Prover's secret values
m1_secret = 30
m2_secret = 70
target = 100  # public: the sum we claim
assert m1_secret + m2_secret == target

r1_secret = randint(1, q - 1)
r2_secret = randint(1, q - 1)

C1 = pedersen_commit(m1_secret, r1_secret, g, h, p)
C2 = pedersen_commit(m2_secret, r2_secret, g, h, p)

print(f"Public information:")
print(f"  C1 = {C1}")
print(f"  C2 = {C2}")
print(f"  Claimed sum: {target}")
print(f"  (m1 and m2 are SECRET)")

# Step 1: Verifier checks the homomorphic sum
# C1 * C2 should equal Commit(target, r1 + r2)
C_product = (C1 * C2) % p
C_target = pedersen_commit(target, (r1_secret + r2_secret) % q, g, h, p)

print(f"\n--- Homomorphic Sum Check ---")
print(f"  C1 * C2 = {C_product}")
print(f"  Commit({target}, r1+r2) = {C_target}")
print(f"  Match? {C_product == C_target}")

# Step 2: To make this zero-knowledge, the prover also proves knowledge
# of the opening of C1*C2 / g^target = h^(r1+r2), a standard Schnorr proof
# of knowledge of the discrete log of (C1*C2/g^target) base h.

excess = (C_product * power_mod(g, q - target % q, p)) % p  # C1*C2 / g^target
r_combined = (r1_secret + r2_secret) % q

# Schnorr proof of knowledge of r_combined
k_proof = randint(1, q - 1)
R_proof = power_mod(h, k_proof, p)
challenge_data = f"{excess}:{R_proof}".encode()
c_proof = int(hashlib.sha256(challenge_data).hexdigest(), 16) % q
s_proof = (k_proof + c_proof * r_combined) % q

# Verify: h^s == R * excess^c
lhs_verify = power_mod(h, s_proof, p)
rhs_verify = (R_proof * power_mod(excess, c_proof, p)) % p

print(f"\n--- Zero-Knowledge Proof of Sum ---")
print(f"  Excess value: C1*C2 / g^{target} = {excess}")
print(f"  This should be h^(r1+r2) = {power_mod(h, r_combined, p)}")
print(f"  Schnorr proof: R={R_proof}, c={c_proof}, s={s_proof}")
print(f"  h^s = {lhs_verify}")
print(f"  R * excess^c = {rhs_verify}")
print(f"  Valid? {lhs_verify == rhs_verify}")
print(f"\nThe verifier is convinced that m1 + m2 = {target}")
print(f"without learning m1 = {m1_secret} or m2 = {m2_secret}.")

Concept Map

Module 09 Concept	Role in ZK Proof Systems
Pedersen commitment $g^m h^r$	Commit to witness values (inputs to the proof)
Homomorphic property	Compose and check commitments without opening
Sigma protocol (commit-challenge-respond)	Structure of every interactive/non-interactive proof
Fiat-Shamir transform	Make proofs non-interactive via hashing
Perfect hiding	Privacy guarantee: proof reveals nothing about witness
Computational binding	Soundness guarantee: prover cannot cheat
Vector Pedersen commitment	Commit to multiple values at once (Bulletproofs inner product)
Pedersen on polynomials	KZG polynomial commitments (SNARKs, PLONK, danksharding)

Summary

Concept	Key idea
Bulletproofs	Decompose a committed value into bits, commit to each with Pedersen, and prove each bit is 0 or 1 using OR-proofs
Groth16	Uses Pedersen-like commitments on elliptic curves to hide witness elements inside proof elements $A, B, C$
KZG polynomial commitments	Generalize vector Pedersen commitments to encode entire polynomials, enabling evaluation proofs for PLONK, Marlin, and danksharding
Confidential transactions	The homomorphic property lets verifiers confirm that inputs equal outputs without revealing any amounts
Common pattern	Commit, challenge, respond. The sigma protocol structure from Module 09 scales from scalars to vectors to polynomials

The common thread is the sigma protocol structure from Module 09: commit, challenge, respond. What scales up is the complexity of the committed objects (from scalars to vectors to polynomials) and the sophistication of the response (from a single linear equation to inner-product arguments to pairing checks). But the core pattern, and the core commitment scheme, remain the same.

---

Back to Module 09: Commitment Schemes and Sigma Protocols