Briefly on zk-SNARKs mathematical foundations

Note:
Hello!

• What zk-SNARKs are and how they work
• polynomial properties, modular arithmetic, homomorphic encryption, knowledge of exponent assumption, elliptic curve cryptography, cryptographic pairings, polynomial interpolation…

Note:
What they are and how work
Talk about mathematical underpinings, such as…

Introduction

• Based on previous work, especially "Why and How zkSNARKs works" by Maksym Petkus
• Also see great explainers by Vitalik and Gabizon
• Will focus on key mathematical tools

Note:
A lot of great explainers, definitely check them out
Will focus more on key mathematical insights, less on mechanical aspects

• zk-SNARK: Zero Knowledge Succinct Non-interactive ARguments of Knowledge
• Prove something without revealing any other information

Note:
Sure you guys are familiar, so I'll brief with intro here
Will break that down soon, but first what useful for?

Allow us to do many things

• Anonymous authorization
• Anonymous payments
• Outsourcing computation

Note:
Proving have access to some system w/o revealing who one is
Making digital money fungible
In p2p, one node doing expensive computation, other nodes verify

Where's Waldo?

Note:
A great example for simple intuition to laypeople is "Where's Waldo?". In this illustration prover Peggy want to prove to the verifier Victor that they know where Waldo is, without revealing where he is.

1. Imagine the Waldo map is like a post card. Now take a bigger piece of paper and put it in front of the Waldo map post card.
2. Make a tiny hole in the big piece of paper and position the Waldo map under it so only Waldo is visible.
3. The verifier Victor can see that you indeed know where Waldo is, but not where on the actual post card he is.

Of course, this is just a toy example to build intuition and doesn't tell us anything about the actual math behind it. We'll dive into that next.

Protocol properties

1. Completeness - if statement is true the a prover can convince a verifier
2. Soundness - a malicious prover can't convince verifier of a false statement
3. Zero-knowledge - a proof only reveals if a statement is true, nothing else

Note:
As it turns out, even though ZK property seems most magical, and is in some sense,
it falls out naturally from verifiable copmuting / soundness aspect

Why do we use polynomials in zk-SNARKs?

• Example: \(x^2 - 3x + 2\) polynomial of degree 2
• More generally, polynomial of degree \(n\): \(P(x) = a_n x^n + a_{n-1} x^{n-1} + \ldots + a_1 x_1 + a_0\)
• Polynomials have some nice properties

Note:
Probably heard zkSNARKs use polynomials, but why?
Example p, deg 2, more general form

A simple proof

• Bit array: \(b = [?, ?, ?, ?, ?, ?, ?, ?, ?, ?]\)
• Prover Peggy: All entries are set to 1, for sure
• Verifier Victor: verifies entries one by one
• To get 95% confidence: check all entries

Note:
Naive simple proof to contrast with polynomials
Victor randomly or sequentially check each one, inefficient

Polynomials

• Fundamental Theorem of Algebra: a degree d polynomial has at most d solutions
• \(p(x) = x^3 - 6x^2 + 11x - 6\)
• Two different polynomials intersect at at most d points

Note:
If we change p a tiny bit we get diff solution
Set two polynomials equal to each other get another one

Proof of polynomial

• Peggy Prover knows a polynomial p(x), which Victor Verifier also knows
• Simple protocol:
  • Victor chooses a random value for x (say 7) and evaluates it locally, \(p(7)=120\)
  • Victor gives this random value 7 to Peggy
  • Peggy evaluates it locally and gives result, \(p(7)=120\) to Victor

Note:
If Peggy says they know a polynomial…

太陽從西邊出來

• If results are same, very likely Peggy knows the same polynomial as Victor
• Range for x values: \(1\) to \(2^{252}\)
• Probability of Peggy accidentally picking point where polynomial evaluation is same is \(\frac{d}{2^{252}}\) which is very unlikely

Good proof medium

• Polynomials are easy to work with when it comes to operations such as addition, multiplication, etc
• Illustration of why zk-SNARks rely on polynomials
• Likely other forms of proof mediums exists

Note:
So polynomials are very easy to work with…
Hopefully contrasting it with naive proof gives some idea for why zksnarks relies on polynomials

Target polynomial

• Victor Verifier don't know \(p(x)\), only Peggy does
• \((x - a_0)(x - a_1) \ldots (x - a_n) = 0\)
• \(x^3 - 6x^2 + 11x - 6 = (x-1)(x-2)(x-3)\)
• Victor knows target polynomial \(t(x)\) which are cofactors in \(p(x)\)
• Ex: \(t(x)=(x-1)(x-2)\) and \(p(x) = t(x) h(x)\), where \(h(x)\) is some arbitrary polynomial, here \((x-3)\)

Note:
In a better world Victor wouldn't know p(x) on its own, only Peggy would
Then Peggy would prove it
Because of fundamental theorem of algebra, can factor polynomial into product of linear factors
Can express p(x) as such
Instead of Victor knowing p(x) it'd know target polynomial t(x) which are cofactors in p(x)

Modified example

1. Victor would evaluate \(t(r)\) and give \(r\) to Peggy
2. Peggy would then calculate \(h(x) = \frac{p(x)}{t(x)}\), evaluate \(p=p(r), h=h(r)\) and give \(p, h\) to Victor
3. Victor would then check that \(p = t \cdot h\), which means that \(t(x)\) is a cofactor to \(p(x)\)

Note:
In this slightly modifed example

A reason to hide

• Peggy knows random value \(r\) Victor chose
• Means Peggy can cheat and not know \(p(x)\)
• Peggy can choose random number \(h\) and set \(p = t(r) \cdot h\) which Victor would accept
• We want to hide \(r\) and \(t(r)\) from Peggy so she can't cheat and break soundness

Note:
In above example Peggy knows \(r\)
This is a problem, Peggy might not know p(x) at all
Instead Peggy can cheat, they can choose random number \(h\) and set polynomial to …
This would pass verification check, despite Peggy not knowing p(x), which breaks soundness

Homomorphic encryption

• Encrypts some number \(x\) with \(E(x)\) so it is hard to find out what \(x\) is
• Different inputs have different different outputs, if \(x \ne y\) then \(E(x) \neq E(y)\)
• If we know \(E(x)\) and \(E(y)\) we can compute arithmetic expressions such as \(E(x+y)\)

Note:
Can think of it as hash with math
Encrypt value and apply arithmetic operations on it
Under certain assumptions, we can think of the modulo operation as a form of encryption. Let's see why.

Modulo, where art thou?

• Starting point: Choose base \(g\) and "encrypt" number by exponentiating \(g\) to it
• Ex: \(g=5\); \(5^3=125\)
• Trivial to find number by dividing by \(5\) until we get to 1: \(\frac{125}{5*3}=1\) where number of steps is the encrypted value, 3

Modular arithmetic

• Use a finite field, e.g. subset of all natural numbers
• Clock arithmetic, 3 o'clock +12h is 3 o'clock
• \(E(v) = g^v \mod n\)

Note:
New encryption function

Different values, same result

• \(5^5 = 3 \mod 7\)
• \(5^{11} = 3 \mod 7\)
• \(5^{17} = 3 \mod 7\)

Note:
Different values will have same result
Hard to figure out what the encrypted value is if order is high enough

Discrete logarithm problem

• DLP: If we choose base \(g\) and order \(n\) right it is very hard to figure out what \(v\) is in \(g^v \mod n\)
• \((\mathbb{Z}_p)^x\) the multiplicative group of integers modulo p, where \(p\) is a prime number
• \(p\) prime, cyclic group; \(g\) generator, generate every element
• Similar exists for elliptic curve cryptography

Note:
This is called the discrete logarithm problem, that essentially says…
In this case we are using this group, the multiplic…
A group is just a set of some elements, integer up to p-1 in this case, and some operation, *,
Since p is a prime it is a cyclic group, and exists g generator that can generate every element in group
Equivalent groups exists for ECC, touch on later

Encrypted operations

• Can encrypt values and perform addition on them: \(E(x+y) = g^{x+y} = g^x \cdot g^y = E(x) \cdot E(y) \mod n\)
• Can't exponentiate encrypted values (next slide)
• Can't multiply two encrypted values, cryptographic pairings
• This is a basic form of HE, with FHE we get arbitrary computation

Note:
Now we have a way to compute E(x+y) from the encrypted values separately
We'll look at dealing with exponentiated encrypted values next
Can't yet multiply encrypted values, will look at pairings later
This is basic HE, also FHE

Encrypted powers

• Idea: Encrypt polynomial by doing each power separately
• To know polynomial means knowing coefficients and its degree
• \(p(x) = x^3 - 3x^2 + 2x\) coefficients are \(1,-3,2\), degree 3
• Prover is given encrypted values: \(E(x), E(x^2), E(x^3)\)

Note:
Can't exponentiate encrypted values, so we encrypt polynomial by doing each power sep
To know polynomial means knowing coefficient and degree
We encrypt each of these terms, so x 1st degree, x 2nd degree, x 3rd degree, and encrypt these powers

Encrypted powers, cont

• We have: \(E(x^3)^1 \cdot E(x^2)^{-3} \cdot E(x)^2 =\)
  \((g^{x^3})^1 \cdot (g^{x^2})^{-3} \cdot (g^x)^2 = g^{1 x^3} \cdot g^{-3 x^2} \cdot g^{2 x} =\)
  \(g^{x^3 - 3x^2 +2x}\)
• We have thus encrypted our polynomial at some \(x\)
• What does our new proof procedure look like?

Note:
We have all these encrypted powers, and when you apply encryption function with coefficients and add together
The result is that our polynomial is encrypted at some x
With that, how does that change our proof procedure?

Victor uses encrypted powers

1. Sample a random secret value \(s\)
2. Encrypt \(s\) for all powers \(i \in {0,1,\ldots, d}\), \(E(s^i) = g^{s^i}\)
3. Evaluate unencrypted target polynomial \(t(s)\)
4. Provide encrypted powers to prover Peggy

Note:
As before, sample some random value
Encrypt s for each term, each power
Evaluate unencrypted target polynomial with s
Provide these encrypted powers to Peggy

Peggy proves

1. Peggy calculates \(h(x)=\frac{p(x)}{t(x)}\) as before
2. Using encrypted powers and coefficients, evaluates \(E(p(s)) = g^{p(s)} = (g^{s^d})^{c_d} \ldots (g^{s^1})^{c_1} \cdot (g^{s^0})^{c_0})\) and \(E(h(s))\)
3. Provides \(g^p\) and \(g^h\) to verifier

Note:
Similar to before, calculate arbitrary polynomial h(x)
Using encrypted powers given by Victor, and apply the coefficients for p(x) polynomial
Do same thing for arbitrary polynomial h(s)
Then we provide these p and h values but in encrypted space to Victor

Victor verifies

• Verifier checks that \(p = t(s) \cdot h\) in encrypted space: \(g^p = (g^h)^{t(s)} \Rightarrow\) \(g^p = g^{t(s) \cdot h}\)
• Proof where Peggy doesn't know \(s\) or \(t(s)\), but could still prove they know \(p(x)\)
• However: possibly for Peggy not to use encrypted powers as intended

Note:
Now Victor is checking that p=t(s)*h, i.e. that t(x) is a cofactor of p(x), but doing so in encrypted space
This is progress! Peggy doesn't know s or t(s) but can use encrypted evaluation
But…

Restrict your polynomials

• Coefficients \(c_i\), \(i=0,1 \ldots d\) in a polynomial act as knowledge
• Requirement: proof based on exponentiation of encrypted power \(E(s^i)^{c_i} = g^{c_i \cdot s^i}\)
• Now Peggy can cheat:
  Use random \(r\), set \(h=g^r\) and \(p=(g^{t(s)})^r\)
  \(g^p = g^{t(s) \cdot h}\) becomes \((g^{t(s)})^r = g^{t(s) \cdot g^r}\)
• Verification check would succeed, despite Peggy not knowing \(p(x)\)

Note:
In zk-SNARKs, we can think of coefficients as representing knowledge
But for that to be the case, we have a requirement - we need the proof to be based on the exponentiation of encrypted powers
That is, our polynomial has to be on the right form
If it isn't, Peggy can cheat, breaking soundness
For example…

Polynomial restriction

• Cheating possible because Peggy can exponentiate to some value other than \(s\)
• Want to ensure we always use encrypted powers of \(s\) and only coefficients are provided
• Can be done with knowledge of exponent assumption (KEA)

KEA - basic idea

• Victor verifier choose a random \(\alpha\)
• Calculate \(a' = a^{\alpha} \mod n\)
• Provide tuple \((a, a')\) to Peggy, who has to exponentiate \((a, a')\) to a random number and reply with a corresponding tuple \((b, b')\)
• Peggy can't reasonably extract \(\alpha\) from \(a'\)

The assumption in KEA

• Only way for Peggy to produce valid \((b, b')\):
  Choose some random \(c\),
  Calculate \(b = (a)^c\), \(b'=(a')^c \mod n\)
  Reply with \((b, b')\)
• Victor verifies: \(b^{\alpha} = b' \Leftrightarrow (a^c)^{\alpha} = (a^{\alpha})^c\)
• Exponent \(c\) must be the same

KEA, cont

• "\(\alpha \text{-shift}\)" useful tool to restrict polynomial, maintain invariant that only coefficients applied to encrypted powers of \(s\), \(g^{c_i \cdot s^i}\)
• For a polynomial with multiple terms, do same and use HE to add together
• Adds one more polynomial restriction verification check for verifier
  Peggy now provides \(g^p\), \(g^h\), \(g^{p'}\) to Victor

Sound, not zero knowledge

• Computationally sound protocol
  Can't convince verifier of a wrong statement
• However: Not zero knowledge
• Zero knowledge: don't want to leak anything about original \(p(x)\) to Victor

Note:
With this, we now have a computationally sound protocol
Can't convince verifier of a false statement
We call it computational because there's a small soundness error, arbitrary small possibility
That Peggy can provide false proof
We can be rigorous about this, quantify it and minimize it, so in practice it isn't something we worry about
Still not ZK - we don't want to leak anything about p(x), let's look at the state of things now

Zero knowledge

• If \(p(x)\) is simple, e.g. coefficients in \(0..10\) range, degree 2 trivial to brute force
• Want secure protocol regardless of number of coefficients or values
• Victor performs following checks:
  • \(p(x)\) has \(t(x)\) as roots: \(g^p = (g^h)^{t(s)}\)
  • polynomial restriction: \((g^p)^{\alpha} = g^{p'}\)

Zero knowledge, cont

• Use same idea as with \(\alpha \text{-shift}\): Peggy chooses random \(\delta\) and exponentiates proof values, introducing randomness
• Verification checks still holds but \(p(x)\) can't be easily brute-forced with \(g^{\delta \cdot p}\) and \(g^{\delta \cdot \alpha p}\)
• Once soundness is sorted we get zero knowledge for "free"
• However: So far, proof is still interactive

Non-interactivity

• Non-interactive: "N" in zk-SNARKs, aka NIZK
• Now: Proof only valid once, if Vinay wants to verify need to start over, Victor can cheat
• Publicly verifiable proofs: prove once, let anyone verify
• Especially attractive with public blockchains like Ethereum

Non-interactivity, cont

• General idea: keep secret parameters public, secure and reusable
• Add a setup phase to compute \(t(s)\) and \(\alpha\) securely
• Use HE? Can't multiply encrypted values, necessary for verification check:
  \(g^p = (g^h)^{t(s)}\), \((g^p)^{\alpha} = g^{p'}\)
• Cryptographic pairings to the rescue
  First, briefly on elliptic curve cryptography

(insert comic relief)

Note:
Silence
Waves to you, the reader, who somehow found this tiny little invisible note, greetings!
Here's a treat: https://www.youtube.com/watch?v=dQw4w9WgXcQ

Elliptic curve cryptography

• ECC used for public-key cryptography, allows for smaller keys with similar security to RSA
• Based on elliptic curves over a finite field, points satisfying: \(y^2 = x^3 + ax + b\), and a "point of infinity" (~\(0\) in normal arithmetic)
• Earlier: Group \((\mathbb{Z}_p)^x\) or \(F_p^x\) DLP is hard, equivalent hardness for \(E(F_p)\) elliptic curves (ECDLP) exists

Note:
ECC … smaller keys than RSA, e.g. 256-bit corresponds to 3072-bit RSA, 10x impact on perf, why people use it now
Earlier had multiplicative group of integers modulo some prime, or over some some finite field modulo p more generally
We have a similar DLP problem for elliptic curves over a finite field, sometimes called ECDLP
How to choose these curves and making them pairing friendly and so on is a whole thing on its own
If interested I recommend checking out djb's Daniel Bernstein work on safe curves, as a starting point

Cryptographic pairings

• Pairing-based cryptography used a lot in modern cryptography
• Multiply encrypted values using bilinear maps
• Mapping between two cyclic groups and some other group: \(e: G_1 \times G_2 \rightarrow G_T\)
• For us, mapping of elliptic curves: \(e(g^a, g^b) = e(g^b, g^a) = e(g, g)^{ab}\), \(a,b \in F_q\) prime order \(q\)
• \(e\) is efficient to compute

Note:
The G_T group is output group, different space
In our case care about EC over finite field, you can "change place" of exponent and basically multiply them
One sloppy way to read this is just to focus on exponent, so in this case we see ab=ba
e pairing operation efficient

Illustration of pairings

Output target group \(G_T\) is in a different space

(from Dan Boneh's talk on cryptographic pairings)

Note:
Illustrate that output group is in a different space, we can't take output and use as input in another pairing
Basically teleported into a different dimension, and unlike Rick and Morty can't easily go back
Finding pairing friendly curves is a problem here, where we want to balance e being efficient to compute
with DLP being hard in the output group

Intermission: Andrew Weil

• Defined first pairings while in jail during WW2
• Suggested mathematicians go to jail
  to be productive
• COVID restrictions maybe not so bad?

Note:
Had pen and paper

Pairings in BLS signatures

• Short signatures that allow for aggregation
• Simple example of pairings
  KeyGen: \(pk=(g_2)^{\alpha}\), \(\alpha\) secret key
  Sign(\(sk\), \(m\)): \(\sigma = H(m)^{\alpha}\)
  Verify(\(pk\), \(m\), \(\sigma\)): \(e(H(m), pk) = e(\sigma, g_2)\),
  both sides equal to \(e(H(m), g_2)^{\alpha}\)

Note:
Very basic and elegant example for pairings
Allows for aggregation, so multiple parties signing results in one signature, used in Eth2
Also very short signatures
…you see in verification that if we substitute pk and sigma, we get alpha as exponent
Recall that we can basically "swap" these, so if sig is valid we get both sides equal to same expression

Pairings, cont

• Can think of output as a new generator \(g_2\)
  \(e(g^a, g^b) \cdot e(g^c, g^d) = g_2^{ab} \cdot g_2^{cd} = g_2^{ab+cd}\)
• Add encrypted products of multiple pairings
• Aside: multi-linear maps hard research problem, \(G \times G \times G \Rightarrow G_T\)
  • If you solve it, Dan Boneh will be your friend for life!
• With pairings, we can do a trusted setup

Trusted setup

• Setup phase before proving and verification
• Starting point: Assume we trust a single entity
• Proof done once, verified many times
• Common reference string: Generate secrets \(s\), \(\alpha\), and encrypted powers of \(s\) with \(\alpha\)-shifts
• Once done, delete raw values, aka toxic waste

Verification with pairings

• CRS generated parameters, two parts:
  Proving key: \((g^{s^i}, g^{\alpha s^i})\), for i in \(0..d\)
  Verification key: \((g^{t(s)}, g^{\alpha})\)
• Verification check with pairings:
  • \(p=t \cdot h\) in encrypted space: \(e(g^p, g) = e(g^t, g^h)\)
  • Polynomial restriction: \(e(g^p, g^{\alpha}) = e(g^{p'}, g)\)

Trusted setup ceremony

• Extend to only trust \(\frac{1}{M}\) with a composite CRS
• Similar to what seen and doing it sequentially, some additional consistency checks, ensure no toxic waste leaks, etc
• Sometimes called a ceremony, elaborated in study of multi-party computation (MPC)
• Join Perpetual Powers of Tau and others

Note:
We can extend this to trusting 1/M
Very similar tools used to do this, have to do it sequentially where output of one step is used as input to next,
Ensuring that each step is used, some additional checks to make sure no toxic waste is leaked
Called toxic waste because…
Can particpate in these yourself … if you don't trust other people, maybe you trust yourself?

Beyond polynomials

• Focused on proving knowledge of a polynomial, how to use for computation?
• Idea: convert program into math formula, turn into set of simple constraints, express constraints as polynomial relationship, and find polynomial that represents constraints
• Peggy proves they know result of secret computation, Victor checks constraints hold

Computation and constraints

• Goal: convert program into set of constraints
• Use variables, constants, binary operations
• Ex: to enforce \(w\) is a binary number we have following constraint \(1 \cdot w \times 1 \cdot w = 1 \cdot w\), valid only for \(w=0\) or \(w=1\)

Arithmetic circuit

Similar to making a computer with logical gates

(From Ariel Gabizon's Explaining SNARKs series)

Multiple constraints

• Can "chain" them with intermediate variables
  \(a \times b = r_1\)
  \(r_1 \times c = r_2\)
• 3 constraints to express \(2 \times 1 \times 3 \times 2\):
  \(2 \times 1 = 2\)
  \(2 \times 3 = 6\)
  \(6 \times 2 = 12\)

Constraint systems

• Real world: many constraints that must hold
• Our constraint system is a Rank 1 Constraint System (RICS)
• Rank 1 is referring to the resulting matrix

Operation polynomial

• Express constraints as operation polynomial \(l(x) \text{ op } r(x) = o(x)\), some \(x=a\) represents evaluation of \(l(x)\), \(r(x)\) and \(o(x)\)
• Want to find operand polynomial that represents left operand for a set of constraints, and same for \(r(x)\) and \(o(x)\)

Note:
We want to express constraints as operation polynomial, which is this equation here: ..
where you have a left and right operand polynomial, a binary operation, and output polynomial
At some x=a the corresponding value in constraint represent evaluation of l(x)
and similar for r(x) and o(x)

Finding operand polynomial

• Using numeric example from before:
  1: \(2 \times .. = ..\), 2: \(2 \times .. = ..\), 3: \(6 \times .. = ..\)
• Evaluating constraints as \(l(a)\) at row \(a\):
  \(l(1) = 2\)
  \(l(2) = 2\)
  \(l(3) = 6\)
• We have three points \((1, 2), (2,2), (3,6)\) the polynomial must goes through

Note:
Previously we had numerical example, and we have left operand, op, right operand, and output
We can look at these constraints as rows,
The first row has 2 in left position, 2nd row as 2, and 3rd row 6
We are looking for a polynomial l that represents the left operand at each row
For example, l(1) here is 2 because the first row has value 2 in the left position
If we do this for each row,
This then gives us 3 points, and those are 3 points which polynomial must go through

Polynomial interpolation

• Use polynomial interpolation to find \(ax^2 + bx + c = y\) that goes through points
• Set of equations with some unknowns, with \(n+1\) points, unique polynomial of degree at most \(n\) exists that expresses this
• Solving, we get \(l(x) = 2x^2 - 6x + 6\)
• Better: Lagrange polynomials, even better: Fast Fourier Transforms (FFT), speed matters with many constraints

Note:
We have some points and we want a polynomial? What do we do? Interpolation!
Want to find equation of this form, basically finding coefficients a,b,c
Recall Fundamental Theorem of Algebra, in this case basic set of eq with some unknowns, and with n+1 points (3) polynomial of at most n (2) degrees exists that expresses
We solve it for a,b,c and get this operand polynomial
In practice, better methods exists like …

Polynomials are flexible

• In practice: Bit more involved, some gotchas with variables, constants, etc, basic idea same
• Polynomials are very flexible, can scale them, compose them, etc
• Do same for \(r(x)\) and \(p(x)\)

Note:
In practice things are a bit more involved, but mostly mechanical, need to take care of variables, constant etc - basic idea same
Polynomials flexible, can…
Same as we did for left operand polynomial do for right and for output polynomials

Succinctness

• No matter how many constraints we have, end up with a single polynomial
• Final proof a few more polynomials, but we "compress" a program into constant form, independent of size of computation
• Where term succinctness, the "S" in zk-SNARKs comes from

Variable polynomials

• Polynomial composition means we can express many additions in a single constraint
• Split up operand polynomial into individual variable polynomials, for variables \(v_i \in {v_1, v_2, \ldots, v_n}\): \(c_l \cdot v_l \times c_r \cdot v_r = c_o \cdot v_o\)
• We thus get constants and additions "for free"
  Ex: \(c_a \cdot a \times c_b \cdot b = c_r \cdot r\); \((a+c) \times b = r\)

Free operations

(From Petkus's "Why and How zk-SNARK Works")

Note:
Here's an illustration of how you get free constants and addition
See L(x) here is composed of 3 curves, for a*la(x) we have l_a polynomial is a at x=1 and 0 at x=2, x=3
This means we can scale it by some constant, eqv for b and c
To do addition, we can take a+c at x=1 curves and add together basically to get L(x)
Hopefully gives some intuition for why constants and additions can be expressed in one constraint

Quadratic arithmetic program

• Variable and target polynomials together called a quadratic arithmetic program
• QAP: Turning computation into polynomials

Where did we end up?

• Before: proof that Peggy knows \(p(x)\)
• Now: Peggy proves they know result of computation, Victor verifies constraints hold
• Difference: Check more polynomials, add a few verifications checks related to variable values and valid operations

Note:
Previously Peggy proved they know a polynomial
Now they instead prove they know result of some computation, and Victor…
Main difference is basically that we have to check a few more polynomials, and add some verification check to variable values and valid operations

Private and public inputs

• Computation C(x, w), x public input, \(w\) witness private input, verifier can supply own input
• Peggy proves they know a witness \(w\) s.t. \(C(x, w) = \text{true}\)
• Example: Victor supply hash of secret \(s\), Peggy prove they have access to \(s\) which hashes to it, without revealing secret \(s\)

Conclusion

• We've looked at the mathematical foundations of zk-SNARKs
• zk-SNARKs just one of many types of ZK-tech, others have different security assumptions (setup, hardness) and performance (proof size, time, etc)

Note:
We looked at what zk-SNARKs are and why they are useful, and looked at the mathematics underlying them
We looked at polynomials, why they are used in zk-SNARKs and their properties, we looked at how to prove we know a polynomial,
we looked at how to hide information with HE
We looked at how we can use the Knowledge Exponent Assumption to ensure soundness, we looked at how we get zk "for free"
We looked at how to make things non interactive and the shape of a trusted setup
We looked briefly at ECC, why we need cryptographic pairings and how they work
We looked at how to go from computation to constraints to polynomials
We looked at how we achieve succinctness by compressing constraints down into polynomial expressions
…
Hopefully this was interesting to you, if you want to learn more I highly recommend check out Petkus 'why and how zksnarks',
Vitalik's writings and Ariel Gabizon for more details

Thanks!

• Questions?
• @oskarth oskarth.com
• @vacp2p vac.dev

Note:
Thank you! Any questions?
You can find me here and on Twitter