Zero Knowledge Proofs
& Computational Complexity

ZK Prereqs Workshop 1 of 6

Foundations: What ZKPs are, what they can do, and the math framework behind them

🔐 The Password Paradox

Every time you log in to a website, you prove you know the password...

...by revealing the password.

What if you could prove you know it
without ever sending it?

That's Zero Knowledge Proofs in one sentence.

Start with this. Let the room sit with it for a moment. Every login, every API key, every authentication — we prove knowledge by revealing it. ZKPs flip this on its head. Ask the room: "Where else do we reveal too much information to prove a simple fact?" Wait 15 seconds. If no one speaks up (or to add to their answers), use these ready-made examples: 1. BUYING ALCOHOL — You show your full driver's license: name, home address, date of birth, organ donor status. The bouncer only needs one fact: age ≥ 21. 2. GETTING A LOAN — You hand over complete bank statements showing every coffee purchase. The bank only needs: monthly income ≥ some threshold. 3. CRYPTO KYC — To trade $50 of Bitcoin, you upload passport + selfie + utility bill. The exchange only needs: "this person is not on a sanctions list." 4. ONLINE SHOPPING — Every checkout page gets your full credit card number. The shop only needs: "this person can pay $29.99." 5. JOB APPLICATIONS — Companies ask for full salary history. They only need: "candidate's expectations are within our budget." In every case, we OVER-prove. We reveal far more data than the fact we're trying to establish. ZKPs fix this: prove JUST the required fact, reveal NOTHING else.

Agenda

Time	Topic
0:00	What Are Zero Knowledge Proofs?
0:10	Computational Complexity: P, NP, PSPACE
0:25	Witnesses & Verification
0:35	Boolean Circuits
0:45	Arithmetic Circuits
0:55	Wrap-up & Practice Problems

Part 1: What Are Zero Knowledge Proofs?

~10 minutes

The Core Idea

A Zero Knowledge Proof lets a prover convince a verifier that a statement is true —

without revealing any information about why it's true.

Analogy: Prove to a bouncer you're over 21 — without showing your ID, name, address, or exact age.

Why ZKPs Matter in Web3

Use Case	What's Proven	What Stays Hidden
Privacy mixers	"I deposited funds earlier"	Which deposit is yours
zkRollups	"All transactions are valid"	Transaction details
Private voting	"I'm eligible and this is my vote"	Who you voted for
Identity	"I meet the criteria"	Personal data

Three Properties of ZKPs

Completeness — If the statement is true and both parties are honest, the verifier will be convinced
Soundness — If the statement is false, no cheating prover can trick the verifier (except with negligible probability)
Zero Knowledge — The verifier learns nothing beyond the truth of the statement

Discussion: Can you think of a situation in smart contracts where you'd want to prove something without revealing the underlying data?

Part 2: Computational Complexity

P, NP, PSPACE — ~15 minutes

To understand what ZK proofs can and cannot do, we need to classify problems by difficulty.

Solving vs. Checking: The Key Difference

Before we classify problems, understand one idea:

🔍 Solving

Finding the answer from scratch.

Like doing a jigsaw puzzle with no picture on the box.

✅ Checking

Verifying someone else's answer is correct.

Like looking at a completed jigsaw and confirming all pieces fit.

Some problems are easy to both solve and check.
Some are hard to solve but easy to check.
Some are hard to even check!
ZK proofs only work when checking is easy.

Problems in P — "Practical"

Easy to solve AND easy to check.

Problem	Solve	Check
Sorting a list	Compare & swap — fast for millions	Scan left to right: each item ≥ previous?
Finding a name	Scan through the whole list	"Alice is at pos 42" → look at pos 42
Drive City A → B?	Try different routes until one works	Follow the directions — do you arrive?

P = "Practical" — Both solving and checking finish in reasonable time, even for huge inputs.

P stands for "Polynomial time" but just think of it as "Practical." These are problems where BOTH finding the answer AND checking the answer are fast. The key intuition: if the input gets 10× bigger, the work might get 20× or 100× bigger — but NOT 1000× bigger. That's manageable growth. Walk through each example: - SORTING: "I have a million names to alphabetize. A computer does it in under a second. And to CHECK? Just scan the list — is each name after the previous one alphabetically? Also under a second." - FINDING: "Is Alice in this phone book? Scan through. Found her on page 42. To CHECK? Someone tells you 'page 42' — you flip there and confirm. Instant." - DRIVING: "Can I drive from Mumbai to Delhi? Try routes until one works. To CHECK someone's route? Just follow their directions turn by turn." All fast to solve, all fast to check. That's P.

Problems in NP

Hard to solve but easy to verify.

Sudoku

Solve: Exponential search through combinations
Verify: O(n²) — check rows, columns, subgrids

3-coloring a map

Solve: Brute-force through exponential color assignments
Verify: O(n) — check each pair of neighbors

Key insight: All P problems are also NP problems. P ⊆ NP

NP is THE important category for ZK proofs. Use these explanations: SUDOKU (primary analogy): "I give you a blank 9×9 Sudoku and say 'solve it.' You might struggle for an hour — trying numbers, hitting dead ends, erasing, starting over. That's SOLVING — it's hard. But now your friend shows you a completed grid and says 'I solved it!' How long does it take you to CHECK? 30 seconds. Just verify: does each row have 1-9? Each column? Each 3×3 box? If yes — it's valid. CHECKING is easy." 3-COLORING: "Here's a map of Indian states. Color every state so that no two neighboring states share a color, using only 3 colors. Finding a valid coloring? You'd try billions of combinations. But if someone shows you a colored map, checking takes seconds: look at each border line and confirm the two states on either side have different colors." KEY POINT TO EMPHASIZE: This gap between hard-to-solve and easy-to-check is EXACTLY what ZK proofs exploit. The prover does the hard work (finding the solution), then proves to the verifier they succeeded — and the verifier only has to do the easy part (checking). Also mention: Every P problem is automatically NP too. If you can both solve and check it fast, it definitely qualifies as "easy to check." So P is a subset of NP.

Problems in PSPACE — "Impossible to Check"

Hard to solve AND hard to check.

	Problem	Why checking is hard
🏆	Best move in chess	Must explore every opponent response & counter-move — no shortcut
🎮	Unbeatable game strategy	Must simulate every possible game against every opponent

No "receipt" exists — nothing anyone can show you makes checking fast.

No ZK proofs possible here — if you can't check the answer quickly, you can't create a proof for it.

PSPACE is the dead zone for ZK proofs. The key difference from NP: there's nothing anyone can show you that lets you quickly verify the answer. CHESS ANALOGY (use this): "A grandmaster tells you: 'The best move here is queen to e5.' Can you verify that? You'd have to check: what if the opponent plays pawn to d4? Then what's the best response? What if they play knight to f6 instead? And for EACH of those moves, what's the best counter-move? You end up rebuilding the entire game tree — billions of positions. There's no shortcut. No receipt. No clever proof. You have to replay everything." Same with game strategies: if someone claims to have the perfect Connect 4 strategy, the only way to verify is to play every possible game against them. That's not fast. This is why ZK proofs are limited to P and NP problems: you NEED efficient checking. No efficient checking = no ZK proof possible.

The Hierarchy

PSPACE

Hard to solve, hard to verify

Hard to solve, easy to verify

Easy to solve, easy to verify

Summary Table

Class	Time to Solve	Time to Verify
P	Polynomial	Polynomial
NP	No requirement (often exponential)	Polynomial
PSPACE	No requirement	No requirement

ZK Proofs only work for P and NP problems — problems where the solution can be verified efficiently. If you can't verify it efficiently, you can't create a ZK proof for it.

⚡ Quick Check: Classify These!

Vote with your hands: 1 finger = P, 2 fingers = NP, 3 fingers = PSPACE

Problem	Your Vote	Answer
Binary search in a sorted list	🤔	P — O(log n) solve & verify
Solving a 9×9 Sudoku	🤔	NP — hard to solve, easy to check
Finding the best chess move	🤔	PSPACE — can't even verify efficiently
"Is 997 prime?"	🤔	P — AKS primality test

Pause here for 2-3 minutes. Read each problem aloud, give students 10 seconds to vote, then reveal answers one at a time (press spacebar/arrow for each fragment). BINARY SEARCH — "We have a sorted phone book with a million names. We want to find 'Smith.' Open the middle — 'M' — too early, go right. Open the middle of that half — 'T' — too far, go left. Each step eliminates half the remaining names. Even for a BILLION names, this takes ~30 steps. Solving is fast. Checking is fast (just look at the result). Both fast = P." SUDOKU — "Give someone a blank 9×9 Sudoku. Solving it might take an hour of trial, error, and backtracking. But once filled in, CHECKING takes 30 seconds: scan each row (has 1-9?), column (has 1-9?), box (has 1-9?). Hard to solve, easy to check = NP." CHESS — "A computer says 'knight to g5 is the BEST move.' Can you verify that's truly the BEST? You'd have to analyze every possible opponent response, and their counter-responses... There's no shortcut. Hard to solve AND hard to check = PSPACE. No ZK proof possible." PRIMALITY — This one surprises people! "Is 997 prime?" There ARE fast algorithms (AKS, discovered in 2002) that check primality in reasonable time. Both solving and checking are fast = P. Fun fact: before 2002, mathematicians weren't sure if this was P or NP! Our understanding of these categories is still evolving.

Part 3: Witnesses & Verification

~10 minutes

What is a Witness?

A witness = the evidence that lets you quickly check a solution. Like a receipt 🧾.

Problem	Witness ("receipt")	How to check
Sorting a list	The sorted list	Scan: each item ≥ previous?
Finding "Alice"	"Position 42"	Look at pos 42
Drive city A→B?	Turn-by-turn directions	Follow them — arrive?
Sudoku	Filled grid	Rows, cols, boxes: all 1-9?
3-coloring	Color per region	Each border: neighbors differ?

PSPACE problems (chess, game strategies) have NO useful witness — no receipt exists.

Use the receipt analogy throughout. Walk through each row: "A witness is like a receipt from a shop. It PROVES something happened, and anyone can quickly verify it." - Sorting: "I claim I sorted your list. My witness IS the sorted list — you just scan it left to right to check." - Finding Alice: "I claim Alice is in the phone book. My witness is 'page 42' — you flip there, confirm. Done in 1 second." - Driving: "I claim you can drive from Mumbai to Delhi. My witness is the route — turn left at X, right at Y. You follow the directions." - Sudoku: "I claim I solved this puzzle. My witness is the completed grid. You check rows, columns, boxes. 30 seconds." - 3-coloring: "I claim I colored this map with 3 colors and no neighbors match. My witness is the coloring. You just check each border." Then the punchline: "For PSPACE problems like chess? There IS no receipt. Nothing anyone can show you makes checking the 'best move' fast. That's why ZK can't work for PSPACE — no witness exists."

The "Knowledge" in Zero Knowledge

The "knowledge" in ZKP = knowledge of the witness.

Concrete example — Sudoku:

Claim:     "I solved this Sudoku puzzle"
Witness:   The completed grid (SECRET — only the prover knows this)
ZK Proof:  Convinces the verifier the grid is valid
               ...WITHOUT ever showing the actual numbers

The ZK pipeline (how it works under the hood):

Express the problem as a circuit (math equations) — we'll learn this today
The prover plugs in their witness (the secret solution)
Cryptographic magic generates a proof
The verifier checks the proof — without ever seeing the witness

Make this concrete with the Sudoku walk-through: "You're in a Sudoku competition. You solved the puzzle — that completed grid is your WITNESS. Now you want to prove to the judges that you solved it, but you don't want to show your grid (you don't want other competitors to copy your answer). A ZK proof lets you do exactly that. Through cryptographic magic (which we'll understand by Workshop 6), you generate a proof. The judges check it. They become convinced your grid is valid — every row, column, and box has 1-9. But they never see a single number on your grid." The 4-step pipeline at the bottom is how ALL ZK proofs work: - Step 1: Turn your problem into math equations (a 'circuit'). We'll learn this in the next section. - Step 2: You (the prover) plug in your secret answer. - Step 3: Cryptographic magic creates a proof. - Step 4: Anyone can check the proof without seeing your answer. We'll spend the rest of today learning Step 1: how to express problems as circuits.

ZKPs Can't Do Everything

ZKPs cannot help you find a solution — only prove you have one
ZKPs cannot work for PSPACE problems — no efficient checking
ZKPs can work for any P or NP problem — anything where checking is fast

Think of ZKPs like a notary stamp: the notary confirms a document is valid, but doesn't create the document for you.

Real Example: Merkle Proof

You've likely seen this in Solidity — let's connect it to what we just learned.

                   ROOT HASH  (stored on-chain)
                  /          \
           Hash(A+B)      Hash(C+D)
            /     \          /     \
       Hash A  Hash B  Hash C  Hash D
          |       |       |       |
       Leaf A  Leaf B  Leaf C  Leaf D
                 ↑
        YOU WANT TO PROVE THIS LEAF IS IN THE TREE

Statement	"Leaf B is part of this Merkle tree"
Witness	Leaf B + Hash A + Hash(C+D) (the sibling hashes along the path)
Checking	Hash the leaf up the tree → does the result match the root?

This is NP: Hard to guess which leaves exist, but easy to verify a claimed leaf with just 2-3 hashes!

Connect to something students already know from Solidity — most have seen OpenZeppelin's MerkleProof.verify(). Walk through the diagram: "Imagine a whitelist of 1000 wallet addresses stored as a Merkle tree. Only the ROOT hash is stored on-chain (saves gas). A user claims: 'My address is on the whitelist.' That's the STATEMENT. Their WITNESS is: their address (Leaf B) plus the sibling hashes along the path to the root. In this diagram, that's Hash A and Hash(C+D) — just 2 hashes! CHECKING is fast: 1. Hash Leaf B → get Hash B 2. Combine Hash A + Hash B → get Hash(A+B) 3. Combine Hash(A+B) + Hash(C+D) → get Root 4. Does it match the on-chain root? If yes — VERIFIED! This is a perfect NP problem: the tree has 1000 leaves (hard to search through all of them), but verifying ANY single leaf takes only ~10 hash operations for a 1000-leaf tree. Bonus: You could wrap this in a ZK proof to prove you're on the whitelist WITHOUT revealing which address is yours!"

Part 4: Boolean Circuits

~10 minutes

We need a universal language to express any verifiable problem.
Boolean circuits give us that.

Boolean Operators

Operator	Symbol	Description
AND	∧	True only when both inputs are true
OR	∨	True when at least one input is true
NOT	¬	Flips true ↔ false

Example formula with variables x₁, x₂, x₃, x₄:

out = (x₁ ∨ ¬x₂ ∨ ¬x₃) ∧ (¬x₂ ∨ x₃ ∨ x₄)

Verifying a Boolean Formula

Given: out = (x₁ ∨ ¬x₂ ∨ ¬x₃) ∧ (¬x₂ ∨ x₃ ∨ x₄)

Proposed witness: x₁=T, x₂=F, x₃=T, x₄=F

Plug in: (T ∨ T ∨ F) ∧ (T ∨ T ∨ F)

= T ∧ T

= TRUE ✓

Finding the assignment → may be exponential
Verifying a proposed assignment → polynomial (just plug in!)

3-Coloring as a Boolean Circuit

Each territory gets Boolean variables per color: WA_G, WA_B, WA_R

Color constraint — exactly one color per territory:

(WA_G ∧ ¬WA_B ∧ ¬WA_R) ∨ (¬WA_G ∧ WA_B ∧ ¬WA_R) ∨ (¬WA_G ∧ ¬WA_B ∧ WA_R)

Boundary constraint — neighbors differ:

¬(WA_G ∧ SA_G) ∧ ¬(WA_B ∧ SA_B) ∧ ¬(WA_R ∧ SA_R)

The Problem with Boolean Circuits

Boolean circuits are overly long for number operations. Express 8 + 4 = 12:

Number	Binary	Boolean vars
8	1000	a₁=1, a₂=0, a₃=0, a₄=0
4	0100	b₁=0, b₂=1, b₃=0, b₄=0
12	1100	c₁=1, c₂=1, c₃=0, c₄=0

✗ Boolean: 12 vars + carry logic

a₁ XOR b₁ = c₁ (with carry)
a₂ XOR b₂ XOR carry = c₂
... MANY more lines

✓ Arithmetic: 3 vars, 1 equation

a + b === c
// That's it. Done.

This is why ZK systems use arithmetic circuits.

Walk through this step by step — it's the key motivation for arithmetic circuits: "To represent '8 + 4 = 12' with Boolean logic, we first need to convert each number to BINARY. How does binary work? - 8 in binary is 1000 (that's: 1×8 + 0×4 + 0×2 + 0×1) - 4 in binary is 0100 (that's: 0×8 + 1×4 + 0×2 + 0×1) - 12 in binary is 1100 (that's: 1×8 + 1×4 + 0×2 + 0×1) Each number needs 4 bits = 4 Boolean variables. Three numbers = 12 variables just to SET UP the problem. Then you need to model how binary addition actually works: add bit by bit from right to left, carrying over to the next column when the sum exceeds 1. Just like long addition with decimal numbers, but in base 2. Each column needs its own formula handling the carry." Now show the right side: "With arithmetic circuits? a + b === c. Three variables. One equation. Done. The numbers work as actual numbers — no binary conversion needed." "This 4:1 ratio gets MUCH worse for bigger numbers. Real ZK proofs use 256-bit numbers. Boolean: 768 variables + huge carry chain. Arithmetic: still just a + b === c."

Part 5: Arithmetic Circuits

~10 minutes

A simpler, more compact way to express problems for ZK proofs.

What is an Arithmetic Circuit?

A system of equations using only three operations:

Addition (+)
Multiplication (×)
Equality (===)

First example:

6 === x₁ + x₂
9 === x₁ * x₂

Satisfied by x₁ = 3, x₂ = 3

=== means assert equal, not assign.
Think: assertEq(left, right)

Constraining Values

How do we force a signal to be 0 or 1?

x(x - 1) === 0

Only x = 0 or x = 1 satisfies this!

How do we force a signal to be one of {1, 2, 3}?

0 === (1 - x) * (2 - x) * (3 - x)

A polynomial that has roots at exactly 1, 2, and 3.

3-Coloring with Arithmetic Circuits

Instead of 3 Boolean variables per territory → 1 signal with values {1, 2, 3}

// Color constraints — each territory is colored 1, 2, or 3
0 === (1 - WA) * (2 - WA) * (3 - WA)
0 === (1 - SA) * (2 - SA) * (3 - SA)
0 === (1 - NT) * (2 - NT) * (3 - NT)
// ... one per territory

// Boundary constraints — neighbors have different colors
// If x ≠ y and both ∈ {1,2,3}, then x*y ∈ {2, 3, 6}
0 === (2 - WA*SA) * (3 - WA*SA) * (6 - WA*SA)
0 === (2 - WA*NT) * (3 - WA*NT) * (6 - WA*NT)
// ... one per border

Same 15 constraints as Boolean, but ⅓ the variables.

Boolean ↔ Arithmetic Translation

Every Boolean gate has an arithmetic equivalent
(when inputs are constrained to 0 or 1):

Boolean	Arithmetic
NOT u → t	`t === 1 - u`
u AND v → t	`t === u * v`
u OR v → t	`t === u + v - u*v`

Conversion Example

Boolean: out = (x ∧ ¬y) ∨ z

Step by step → Arithmetic:

// Constrain inputs to 0 or 1
x(x - 1) === 0
y(y - 1) === 0
z(z - 1) === 0

// ¬y       →  (1 - y)
// x ∧ ¬y   →  x * (1 - y)
// ... ∨ z  →  x*(1-y) + z - x*(1-y)*z

// Final:
out === x - x*y + z - x*z + x*y*z

The ZK Pipeline

Real-world problem

↓

Arithmetic Circuit (system of constraints)

↓

Prover: "I know a witness that satisfies all constraints"

↓

ZK Proof: Verifier confirms without seeing the witness

All problems in P and NP can be expressed as arithmetic circuits.
This is the foundation everything else is built on.

Live Demo: Boolean vs Arithmetic

Prove (x AND NOT y) OR z equals its arithmetic version for ALL inputs.

def boolean_circuit(x, y, z):          # Python keywords
    return (x and not y) or z

def arithmetic_circuit(x, y, z):       # Only +, *, integers
    assert x*(x-1) == 0 and y*(y-1) == 0 and z*(z-1) == 0
    return x - x*y + z - x*z + x*y*z  # NOT=(1-y), OR=a+b-ab

for x in [0,1]:                        # Test all 8 combos
    for y in [0,1]:
        for z in [0,1]:
            b = 1 if boolean_circuit(x,y,z) else 0
            a = arithmetic_circuit(x,y,z)
            assert b == a
            print(f"x={x}, y={y}, z={z} -> {a}")
print("All 8 match!")

Walk through this BEFORE running it: "This code has three parts: 1. BOOLEAN VERSION (line 3-4): Exactly the formula from our conversion slide, using Python's regular 'and', 'or', 'not' keywords. Nothing fancy. 2. ARITHMETIC VERSION (line 8-15): The SAME logic but expressed with only numbers and math. The asserts enforce that inputs must be 0 or 1 (this is x(x-1)===0 from our 'Constraining Values' slide). The return line is the simplified arithmetic formula we derived: x - x*y + z - x*z + x*y*z. 3. TEST LOOP (line 18-24): Tries EVERY combination of inputs. x can be 0 or 1, y can be 0 or 1, z can be 0 or 1 — that's 2×2×2 = 8 total combinations. For each one, it runs BOTH versions and checks they give the same answer. Run it, and you'll see all 8 combinations print with matching results. This PROVES the arithmetic formula is a perfect translation of the Boolean formula. If students want to experiment: change the Boolean formula (try 'x or y' or 'x and y and z') and derive the new arithmetic version using the conversion table. Then test it the same way."

Key Takeaways

ZKPs let you prove you know something without revealing it
Only P and NP problems can have ZK proofs (solutions must be efficiently verifiable)
Witnesses are the secret knowledge the prover has
Arithmetic circuits are systems of equations (add, multiply, equals) that model any NP problem
Arithmetic circuits are more compact than Boolean circuits for most ZK applications

Practice Problems

Classify as P, NP, or PSPACE: shortest path in a graph, prime factorization, best Go move, primality testing
Create an arithmetic circuit satisfied when all signals x₁...x_n are 1
Create an arithmetic circuit satisfied when at least one signal is 0
Convert this Boolean formula to arithmetic: out = (a ∨ b) ∧ ¬c
Design a 2-coloring circuit for a bipartite graph (hint: adjust the 3-coloring scheme)

Assign these as homework. Complete solutions are in the ANSWER_KEY.md file and the solutions/ folder (one .py per problem) in this workshop's directory. Do NOT share these with students — they are instructor-only. Hints you can give if students get stuck: - Problem 1: Ask yourself "Can I CHECK the answer quickly?" - Shortest path: given a path, follow it and count distance → easy to check → P - Prime factorization: given factors, multiply them → easy to check → NP - Best Go move: no way to quickly verify it's truly the best → PSPACE - Primality testing: AKS algorithm solves it fast → P - Problem 2: "All signals are 1" — if you multiply them all together, the product is 1 only when every signal is 1. So: x₁ × x₂ × ... × xₙ === 1 - Problem 3: "At least one is 0" — same product trick! If any signal is 0, the product is 0. So: x₁ × x₂ × ... × xₙ === 0 - Problem 4: Use the Boolean → Arithmetic conversion table: NOT c = (1-c) a OR b = a + b - a*b AND = multiply So: (a + b - a*b) * (1 - c) === 1 - Problem 5: For 2 colors use values 0 and 1. Neighbors must differ. XOR trick: vᵢ + vⱼ - 2*vᵢ*vⱼ === 1

Next Workshop

Finite Fields & Modular Arithmetic

How arithmetic circuits handle division and overflow
Modular arithmetic — the number system ZK proofs operate in
Additive and multiplicative inverses
Polynomials over finite fields

This is the number system that makes ZK proofs possible.

Zero Knowledge Proofs& Computational Complexity

🔐 The Password Paradox

Agenda

Part 1: What Are Zero Knowledge Proofs?

The Core Idea

Why ZKPs Matter in Web3

Three Properties of ZKPs

Part 2: Computational Complexity

Solving vs. Checking: The Key Difference

🔍 Solving

✅ Checking

Problems in P — "Practical"

Problems in NP

Sudoku

3-coloring a map

Problems in PSPACE — "Impossible to Check"

The Hierarchy

Summary Table

⚡ Quick Check: Classify These!

Part 3: Witnesses & Verification

What is a Witness?

The "Knowledge" in Zero Knowledge

ZKPs Can't Do Everything

Real Example: Merkle Proof

Part 4: Boolean Circuits

Boolean Operators

Verifying a Boolean Formula

3-Coloring as a Boolean Circuit

The Problem with Boolean Circuits

Part 5: Arithmetic Circuits

What is an Arithmetic Circuit?

Constraining Values

3-Coloring with Arithmetic Circuits

Boolean ↔ Arithmetic Translation

Conversion Example

The ZK Pipeline

Live Demo: Boolean vs Arithmetic

Key Takeaways

Practice Problems

Next Workshop

Finite Fields & Modular Arithmetic

Zero Knowledge Proofs
& Computational Complexity