Zero-Knowledge Proofs

Statement: "I control one of the addresses in set S"
Proof: ZK proof that prover knows private key for some address in S
Revealed: Nothing about which specific address

Statement: "This message was signed by a member of group G"
Proof: ZK proof of valid signature from some member
Revealed: The message is authentic, but not who sent it

Statement: "This message was sent between T1 and T2"
Proof: ZK proof that timestamp falls within range
Revealed: Time range, but not exact timestamp

Statement: "I am a member of group G"
Proof: ZK proof of membership credential
Revealed: Membership is valid, but not which member

┌─────────────────────────────────────────────────────────┐
│ ZK Circuit Structure                                     │
├─────────────────────────────────────────────────────────┤
│                                                         │
│  ┌──────────────┐    ┌──────────────┐                  │
│  │ Private      │    │ Public       │                  │
│  │ Inputs       │    │ Inputs       │                  │
│  │              │    │              │                  │
│  │ - Secret key │    │ - Merkle root│                  │
│  │ - Leaf data  │    │ - Message    │                  │
│  │ - Path       │    │ - Nullifier  │                  │
│  └──────┬───────┘    └──────┬───────┘                  │
│         │                   │                          │
│         └─────────┬─────────┘                          │
│                   ▼                                    │
│         ┌─────────────────┐                            │
│         │ Constraint      │                            │
│         │ System          │                            │
│         │                 │                            │
│         │ R1CS Equations  │                            │
│         └────────┬────────┘                            │
│                  ▼                                     │
│         ┌─────────────────┐                            │
│         │ Proof Output    │                            │
│         │ (zk-SNARK)      │                            │
│         └─────────────────┘                            │
│                                                         │
└─────────────────────────────────────────────────────────┘

Merkle Tree Structure:

              Root (public)
             /            \
          H01              H23
         /    \          /    \
       H0      H1      H2      H3
       │       │       │       │
     Leaf0   Leaf1   Leaf2   Leaf3
     (member)(member)(member)(member)

Leaf = Hash(identity_commitment)
identity_commitment = Hash(secret || nullifier)

FUNCTION generate_membership_proof(
    secret: bytes32,
    nullifier_seed: bytes32,
    merkle_path: bytes32[],
    path_indices: bits[],
    message: bytes,
    context: bytes
):
    // Step 1: Compute identity commitment
    identity_commitment = Poseidon_Hash(secret, nullifier_seed)

    // Step 2: Compute nullifier (prevents double-use)
    nullifier = Poseidon_Hash(nullifier_seed, context)

    // Step 3: Compute Merkle root from path
    current = identity_commitment
    FOR i IN 0..merkle_path.length:
        IF path_indices[i] == 0:
            current = Poseidon_Hash(current, merkle_path[i])
        ELSE:
            current = Poseidon_Hash(merkle_path[i], current)
    computed_root = current

    // Step 4: Sign message with secret
    message_hash = Poseidon_Hash(message)
    signature_commitment = Poseidon_Hash(secret, message_hash)

    // Step 5: Generate SNARK proof
    public_inputs = {
        merkle_root: computed_root,
        nullifier: nullifier,
        message_hash: message_hash,
        signature_commitment: signature_commitment
    }

    private_inputs = {
        secret: secret,
        nullifier_seed: nullifier_seed,
        merkle_path: merkle_path,
        path_indices: path_indices
    }

    proof = Groth16_Prove(
        circuit = membership_circuit,
        public_inputs = public_inputs,
        private_inputs = private_inputs,
        proving_key = pk
    )

    RETURN {
        proof: proof,
        public_inputs: public_inputs
    }

FUNCTION generate_identity_proof(
    private_key: bytes32,
    public_key_set: bytes32[],  // Set of valid public keys
    statement: bytes
):
    // Step 1: Compute own public key
    own_public_key = EdDSA_PublicKey(private_key)

    // Step 2: Find index in set (private)
    index = find_index(own_public_key, public_key_set)

    // Step 3: Build set commitment
    set_root = build_merkle_root(public_key_set)

    // Step 4: Compute signature on statement
    signature = EdDSA_Sign(private_key, statement)

    // Step 5: Generate proof
    proof = Groth16_Prove(
        circuit = identity_circuit,
        public_inputs = {
            set_root: set_root,
            statement_hash: Hash(statement)
        },
        private_inputs = {
            private_key: private_key,
            public_key: own_public_key,
            merkle_path: get_merkle_path(index),
            signature: signature
        }
    )

    RETURN proof

FUNCTION verify_membership_proof(
    proof: SnarkProof,
    merkle_root: bytes32,
    nullifier: bytes32,
    message_hash: bytes32,
    signature_commitment: bytes32
):
    // Step 1: Validate proof format
    IF NOT valid_proof_format(proof):
        RETURN FALSE

    // Step 2: Check nullifier not used
    IF nullifier IN used_nullifiers:
        RETURN FALSE  // Replay attack detected

    // Step 3: Verify Merkle root is current
    IF merkle_root NOT IN valid_roots:
        RETURN FALSE  // Outdated or invalid root

    // Step 4: Verify SNARK proof
    public_inputs = [merkle_root, nullifier, message_hash, signature_commitment]

    is_valid = Groth16_Verify(
        verification_key = vk,
        proof = proof,
        public_inputs = public_inputs
    )

    // Step 5: Mark nullifier as used
    IF is_valid:
        used_nullifiers.add(nullifier)

    RETURN is_valid

FUNCTION batch_verify_proofs(proofs: SnarkProof[], inputs: PublicInputs[]):
    // Combine proofs for batch verification
    // ~40% faster than individual verification

    combined_check = 1  // Identity in pairing group

    FOR i IN 0..proofs.length:
        random_scalar = secure_random()  // For soundness
        combined_check *= pairing_check(proofs[i], inputs[i]) ^ random_scalar

    RETURN combined_check == 1

┌─────────────────────────────────────────────────────────┐
│ ZK Proof Wire Format                                     │
├─────────────────────────────────────────────────────────┤
│ Field              │ Size      │ Description            │
├─────────────────────────────────────────────────────────┤
│ version            │ 1 byte    │ Proof format version   │
│ proof_type         │ 1 byte    │ 0x01=membership        │
│                    │           │ 0x02=identity          │
│                    │           │ 0x03=range             │
├─────────────────────────────────────────────────────────┤
│ proof_a            │ 64 bytes  │ G1 point (compressed)  │
│ proof_b            │ 128 bytes │ G2 point (compressed)  │
│ proof_c            │ 64 bytes  │ G1 point (compressed)  │
├─────────────────────────────────────────────────────────┤
│ public_input_count │ 1 byte    │ Number of public inputs│
│ public_inputs      │ variable  │ 32 bytes per input     │
├─────────────────────────────────────────────────────────┤
│ Total (4 inputs)   │ 386 bytes │                        │
└─────────────────────────────────────────────────────────┘

FUNCTION encode_proof(proof: SnarkProof, public_inputs: bytes32[]):
    buffer = ByteBuffer()

    // Header
    buffer.write_u8(0x01)                    // version
    buffer.write_u8(proof.type)              // proof type

    // Proof elements (compressed points)
    buffer.write_bytes(compress_g1(proof.a)) // 64 bytes
    buffer.write_bytes(compress_g2(proof.b)) // 128 bytes
    buffer.write_bytes(compress_g1(proof.c)) // 64 bytes

    // Public inputs
    buffer.write_u8(public_inputs.length)
    FOR input IN public_inputs:
        buffer.write_bytes(input)            // 32 bytes each

    RETURN buffer.to_bytes()

┌─────────────────────────────────────────────────────────┐
│ Message with ZK Proof                                    │
├─────────────────────────────────────────────────────────┤
│ message_header     │ Standard message header            │
│ encrypted_content  │ AES-256-GCM encrypted payload      │
│ zk_proof_present   │ 1 byte (0x01 if proof attached)    │
│ zk_proof           │ Proof bytes (if present)           │
│ auth_tag           │ 16 bytes GCM tag                   │
└─────────────────────────────────────────────────────────┘

Trusted Setup Process:

Participant 1        Participant 2        Participant N
     │                    │                    │
     ▼                    ▼                    ▼
Generate τ₁          Generate τ₂          Generate τₙ
     │                    │                    │
     ▼                    ▼                    ▼
Compute               Compute               Compute
CRS₁ = f(τ₁)         CRS₂ = f(τ₂,CRS₁)    CRSₙ = f(τₙ,CRSₙ₋₁)
     │                    │                    │
     ▼                    ▼                    ▼
Delete τ₁            Delete τ₂            Delete τₙ
     │                    │                    │
     └────────────────────┴────────────────────┘
                          │
                          ▼
                   Final CRS (pk, vk)

Security: If ANY participant deletes their τ, the setup is secure.

nullifier = Hash(nullifier_seed, context)

Where context includes:
- Group ID (for group-specific proofs)
- Time epoch (for time-bounded proofs)
- Action type (for action-specific proofs)

Root Validity Policy:

current_root → Always valid
previous_root → Valid for 1 hour (transition period)
older_roots → Invalid (forces re-proof with current root)

Standard Message Flow (authenticated sender):
  Sender → [E2EE Message + Signature] → Recipient

Anonymous Message Flow (ZK authenticated):
  Sender → [E2EE Message + ZK Proof] → Recipient

The E2EE layer remains identical. Only the authentication method differs.

1. Group Setup:
   - Create Merkle tree of member commitments
   - Distribute root to all members

2. Sending Anonymous Message:
   - Generate membership proof
   - Encrypt message with Sender Keys
   - Attach proof to encrypted message

3. Receiving:
   - Verify ZK proof (confirms sender is member)
   - Decrypt with Sender Key
   - Display message (sender unknown but verified)

Circuit Request with ZK Auth:
  ┌─────────────────────────────────────────┐
  │ "I am a valid network participant"      │
  │ + ZK Proof of stake/membership          │
  │ (No identity revealed)                  │
  └─────────────────────────────────────────┘

Curve Parameters:
  p = 21888242871839275222246405745257275088696311157297823662689037894645226208583
  r = 21888242871839275222246405745257275088548364400416034343698204186575808495617

Embedding degree: 12
Security: ~100-bit (sufficient for current applications)