Proving System

The ZKVAULT proving system implements a highly optimized zk-SNARK protocol based on the Groth16 construction. This document provides deep technical details on witness generation, constraint synthesis, polynomial commitments, and proof generation.

Witness Generation

Witness generation is the process of computing all circuit wire values that satisfy the constraint system.

Circuit Representation

ZKVAULT circuits are represented as Rank-1 Constraint Systems (R1CS):

A · witness ⊙ B · witness = C · witness

Where:
• A, B, C are matrices of field elements
• witness = [1, public_inputs..., private_inputs..., intermediate_values...]
• ⊙ denotes element-wise multiplication
• All operations in finite field Fₚ (p = BN254 scalar field order)

Witness Computation Algorithm

function computeWitness(circuit, inputs):
  // Initialize witness vector
  witness[0] = 1  // Constant one
  
  // Assign public inputs
  for i in public_inputs:
    witness[i] = inputs.public[i]
  
  // Assign private inputs
  for i in private_inputs:
    witness[i] = inputs.private[i]
  
  // Compute intermediate wires in topological order
  for gate in circuit.gates:
    if gate.type == "mul":
      witness[gate.output] = witness[gate.a] * witness[gate.b] mod p
    elif gate.type == "add":
      witness[gate.output] = witness[gate.a] + witness[gate.b] mod p
    elif gate.type == "constant":
      witness[gate.output] = gate.value
  
  // Verify all constraints satisfied
  for constraint in circuit.constraints:
    a = dot(constraint.A, witness)
    b = dot(constraint.B, witness)
    c = dot(constraint.C, witness)
    assert (a * b) mod p == c mod p
  
  return witness

Constraint Synthesis

Constraint synthesis transforms high-level circuit operations into R1CS constraints.

Example: Range Proof Circuit

Proving that a value x is in range [0, 2ⁿ):

// High-level constraint: 0 ≤ x < 2⁸
function rangeCheck8Bit(x):
  // Decompose x into bits
  let bits = [b₀, b₁, ..., b₇]
  
  // Constraint 1: Each bit is boolean
  for i in 0..7:
    bits[i] * (1 - bits[i]) = 0
  
  // Constraint 2: Bits reconstruct x
  x = Σ(bits[i] * 2^i)
  
  // This generates 9 R1CS constraints total

R1CS Constraint Matrix

For the above circuit:

Witness = [1, x, b₀, b₁, b₂, b₃, b₄, b₅, b₆, b₇]

Constraints (boolean checks):
• b₀ * (1 - b₀) = 0  →  A₀ · w ⊙ B₀ · w = C₀ · w
• b₁ * (1 - b₁) = 0
...
• b₇ * (1 - b₇) = 0

Constraints (reconstruction):
• x = b₀ + 2b₁ + 4b₂ + ... + 128b₇

Polynomial Commitment Scheme

ZKVAULT uses Kate-Zaverucha-Goldberg (KZG) polynomial commitments over BN254 elliptic curve.

Trusted Setup

The proving system requires a trusted setup ceremony to generate proving and verification keys:

Powers of Tau ceremony generates:
• τ (secret, destroyed after ceremony)
• [τ⁰G₁, τ¹G₁, τ²G₁, ..., τⁿG₁]  (proving key, G₁ points)
• [τ⁰G₂, τ¹G₂, τ²G₂, ..., τⁿG₂]  (verification key, G₂ points)

Where:
• G₁, G₂ are generators of BN254 curve groups
• τ is sampled uniformly at random
• n = max circuit degree

Polynomial Commitment

// Commit to polynomial p(x) = Σ aᵢxⁱ
function commit(p, setup):
  return Σ aᵢ · [τⁱ]G₁  // Elliptic curve multiexponentiation
  
// Verify commitment opens to value y at point z
function verify(commitment, z, y, proof):
  // Check e(proof, [τ]G₂ - [z]G₂) = e(commitment - [y]G₁, G₂)
  return pairing(proof, [τ-z]G₂) == pairing([p(τ)-y]G₁, G₂)

Pairing Strategy

Groth16 verification relies on bilinear pairings over BN254 curve:

Pairing function: e: G₁ × G₂ → Gₜ

Properties:
• Bilinearity: e(aP, bQ) = e(P, Q)^(ab)
• Non-degeneracy: e(G₁, G₂) ≠ 1
• Computability: Efficient ate pairing algorithm

Verification equation:
e(A, B) = e(α, β) · e(C, δ) · e(Σ public_inputs[i] · γⁱ, γ)

Transcript Construction

The Fiat-Shamir heuristic transforms interactive proofs into non-interactive ones:

// Transcript manages challenge generation
struct Transcript:
  state: Hash  // Running hash state (BLAKE2b)
  
  function append(label, data):
    self.state = BLAKE2b(self.state || label || data)
  
  function challenge(label):
    self.append(label, "challenge")
    return self.state mod p  // Map to field element

// Prover generates challenges deterministically
transcript = Transcript()
transcript.append("domain", circuit_hash)
transcript.append("public_inputs", public_inputs)
transcript.append("commitment_A", A)
challenge_r = transcript.challenge("r")
challenge_s = transcript.challenge("s")

Fiat-Shamir Transform

Converting interactive protocol to non-interactive:

Interactive Protocol:
1. Prover → Verifier: Send commitment
2. Verifier → Prover: Send random challenge
3. Prover → Verifier: Send response
4. Verifier: Check response

Non-Interactive (Fiat-Shamir):
1. Prover: Compute commitment
2. Prover: Derive challenge = Hash(commitment, public_inputs)
3. Prover: Compute response using challenge
4. Prover: Send (commitment, response) to Verifier
5. Verifier: Recompute challenge, check response

Recursive SNARKs

ZKVAULT supports proof recursion for aggregation:

// Verifier circuit: Proves "I verified a valid proof"
circuit VerifierCircuit:
  public inputs:
    - proof_commitment
    - public_inputs_hash
  
  private inputs:
    - proof (π₁)
    - public_inputs
  
  constraints:
    - verify_groth16(proof, public_inputs) == true
    - hash(public_inputs) == public_inputs_hash
    - commit(proof) == proof_commitment

// Generate proof of proof verification
π₂ = Prove(VerifierCircuit, {proof: π₁, ...})

// π₂ now proves "π₁ is valid" in constant size

Example: Proof Generation Pseudocode

function generateProof(circuit, inputs, provingKey):
  // 1. Compute witness
  witness = computeWitness(circuit, inputs)
  
  // 2. Compute A, B, C commitments
  A = multiexp(provingKey.A_points, witness)
  B_G1 = multiexp(provingKey.B_G1_points, witness)
  B_G2 = multiexp(provingKey.B_G2_points, witness)
  C = multiexp(provingKey.C_points, witness)
  
  // 3. Add randomness for zero-knowledge
  r, s = random_field_elements()
  A = A + r * provingKey.delta
  B_G1 = B_G1 + s * provingKey.delta
  C = C + r*s * provingKey.delta
  
  // 4. Compute H polynomial (constraint satisfaction proof)
  H = computeH(circuit, witness)
  H_commitment = multiexp(provingKey.H_points, H)
  
  // 5. Assemble proof
  proof = {
    A: A,           // G₁ point (32 bytes)
    B: B_G2,        // G₂ point (64 bytes)  
    C: C + H_commitment  // G₁ point (32 bytes)
  }
  
  return proof  // Total: 128 bytes (compressed)

For details on how proofs are compressed before on-chain submission, see Compression Pipeline.