Zero-Knowledge Proofs (ZKP) cho phép chứng minh rằng mình biết một thông tin mà không tiết lộ chính thông tin đó.

Zero-Knowledge Proofs (ZKP) allow proving knowledge of information without revealing the information itself.

// What is a ZKP?

  • Completeness — honest prover always convinces verifier
  • Soundness — cheating prover cannot convince verifier
  • Zero-knowledge — verifier learns nothing beyond validity

Hình thức: cho relation $R$, prover chứng minh $\exists w: (x, w) \in R$ mà không tiết lộ $w$.

Formally: given relation $R$, the prover demonstrates $\exists w: (x, w) \in R$ without revealing $w$.

// Schnorr Protocol

Chứng minh biết $x$ sao cho $h = g^x \bmod p$:

Proves knowledge of $x$ such that $h = g^x \bmod p$:

  1. Commit: Prover: $v \xleftarrow{R} \mathbb{Z}_q$, send $r = g^v \bmod p$
  2. Challenge: Verifier: $c \xleftarrow{R} \mathbb{Z}_q$
  3. Response: Prover: $s = v - cx \bmod q$
  4. Verify: $g^s \cdot h^c \equiv r \pmod{p}$

$$\text{Verify: } g^s \cdot h^c = g^{v-cx} \cdot g^{cx} = g^v = r \quad \checkmark$$

use rand::Rng;
use num_bigint::BigUint;

struct SchnorrProof {
    commitment: BigUint,
    response: BigUint,
}

struct SchnorrParams {
    p: BigUint, q: BigUint, g: BigUint,
}

impl SchnorrParams {
    fn prove(&self, x: &BigUint, challenge: &BigUint) -> SchnorrProof {
        let mut rng = rand::thread_rng();
        let v = rng.gen_biguint_below(&self.q);
        let commitment = self.g.modpow(&v, &self.p);
        let response = (&v + &self.q - (challenge * x) % &self.q) % &self.q;
        SchnorrProof { commitment, response }
    }

    fn verify(&self, h: &BigUint, proof: &SchnorrProof, c: &BigUint) -> bool {
        let lhs = (self.g.modpow(&proof.response, &self.p)
            * h.modpow(c, &self.p)) % &self.p;
        lhs == proof.commitment
    }
}
rust

// Fiat-Shamir Heuristic

Biến interactive proof thành non-interactive bằng hash:

Transforms interactive proof into non-interactive via hash:

$$c = H(g \| h \| r)$$

use sha2::{Sha256, Digest};

fn fiat_shamir_challenge(
    g: &BigUint, h: &BigUint, commitment: &BigUint,
) -> BigUint {
    let mut hasher = Sha256::new();
    hasher.update(g.to_bytes_be());
    hasher.update(h.to_bytes_be());
    hasher.update(commitment.to_bytes_be());
    BigUint::from_bytes_be(&hasher.finalize())
}
rust

// Soundness

$$\Pr[\text{cheat}] \leq \frac{1}{q^k}$$

// Applications

  • zk-SNARKs — Zcash, Ethereum
  • zk-STARKs — Transparent, no trusted setup
  • zk-Rollups — zkSync, StarkNet, Polygon zkEVM
  • Privacy — Selective disclosure, anonymous credentials