# PCS

A polynomial commitment scheme allows a *prover* to commit to a polynomial $p(X)$, later on, the prover can compute openings to prove to the *verifier* that the commited polynomial can be evaluated to a claimed value $y$ at a certain point $x$, i.e. $y = p(x)$.

A polynomial commitment scheme should be:
- **binding**: once a polynomial is commited, it cannot be altered
- **hiding**: the verifier learns nothing about the polynomial beyond what is revealed in the proofs

# Comparison of IPA, FRI, and KZG Commitment Schemes

| **PCS** | **IPA** | **FRI** | **KZG** |
| ------------------------------------------------------------------------------- | --------------------------------------------------------------------------------------------------------------------------------------------------- | ------------------------------------------------------------------------------------------------------------------ | ------------------------------------------------------------------------------------------------------- |
| **Trusted Setup** | <span style="color:green">Not required. </span> | <span style="color:green">Not required. </span> | Required |
| **Underlying Cryptography** | Rely on ECC. <span style="color:red">Requires a special cycle of elliptic curves (e.g., Pasta curves) for recursion. </span> | Rely on Reed-Solomon codes. <span style="color:green">Not rely on ECC. </span> | Rely on ECC (e.g., Elliptic Curve Pairings). |
| **Proof Size** |- <span style="color:orange">Small when recursion is used. </span> <br> - <span style="color:red">grows with circuit size otherwise. </span> | <span style="color:red">Larger proof sizes compared to IPA and KZG. </span> | <span style="color:green">Small, constant-sized proofs. </span> |
| **Verification Time** | Linear in circuit size if recursion is not used. |<span style="color:red"> Larger verification time compared to IPA (recursed) and KZG. </span> | <span style="color:green">Constant, highly efficient verification. </span> |
| **Quantum Resistance** | No. | <span style="color:green">Yes </span> | No |
| **Applicability to zk-Rollups (on-chain verification is executed on Ethereum)** | Inefficient due to linear verification scaling. (the efficient recursive version relied on Pasta curves are currently not supported on Ethereum.) | Inefficient due to larger proof sizes and slower verification. | <span style="color:green">Best suited due to constant-sized proofs and fast verification. </span> |

In summary:
| **PCS** | **IPA** | **FRI** | **KZG** |
| ------------------------------------------------------------------------------- | --------------------------------------------------------------------------------------------------------------------------------------------------- | ------------------------------------------------------------------------------------------------------------------ | ------------------------------------------------------------------------------------------------------- |
| **Advantages** | - No trusted setup required. <br>- Efficient recursive composition when using Pasta curves. | - No trusted setup required. <br>- Not rely on elliptic curve cryptography.<br>- Fast proof generation and quantum resistance. |- Small proof size and fast verification time, even for large circuits.<br>- Suitable for zk-rollups due to scalability.|
| **Drawbacks** | - Requires Pasta curves for recursion, which are not efficiently supported on Ethereum. <br> - Without recursion, proof verification time grows linearly with circuit size, making it infeasible for large circuits like zk-rollups. | Large proof sizes and slow verification. | Requires a trusted setup, which can be a potential security risk if not done securely. |

# References
1. [KZG in Practice: Polynomial Commitment Schemes and Their Usage in Scaling Ethereum](https://scroll.io/blog/kzg)
2. [Proto-Danksharding](https://notes.ethereum.org/@vbuterin/proto_danksharding_faq#Couldn%E2%80%99t-we-use-some-other-commitment-scheme-without-a-trusted-setup)