Privacy And Zero-Knowledge

Why Privacy Needs Its Own Week

In week 6 you studied identity: how a person or a device can show who they are without a central registry. Identity raises a new question right away. If every claim must be shown in full, then a person who proves they are an adult must also show their birth date, their name, and their address. Public ledgers make this sharper, because anything written on a public chain can be read by everyone, forever.

Privacy in decentralized systems means that each participant controls what others learn about them. Three things are worth keeping apart. Confidentiality hides the content of data. Anonymity hides who performed an action. Unlinkability hides the fact that two actions came from the same person. A system can offer one without the others, so a good designer names which one the application needs.

This week introduces the main tool for this job: the zero-knowledge proof. It lets a prover convince a verifier that a statement is true, while the verifier learns nothing beyond the fact that the statement holds.

What A Zero-Knowledge Proof Proves

A proof system has two roles. The prover knows a secret, called the witness. The verifier knows a public statement, such as 'this person is over 18' or 'this number is the hash of something I know'. The prover sends a short message, and the verifier checks it and answers accept or reject.

A zero-knowledge proof has three properties. Completeness: if the statement is true and both sides follow the rules, the verifier accepts. Soundness: if the statement is false, a cheating prover is rejected, except with a tiny probability. Zero-knowledge: the verifier learns nothing about the witness beyond the truth of the statement.

Notice what the proof gives you. It proves a statement about a secret, not the secret itself. The statement can be simple, such as 'I know the password behind this hash', or large, such as 'this batch of one thousand payments was computed correctly'. In the second case the proof also compresses work, because the verifier checks a small proof instead of redoing the whole computation.

• Prover: holds the secret and builds the proof.
• Verifier: holds the public statement and checks the proof.
• Witness: the secret input that makes the statement true.
• Statement: the public claim being proven.

The Cave Analogy

A classic story makes the idea concrete. Picture a ring-shaped cave with an entrance on one side and a magic door at the far end of the ring, which opens only for someone who knows a secret word. The paths on the left and right both lead to the door. Peggy, the prover, claims she knows the word. Victor, the verifier, wants proof but does not want to learn the word.

Peggy walks in and picks the left or right path while Victor waits outside, unable to see which one she chose. Victor then walks to the entrance and shouts which side he wants her to come out from. If Peggy knows the word, she can open the door and always come out of the requested side. If she does not, she can only succeed when Victor happens to name the side she already took, which happens half the time.

Repeat the round twenty times. A cheater survives every round with probability one in about a million. Victor becomes convinced, yet he never heard the word and saw nothing that he could replay to a third person. The story shows the shape of every interactive proof: a commitment (the path chosen), a challenge (the side shouted), and a response (coming out correctly).

Chance A Cheater Survives The Cave

percent

A prover who does not know the secret guesses the side with probability one half each round. Source: Cave protocol of Quisquater et al., 1989

Commitments: Sealing A Value Now, Opening It Later

Most proof systems start from a commitment. A commitment is a sealed envelope. You put a value inside, seal it, and hand the envelope to someone. Later you can open it, and nobody can accuse you of changing the value in between.

A good commitment is hiding and binding. Hiding means the envelope reveals nothing about the value. Binding means the committer cannot open the envelope to a different value later. A simple construction uses a hash function from week 2: publish hash(value plus a random salt). The salt is a long random string that stops guessing, because without it anyone could hash every possible vote and compare.

Commitments appear everywhere in decentralized systems. Sealed-bid auctions, commit and reveal voting, and the leaves of the Merkle trees you met in earlier weeks all use the same idea. A Merkle root is a commitment to a whole list, and a short path of hashes can later prove that one item belongs to that list.

SNARKs And STARKs At Intro Level

The cave story needs many back and forth rounds. Modern systems remove the conversation, so a prover publishes one proof that anyone can check at any time. These are called non-interactive proofs. The two best known families carry names worth learning.

A SNARK is a Succinct Non-interactive ARgument of Knowledge. Succinct means the proof is tiny and fast to check, often a few hundred bytes. Many SNARKs need a trusted setup, a one-time ceremony that produces public parameters. If the secret leftovers of that ceremony were kept, someone could forge proofs, so ceremonies involve many independent participants and only one honest participant is needed.

A STARK is a Scalable Transparent ARgument of Knowledge. Transparent means no trusted setup; it relies on hash functions and public randomness. STARK proofs are larger than SNARK proofs, but the approach is considered resistant to attacks by future quantum computers, since it relies on hashes rather than on elliptic curve math. Neither family is better in every case. Teams choose by proof size, verification cost, setup assumptions, and tooling.

To use either family, a developer writes the statement as a circuit: a list of arithmetic constraints. Languages and toolkits such as Circom or Noir help with this step, and a proving library then turns a witness into a proof.

SNARKs And STARKs At A Glance

	SNARK	STARK
Proof size	Very small	Larger
Trusted setup	Often needed	Not needed
Built on	Elliptic curve math	Hash functions
Quantum outlook	Weaker	Believed stronger

General tendencies. Individual systems vary, so check each design. Source: Course synthesis; Ben-Sasson et al. on STARKs

Private Voting With MACI

Voting shows why privacy and verification must work together. On a public chain, votes are visible, so voters can be pressured, and a buyer can check that a bribed voter complied. MACI, which stands for Minimum Anti-Collusion Infrastructure, is a design that removes the buyer's ability to check.

The flow at a conceptual level has four parts. Voters sign up with a key. Each voter encrypts a message containing their vote and publishes it on chain. A trusted coordinator decrypts all messages off chain, counts them, and publishes the tally together with a zero-knowledge proof that the count follows the rules. The contract verifies the proof, so the coordinator cannot invent results.

The key trick is that a voter can later publish a new message that changes their key and overrides earlier votes. A briber cannot tell whether the vote they paid for is the final one, because nobody except the coordinator can see which message was valid. A bribe loses its value. The coordinator learns the votes, so MACI trusts them for privacy, though not for correctness, since the proof covers correctness. You will meet MACI again in weeks 8 and 9 when voting mechanisms come up.

MACI Vote Flow

1. Voter signs and encrypts a vote
2. Messages go on chain
3. Coordinator decrypts and tallies
4. Coordinator posts a zero knowledge proof
5. Contract verifies the proof

The proof shows the tally is right without revealing who voted for what.

Honest Limits And Design Questions

Zero-knowledge tools are powerful and still young. Circuits are hard to write correctly, and a bug in a circuit can accept false statements while looking perfect from the outside. Audits, formal checks, and simple designs reduce this risk. Proving can also be expensive in time and memory, though it keeps improving.

Metadata is a second limit. A perfect proof does not help if your network address, timing, or transaction fees reveal who you are. Privacy needs care at every layer, from the application down to the network.

Finally, privacy has a social side. Communities need ways to handle abuse, legal duties, and accountability. Many designs offer selective disclosure: a user keeps data private by default and can reveal a specific fact to a specific party when needed. When you design an application, begin with the question 'what is the smallest fact the verifier needs?' and prove only that.

• Prove the narrow fact, not the whole record.
• Decide which kind of privacy you need: confidentiality, anonymity, or unlinkability.
• Plan for audits of any circuit you depend on.

Key Terms

Zero-knowledge proof

A method for proving a statement is true while revealing nothing else about the secret behind it.

Prover

The party who holds the secret and produces the proof.

Verifier

The party who checks a proof against a public statement.

Witness

The secret input that makes a statement true.

Commitment

A sealed value that hides its content and binds the sender to it.

SNARK

A succinct non-interactive proof that is small and fast to verify, often needing a trusted setup.

STARK

A transparent, scalable proof that avoids trusted setup and relies on hash functions.

Trusted setup

A one-time ceremony that creates public parameters for some proof systems.

MACI

Minimum Anti-Collusion Infrastructure, a voting design where a coordinator tallies encrypted votes and proves the count.

Exercise: Build And Test A Hash Commitment

1. Open a terminal and start Python 3. Import hashlib and secrets.
2. Write a function commit(value) that makes a random 16 byte salt, hashes salt plus value with SHA-256, and returns the hex digest and the salt.
3. Write a function verify(digest, value, salt) that recomputes the hash and compares it.
4. Commit to the word 'yes', publish only the digest, then open it with verify and confirm it returns True.
5. Try to open the same digest with the value 'no' and confirm verification fails. This shows the binding property.
6. Remove the salt, hash 'yes' and 'no' yourself, and compare both to the digest. Write two sentences on why the salt is needed for hiding.

Further Reading

• How to Explain Zero-Knowledge Protocols to Your Children, Jean-Jacques Quisquater and others, 1989 (the cave story)
• Zero Knowledge Proofs: An illustrated primer, Matthew Green, blog A Few Thoughts on Cryptographic Engineering
• Minimal Anti-Collusion Infrastructure, Vitalik Buterin, ethresear.ch, 2019
• Privacy and Scaling Explorations documentation, Ethereum Foundation, pse.dev
• Zero Knowledge Proofs MOOC, Dan Boneh, Shafi Goldwasser, Dawn Song, Justin Thaler, Yupeng Zhang, zk-learning.org