*Disclaimer, I do not know enough yet

###### tags: `zero-knowledge`

# Zk notes
Proof that a computation has been carried out correctly

Flow, Proof -> hash -> zk snark

# Proof models* [link](https://www.youtube.com/watch?v=KjkIQLJk4eQ&t=914s&ab_channel=ZeroKnowledge)
- PCP (probabiility checkable proof, non interactive, with oracle(oracle means able to query the proofs)) (not practical due to large proofs)
- IP (interactive proofs) (interactive and verifier can query randomly)
- IOP (interaactive oracle proofs) (interactive with oracle and random) used by the majority (able to convert to noninteractive with the help of [fiat shamir](https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic))
- MIP (multi interactive proof) (not used yet? how to ensure multi party prover does not collude seems to be the question in everyones mind, or no good compiler to convert this to snark)

# Hash Function

## Prover and verifier
- Prover will try to compute the equation/problem or whatever (provers are very powerful and it is assumed that we do not need to care of how heavy things get. limit to pspace?)
- Verifier will ensure that the proofs by the provers are can be accepted at a very high probability (refer completeness and soundness). Verifier are generally weaker in computational power

## Proofs have to have:
Completeness - Able to generate proofs when statemnt is true
Soundness - Unable to generate false proof at a high probability
Zero knowledge - verifier does not need to know the inputs and computation

## General Pinochio explanation
Step 1: Generate computation
Step 2: Flatten the computation that is similar to
<img src='https://i.imgur.com/xSnQLq8.png' width=300>
Step 3: Create R1CS (another reduction) This 3 vectors bascially represents our computation.
<img src='https://i.imgur.com/NT4fGah.png' width=400>
Step 4: Convert to QAP (a form of polynomial, mainly using Lagrange polynomial) (H(x) will be the prove of computation, however the prover will need to hide it)
<img src='https://i.imgur.com/iuM1mVk.png' width=600>
Step 5: Hiding will involve cryptographic hash function.Will need a trusted Setup. And the 'toxic waste (used in the trusted setup)' needs to be discarded without anyone knowing about it. As by knowing the secret used to setup, the prover has the ability to cheat
Step 6: Create pairings. Using eliptical curve in finite field prime as it allows us to do (multiplication, summation, division,... all the normal math rules. rule of finite field in a prime number).

## Zk-Stark prereq
knowledge of FRI and deep FRI which in turns require knowledge on Fourier Transform and FFT (to read about)

## References:

Link to my other cryptography notes
https://hackmd.io/iW8SRqjoTxaqOXb-SPsyDg

Zk snark article directory by Mina Protocol:
https://minaprotocol.com/blog/a-guide-to-zk-snarks

What is trusted setup and toxic waste in ZCash

Brief math explanation of eliptical curve and EC on finite field (takeaway, its hard to compute discrete log in finite field, refer to cloudflare link for simpler explanation of RSA and ECSDA)
https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627

Construction of commitment from a problem, uses Pinochio (R1CS, QAP)
https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649
https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6

Another Pinochio Protocol Explanation
https://www.zeroknowledgeblog.com/index.php/the-pinocchio-protocol

Zk snark (polynomial commitments, hash function for privacy)
https://vitalik.ca/general/2021/01/26/snarks.html

ZCash link(no pairing, no trusted setups) (to read)
https://vitalik.ca/general/2021/11/05/halo.html

Anatomy of Stark (to read)
https://aszepieniec.github.io/stark-anatomy/

Plonk article by Vitalik
https://vitalik.ca/general/2019/09/22/plonk.html