# zk-SNARKs

**Zero-Knowledge Succinct Non-interactive ARguments of Knowledge.**

Used to verify the correctness of computations without having to execute them and you will not even learn what was executed - just that it was done correctly.

**Encoding as a polynomial problem**

The program needs to be compiled into a quadratic equation of polynomials: `t(x)h(x) = w(x)v(x)`

. Equality holds only if program is computed correctly; prover wants to convince verifier of this equality.

**Succintness by random sampling**

The Verifier chooses a secret evaluation point `s`

to reduce the problem from multiplying polynomials to multiplcation/equality check on numbers (i.e. `t(s)h(s) = w(s)v(s)`

). This reduces proof size and verification time.

*the sizes of the messages are tiny in comparison to the length of the actual computation*

**Homomorphic encoding/encryption: encryption function**

`E`

, has some homomorphic properties allowing the prover to compute `E(t(s))`

, `E(h(s))`

, `E(w(s))`

, `E(v(s))`

without knowing `s`

, just `E(s)`

.

**Zero knowledge**

Prover permutes the values `E(t(s))`

, `E(h(s))`

, `E(w(s))`

, `E(v(s))`

by multiplying by some number so the verifier can check the structure without knowing the actual values.

*during the interaction, the verifier learns nothing apart from the validity of the statement. The verifier especially does not learn the witness string - we will see later what that is exactly.*

of Knowledge: it is not possible for the prover to construct a proof/argument without knowing a certain so-called witness (for example the address she wants to spend from, the preimage of a hash function or the path to a certain Merkle-tree node).

**Quadratic Span Problems/Programs**

A Quadratic Span Program consists of a set of polynomials and the task is to find a linear combination of those that is a multiple of another given polynomial

**TO BE CONTINUEDâ€¦**

## Relevant Articles

- https://vitalik.ca/general/2019/09/22/plonk.html
- https://medium.com/starkware/hello-cairo-3cb43b13b209