ZK Verification Specification

This document specifies the zero-knowledge proof system used by the Markovian Protocol to prove correct Markov state transitions without revealing input or output state vectors. Any third party can verify a proof using this specification without access to SigmaSynth infrastructure.

1. Overview

Each block in the Markovian Protocol contains a proof that the miner applied the canonical governance matrix M exactly N times to a starting state vector derived from the previous block hash. The proof is zero-knowledge: it demonstrates the computation was performed correctly without revealing the state vectors themselves.

The proof system uses BN128 Pedersen vector commitments with Schnorr sigma proofs under the Fiat-Shamir non-interactive transform.

2. Cryptographic Primitives

2.1 Elliptic Curve

2.2 Secondary Generator H

H is derived deterministically from a protocol seed with no trusted setup:

seed  = SHA256("Markovian-H-generator-v1")
H     = seed_int mod curve_order * G1

where seed_int is the SHA256 output interpreted as a big-endian integer.

2.3 Pedersen Commitments

A commitment to integer value v with blinding factor r:

C = r·G + v·H

Computationally binding under the discrete logarithm assumption. Perfectly hiding.

2.4 Fiat-Shamir Hash

e = SHA256(str(D_x) || "||" || str(D_y) || "||" || str(R_x) || "||" || str(R_y) || "||" || context) mod r

3. State Vector Encoding

State vectors are elements of the probability simplex: s[0] + s[1] + s[2] = 1, s[i] ≥ 0. Each component is scaled: s_int[i] = round(s[i] × SCALE_S).

4. Governance Matrix (m_version=1)

The canonical transition matrix M. Entry M[i][j] is the probability of transitioning from state i to state j:

M = [[0.70, 0.25, 0.05],   # from Accumulation
     [0.10, 0.75, 0.15],   # from Markup
     [0.20, 0.15, 0.65]]   # from Distribution

M.T × 20 = M_INT:
M_INT = [[14, 2,  4],
         [ 5, 15, 3],
         [ 1,  3, 13]]

The Markov computation uses M.T (transpose): s_next = M.T @ s_current.

5. Per-Step Proof

For each Markov step from s_in to s_out, the prover generates a StepProof containing:

• C_in[0..2] — Pedersen commitments to s_in components
• C_out[0..2] — Pedersen commitments to s_out components
• epsilons[0..2] — integer rounding corrections, |ε[j]| ≤ 50
• proofs[0..2] — Schnorr discrete-log proofs

5.1 Proof Construction (per output component j)

D[j] = M_DENOM·C_out[j] - Σ_k M_INT[j,k]·C_in[k] - ε[j]·H

By the homomorphic property of Pedersen commitments, D[j] = δ_r[j]·G where:

δ_r[j] = M_DENOM·r_out[j] - Σ_k M_INT[j,k]·r_in[k]

The prover then generates a Schnorr proof of knowledge of δ_r[j]:

k ← random
R = k·G
e = H(D, R, context)      # Fiat-Shamir
s = k - e·δ_r[j] mod r
proof = {R, s, e}

Context string: b"mkv|v{m_version}|N={n_steps}|i={step_index}|step|j={j}|eps={epsilon}"

5.2 Verification (per output component j)

1. Check |ε[j]| ≤ TOLERANCE
2. Reconstruct D[j]:
   D[j] = M_DENOM·C_out[j] - Σ_k M_INT[j,k]·C_in[k] - ε[j]·H
3. Verify Schnorr:
   lhs = s·G + e·D[j]
   check lhs == R
4. Re-derive challenge:
   e_check = H(D[j], R, context)
   check e_check == e

6. Full N-Step Proof

A MarkovProof contains N StepProof records. Valid iff:

1. len(steps) == n_steps
2. Each step verifies independently (Section 5.2)
3. Chain continuity: steps[i].C_out == steps[i+1].C_in for all i < N-1

7. Proof Serialization (JSON)

{
  "type":      "markov_schnorr_v1",
  "m_version": 1,
  "n_steps":   2,
  "C_input":   [[x0,y0],[x1,y1],[x2,y2]],
  "C_output":  [[x0,y0],[x1,y1],[x2,y2]],
  "steps": [
    {
      "C_in":     [[x,y],[x,y],[x,y]],
      "C_out":    [[x,y],[x,y],[x,y]],
      "epsilons": [e0, e1, e2],
      "proofs": [
        {"R": [x,y], "s": int, "e": int},
        {"R": [x,y], "s": int, "e": int},
        {"R": [x,y], "s": int, "e": int}
      ]
    }
  ]
}

EC points are serialized as [x_int, y_int] where x and y are BN128 field elements as Python integers. Scalars are Python integers mod curve_order.

8. Test Vectors

9. Standalone Verifier

A self-contained Python verifier implementing this specification:

pip install py_ecc numpy
python3 mkv_verify.py proof.json
python3 mkv_verify.py --test

10. Live Verifier

Synthesis run proofs can be verified interactively at api.quantsynth.net/verify.

Archive Merkle root verification: api.quantsynth.net/archive/verify