# KZG commitment scheme and it's use in Ferveo

[KZG Paper](https://cacr.uwaterloo.ca/techreports/2010/cacr2010-10.pdf)

## In Ferveo

https://github.com/arkworks-rs/poly-commit/pull/79
https://nikkolasg.github.io/ferveo/fastkzg.html

## Implementations of KZG schemes:
- https://github.com/arkworks-rs/poly-commit/tree/master/src
- https://github.com/sifraitech/rust-kzg
- https://github.com/ralexstokes/kzg

## KZG ceremonies

https://github.com/a16z/evm-powers-of-tau
https://github.com/arnaucube/eth-kzg-ceremony-alt
https://github.com/ethereum/kzg-ceremony-sequencer

## Resources

https://twitter.com/bkiepuszewski/status/1518163771788824576
https://scroll.io/blog/kzg#heading-0

https://hackmd.io/@yelhousni/kzg
https://notes.ethereum.org/@dankrad/kzg_commitments_in_proofs
https://ethresear.ch/t/a-minimum-viable-kzg-polynomial-commitment-scheme-implementation/7675
https://www.youtube.com/watch?v=W1E2CI_u6d0
https://taoa.io/posts/Understanding-KZG10-Polynomial-Commitments
https://alinush.github.io/2020/05/06/kzg-polynomial-commitments.html

https://www.youtube.com/watch?v=J9SOk9dIOCk
https://www.youtube.com/watch?v=bz16BURH_u8&t=1s
https://www.youtube.com/watch?v=dTBy661ubgg
https://www.youtube.com/watch?v=IkNZWJFcfcU
https://www.youtube.com/watch?v=g6s4zpypPT4

## Notes

### https://www.youtube.com/watch?v=g6s4zpypPT4

- We want to succinctly commit to the data and then be able to link certain facts to this data
- 48 bytes - a commitment to a tree that is an elliptic curve point

- Our data = coefficients
- data <== (FFT) ==> blob


- "opening a polynomial" = verryfing a proof






### https://www.youtube.com/watch?v=W1E2CI_u6d0

- for a polynomial $f = f_0 + f_1*x + f_2*x^2 + ...$, commitment $f` = com(f)$
- "opening" = evaluation proof
- $f`: z, f(z), \pi$
- "proof pi that that f(z) returns a correct result for a given z"
- Kate PCS (KGZ)
- PCS - Polynomial Commitment Scheme
- requires trusted setup
- "toxic waste"
- these the parameters are called "common reference string" (CRS), or "structured reference string" (SRS)
- pairing-based, hence short proofs
- Mina/Halo
- inner product-based PCS
- bootleproof-type and bullet-proof-type construcitons
- no trusted setup
- longer proofs

### https://scroll.io/blog/kzg

#### Polynomial interpolation
- Using interpolation to store data vector in the polynomial
- 
- "For example, we could take the 33-dimensional vector $v = [2, 0, 6]$, and represent it as the polynomial $\phi(x) = 4x^2 - 14x + 12ϕ(x)=4x−14x+12$. You can plug in values to verify that indeed $\phi(1) = 2$, $\phi(2) = 0$, and $\phi(3) = 6$"

#### Polynomia commitment schemes

- Commitment schemes
- In a commitment scheme, the commiter commits to a message m by outputting some commitment $c$.
- The commiter can then later reveal the message $m$, and a verifier can validate that indeed the commitment $c$ corresponds to $m$.
- A commitment scheme should have the following properties:
- "binding" - once $c$ is published, it shoudln't be possible to find some other message $m' \neq m$ that also corresponds to $c$
- "hiding" - publishing $c$ should not reveal any information about the underlying message $m$
- _Polynomial_ commitment schemes (PCS)
- In PCS, the commiter commits to a polynomial $\phi$ rather than some arbitrary message $m$w
- They also achieve an additional property: "opening", or proof-verification.
- The commiter should be able to "open" certain evaluations of the commited polynomial without revealing the entire thing
- Example: prove that $\phi(a)=b$
- Very useful for ZKP applications
- An additiona benefit is that $c$ is generally much smaller than the polynomial it represents
- KZG PCS
- Step 1 (Setup):
- Perform one-time trusted setup
- Once this step is completed, other steps can be repeated to commit to and reveal various different polynomials
- Let $g$ be a generator of some pairing-friendly elliptic curve group $G$
- Let $l$ be the maximum degree of the polynomials we want to commit to
- Pick some random field element $\tau \in F_p$
- Compute $(g, g^{\tau}, g^{\tau^2}, ..., g^{\tau^l})$ and release it publicly
- Note: $\tau$ should not be revealed - it is a secret parameter of the setup, and should be discarded after the setup ceremony such that nobody can figure out its value
- Step 2 (Commit to polynomial):
- Given a polynomial $\phi(x) = \sum_{i=0}^l \phi_{i}*x^{i}$
- Compute and output commitment $c=g^{\phi(\tau)}$
- The commiter cannot compute $c=g^{\phi(\tau)}$ directly since they don't know \tau
- Instead, they can compute it using the output of the setup $(g, g^{\tau}, g^{\tau^2}, ..., g^{\tau^l})$:
- $\prod_{i=0}^l(g^{{\tau}^{i}})^{\phi^{i}} = g^{\sum_{i=0}^l \phi_i*\tau^i} = g^{\phi(\tau)}$
- Step 3 (Prove an evaluation):
- Given an evaluation $\phi(a) = b$
- Compute and output proof $\pi = g^{q(\tau)}$
- Where $q(x) := \frac{\phi(x) -b}{x-a}$
- This is called the "quotient polynomial"
- Note that such $q(x)$ exists if and only if $\phi(a) = b$. The existance of this quotient polynomial therefore serves as a proof of the evaluation.
- Step 4 (verify an evaluation proof):
- Given a commitment $c = g^{\phi(\tau)}$, and evaluation $\phi(a) =b$, and a proof $\pi = g^{q(\tau)}$
- Verify that $e(\frac{c}{g^b}, g) = e(\pi, \frac{g^{\tau}}{g^a})$, where $e$ is a non-trivial billinear mapping
- Some algebra shows that this is equivalent to checking that the property in step 3 holds at $\tau$:
- $q(\tau) = \frac{\phi(\tau) - b}{\tau - a}$
- The billinear mapping enables us to check this property without knowing the secret setup parameter \tau
- Once the verification is complete, we can conclude that (with overwhelmingly high probability) the quotient polynomial is correct, and therefore that the evaluation is correct.
- More resources
- https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html
- https://alinush.github.io/2020/05/06/kzg-polynomial-commitments.html

### https://www.youtube.com/watch?v=IkNZWJFcfcU