FNP Halo2 Zero-Knowledge Circuits

ELI5

A zero-knowledge proof is a mathematical way to prove “I know a secret” without revealing the secret. Imagine you have a treasure map and want to prove you know where the treasure is buried without showing the map — a ZK proof lets you do exactly that. Halo2 is one way to create such proofs using a technology called “circuits.”

Technical Deep Dive

ZK Proof Properties (the Triangle)

A valid ZK proof must have three properties:

1. Completeness: If statement is true, prover can convince verifier

   "I inserted character X at position P"
   If true: Halo2 proof verifies ✓

2. Soundness: If statement is false, no prover can convince verifier

   Attacker claims: "I inserted at position P" (false)
   Halo2 proof fails ✗ (with probability 1 - 2^-256)

3. Zero-Knowledge: Verifier learns nothing about the secret

   Verifier sees: proof + (position, content)
   Verifier learns: operation is valid
   Verifier learns nothing: secret encryption key

FNP’s ZK Circuit

FNP generates Halo2 proofs for insert operations:

Witness (secret):
- Kyber secret key
- Position components [digit, site, counter]
- Content plaintext
- M²-ORE randomness

Public inputs:
- Encrypted position
- Encrypted content
- Halo2 proof

Circuit constraints:
- Kyber decryption is correct
- M²-ORE encryption is deterministic
- Operation signature matches
- Lamport clock is monotonic

Constraint count: ~51,350 constraints per insert operation

Halo2 system:

• Scheme: Polynomial IPA (Inner Product Argument)
• Security: 128-bit
• Proof size: 514-528 bytes
• Verification time: <15ms (on mobile)
• Prover time: ~1 second (mobile), ~50ms (server)

Inner Product Argument (IPA)

Halo2 uses IPA, which achieves logarithmic proof size:

Proof size: O(log N) where N = number of constraints

Traditional ZK (Groth16): O(1) but needs trusted setup
Halo2 (IPA): O(log N) but trustless (no toxic waste)

For 51k constraints: log₂(51k) ≈ 16 components
Proof: 16 curve elements + 1 scalar ≈ 514 bytes

Proof Generation & Verification

Client generates proof (slow, interactive):

1. Sample randomness r ← Z_p
2. Compute commitment COM(r)
3. Receive challenge c from verifier (Fiat-Shamir)
4. Compute response z = r + c·witness
5. Output proof (COM(r), c, z)

Server verifies proof (fast, non-interactive):

1. Receive proof (COM(r), c, z)
2. Check: z·G = COM(r) + c·public_input
3. If check passes: operation is valid
4. If check fails: reject operation

Verification: single pairing check, <15ms

FNP Circuit Example

For an INSERT operation, the circuit proves:

1. Position_encrypted = M²-ORE.Encrypt(position_plaintext)
2. Content_encrypted = Kyber.Encapsulate(content_plaintext)
3. Signature_valid = Dilithium.Verify(operation_bytes, signature)
4. Lamport_clock >= previous_clock (monotonic)
5. (position, content) ≠ previous_operation_ids (no replay)

If all constraints are satisfied, the proof verifies.

Key Terms

• Zero-knowledge → Proof reveals nothing except statement validity
• Completeness, Soundness, ZK → The three properties of valid ZK proofs
• Inner Product Argument (IPA) → Logarithmic-size proof system; no trusted setup
• Constraint → A polynomial equation the witness must satisfy
• Fiat-Shamir → Technique converting interactive proofs to non-interactive (using hash as challenge source)

Q&A

Q: Why not use Groth16 instead of Halo2? A: Groth16 has smaller proofs (128 bytes) but requires a trusted setup (“toxic waste”). Halo2 is trustless (no setup needed) and universal (same proof works for any circuit size). For FNP, trust matters more than proof size.

Q: Can the verifier learn anything from the proof? A: The proof is zero-knowledge: verifier learns only that the statement is valid. Verifier doesn’t learn the plaintext position, encryption keys, or randomness used in proof generation.

Q: How long does proof generation take? A: ~50ms on server, ~1-7 seconds on mobile (depending on device). Client-side proofs are cached (5-min TTL), amortizing cost across users.

Examples

A Halo2 proof is like a bank teller authenticating a check without opening the envelope: teller verifies signature, date, amount on the outside without reading the memo inside. The proof system is similar — verifying operation validity without revealing content.