Zero-Knowledge & MPC

Two cryptographic capabilities that sound impossible: prove you know X without revealing X, and let multiple people compute on each other's secrets without seeing them. Both are real, both ship in production today, and both are foundational to the next decade of privacy-preserving systems.

The math is heavy; the intuitions are surprisingly clean.

Zero-knowledge proofs (ZKPs)

The setup: a prover wants to convince a verifier that a statement is true, without revealing why. The classic toy example: "I know the password that hashes to H, but I won't tell you the password." A ZKP lets you do exactly that.

A zero-knowledge proof has three properties:

Property	What it means
Completeness	If the statement is true and the prover knows the witness, the verifier accepts.
Soundness	If the statement is false, no prover (even cheating) can convince the verifier — except with negligible probability.
Zero-knowledge	The verifier learns only that the statement is true. They learn nothing about the witness.

The classic intuition is the cave puzzle: Alice claims to know the password to a magic door at the back of a Y-shaped cave. Bob waits at the entrance; Alice goes in. Bob then yells "come back from the left side!" or "come back from the right side!". If Alice doesn't know the password, she's stuck on whichever side she chose; she can only correctly emerge on the demanded side 50% of the time. Repeat 20 times, and her chance of fooling Bob without the password is 2^-20 — vanishingly small. Bob ends up convinced she knows the password without ever hearing it.

That's an interactive ZKP. Modern systems make them non-interactive via the Fiat-Shamir heuristic: the verifier's challenges become hashes of the prover's earlier messages. Now the prover can produce a single proof string that anyone can verify.

zk-SNARKs

zk-SNARKs (Succinct Non-interactive ARguments of Knowledge):

• Succinct — proofs are tiny (~200 bytes) and verification is fast (~ms), regardless of the statement's complexity.
• Non-interactive — single message from prover to verifier.
• Arguments of knowledge — proves the prover knows a witness, not just that one exists.

The cost: a trusted setup ceremony. The proving system needs structured reference parameters that, if leaked, let an attacker forge proofs. To generate them safely, multiple parties contribute randomness in a coordinated ceremony; as long as one honest participant deletes their share ("the toxic waste"), the system is secure.

Where SNARKs ship today:

• Zcash — first major SNARK deployment, 2016. Private transactions on a public ledger.
• Tornado Cash — privacy mixing on Ethereum (sanctioned by OFAC; technically interesting regardless).
• ZK-rollups — zkSync, StarkNet, Aztec, Polygon zkEVM. Aggregate thousands of L2 transactions into one SNARK, post on Ethereum L1, prove correctness with one verifier call.
• Filecoin — uses SNARKs to prove storage providers really have the bytes they claim.

Modern SNARK constructions: Groth16 (smallest proofs, requires per-circuit setup), PLONK (universal setup, slightly larger proofs), Halo2 (no trusted setup at all, larger proofs).

zk-STARKs

zk-STARKs (Scalable Transparent ARguments of Knowledge):

• Scalable — prover work is O(n log² n); verification is O(log² n). Better asymptotics than SNARKs at large input sizes.
• Transparent — no trusted setup. Just public hash functions.
• Post-quantum secure — based on collision-resistant hashing, not pairings or discrete-log. Survives Shor's algorithm.

The cost: proofs are bigger (~100 KB vs SNARKs' 200 bytes), and verification is slower in absolute terms.

Where STARKs ship today:

• StarkNet — L2 on Ethereum, Cairo programming language, native STARK proving.
• Polygon Miden — STARK-based VM with public auditability.
• dYdX v3 (legacy) — used StarkEx for high-throughput trading.

The choice between SNARK and STARK is mostly: how much do proof size and post-quantum security matter for your use case?

Multi-party computation (MPC)

MPC asks a different question: can several parties jointly compute a function of their private inputs, where each party only sees the output, not the others' inputs?

The textbook example is Yao's millionaires problem (1982): Alice and Bob want to know who's richer, without revealing their actual wealth. MPC says yes. They run a protocol that produces a single bit — "Alice richer" or "Bob richer" — without leaking the dollar amounts.

The same machinery scales to arbitrary functions: comparison, addition, lookup tables, even general circuit evaluation. There are several protocol families:

• Yao's garbled circuits — for 2 parties. One party "garbles" the circuit, the other evaluates it on their input via oblivious transfer.
• GMW — extension to n parties via secret sharing.
• BGW — robust against malicious parties (with thresholds).
• SPDZ — the modern preprocessing model. Slow setup, fast online phase. Production-ready.

Each protocol has trade-offs along three axes:

	Pre-processing	Online speed	Threat model
Yao	None	Fast	Semi-honest
GMW	None	Slow (rounds = depth)	Semi-honest
BGW	None	Slow	Malicious
SPDZ	Heavy	Very fast	Malicious

Real-world MPC

• Threshold signing. Bitcoin / Ethereum custody: instead of one private key (single point of failure), split it across n custodians using MPC. Any t-of-n can sign; t-1 reveal nothing. Used by Coinbase Custody, Fireblocks, Unbound (now Coinbase).
• Threshold KMS. AWS KMS supports MPC-style HSM splits internally. Vault has integrations.
• Private set intersection (PSI). Apple, Google, Signal, and many others: "do we have any contacts in common, without revealing my address book?". Apple's PSI was deployed for CSAM detection (rolled back), but the underlying primitive ships in iCloud Shared Albums and similar features.
• Joint analytics. Hospitals, banks, telcos: "what's the average across our combined data without anyone seeing the individual rows?". Estonian tax revenue calculation uses MPC across multiple ministries (Sharemind).
• Signal contact discovery. Originally MPC + SGX; now using a different oblivious-RAM primitive. Goal: tell the user "who in your contacts uses Signal?" without the server learning their full contact list.

ZK + MPC together

The two compose nicely. Combined examples:

• ZK-rollups operate MPC sequencers. The proof is ZK; the off-chain ordering is MPC across multiple operators.
• Threshold signatures + ZK proofs of correct signing. Lets a custody system prove a signature was correctly produced without revealing how many operators participated.
• Verifiable secret sharing. MPC primitive that uses ZK to prove the shares were generated honestly.

What's next

• MLS (Messaging Layer Security) is making group end-to-end encryption practical without per-pair MPC.
• FHE (Fully Homomorphic Encryption) is the next frontier — compute anything on encrypted data without decrypting. Currently 1000-10000× slower than plaintext; in active research.
• Post-quantum ZK — STARKs are already post-quantum. SNARKs based on lattices (Plonky3, ICICLE) are coming.

When to reach for them

• You need to prove a property of secret data publicly. ZKP. (Age verification, KYC-without-PII, balance > 0 in a private wallet.)
• You need to compute on data that no one party can see. MPC. (Joint analytics, threshold signing, private auctions.)
• You're aggregating L2 transactions for an L1 settlement. ZK-rollup.
• Your business model depends on combining sensitive datasets without trusting any single party. MPC.

If you're an applied engineer, you don't need to write SNARK proving systems from scratch. You need to know what they enable so you recognise the right tool when a use case matches. "We can't share the data" doesn't always mean "we can't compute on the data."

A worked intuition: hash-preimage ZKP

Concrete example. You commit to a secret x by publishing H = SHA-256(x). You want to prove later that you know x without revealing it.

In a SNARK system:

1. Express the predicate as a circuit: out = SHA256(in) - target. Output is 0 if in is the preimage of target.
2. Compile to an R1CS / arithmetic circuit.
3. Run the SNARK prover with in = x (private) and target = H (public). Get a proof.
4. Anyone with H and the proof verifies: "yes, the prover knows some x with SHA256(x) = H."

The proof is ~200 bytes. Verification is ~5ms. The prover never reveals x. The verifier never asks for it.

That's the magic. The circuit can be anything — a shuffle, a merkle proof, a balance update, a model inference. Whatever you can express as an arithmetic circuit, you can prove without revealing the inputs. That's the unlock.