Zero-Knowledge Proofs in Python — Deep Dive

Schnorr identification protocol from scratch

The Schnorr protocol is the simplest interactive zero-knowledge proof: proving you know a discrete logarithm (a secret key) without revealing it.

from py_ecc.bn128 import G1, multiply, add, eq, curve_order
import secrets
import hashlib

def schnorr_prove(secret_key: int) -> tuple:
    """Prover generates a non-interactive Schnorr proof (Fiat-Shamir)."""
    # Public key: P = secret_key * G
    public_key = multiply(G1, secret_key)

    # Step 1: Choose random nonce k, compute commitment R = k * G
    k = secrets.randbelow(curve_order)
    R = multiply(G1, k)

    # Step 2: Fiat-Shamir — hash commitment and public key to get challenge
    challenge_input = str(R) + str(public_key)
    e = int(hashlib.sha256(challenge_input.encode()).hexdigest(), 16) % curve_order

    # Step 3: Compute response s = k - e * secret_key (mod order)
    s = (k - e * secret_key) % curve_order

    return (R, s, public_key)

def schnorr_verify(proof: tuple) -> bool:
    """Verifier checks the proof without learning the secret key."""
    R, s, public_key = proof

    # Recompute challenge
    challenge_input = str(R) + str(public_key)
    e = int(hashlib.sha256(challenge_input.encode()).hexdigest(), 16) % curve_order

    # Verify: s * G + e * P should equal R
    left = add(multiply(G1, s), multiply(public_key, e))
    return eq(left, R)

# Usage
secret = secrets.randbelow(curve_order)
proof = schnorr_prove(secret)
assert schnorr_verify(proof)  # True — prover knows the secret
print("Proof verified without revealing the secret key")

The verifier learns that the prover knows secret_key such that public_key = secret_key * G, but the values R and s are computationally indistinguishable from random — revealing nothing about the secret.

Building a Sigma protocol for equality of discrete logs

Proving you know a single value x that satisfies two relations simultaneously — for instance, that the same secret key was used with two different generators:

def prove_dlog_equality(x: int, G, H):
    """Prove knowledge of x such that P = x*G AND Q = x*H."""
    P = multiply(G, x)
    Q = multiply(H, x)

    # Random nonce
    k = secrets.randbelow(curve_order)
    R1 = multiply(G, k)
    R2 = multiply(H, k)

    # Fiat-Shamir challenge
    challenge_input = str(R1) + str(R2) + str(P) + str(Q)
    e = int(hashlib.sha256(challenge_input.encode()).hexdigest(), 16) % curve_order

    s = (k - e * x) % curve_order
    return (R1, R2, s, P, Q)

def verify_dlog_equality(proof, G, H) -> bool:
    R1, R2, s, P, Q = proof

    challenge_input = str(R1) + str(R2) + str(P) + str(Q)
    e = int(hashlib.sha256(challenge_input.encode()).hexdigest(), 16) % curve_order

    # Check: s*G + e*P == R1 AND s*H + e*Q == R2
    check1 = eq(add(multiply(G, s), multiply(P, e)), R1)
    check2 = eq(add(multiply(H, s), multiply(Q, e)), R2)
    return check1 and check2

This pattern is foundational for anonymous credentials — proving that the same identity was used across two systems without revealing the identity.

Pedersen commitments — hiding values while binding them

A Pedersen commitment lets you commit to a value without revealing it, and later prove properties about the committed value:

class PedersenCommitment:
    """Commit to values with information-theoretic hiding."""

    def __init__(self):
        # H is a second generator with unknown discrete log relation to G
        self.G = G1
        self.H = multiply(G1, int(hashlib.sha256(b"nothing up my sleeve").hexdigest(), 16) % curve_order)

    def commit(self, value: int) -> tuple:
        """Create commitment C = value*G + blinding*H."""
        blinding = secrets.randbelow(curve_order)
        C = add(multiply(self.G, value), multiply(self.H, blinding))
        return C, blinding

    def verify_opening(self, C, value: int, blinding: int) -> bool:
        """Verify a commitment opening."""
        expected = add(multiply(self.G, value), multiply(self.H, blinding))
        return eq(C, expected)

    def prove_sum(self, commitments, values, blindings, expected_sum):
        """Prove that committed values sum to expected_sum without revealing individual values."""
        total_blinding = sum(blindings) % curve_order
        # The sum of commitments equals commitment to the sum
        C_sum = commitments[0]
        for c in commitments[1:]:
            C_sum = add(C_sum, c)
        # Verify against commitment to expected_sum with combined blinding
        C_expected = add(multiply(self.G, expected_sum), multiply(self.H, total_blinding))
        return eq(C_sum, C_expected)

Pedersen commitments are additively homomorphic: the sum of commitments equals the commitment to the sum. This enables proving arithmetic properties of hidden values.

Range proofs — proving a value lies in [0, 2^n)

Range proofs are crucial for financial applications: proving a transaction amount is positive without revealing the amount.

def simple_range_proof(value: int, bits: int = 32):
    """
    Simplified bit-decomposition range proof.
    Proves value is in [0, 2^bits) by committing to each bit.
    Real implementations use Bulletproofs for logarithmic proof size.
    """
    assert 0 <= value < 2**bits, "Value out of range"

    pc = PedersenCommitment()
    bit_commitments = []
    bit_blindings = []

    for i in range(bits):
        bit = (value >> i) & 1
        C, r = pc.commit(bit)
        bit_commitments.append(C)
        bit_blindings.append(r)

    # Prove each commitment is to 0 or 1 (via OR proof)
    # Prove the weighted sum equals the committed value
    # (Full implementation requires Bulletproofs for efficiency)

    return {
        "bit_commitments": bit_commitments,
        "bits": bits,
        # In practice: include proofs that each bit is 0 or 1
        # and that 2^0 * b0 + 2^1 * b1 + ... = value
    }

Bulletproofs compress this into a logarithmic-size proof. A 64-bit range proof using Bulletproofs is only ~700 bytes, versus ~2 KB for naive bit decomposition. The bulletproofs Python package or Rust FFI bindings provide production implementations.

Circuit-based SNARKs with circom integration

For complex statements, define them as arithmetic circuits in circom and generate proofs from Python:

// circuit.circom — prove knowledge of preimage
pragma circom 2.0.0;

include "circomlib/circuits/poseidon.circom";

template PreimageProof() {
    signal input preimage;    // Private
    signal input hash;        // Public

    component hasher = Poseidon(1);
    hasher.inputs[0] <== preimage;
    hash === hasher.out;
}

component main {public [hash]} = PreimageProof();

import subprocess
import json

def compile_and_prove(preimage: int, expected_hash: int):
    """Compile circom circuit and generate proof via snarkjs."""
    # Write input
    input_data = {"preimage": str(preimage), "hash": str(expected_hash)}
    with open("input.json", "w") as f:
        json.dump(input_data, f)

    # Compile circuit
    subprocess.run(["circom", "circuit.circom", "--r1cs", "--wasm", "--sym"], check=True)

    # Generate witness
    subprocess.run([
        "node", "circuit_js/generate_witness.js",
        "circuit_js/circuit.wasm", "input.json", "witness.wtns"
    ], check=True)

    # Generate proof (Groth16)
    subprocess.run(["snarkjs", "groth16", "prove",
                     "circuit_final.zkey", "witness.wtns",
                     "proof.json", "public.json"], check=True)

    # Verify
    result = subprocess.run(["snarkjs", "groth16", "verify",
                              "verification_key.json", "public.json", "proof.json"],
                             capture_output=True, text=True)
    return "OK" in result.stdout

def verify_proof_onchain(proof_path: str, public_path: str):
    """Load proof for on-chain verification."""
    with open(proof_path) as f:
        proof = json.load(f)
    with open(public_path) as f:
        public_signals = json.load(f)
    return proof, public_signals

Performance comparison across ZKP systems

System	Proof size	Prove time (10K gates)	Verify time	Trusted setup
Groth16 (SNARK)	192 bytes	~2 seconds	~5 ms	Yes (per-circuit)
PLONK (SNARK)	~400 bytes	~4 seconds	~8 ms	Yes (universal)
STARK	~50 KB	~5 seconds	~50 ms	No
Bulletproofs	~700 bytes	~10 seconds	~1 second	No

Circuit size matters enormously. SHA-256 requires ~25,000 gates. Poseidon hash (designed for ZKPs) requires ~250 gates. Choosing ZKP-friendly primitives dramatically reduces proving time.

Practical application: anonymous credential verification

Combining the above primitives to build a real-world system — proving you’re over 18 without revealing your birthdate:

class AgeVerificationSystem:
    """ZKP-based age verification without revealing birthdate."""

    def __init__(self):
        self.pc = PedersenCommitment()

    def issue_credential(self, birthdate_timestamp: int):
        """Issuer creates committed credential."""
        commitment, blinding = self.pc.commit(birthdate_timestamp)
        # Issuer signs the commitment (using BLS or ECDSA)
        return {"commitment": commitment, "blinding": blinding}

    def prove_over_18(self, birthdate_timestamp: int, blinding: int,
                      current_timestamp: int, min_age_seconds: int):
        """Prove age >= 18 without revealing birthdate."""
        age_seconds = current_timestamp - birthdate_timestamp

        # Prove: committed_value <= current_timestamp - min_age_seconds
        threshold = current_timestamp - min_age_seconds

        # This is a range proof on (threshold - birthdate)
        # which must be non-negative for age >= 18
        difference = threshold - birthdate_timestamp
        assert difference >= 0, "Under age!"

        # Generate range proof that difference is in [0, 2^40)
        range_proof = simple_range_proof(difference, bits=40)

        return {
            "range_proof": range_proof,
            "threshold_commitment": self.pc.commit(threshold),
            # Plus proof linking this to the original credential commitment
        }

Debugging ZKP circuits

The most common errors when developing ZKP applications:

Constraint not satisfied. Your witness (private input) doesn’t satisfy the circuit equations. Log intermediate values during witness generation.

Under-constrained circuit. The circuit accepts inputs it shouldn’t. Use tools like circom --inspect to find unconstrained signals.

Overflow in finite field. All ZKP arithmetic happens modulo a large prime. Negative numbers wrap around. If your circuit computes 5 - 10, the result isn’t -5 but prime - 5.

def debug_circuit_witness(input_data: dict, circuit_wasm: str):
    """Generate witness with debug output."""
    import json
    with open("debug_input.json", "w") as f:
        json.dump(input_data, f)

    result = subprocess.run([
        "node", "-e", f"""
        const wc = require('./{circuit_wasm}');
        const input = require('./debug_input.json');
        wc.then(w => w.calculateWitness(input, true))  // sanityCheck=true
          .then(w => console.log('Witness:', w.slice(0, 10).map(String)))
          .catch(e => console.error('Constraint failed:', e.message));
        """
    ], capture_output=True, text=True)
    print(result.stdout or result.stderr)

The one thing to remember: Practical ZKP development in Python involves choosing between Sigma protocols (simple proofs of knowledge), Bulletproofs (range proofs without trusted setup), and SNARK/STARK systems (arbitrary computation) — with circom/snarkjs integration providing the most mature path for complex circuit-based proofs.