Exercises: Zero-Knowledge Proofs

Section A: Conceptual Understanding

Exercise 37.1 — The Ali Baba Cave with Multiple Doors

Extend the Ali Baba cave analogy. Instead of a single magic door, the cave now has three branching tunnels that meet at a central chamber with two doors (one between tunnel A and tunnel B, another between tunnel B and tunnel C). Peggy claims she knows the password for both doors. Design a verification protocol. How many rounds does Victor need to achieve a confidence level of at least 99.99%? Show your probability calculation.

Exercise 37.2 — Identifying the Three Properties

For each of the following scenarios, identify which of the three ZK properties (completeness, soundness, zero-knowledge) is violated, and explain why.

(a) A proof system where a prover who knows the correct answer is only accepted 70% of the time.

(b) A proof system where the verifier can determine the prover's secret from the proof transcript with probability 1/1000.

(c) A proof system where a dishonest prover can convince the verifier of a false statement 40% of the time after 20 rounds.

(d) A proof system where every true statement is provable, every false statement is rejected, but the verifier can reconstruct the witness by analyzing 100 proof transcripts.

Exercise 37.3 — Simulating Zero-Knowledge

The formal definition of zero-knowledge requires the existence of a simulator that produces transcripts indistinguishable from real ones. Explain in your own words why the existence of such a simulator guarantees privacy. Then explain why Victor cannot use a real proof transcript to convince his friend Carol that Peggy knows the password.

Exercise 37.4 — Interactive vs. Non-Interactive

A blockchain network has 10,000 validator nodes. Explain why an interactive ZK proof is impractical in this setting, and how the Fiat-Shamir heuristic solves the problem. What role does the hash function play in replacing the verifier? What assumption about the hash function is required for security?

Section B: Technical Analysis

Exercise 37.5 — Arithmetic Circuit Construction

Construct an arithmetic circuit (using addition and multiplication gates) for the following computation:

Given private inputs x, y, z and public output r, prove that x^2 + y * z = r.

Draw the circuit as a directed acyclic graph (DAG) with labeled gates. How many multiplication gates does your circuit contain? (Remember: each multiplication gate corresponds to one R1CS constraint.)

Exercise 37.6 — R1CS Constraint System

Using the arithmetic circuit from Exercise 37.5, write out the R1CS constraints. Define the solution vector s = (1, x, y, z, r, w1, w2, ...) where w_i are intermediate wire values. Express each constraint in the form (A_i . s) * (B_i . s) = (C_i . s).

Hint: You will need intermediate variables for x^2 and y * z.

Exercise 37.7 — Why Polynomials Enable Succinctness

The chapter states that if two polynomials of degree d agree at more than d points, they must be identical. This is known as the Schwartz-Zippel lemma (in a simplified form).

(a) Explain intuitively why this property allows checking polynomial equality by evaluating at a single random point.

(b) A QAP encodes 1 million R1CS constraints into polynomials of degree approximately 1 million. A random evaluation point is chosen from a field of size approximately 2^256. What is the probability that the polynomial check passes for an invalid witness? Express this as a fraction and then as a decimal.

(c) Why is this probability considered "negligible" in cryptographic terms?

Exercise 37.8 — Trusted Setup Analysis

The Zcash "Powers of Tau" trusted setup ceremony involved 87 participants in its first phase.

(a) What is the security assumption about these participants? How many need to be honest for the setup to be secure?

(b) If an adversary controlled 86 of the 87 participants, could they forge proofs? Why or why not?

(c) PLONK uses a "universal and updateable" setup. Explain what "universal" and "updateable" mean in this context and why these properties are significant improvements over Groth16's circuit-specific setup.

Section C: Comparative Analysis

Exercise 37.9 — SNARKs vs. STARKs Decision Matrix

You are the CTO of a blockchain startup choosing between zk-SNARKs and zk-STARKs for your project. For each of the following scenarios, recommend one system and justify your choice using specific technical properties.

(a) A financial compliance platform that must remain secure for 30+ years and will be audited by government regulators who require full transparency of the cryptographic setup.

(b) A high-frequency trading rollup on Ethereum where on-chain verification gas costs are the primary concern and computations are relatively small.

(c) A privacy-preserving voting system for a national election where public trust is essential and no party should need to be trusted.

(d) A gaming rollup that processes millions of simple state transitions per day and needs the fastest possible proving time.

Exercise 37.10 — ZK-EVM Type Classification

A new ZK-rollup project makes the following claims: - "Any Solidity smart contract can be deployed on our rollup without modification." - "We compile Solidity to our custom VM bytecode, not to EVM bytecode." - "Gas costs for some operations differ from Ethereum mainnet."

Using Vitalik Buterin's ZK-EVM taxonomy (Types 1-4), classify this project. Explain your reasoning and identify the tradeoffs inherent in this design choice.

Section D: Application Design

Exercise 37.11 — ZK Identity System Design

Design a ZK-based age verification system for an online platform. Your system should allow users to prove they are over 18 without revealing their date of birth, name, or any other personal information.

Address the following in your design: 1. What is the statement being proven? 2. What is the witness (the private input)? 3. What is the public input (what the verifier sees)? 4. Who issues the credential, and how is it bound to the user? 5. What prevents a user from sharing their proof with an underage person? 6. What are the privacy guarantees? 7. What are the limitations?

Exercise 37.12 — ZK-Rollup Economics

A ZK-rollup batches 5,000 transactions into a single proof. The proof verification costs 300,000 gas on Ethereum L1. Posting the transaction data (calldata) costs an additional 500,000 gas. Assume Ethereum gas costs $0.000003 per gas unit (a reasonable average).

(a) What is the total L1 cost per batch?

(b) What is the L1 cost per transaction?

(c) A simple ETH transfer on L1 costs approximately 21,000 gas. How much does the same transfer cost via the ZK-rollup (L1 component only)? Express this as a percentage of the L1 cost.

(d) If the rollup increases its batch size to 50,000 transactions, the proof verification cost rises to 350,000 gas and the calldata cost rises to 4,000,000 gas. Recalculate the per-transaction L1 cost. Does batching more transactions always improve economics? What limits batch size in practice?

Exercise 37.13 — Recursive Proof Chain

Mina Protocol uses recursive proofs to maintain a constant-size blockchain proof (~22 KB). Explain how this works by describing the following:

(a) What does the "base case" proof verify (the very first block)?

(b) What does each subsequent proof verify?

(c) Why does the proof remain approximately the same size regardless of the number of blocks?

(d) A new full node joins the Mina network. What does it need to download and verify to trust the current state? Compare this to what a new Bitcoin full node must do.

Section E: Critical Thinking

Exercise 37.14 — The Limits of Zero-Knowledge

ZK proofs are sometimes described as proving "anything about everything without revealing anything." Critically evaluate this claim.

(a) What are the computational limits? (What kinds of statements are currently impractical to prove with ZK technology?)

(b) What are the trust limits? (In what situations must you still trust someone, even with ZK proofs?)

(c) What are the social limits? (Can ZK proofs solve problems that are fundamentally social rather than technical? Consider the Worldcoin example from Case Study 2.)

Exercise 37.15 — ZK and Regulation

A government regulator proposes the following: "Financial institutions should use ZK proofs to prove regulatory compliance without revealing customer data to the regulator."

(a) What are the benefits of this approach for financial institutions? For customers? For regulators?

(b) What concerns might regulators have about this approach? (Consider enforcement, investigation, and the difference between compliance monitoring and compliance auditing.)

(c) Design a hybrid system that uses ZK proofs for routine compliance checking but allows regulators to access underlying data under specific, legally defined circumstances. What role do ZK proofs play in this hybrid system?

Exercises 37.1-37.4 test conceptual understanding (Bloom: Understand/Apply). Exercises 37.5-37.8 test technical foundations (Bloom: Apply/Analyze). Exercises 37.9-37.10 test comparative judgment (Bloom: Analyze/Evaluate). Exercises 37.11-37.13 test application design (Bloom: Apply/Create). Exercises 37.14-37.15 test critical evaluation (Bloom: Evaluate).