# (Very brief) Introduction to VOLE based IZK

#### Recap: What is ZKP?

Given relation $R$, statement $x$ and witness $w$,
Prove $R(x,w) == 1$ without leaking knowledge about $w$

## What is IZK?
-> **I**nteractive **Z**ero-**K**nowledge proofs

### Pros
- No trusted setup
- Fast prover
- Memory efficient
- (Thought to be) Quantum secure

### Cons
- Require interaction
- Designated Verifier*

*_{There exists [new protocol](https://eprint.iacr.org/2023/996) with universal verifier}

---

# What is VOLE?

## OLE: Oblivious Linear Evaluation

\***We can see OLE as a MAC**

## Generate OLE from OT


## VOLE: Vector Oblivious Linear Evaluation


Like OT extension, VOLE can be constructed efficiently with few number of base OT calls then expand to much larger number of VOLE after without calling additional OTs with LPN assumption.
More detail here -> [Realizing VOLE](https://blog.chain.link/realizing-vole/)

---
## How VOLE based IZK works

### Commit to the wire values

### Generate commitment values for each wire in a circuit

1. Prover, Verifier generates commitment values for **input wires** of a circuit and **output wires of each AND (MUL) gate** in a circuit
2. Commitment values of each output wire of XOR (ADD) gates can be calculated based on additive homomorphism of VOLE. -> No need for commitments.

---

### Proving phase

#### To prove circuit $C$ and input $x$ satisfies $C(x) == 1$
1. Prove output wire is 1 -> Prove just opens the commitment of the output wire
2. Prove the consistency of input and output wires of every AND gate -> $w_a ・w_b = w_c$

---

#### Checking AND gates

---

---

### Mask the A and B for ZK
completeness -> additive homomorphism

---

### Batch checking the many gates

How to check n AND gates at once?
-> Take random linear combination of $(A_{i,0}, A_{i,1}, B_i)$ for $i \in \{0..n\}$, then check.

completeness -> additive homomorphism
This is why we need the same $\Delta$ for every commitment.

---

## Quicksilver
[paper](https://eprint.iacr.org/2021/076.pdf)
#### Efficient and Scalable VOLE based IZK protocol
#### -> can prove hundreds millions of gates with 1GB memory.
Proving the multiplication of two 1024 × 1024 matrices, with one thread and 1 GB of memory, only needs 10 seconds and communicates 25 MB. Needs to send only one field element per multiplication gate. Addition gate is free.


---

### Further reading
- [Chainlink research VOLE based ZK blog series](https://blog.chain.link/vole-based-zk/)
- [Quicksilver](https://eprint.iacr.org/2021/076.pdf)
- [VOLE in the head](https://eprint.iacr.org/2023/996)
- [SoK: VOLE based IZK](https://eprint.iacr.org/2023/857.pdf)