---
marp: true
title: "Taipei ZK Workshop: Understanding the Math Behind ZKPs"
paginate: true
_paginate: false
---

## Taipei ZK Workshop

- Third session: Understanding math (1415-1600)
- Stop for exercises twice
- Short break in middle

Note:
- Any questions from previous session?

---

## Understanding the Math Behind ZKPs (1)


- Based on [Understanding the Math Behind ZKPs](https://zkintro.com/articles/understanding-the-math-behind-zkps)

---

## Understanding the Math Behind ZKPs (1)

- Intuition on how ZKPs work under the hood
- Minimal math background required (no polynomials or elliptic curves)
- A toy protocol (ZKBoo) as example, 100 LOC

Note:
- Target: a "rusty STEM grad" or motivated HS student.

---

## Prerequisites (1.1)

- Familiarity with basic ZKP ideas
- e.g. "Friendly Introduction to Zero Knowledge" (previous session)
- Comfortable with symbols & basic math
- e.g. modular arithmetic, Boolean ops, randomness
- Notion of probability & prime numbers
- Curiosity & willingness to look up unfamiliar topics

Note:
- Examples remain accessible without deep cryptography background.

---

## Overview (1.2)

- Covers:
- Circuits, functional completeness
- Commitments, secret sharing
- Sigma protocols
- ZKBoo step-by-step
- Where it fits in the zkSNARK landscape
- Foundation for understanding ZKP math

Note:
- Build foundational understanding for bigger ZK frameworks.
- Don't worry don't understand terms now

---

## Overview (1.2 cont)

- Prove a set of constraints

$$
\begin{aligned}
a \cdot b &= c \\
c+d &= e
\end{aligned}
$$

Note:
- secret sharing, then sigma protocol interactive, improve security,
- see how non-interactive, etc

---

## Key Concepts (2)

- Circuits
- Functional completeness
- Commitments
- Secret sharing
- Sigma protocols

Note:
- These building blocks form the bedrock of ZKBoo and many ZK protocols.

---

## Circuits (2.1)

- Express computations as sets of constraints
- Example:
$$
\begin{aligned}
a \cdot b &= c \\
c+d &= e
\end{aligned}
$$

- Some vars private (witness), some public (instance)

Note:
- Constraints are unordered; each must be satisfied.

---

## Circuit (2.1)

- Witness variables (private, only prover knows)
- Instance variables (public, known by prover and verifier)

---

## Circuit (2.1)

Mathematically speaking:

$$
C(x,w) = 0
$$

Where $x$ is the public variable ($e$), $w$ the witness variables ($a, b, d$)

That is, we have:
$$
\begin{aligned}
a \cdot b - c = 0 \\
c + d - e = 0
\end{aligned}
$$

Note:
- Set of equations hold, w/o revealing private variables

---

## Functional Completeness (2.2)

- Boolean circuits: 0 or 1 values
- `XOR` & `AND` form a complete basis
- For binary arithmetic:
- `+` behaves like XOR (mod 2)
- `*` behaves like AND
- Any computation can be built from these gates
- (Arithmetic circuits, see Appendix B)

Note:
- True for arithmetic circuits over finite fields too.

---

## Functional Completeness (2.2)

$$
\begin{array}{|c|c|c|c|}
\hline
a & b & \text{XOR/(ADD)} & \text{AND/(MUL)} \\
\hline
0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 \\
1 & 0 & 1 & 0 \\
1 & 1 & 0 & 1 \\
\hline
\end{array}
$$

Note:
- Works for OR, NAND; Nand course
- Arithmetic circuits normal integers Appendix A

---

## Commitments (2.3)

- Cryptographic "lockbox"
- Hiding: hides the committed value
- Binding: cannot change after committing
- Often via hash:
`commit = sha256(msg || rand)`
- Later "open" the commitment to reveal original

Note:
- Prevents changing mind, ensures secrecy
- We saw this in previous session

---

## Secret Sharing (2.4)

- Split a secret `x` into multiple parts:
`x = x1 + x2 + x3`
- Knowing any subset of shares (less than total) reveals no info about `x`
- "MPC-in-the-Head": imagine multiple parties each holding a share

Note:
- A puzzle piece analogy: need all pieces to see the full secret.

---

## Secret sharing (2.4)


Note:
- All pieces needed to see full secret

---

## Sigma Protocol (2.5)

$$
\scriptsize
\begin{array}{c}
\textbf{A Sigma Protocol} \\[10pt]
\text{Prover} \xrightarrow{\text{1. Commitment}} \text{Verifier} \\[10pt]
\text{Prover} \xleftarrow{\text{2. Challenge}} \text{Verifier} \\[10pt]
\text{Prover} \xrightarrow{\text{3. Response}} \text{Verifier} \\[15pt]
\end{array}
$$

- Interactive protocol
- After challenge, response convincing

Note:
- Combine commitments and secrt sharing; all needed for ZKBoo
- 3-step interaction: commit → challenge → response
- Challenge: hard question; verifier covinced by response
- Prover commits, Verifier challenges, Prover responds

---

## Sigma Protocol (2.5)

- Ensures:
- Completeness: correct Prover always convinces
- Soundness: dishonest Prover ~can't get away with cheating
- Zero Knowledge: hides Prover’s secret from Verifier

Note:
- ZKBoo builds on these ideas with more details.

---

## Exercises (2.6)

1. In $x + 1 = y; y + 5 = z$, if $x$ is a secret, what is witness variable and public output?
2. Why does the order of constraints not matter? What if we swap order of them?
3. Alice commits to x `SHA256(x || r)`. Later she claims she committed to 42, how prove?
4. If Bob splits `x=12` into $x_1 + x_2 + x_3 = x$, what can $(x_1, x_2, x_3)$ be? Why does revealing $x_2$ and $x_3$ not give us info about $x$?
5. In a sigma protocol, why does Prover commit before Verifier sends challenge?

---

## Exercises and break

- Take 10-15m to discuss above
- Then 10m break

---

## ZKBoo (3)

- A simple ZKP protocol using:
- Boolean circuits
- Commitments
- Secret sharing
- Sigma protocols
- Not succinct but conceptually clear
- Good for learning core ZK math

Note:
- We'll see how to implement `a*b=c` and `c+d=e` step by step.
- Easy to generalize for arithmetic circuits

---

## ZKBoo Example (3.1)

$$
\begin{aligned}
a \cdot b &= c \\
c+d &= e
\end{aligned}
$$

- Focus on $c+d=e$ for now
- Split using secret sharing

---

## ZKBoo Example (Addition) (3.1)

- Suppose $c + d = e$ with `c,d` private, `e` public
- Split variables into 3 shares each:
- $c = c_1 + c_2 + c_3$
- $d = d_1 + d_2 + d_3$
- $e = e_1 + e_2 + e_3$, with $e_1 = c_1 + d_1$, and similar for $e_2, e_3$

Note:

---

### Splitting our variables (3.1)

$$
\begin{array}{c|ccc}
& \text{Column 1} & \text{Column 2} & \text{Column 3} \\ \hline
\text{Row 1} & c_1 & c_2 & c_3 \\
\text{Row 2} & d_1 & d_2 & d_3 \\
\text{Row 3} & e_1 & e_2 & e_3 \\
\end{array}
$$

Note:
- MPC-in-head paradigm

---

## ZKBoo Example (Addition) (3.1)

Verifier challenges Prover to reveal two random columns, e.g $(2,3)$:

$$
\begin{aligned}
c_2 + d_2 \stackrel{?}{=} e_2 \\
c_3 + d_3 \stackrel{?}{=} e_3
\end{aligned}
$$

Note:
- Prover could guess columns, look at later

---

## Sigma protocol for ZKBoo (3.2)

- How can prover convince verifier they know c,d?
- Prover commits to each column 1..3
- Verifier challenges Prover to reveal $(i,j)$ column
- Prover responds with values from columns
- Verifier then does *consistency check* and *commitment check*

Note:
- How can prover convince verifier?

---

## Sigma protocol for ZKBoo (3.2)

$$
\scriptsize
\begin{array}{c}
\textbf{Prover} \qquad\qquad\qquad \textbf{Verifier} \\
\xrightarrow{\text{Commitment: } \{\text{com}_1, \text{com}_2, \text{com}_3\}\ \text{ where } \text{com}_k = \text{hash}(c_k, d_k, e_k, r_k) \text{ for } k =1,2,3} \\
\xleftarrow{\text{Challenge: Reveal two columns } (i, j)} \\
\xrightarrow{\text{Response: } (c_i, d_i, e_i, r_i), (c_j, d_j, e_j, r_j)} \\
\text{Verifier checks:} \\
\begin{aligned}
9. &\quad c_i + d_i \stackrel{?}{=} e_i, \, c_j + d_j \stackrel{?}{=} e_j, \\
10. &\quad \text{com}_i \stackrel{?}{=} \text{hash}(c_i, d_i, e_i, r_i), \, \text{com}_j \stackrel{?}{=} \text{hash}(c_j, d_j, e_j, r_j).
\end{aligned}
\end{array}
$$

---

## Sigma protocol for ZKBoo (3.2)

- Completeness: Prover knows solution, can convince Verifier
- Soundness: Verifier only convinced if Prover knows secret\*
- Zero-knowledge: Verifier doesn't learn anything about c,d
- \* We'll look at cheating soon

Note:
- 1/3 chance of cheating, statistical nature; guess columns
- In practice we will reduce this to negliglbe prob

---

## ZKBoo: Supporting multiplication (3.3)

- For `a*b = c`, naive approach fails due to cross-terms

$$
\begin{aligned}
a \cdot b & = (a_1 + a_2 + a_3) \cdot (b_1 + b_2 + b_3) \\
&= a_1 b_1 + a_1 b_2 + \dots + a_3 b_2 + a_3 b_3 \\
&\neq a_1 b_1 + a_2 b_2 + a_3 b_3
\end{aligned}
$$
- Cross-terms: $a_1b_2, a_1b_3, a_2b_1, a_2b_3, a_3b_1, a_3b_2$
- We fix it by distributing cross-terms across $c_i$

----

## ZKBoo: Supporting multiplication (3.3)

$$
\begin{aligned}
c_1 = a_1 b_1 + a_1 b_2 + a_2 b_1 \\
c_2 = a_2 b_2 + a_2 b_3 + a_3 b_2 \\
c_3 = a_3 b_3 + a_1 b_3 + a_3 b_1 \\
\end{aligned}
$$

- Now $a \cdot b = c$
- New problem: revealing $(1,2)$ reveal info about 3rd column
- Let's fix by introducing randomness!

---

## ZKBoo: Supporting multiplication (3.3)

$$
\begin{aligned}
c_1 = a_1 b_1 + a_1 b_2 + a_2 b_1 + r_1 - r_2\\
c_2 = a_2 b_2 + a_2 b_3 + a_3 b_2 + r_2 - r_3 \\
c_3 = a_3 b_3 + a_1 b_3 + a_3 b_1 + r_3 - r_1 \\
\end{aligned}
$$
- All random variables cancel out: $r_1 - r_2 + r_2 - r_3 + r_3 - r_1 = 0$
- Not revealing any information about third column now

Note:
- Common trick in cryptography

---

## ZKBoo: Supporting multiplication (3.3)

$$
\begin{array}{c|ccc}
& \text{Column 1} & \text{Column 2} & \text{Column 3} \\ \hline
a & a_1 & a_2 & a_3 \\
b & b_1 & b_2 & b_3 \\
r & r_1 & r_2 & r_3 \\[6pt]
c & c_1 & c_2 & c_3 \\
\end{array}
$$

Note:
- r another variable, reveal (1,2) reveals r1 r2, not r3

---

## Putting it all together (3.4)

$$
\begin{aligned}
a \cdot b &= c \\
c+d &= e
\end{aligned}
$$

- Prover sets $a,b,d$ shares randomly
- ...sets c s.t. $a \cdot b =c$, and same for all shares
- ...sets e s.t. $c+d=e$, and same for all shares

Note:

---

## Updated sigma protocol (3.4)

$$
\scriptsize
\begin{array}{c}
\textbf{Prover} \qquad\qquad\qquad \textbf{Verifier} \\
\xrightarrow{\{\text{com}_1, \text{com}_2, \text{com}_3\} \ \text{ where } \text{com}_k = \text{hash}(a_k, b_k, c_k, d_k, e_k, r_k) \text{ for } k = 1,2,3} \\
\xleftarrow{\text{Reveal two columns } (i, j)} \\
\xrightarrow{(a_i, b_i, c_i, d_i, e_i, r_i), (a_j, b_j, c_j, d_j, e_j, r_j)} \\
\end{array}
$$

---

## Checks (3.4)

$$
\scriptsize
\begin{array}{l}
\textbf{Consistency: Verify } a \cdot b = c \text{ for shares:} \\
\quad c_i \stackrel{?}{=} (a_i b_i + a_i b_j + a_j b_i) + (r_i - r_j), \\
\quad c_j \stackrel{?}{=} (a_j b_j + a_j b_k + a_k b_j) + (r_j - r_k) \\
\quad \text{Note: } r \text{ subscripts } i, j, k \text{ are } \bmod 3 \\
\textbf{Verify } c + d = e \text{ for shares:} \\
\quad c_i + d_i \stackrel{?}{=} e_i, \quad c_j + d_j \stackrel{?}{=} e_j \\
\textbf{Commitment checks:} \\
\quad com_i \stackrel{?}{=} \text{hash}(a_i, b_i, c_i, d_i, e_i, r_i), \\
\quad com_j \stackrel{?}{=} \text{hash}(a_j, b_j, c_j, d_j, e_j, r_j)
\end{array}
$$

Note:
- Consistency and commitment checks
- Proven set of constraints with add and mul; functional completeness

---

## What did we do? (3.4)

- Prove set of constraints using + and \* => functional completeness
- Kept private values private, and convinced Verifier Prover knows them
- Next: Improve soundness

---

## Improving Soundness (3.5)

- What if Prover cheats? Guess columns (2,3) picked
- => don't need to know private values! Make up to make checks succeed
- E.g. pick random $c_2, d_2$ s.t. $c_2+d_2=e_2$, and same $c_3, d_3$
- Commitments before: can't change mind (but can get lucky)
- Chance of picking right columns: $\frac{1}{3}$ (soundness error)

---

## Improving Soundness (3.5)

- How improve this? Mulitple rounds!
- Run Sigma protocol $n$ times, new shares every time
- Probabilitty of cheating:

$$
\left(\frac{1}{3}\right)^n
$$

- Can make astronomically small with say 100 rounds

Note:
- In an interactive protocol, that’s many back-and-forth steps.

---

## Improving Soundness (3.5)

- Can get arbitrarily small soundness error; good
- But: 3 messages per round, 100 rounds = 300 interactions! Slow and not usable
- Fix by making protocol *non-interactive*, a single message!

---

## Fiat-Shamir Transform (3.6)

Sigma protocol single round:

$$
\scriptsize
\begin{array}{c}
\textbf{Prover} \qquad\qquad\qquad \textbf{Verifier} \\
\xrightarrow{\{\text{com}_1, \text{com}_2, \text{com}_3\} \ \text{ where } \text{com}_k = \text{hash}(a_k, b_k, c_k, d_k, e_k, r_k) \text{ for } k = 1,2,3} \\
\xleftarrow{\text{Reveal two columns } (i, j)} \\
\xrightarrow{(a_i, b_i, c_i, d_i, e_i, r_i), (a_j, b_j, c_j, d_j, e_j, r_j)} \\
\end{array}
$$

- Goal of Fiat-Shamir: Turn interactive protocol into non-interactive (single message)
- Why verifier sending challenge after commitment?
- Breaks soundness; want randomness

Note:
How else can we get this randomness?

---

## Fiat-Shamir Transform (3.6)

- Key idea: Replace randomness Verifier is using with deterministic hash function
- Hash functions are pseudo-random; randomly select two columns

---

From:

$$
\scriptsize
\begin{array}{c}
\textbf{A Sigma Protocol} \\
\text{Prover} \xrightarrow{\text{1. Commitment}} \text{Verifier} \\[10pt]
\text{Prover} \xleftarrow{\text{2. Challenge}} \text{Verifier} \\[10pt]
\text{Prover} \xrightarrow{\text{3. Response}} \text{Verifier} \\[15pt]
\end{array}
$$

To:
$$
\scriptsize
\begin{array}{c}
\textbf{A Non-interactive Protocol} \\
\text{Prover} \xrightarrow{\text{\{Commitment, Challenge, and Response\}}} \text{Verifier} \\[15pt]
\end{array}
$$

---

## Fiat-Shamir Transform (3.6)

- Challenge produced with hash (SHA256), include commitments and public info ("random seed")
- Prover and Verifier agree on; not something Prover can decide on own
- Re-calculated by both
$$
\scriptsize
\text{challenge} = \text{hash}(com_1, com_2, com_3, \text{<public info>})
$$

---

## Fiat-Shamir Transform (3.6)

- To ensure soundness we run multiple rounds; previous round input into next round
- This prevents "backtracking" by prover, not predictable

$$
\scriptsize
\text{challenge}_k = \text{hash}(com_{1,1}, com_{1,2}, com_{1,3}, \dots, com_{k,3},\text{<public info>}, k) \mod 3
$$

Note:
commitment for kth round

---

## Fiat-Shamir Transform (3.6)

Proof sent over: commitments and responses

$$
\scriptsize
\begin{array}{c}
\text{Prover} \xrightarrow{\Pi = \{\text{Commitments: } \{com_{k,1}, com_{k,2}, com_{k,3}\}, \text{Responses: } \{(c_{k,i_k}, \dots)\}} \text{Verifier} \\[15pt]
\end{array}
$$

- Commitments: binding so can't change mind on input
- $k$ rounds, soundness with very high probability

---

## ZKBoo summing up (3.6)

- We got a sound protocol that is non-interactive, great!
- Unfortunately a lot of data - proof has $n \cdot k$ responses, where n is variables and k rounds
- ZKBoo not succinct; need more advanced tools for this
- Appendix: Generalize to arithmetic circuit and also code (60 LOC)

---

## zkSNARKs (4)

- `ZK`: Zero Knowledge
- `N`: Non-Interactive (Fiat-Shamir)
- `AR`: ARgument of (computational soundness)
- `K`: of Knowledge
- `S`: Succinctness (short proof, fast verify)
- ZKBoo misses succinctness → proof size grows linearly
- ...Not all "ZK" projects are "ZK"
- (See Appendix for more math def)

Note:
- Deeper math (polynomials, ECC) enable sublinear or constant proof sizes.
- Not ZK: verifiable computation

---

## On Succinctness (4.1)

- ZKBoo:
- Proof grows ~ O(n) with number of constraints
- Verify time ~ O(n) (check all constraints)
- For true succinctness:
- Want sublinear or constant proof size
- Typically need *polynomial commitment schemes*
- ZKBoo remains a great stepping stone

Note:
- Practical SNARKs use advanced polynomial math.

---

## On Succinctness (4.1)

- We want either $O(\log n)$ or $O(1)$

Note:
- Big Oh; we want "below"

---

## Exercises (3.7)

1. In a sigma protocol with 3 shares, where two shares are revealed, what is the probability of a cheating Prover to convince a Verifier in a single round? How does running multiple rounds help?
2. If the Prover knew in advance which columns a Verifier would choose, how could they cheat?
3. In Fiat-Shamir, why does hashing all commitments before generating the challenge make it harder to cheat?

---

## Exercises (4.3)

4. What properties do we get from ZKBoo?
5. Why is ZKBoo not succinct? Intuitively speaking.

Note:

---

### Problems

6. Implement multiple rounds in SageMath (see Appendix A)
7. Implement Fiat-Shamir in SageMath (see Appendix A)
8. Find a few proof systems you've heard about. Identify how they are similar and different from each other. Compare and contrast with ZKBoo.

---

## Math & Break

- Break up into smaller groups
- Solve exercises above (20-30m)

---

(Mathing)

---

### Next - Teaser (4.2)

- Polynomials and succinctness; Commitments -> Polynomial Commitment Schemes (PCS); Sigma protocols -> Polynomial Interactive Oracle Proofs (IOP); Understanding PCS + Poly-IOPs framework for modern ZKP systems; Diff PCS: KZG/FRI/IPA
- Domains: server/client side proving; Field size, post-quantum, setups, security assumptions
- Public blockchains for verifying proofs; STARKs are SNARKs, Structured/unstructured circuits, Novel ZKPs...

---

## Conclusion (4.5)

- We learned:
- Circuits & functional completeness
- Commitments & secret sharing
- Sigma protocols -> ZKBoo -> Increased soundness
- Non-interactive via Fiat-Shamir
- Why ZKBoo is not succinct
- How other proof systems differ at high level

Note:

---

## One last thing...

- Booklets in English; want Chinese version
- Help wanted to translate into Chinese!
- Update: Done by Anton, Nicole and Pinhao!
- Join TG (second QR code) or talk to me :)

---

## Thank you

- Questions
- (Tomorrow: more proof systems and applications)

Note:
- Wrap-up & Q&A

---