# KZG Commitments Made Easy: Trusted Setup, Proofs, and Verification

The KZG (Kate–Zaverucha–Goldberg) commitment scheme is a cryptographic method for **locking a polynomial in a secure way**. Once you lock it, you can later **prove facts about that polynomial without revealing the polynomial itself**. Think of it like sealing a document in a tamper-proof envelope: everyone can verify that the contents are consistent, but no one can see what’s inside. It works using advanced mathematics based on **elliptic curves**, which makes the commitments **small, fast to verify, and secure**. This efficiency is what makes KZG especially useful in blockchain systems.

In Ethereum, KZG is an important building block for recent and upcoming upgrades. It helps the network **verify data quickly and securely**, while supporting better **scalability and privacy**. Because of these properties, KZG is widely used in modern cryptographic proving systems and plays a key role in making blockchains more efficient.

## Motivation — ZK-SNARKs

Learning about **Polynomial Commitment Schemes (PCS)** is important because they are a core building block of **ZK-SNARKs**. ZK-SNARKs are cryptographic techniques that let one person (called the prover) convince another person (called the verifier) that they know some information - such as a number or a solution - **without revealing the information itself**.

This works by combining two ideas:

- **Polynomial Commitment Schemes (PCS)**, which securely commit to polynomials, and
- **Interactive Oracle Proofs (IOPs)**, which define how proofs are structured and checked.

In simple terms, a modern ZK-SNARK is built by putting these together: **Modern ZK-SNARK = Functional Commitment Scheme + Compatible Interactive Oracle Proof (IOP)**. This combination makes proofs small, fast to verify, and privacy-preserving.

## Use Cases in the Ethereum Ecosystem

The KZG commitment scheme has become a very important building block in the Ethereum ecosystem. It plays a key role in Proto-Danksharding and its future upgrade, Danksharding, and is widely used in Zero-Knowledge (ZK)–based systems. KZG allows Ethereum to verify large amounts of data efficiently without revealing the actual data, which is essential for scalability and privacy.

### Proto-Danksharding (EIP-4844)
Proto-Danksharding aims to reduce the cost of posting data on Ethereum Layer 1 for rollups. It introduces blob-carrying transactions, which can include large data blobs. Instead of storing the full data on-chain, Ethereum only stores a KZG commitment to the blob. This makes data verification cheap while keeping the system scalable.

### Data Availability Sampling (DAS)
KZG-based Polynomial Commitment Schemes enable Data Availability Sampling, an important part of Ethereum’s scaling roadmap. With DAS, validators can check that data blobs are available and correct without downloading the entire data. This makes large-scale data handling practical for Danksharding.

### PSE’s Summa – Proof of Solvency
The Ethereum Foundation’s PSE (Privacy & Scaling Explorations) project Summa uses KZG commitments to build a Proof of Solvency system. This allows exchanges and custodians to prove that their total assets are greater than their liabilities without revealing individual user balances, preserving user privacy.

### Scroll zkRollups
Scroll, a zkEVM-based Layer 2 solution, uses KZG to commit to sets of polynomials that represent computations. Verifiers can then ask for polynomial evaluations at random points to check that the computation was done correctly.

### Jellyfish
Jellyfish uses KZG commitments during its polynomial commitment phase. It takes advantage of the homomorphic properties of KZG, allowing efficient evaluation of polynomials at chosen points without revealing the polynomial’s coefficients.

### Hyperplonk
Hyperplonk uses multi-linear KZG commitments, showing that KZG can also be applied to proof systems that rely on multi-linear polynomials, not just single-variable ones.

## Goal

Now that we are motivated to learn Polynomial Commitment Schemes (PCS), let’s clearly define the problem we want to solve using the KZG scheme. Assume we have a polynomial (or function)

$$
f(x) = f_0 + f_1 \cdot x + f_2 \cdot x^2 + … + f_t \cdot x^t
$$

The degree of this polynomial is t, and the values $f_0, f_1, …, f_t$ are its coefficients. The main goal of the KZG schemeis this: we want to prove that we know this polynomial without revealing the polynomial itself, meaning we do not reveal its coefficients.

In practice, instead of revealing the full polynomial, we prove something more specific and smaller. We prove that we know the value of the polynomial at a particular point.

That is, for some value $x = a$, we prove knowledge of: $f(a)$

This allows someone else to verify our claim without learning the polynomial, which is exactly what KZG is designed to achieve.

## Prerequisite Knowledge

Before understanding the **KZG scheme**, there are a few basic ideas we need to know. The good news is that we **do not need deep mathematics**. A simple, engineering-level understanding - similar to high school math—is enough. The goal is to build intuition so we can follow how the KZG protocol works, without getting stuck in complex theory.

### Modular Arithmetic

Modular arithmetic is easiest to understand using an **analog clock**. On a clock, after 12 comes 1 again. If it is 10 o’clock and you add 5 hours, you don’t get 15 - you get 3. This is because the clock works modulo 12.

In the same way, modular arithmetic means:

- Numbers *"wrap around"* after reaching a fixed limit (the modulus).
- We still use normal operations like addition, subtraction, multiplication, and division.
- After each operation, we reduce the result using the modulus.

For understanding KZG, this clock-style intuition is enough. Just remember: **numbers don’t grow forever - they loop back around**, just like hours on a clock.

## Finite Field of Order Prime p

A finite field of order prime $p$, written as $Fₚ$, is a small and well-defined set of numbers where we can safely do all normal math operations - addition, subtraction, multiplication, and division (except by zero)—and everything still works as expected. The word "**order**" simply means how many elements are in the field. Since p is a prime number, the field contains exactly *p* elements.

### How $Fₚ$ Is Formed:

The most common way to build $Fₚ$ is by:
- Taking all integers
- Dividing them by $p$
- Keeping only the remainders

This gives us the set:
$\{0, 1, 2, …, p−1\}$
#### Example: $p = 5$

The finite field is:

$F_5 = {0, 1, 2, 3, 4}$

In this field:
- $4 + 3 = 7,\; 7 \equiv 2 \pmod{5}$
- $3 \times 4 = 12 \equiv 2 \pmod{5}$

All results **wrap around** once they reach $5$. This "wrap-around" behavior is exactly like modular arithmetic and is a key property of finite fields.

### Wrap-Around Property

In $Fₚ$, numbers behave as if they reset after reaching $p − 1$. This guarantees that results always stay inside the field, which is crucial for cryptographic systems like KZG.

#### Addition and Multiplication View

When defining a finite field, we often specify:
- The set $(F_P)$
- The operation we are focusing on
- $(F_P, +)$ → field under addition
- $(F_P*, ×)$ → field under multiplication

Here, $Fₚ*$ means $F_P$ without the element $0$. This is necessary because:
- Division requires a **multiplicative inverse**
- Zero does **not** have an inverse

By removing zero, every remaining element has an inverse, which satisfies the rules required for a proper field structure.

## Group

A Group is similar in spirit to a **finite field**, but with one key difference: a group has **only one arithmetic operation**, not two. That operation is usually either **addition** or **multiplication**.

Just like a finite field, a group must follow certain rules:
1. There is an **identity element**
- $0$ for addition
- $1$ for multiplication
2. Every element has an **inverse**
- For addition: an element that adds to give $0$
- For multiplication: an element that multiplies to give $1$
3. The operation is **closed** (results stay inside the set)
4. The operation is **associative**

### Group Notation

- $(G, +)$: This represents a group where **addition** is the group operation.
- $(G*, ·)$: This represents a group where **multiplication** is the group operation.

The $*$ symbol means we **exclude the zero element**. This is necessary because zero doesnot have a multiplicative inverse, and division by zero is **not** allowed.

### Key Difference from Finite Fields

- Finite Field → has **two operations** (addition and multiplication)
- Group → has **only one operation**

Even with this limitation, groups are extremely powerful and form the foundation of many cryptographic systems, including KZG commitments.

## Generator of a Group

A **generator** is a special element of a group that can produce **every other element of the group** by repeatedly applying the group’s operation (addition or multiplication). In simple words: if you keep combining a generator with itself, you eventually get **all elements of the group**.

### Mathematical Idea

If we have a group $(G, ·)$ and an element $g ∈ G$, then $g$ is called a **generator** if:

- Repeating the group operation on $g$ $(\text{like } g, g^2, g^3, \ldots)$ produces every element in $G$.
- For finite groups, this repetition cycles through all elements before returning to the identity.

This idea is best understood through examples.

### Generator of an Additive Group

Consider the additive group:

$(G_7, +)$ with elements $\{0, 1, 2, 3, 4, 5, 6\}$ and all operations done **modulo** $7$.

This is a valid group because:
- **Closure**: Adding any two elements (mod 7) stays inside the set
- **Associativity**: $(a + b) + c = a + (b + c)$
- **Identity**: $0$ (adding $0$ changes nothing)
- **Inverse**: Every element has an additive inverse
- Example: $3 + 4 = 7 \equiv 0 \pmod{7}$

#### Choosing a Generator

Since the group has prime order $(7)$, every non-zero element is a generator. Let’s choose $g = 1$.

Repeated addition of $1 \pmod{7}$:

$1 = 1$
$1 + 1 = 2$
$1 + 1 + 1 = 3$
$1 + 1 + 1 + 1 = 4$
$1 + 1 + 1 + 1 + 1 = 5$
$1 + 1 + 1 + 1 + 1 + 1 = 6$
$1 + 1 + 1 + 1 + 1 + 1 + 1 = 7 \equiv 0 \pmod{7}$

We generated **all elements of the group**, so $1$ **is a generator** of $(G_7, +)$. The same works for $2, 3, 4, 5,$ or $6$ - this is a special property of additive groups with prime size.

### Generator of a Multiplicative Group

Now consider the multiplicative group:

$(G_7*, ·)$ with elements $\{1, 2, 3, 4, 5, 6\}$ under multiplication **modulo** $7$. Zero is excluded because it has **no multiplicative inverse**.

This group satisfies:
- **Closure**: Multiplication (mod $7$) stays in the set
- **Associativity**: $(a · b) · c = a · (b · c)$
- **Identity**: $1$
- **Inverse**: Every element has a multiplicative inverse
- Example: $3 \cdot 5 = 15 \equiv 1 \pmod{7}$

#### Testing for Generators

Try 2:
- $2^1 = 2$
- $2^2 = 4$
- $2^3 = 8 ≡ 1 \pmod{7}$

We returned to $1$ **too early**, without generating all elements. So $2$ **is not a generator**.

Now try $3$:
- $3^1 = 3$
- $3^2 = 2$
- $3^3 = 6$
- $3^4 = 4$
- $3^5 = 5$
- $3^6 = 1 \pmod{7}$

Here, we generated **all elements before returning to $1$**. So **$3$ is a generator** of $(G_7*, ·)$. You can similarly verify that $5$ is also a generator of this group.

## Why Primes Are Used for Modulo Operations in Fields

Using a **prime number** as the modulus when defining a finite field makes the mathematics clean, reliable, and efficient. This is why prime fields are widely used in cryptography and systems like KZG. Below are the key reasons.

1. **Well-Defined Division**

In a finite field, every non-zero number must be divisible. When the modulus is a prime p, every number in $\{1, 2, 3, …, p−1\}$ has a multiplicative inverse modulop. This means division always works. If the modulus is not prime, some numbers cannot be divided, which breaks the field structure (except in special constructions like extension fields).

**Example (Prime modulus)**:

Take modulus $7$.

Numbers: $\{1, 2, 3, 4, 5, 6\}$

- Inverse of $3$ is $5$ because $3 × 5 = 15 ≡ 1 \pmod{7}$
- Inverse of $2$ is $4$ because $2 × 4 = 8 ≡ 1 \pmod{7}$

Every non-zero number has an inverse → division always works.

**Example (Non-prime modulus)**:

Take modulus 8.

- Try to find inverse of $2$
$2 \times ? \equiv 1 \pmod{8} \;\; \text{--> (impossible)}$

Division fails → not a field.

2. **Simple Construction**

Prime fields are easy to build. The field elements are just the numbers {0, 1, 2, …, p−1}, and all arithmetic is done modulo p.For non-prime moduli, creating a field requires more complicated mathematics, such as polynomial-based constructions.

**Example**:
For prime $p = 11$:

- Field elements: $\{0, 1, 2, …, 10\}$
- Operations: normal arithmetic followed by "mod 11"

**Example**:
- $9 + 5 = 14 ≡ 3 \pmod{11}$
- $7 × 8 = 56 ≡ 1 \pmod{11}$

No extra structure is needed. For non-prime moduli, simple modulo arithmetic is not enough to form a field.

3. **Guaranteed Field Properties**

A prime modulus guarantees all the required field rules:
- Additive and multiplicative identity elements
- Additive and multiplicative inverses
- Commutative, associative, and distributive laws

With a prime modulus, these properties always hold without exceptions.

**Example (mod 5)**:

- Additive identity: 0 (0 keeps values unchanged)
$3 + 0 = 3$
- Multiplicative identity: 1 (1 keeps values unchanged)
$4 × 1 = 4$
- Inverse exists: (Every non-zero element has an inverse)
$4 × 4 = 16 ≡ 1 \pmod{5}$

All rules hold automatically.

4. **Uniform Multiplication Behavior**

In a prime field, the non-zero elements are evenly distributed under multiplication. Every non-zero value appears exactly once in each row and column of the multiplication table (excluding zero). This regular structure is important for correctness and security.

**Example (mod 7)**:
Multiply by 3:

$3 × \{1, 2, 3, 4, 5, 6\}$
= $\{3, 6, 2, 5, 1, 4\} \pmod{7}$

Every non-zero element appears exactly once. There are no missing or repeated values. This regularity is important in cryptography.

5. **Simpler and Faster Algorithms**

Many algorithms used in cryptography are easier and faster in prime fields. For example, multiplicative inverses can be efficiently computed using the Extended Euclidean Algorithm, without needing complex polynomial arithmetic.

**Example: Finding an inverse**

Find inverse of $7$ mod $11$:

Using Extended Euclidean Algorithm:

- $11 = 1×7 + 4$
- $7 = 1×4 + 3$
- $4 = 1×3 + 1$

So:
- $1 = 4 − 1×3$
- Inverse of $7$ modulo $11$ is $8$.

This works cleanly because $11$ is prime.

6. **Strong Cryptographic Security**

Security assumptions like the Discrete Logarithm Problem are well understood in prime fields. This makes cryptographic systems more predictable and secure. With composite moduli, the structure can introduce weaknesses or unclear security guarantees.

**Example (Conceptual)**
Given:
- $g = 2$
- $p = 11$
- $g^a = 2^7 ≡ 7 \pmod{11}$

Finding $a = 7$ from ${2, 7}$ is difficult at large scales. Prime fields avoid hidden structures that could weaken security, which can happen with composite moduli.

7. **Computational Efficiency**

Certain primes, such as $31$ or primes of the form $2^n − 1$, are well optimized by CPUs. This leads to faster arithmetic operations, which is important for performance-critical cryptographic applications.

**Example**:
For prime $31 = 2^5 − 1$:

- Modulo reduction is cheap:
$x$ mod $31$ ≈ ($x$ & $31$) + ($x$ >> $5$)

This makes arithmetic faster than arbitrary moduli, which matters in cryptographic systems processing millions of operations.

## Cryptographic Assumptions

To make the KZG commitment scheme secure, we rely on two important cryptographic assumptions. We won’t go into formal proofs, but we’ll build intuition for why these assumptions are necessary and what they mean in simple terms.

### Discrete Logarithm Assumption

Suppose:

- $g$ is a generator of a group $Gₚ*$
- $a$ is a value from the finite field $Fₚ*$
- $g^a$ is an element in the group

The Discrete Logarithm assumption says:
> Given $g$ and $g^a$, it is computationally infeasible to find $a$.

In other words:

- Computing $g^a$ from $g$ and $a$ is easy
- Figuring out $a$ from $g$ and $g^a$ is extremely hard

#### Simple Example

Let’s work with small numbers (only for intuition):

- Let $g = 2$
- Let $a = 7$
- Compute $g^a = 2^7 = 128$

Now imagine someone only sees:

- $g = 2$
- $g^a = 128$

Finding **$a = 7$** from this is easy for small numbers, but when these values are very large (as in real cryptography), finding a becomes computationally infeasible.

#### Intuition

Think of **$g$** as a special lock and $a$ as the number of times you turn it. Turning the lock forward a times is simple. But if someone only sees the final position (**$g^a$**), figuring out **how many turns** you made is nearly impossible - even if they know the lock and the rules. This one-way difficulty is what keeps secrets hidden in cryptographic systems like KZG.

### Strong Diffie–Hellman Assumption

Now suppose:
- $g$ is a generator of $Gₚ*$
- $a$ and $b$ are secret values in $Fₚ*$
- We know $g^a$ and $g^b$

The **Strong Diffie–Hellman assumption** says: Knowing **$g^a$** and **$g^b$** does not allow you to learn anything useful about **$g^{ab}$**. That is, **$g^{ab}$** remains indistinguishable and hidden unless you actually know **$a$** or **$b$**

#### Simple Example

Again, using small numbers for intuition:

- $g = 3$
- $a = 4 → g^a = 3^4 = 81$
- $b = 5 → g^b = 3^5 = 243$

Even if someone knows:
- $g^a = 81$
- $g^b = 243$

They still cannot easily compute:
- $g^{ab} = 3^{20}$

In real cryptographic groups, this becomes **infeasible**.

#### Intuition

Imagine **$g$** is a secret ingredient.

- Alice uses her private recipe a and produces **$g^a$**
- Bob uses his private recipe b and produces **$g^b$**

Even if someone sees both **$g^a$** and **$g^b$**, they still **cannot figure out** what happens when Alice’s and Bob’s secrets are combined into **$g^{ab}$**. Knowing the individual results gives **no useful information** about the combined secret.

### Why These Assumptions Matter for KZG

- **Discrete Logarithm** ensures that polynomial coefficients remain hidden
- **Strong Diffie–Hellman** ensures that commitments and proofs cannot be forged or manipulated

Together, these assumptions make KZG:

- Secure against malicious provers
- Binding (you can’t change the committed polynomial)
- Hiding (you don’t reveal the polynomial itself)

They are fundamental to why KZG works safely in cryptographic and blockchain systems.

## Pairing Function

Assume:
- **$g$** is a generator of a group **$Gₚ$***
- **$a$** and **$b$** are elements of the finite field **$Fₚ$***
- **$gᵃ$** and **$gᵇ$** are elements of the group

A **pairing function** is a special mathematical function that takes **two group elements** as input and produces **one element** in another group. It lets us combine elements from groups in a structured and secure way.

Formally, a pairing is written as:

$e : G₁ × G₂ → Gₜ$

This function must satisfy two very important properties: **bilinearity and non-degeneracy**.

### Bilinearity

Bilinearity means that **exponents can move in and out of the pairing in a predictable and reversible way**.

Mathematically:
$$
e(gᵃ, gᵇ) = e(g, g)ᵃᵇ
= e(gᵃᵇ, g)
= e(g, gᵃᵇ)
$$

This property is extremely powerful because it allows us to:
- Combine values inside the pairing
- Verify relationships between exponents without revealing them

This is one of the key reasons pairings are useful in KZG commitments.

### Non-degeneracy

Non-degeneracy means the pairing is not trivial.

Formally:

$e(g, g) ≠ 1$

If pairing the generator with itself resulted in the identity element, the function would be useless. Non-degeneracy ensures that the pairing actually carries meaningful information.

### Symmetric vs Asymmetric Pairings

- If **$G₁ = G₂$**, the pairing is called a **symmetric pairing**
- If **$G₁ ≠ G₂$**, the pairing is called an **asymmetric pairing**

Most modern cryptographic systems (including Ethereum’s KZG usage) rely on **asymmetric pairings** because they are more efficient and secure.

### Intuition for Pairing Functions

Imagine two separate islands:
- One island is full of **Unicorns**
- The other island is full of **Dragons**

Each Unicorn belongs to one group $(G₁)$
Each Dragon belongs to another group $(G₂)$

A **pairing function** is like a magical bridge between the islands.

When:

- One Unicorn and one Dragon cross the bridge together,
- They form a **new magical creature** called a *Dracorn*.

This Dracorn:

- Is unique to that specific Unicorn–Dragon pair
- Lives in a third land $(Gₜ)$

#### Why this matters

Even if you see many Unicorns and Dragons separately, you cannot predict the exact Dracorn they will form unless you know the precise pair.

In simpler terms:
- You take **one key from each of two keyrings**
- Combine them
- Get a **unique lock** that proves which two keys were used - without revealing the keys themselves

### Why Pairings Matter for KZG

Pairing functions allow KZG to:
- Verify polynomial evaluations efficiently
- Check correctness using small proofs
- Preserve secrecy of polynomial coefficients

They enable secure cross-group verification, which is the mathematical backbone of KZG commitments and many advanced cryptographic protocols.

## Properties of Commitments

Commitment schemes are like **digital promises**. They allow someone to commit to a piece of information (a secret message) in a way that **locks it** in without revealing it. Later, the person can reveal the secret and prove that it matches what they committed to earlier.

Here’s the idea step by step:

### Making the Promise (Commitment)

You start with a secret message and use a commitment scheme to create a **commitment**. This commitment is like a sealed envelope - it proves you fixed some value, but it does not show what that value is.

### Keeping It Secret (Hiding)

The commitment **hides the secret message**. Anyone can see the commitment, but no one can learn the secret from it. It’s like locking your message in a chest where only you have the key.

### Proving You’re Honest (Binding)

Once you create a commitment, you **cannot change the secret later** without being detected. This means you are bound to the original message - you can’t swap it for a different one afterward.

### Revealing the Secret

When the time comes, you reveal:
- The original secret message, and
- The information needed to open the commitment

A verifier can then check that the revealed message **matches the original commitment**, confirming that you kept your promise.

The security of the KZG commitment scheme depends on two essential properties: **hiding** and **binding**. The hiding property ensures that the committed polynomial remains completely secret and that no information about its coefficients can be learned from the commitment. The binding property guarantees that once a commitment is made, it cannot be changed or forged later. In KZG, both of these properties are grounded in the underlying cryptographic assumptions of the **Discrete Logarithm** and **Strong Diffie–Hellman** problems. Together, these assumptions ensure that the polynomial stays hidden and that the commitment faithfully represents a single, unchangeable polynomial

## KZG Protocol Flow

Let’s restate the exact problem KZG solves:

> We want to prove that we know the value of a polynomial
> $f(x)$ evaluated at a point $x = a$,
> without revealing the polynomial itself.

KZG achieves this using three roles: a **Trusted Third Party**, a **Prover**, and a **Verifier**.

### Roles in the KZG Scheme

1. **Trusted Third Party (Setup Authority)**

The Trusted Third Party is only involved in the setup phase.
- It chooses a **secret value** $a ∈ Fₚ$
- Using this secret, it generates public parameters (also called the Common Reference String, CRS):

    PP = ⟨ g, a·g, a²·g, … , aᵗ·g ⟩

- The secret value a is then deleted
- The public parameters $PP$ are sent to both the Prover and the Verifier

> ⚠️ Security depends on the secret **$a$** never being revealed after setup.

After this step, the Trusted Party has no further role in proving or verifying.

2. **Prover**

The Prover:
- Chooses a polynomial $f(x) ∈ Fₚ[x]$
- Uses the public parameters PP to compute a commitment to the polynomial

The commitment is:
$$
C_f = 𝑓(a)⋅g
$$ A natural question that comes to mind is: if the secret value a` **is generated and then deleted by the trusted third party during the setup, how is the Prover still able to compute the commitment $C_f$ = 𝑓(a) · g without knowing a**? We will answer this question in the **[Commitment of the Polynomial](https://hackmd.io/YlrNNRVHSs25svYcxNibvg?both#Why-the-Prover-Can-Compute-This)** section, which we will discuss later in this flow, where this exact point becomes clear.

This commitment $𝐶_𝑓$:

- Fixes the polynomial
- Does not reveal its coefficients

When the Prover is asked to prove an evaluation at a point **b**, it:
- Computes the quotient polynomial:

$$
Q_b(x) = \frac{f(x) - f(b)}{x - b}
$$

- Computes a commitment to this quotient:
$$
C_Q = Q_b(a) ⋅ g
$$

3. **Verifier**

The Verifier:
- Receives the public parameters **$PP$**
- Receives the commitment **$C_f$**
- Chooses a challenge point **$b ∈ Fₚ$**
- Receives from the Prover:
- the point **$b$**
- the value $f(b)$
- the commitment $C_Q$

The Verifier then checks a pairing equation:

$$
e(C_f − f(b)·g, g) == e(C_Q, a·g − b·g)
$$ If this equation holds, the Verifier is convinced that:

- The Prover knows a polynomial committed in $C_f$
- The polynomial evaluates to $f(b)$ at point $b$
- The Prover did not cheat

All of this happens **without revealing the polynomial**.

### End-to-End Flow (Step-by-Step)

1. **Trusted Party**
- Chooses secret $a$
- Computes $PP = ⟨g, a·g, a²·g, …⟩$
- Deletes $a$
- Sends $PP$ to Prover and Verifier
2. **Prover**
- Chooses polynomial $f(x)$
- Computes commitment $C_f = f(a)·g$
- Sends $C_f$ to Verifier
3. **Verifier**
- Chooses point $b$
- Asks Prover to open at $b$
4. **Prover**
- Computes $f(b)$
- Computes $Q_b(x)$
- Computes $C_Q = Q_b(a)·g$
- Sends $(b, f(b), C_Q)$ to Verifier
5. **Verifier**
- Checks the pairing equation
- Accepts if it holds

## Trusted Setup

The trusted setup is the first and most sensitive step in the **KZG commitment scheme**. It is done **once**, before the protocol is ever used.

### What Happens in the Trusted Setup

1. A trusted third party chooses a random secret value

$a ∈ Fp$
2. Using this secret, they compute the public parameters (also called the **Common Reference String**, CRS):

$⟨a^0⋅g ,a^1⋅g ,a^2⋅g,… ,a^t⋅g⟩$
3. The secret value $a$ is then deleted forever

This deletion step is **extremely important**.
If anyone ever learns $a$, they could break the security of the entire KZG system.

4. The CRS is sent to:

- the Prover
- the Verifier

After this, the trusted party has **no further role** in the protocol.

### Why Deleting the Secret Matters

The CRS is safe to use only if the secret $a$ is unknown. If $a$ were leaked, an attacker could:

- Forge commitments
- Create fake proofs that still verify

So the security of KZG relies on the assumption that no one knows $a$ after setup.

### How This Works in Practice (MPC Ceremony)

In real systems, the setup **is not done by a single person**. Instead, it is wrapped in a **Multi-Party Computation (MPC)** ceremony:

- Many participants each add their own randomness
- Each participant deletes their secret after contributing
- As long as **at least one participant is honest**, the final secret remains unknown

This makes the setup effectively secure, even if many participants are malicious.

#### One-Time, Reusable Setup

- The trusted setup is done **once**
- The generated CRS is reused every time the protocol runs
- No further trust or interaction with the participants is required

As long as the secrets are forgotten, the system remains secure forever.

#### Powers of Tau

Modern KZG-based systems use a powers-of-tau setup:

- Can involve **hundreds or thousands of participants**
- Security depends on **just one honest participant**
- Considered *"close enough to trustless"* in practice

#### Ethereum and Trusted Setup

Ethereum provides detailed public documentation of its trusted setup ceremonies, explaining how the CRS is generated, verified, and safely reused for KZG-based protocols.

## Initial Configuration

At the start of the KZG protocol, we fix some basic mathematical objects that both the Prover and Verifier will work with.

### Polynomial Selection

The Prover has a polynomial defined over a finite field:

$f(x) = f_0​ + f_1​⋅x + f_2​⋅x^2 + ⋯ + f_t⋅​x^t$

- The coefficients $f_0 , f_1 , … , f_t$ belong to the finite field $Fp$
- The degree of the polynomial is **t**
- We require $t<p$, where $p$ is the order of the field

This is commonly written as:
$$
f(x) ∈ F_p[x]
$$
### Finite Field and Group Setup

- $F_p$ is a finite field of **prime order $p$**
- $G_p$ is an **elliptic curve group** of order $p$
- The group has a **generator** $g$

In practice:
- The prime $p$ is very large
- It is chosen such that $p > 2^k$ where $k$ is a security parameter (this ensures cryptographic security)

### Pairing Function

The Prover also works with a pairing function that satisfies:
- Bilinearity
- Non-degeneracy

The pairing is written as:
$$
e: G_1​ × G_2​ → G_T​
$$ This pairing operates over elliptic curve groups and is a key tool that enables efficient verification later in the protocol. With these components in place, the system is fully prepared to move forward with commitment, proof generation, and verification in the KZG scheme

## Commitment of the Polynomial

Let the commitment to the polynomial $f(x)$ be denoted by $C_f$. You can think of this commitment as being similar to a cryptographic hash: it fixes the polynomial without revealing its coefficients.

### Polynomial and Secret Point

The polynomial is:

$$
f(x) = f_0​ + f_1⋅​x + f_2​⋅x^2 + ⋯ + f_t⋅​x^t
$$ The commitment is defined as the polynomial evaluated at a secret point $a$, multiplied by the group generator $g$:

$$
C_f = f(a)⋅g
$$ Expanding $𝑓(𝑎)$:

$$C_f = (f_0​ + f_1⋅​​a + f_2​⋅​a^2 + ⋯ + f_t​⋅​a^t)⋅g$$

### Expanding the Commitment

Using distributivity, we can rewrite this as:

$$C_f ​= f_0​⋅g + f_1​⋅​​a⋅g + f_2​​⋅​a^2⋅g + ⋯ + f_t⋅a^t⋅g$$

Which can also be written as:

$$C_f ​= f_0​⋅g + f_1​⋅(a​⋅g) + f_2​⋅(a^2​⋅g) + ⋯ + f_t​⋅(a^t​⋅g)$$

### Why the Prover Can Compute This

Even though the Prover does not know the secret value $a$, *they can still compute the commitment*.

This is because the **Common Reference String (CRS)** contains the values:

$$⟨g,a⋅g,a^2⋅g,…,a^t⋅g⟩$$

Using these public values, the Prover simply:

- Multiplies each CRS element by the corresponding coefficient
- Adds them together

This allows the Prover to compute $C_f$ without ever learning $a$.

### Final Step

The Prover sends the commitment $C_f$ to the Verifier.

At this point:
- The polynomial is **fully committed**
- The coefficients remain **hidden**
- The Prover is **bound** to this polynomial for all future proofs

This commitment is the foundation for proving polynomial evaluations in the KZG scheme.

## Opening of the Polynomial

Once the Verifier receives a commitment to a polynomial, denoted by $C_f​$, the next step is to **check a specific value of that polynomial** - without learning the polynomial itself.

### **Step 1: Verifier Chooses a Point**

The Verifier randomly selects a point
$$b ∈ Fp​$$ and asks the Prover to open the polynomial at $𝑥 = 𝑏$.

### What Does “Opening the Polynomial” Mean?

Opening the polynomial at $x=b$ simply means **revealing the value of the polynomial at that point**.

The Prover computes:

$$f(b) = f0 ​+ f_1​​⋅​​b + f_2​⋅​​​b^2+ ⋯ + f_t​​⋅​​b^t$$

Assume this evaluates to:
$$
f(b) = d
$$ Now the Prover must prove to the Verifier that:
- the committed polynomial really evaluates to $d$ at $x = b$,
- **without revealing the polynomial coefficients**.

### Step 2: Constructing the Evaluation Proof

The Prover constructs a **quotient polynomial** $𝑄(𝑥)$ .

#### Why This Works?
Since $𝑓(𝑏) = 𝑑$, the polynomial:
$$f(x) − d$$ has a root at $x = b$.
That means it is divisible by $(𝑥 − 𝑏)$ with no remainder.

#### Quotient Polynomial Definition

$$
Q(x) = \frac{f(x) - f(b)}{x - b} = \frac{f(x) - d}{x - b}
$$

This division works only if $𝑓(𝑏) = 𝑑$.
If the Prover tried to cheat, this would not be a valid polynomial.

### Step 3: Commit to the Quotient Polynomial

Using the CRS, the Prover computes a commitment to $𝑄(𝑥)$ :
$$
C_Q = Q(a) ⋅ g
$$ Just like before:
- The Prover does not know the secret $a$.
- But can compute $C_Q$ using the CRS.

### Step 4: Send the Opening to the Verifier
The Prover sends the tuple:

$$
<b, f(b), C_Q>
$$ That is:
- The evaluation point $b$
- The claimed value $f(b) = d$
- The commitment of the quotient polynomial $C_Q$.

### Why This Is Secure
- If the Prover lies about $f(b)$, the division by (x-b) breaks
- Then $Q(x)$ is not a valid polynomial.
- And the proof will fail verification.

This guarantees:
- **Correctness**: only the true value passes
- **Hiding**: the polynomial stays secret
- **Binding**: the Prover cannot change the polynomial later

## Verification Proof
Let’s walk through how the Verifier checks that the Prover’s claimed value
$$
f(b) = d
$$ is correct - **without knowing the secret $a$ and without learning the polynomial**.

### What the Verifier Knows
At this stage, the Verifier has:
- The polynomial commitment:
$$C_f = f(a)⋅g$$
- The opening point:
$$b∈Fp$$
- The claimed evaluation:
$$ f(b) = d $$
- The commitment to the quotient polynomial:
$$ C_Q = Q(a)⋅g$$

#### Reminder: Commitment Scheme Properties
- **Completeness**
If the statement is true, an honest Prover can always produce a proof.
- **Soundness**
A false statement cannot be proven (a cheating Prover will be caught).

### The Key Polynomial Identity
Recall the quotient polynomial:
$$
Q(x) = \frac{f(x) - d}{x - b}
$$ By construction:
$$
(x−b)⋅Q(x)=f(x)−d
$$ Now evaluate this identity at the secret point $x=a$:
$$
(a−b)⋅Q(a)=f(a)−d
$$ Multiply both sides by the generator $g$:
$$
(a−b)⋅Q(a)⋅g=f(a)⋅g−d⋅g
$$ Substitute commitments:
$$
(a−b)⋅C_Q​=C_f​−d⋅g
$$ This is the core correctness condition.

#### The Problem

The Verifier cannot compute $a−b$ because:
- $a$ is secret
- Only $a⋅g$ is public (from the CRS)

So the Verifier cannot check this equality directly.

#### The Solution: Pairings

We use an elliptic curve pairing:
$$e:G×G→G_T​$$ Key Properties:
- Bilinearity
- Non-degeneracy

### Apply the Pairing
Start with the equality:
$$(a−b)⋅C_Q​=C_f​−d⋅g$$ Apply the pairing with g on both sides:
$$e((a−b)⋅C_Q​,g)=e(C_f​−d⋅g,g)$$ Using bilinearity, move the scalar:
$$ e(C_Q​,(a−b)⋅g)=e(C_f​−d⋅g,g)$$ Rewrite:
$$ (a−b)⋅g=a⋅g−b⋅g $$ So the final verification equation becomes:
$$ e(C_Q​,a⋅g−b⋅g)=e(C_f​−d⋅g,g) $$

### Why the Verifier Can Check This
- The Verifier knows:
- $a⋅g$ (from the CRS)
- $b$ (chosen by the Verifier)
- $g$
- $C_f, C_Q, d$
- The Verifier does not need:
- $a$
- the polynomial coefficients

If this pairing equation holds, the proof is valid.

### Why This Guarantees Soundness
- If the Prover lies about $d=f(b)$:
- $Q(x)$ is not a valid polynomial
- The equality breaks
- The pairing check fails

So:
- True statements always verify (completeness)
- False statements cannot pass (soundness)

#### Full Opening vs Partial Opening
##### Full Opening
- Prover reveals the entire polynomial
- Verifier recomputes the commitment
- Easy to verify, but no privacy

##### Partial Opening (KZG)
- Prover reveals only one value $f(b)$
- Uses an evaluation proof
- Polynomial remains hidden
- Verification is constant-size and efficient

## KZG by Hand — What We Are Doing

The goal is to prove one polynomial evaluation using:
- a small finite field
- simple group arithmetic
- a toy “pairing” function
This helps us see why KZG works.

### Initial Configuration
- Finite Field:
$F_{11} = {0, 1, 2, ..., 10}$
- Group:
$(G_{11},+)$ (additive group mod 11)
- Generator:
$g=2$
- Polynomial chossen by Prover:
$f(x) = 5x^2 + 55x + 11$
- Degree:
$t=2$
- Pairing function (toy):
$e(x, y) = x⋅y$ (mod 11)

> **Important note (conceptual)**:
This is not cryptographically secure, but it does preserve the algebraic structure needed to understand KZG.

### Trusted Setup
- Trusted Party chooses secret:
$a=3$
- CRS generation:
$<g, a⋅g, a^2⋅g>$ = $<2,6,7>$ (mod 11)
- Secret $a$ is deleted
- CRS is sent to Prover and Verifier

### Commitment of the Polynomial
Commitment definition:
$$
C_f = f(a) ⋅ g
$$ But the Prover computes it without knowing $a$, using the CRS:
$$
C_f = 11 ⋅ g + 55 ⋅ (ag) + 5 ⋅ (a^2g)
$$ Substitute values:
$$
= 11 \cdot 2 + 55 \cdot 6 + 5 \cdot 7
= 22 + 330 + 35
= 387 \equiv 2 \pmod{11}
$$ So:
$$ C_f = 2 $$

### Opening the Polynomial
Verifier challenges:
$$b=4$$
Evaluate:
$$f(b) = f(4) = 5 \cdot 4^2 + 55 \cdot 4 + 11 = 80 + 220 + 11 = 311 ≡ 3\pmod{11} $$ So:
$$f(b) = d=3$$

### Quotient Polynomial
By construction:
$$
Q(x) = \frac{f(x) - d}{x - b}
$$ You correctly compute:
$$
Q(x) = \frac{5x^2 + 55x + 11 - 3}{x - 4} = \frac{5x^2 + 55x + 8}{x - 4} = 5x +75 \text{ (mod } 11) ≡ 5x + 9
$$ Remainder is zero (as required).
#### Polynomial Division
$$
\begin{array}{r|l}
& \underline{5x + 75 ≡ (5x + 9)(\text{mod } 11)} \\
x - 4 & 5x^2 + 55x + 8 \\
& \underline{5x^2 - 20x + \phantom{8}} \\
& \phantom{5x^2} + 75x + 8 \\
& \underline{\phantom{5x^2} + 75x - 300} \\
& \phantom{5x^2 + 75x} + 308 \\
& \phantom{5x^2 + 75x} ≡ \text{0 } (\text{mod } 11)
\end{array}
$$

### Commitment to the Quotient Polynomial
$$
C_Q = Q(a) \cdot g
$$ Using CRS:
$$
C_Q = 5 \cdot (ag) + 9 \cdot g = 5 \cdot 6 + 9 \cdot 2 = 30 + 18 = 48 ≡ 4 \text{ (mod } 11)
$$ So:
$$
C_Q = 4
$$ Prover sends:
$$
⟨b,f(b),C_Q⟩=⟨4,3,4⟩
$$

### Verification Equation
Core identity:
$$
e(C_Q,a⋅g−b⋅g)=e(C_f−d⋅g,g)
$$
Verifier cannot compute $a$, so uses pairing.
#### Left-hand side
$$
e(C_Q,a \cdot g−b \cdot g)=e(4,6−8)=e(4,-2 \text{ (mod } 11))= e(4,9) = 4 \cdot 9 = 36≡3\text{ (mod } 11)
$$
#### Right-Hand Side
$$
e(C_f-d \cdot g, g) = e(2-6, 2) = e(-4 \text{ (mod } 11), 2 ) = e(7,2) = 7 \cdot 2 = 14 ≡3\text{ (mod } 11)
$$

## Security of KZG

### Why deleting the “toxic waste” matters
The security of the KZG commitment scheme critically depends on deleting the secret value a after the trusted setup. This secret is often called toxic waste because if it ever leaks, the entire security of the scheme collapses.

Let’s see why using your concrete example.

### What Goes Wrong If $a$ Is Leaked

Assume:
- The trusted setup secret is
$$ a=3 $$
- The finite field is
$$ F_{11} $$ Now imagine a malicious Prover somehow learns $a$.

### Two Different Polynomials
The Prover constructs two different polynomials:
$$
f_1(x)=3x^2+5x+7
$$ $$
f_2(x)=2x^2+7x+10
$$ These are clearly not the same polynomial.

### Evaluate Both at the Secret Point

Evaluate both polynomials at the secret point $x=a=3$:
#### First polynomial
$$f_1(3)=3⋅3^2+5⋅3+7=49≡5(mod11)$$
#### Second ploynomial
$$f_2(3)=2⋅3^2+7⋅3+10=49≡5(mod11)$$ So:
$$
f_1(3)=f_2(3)=5
$$

### Why This Breaks KZG
Recall that a KZG commitment is:
$$
C_f=f(a)⋅g
$$ Since both polynomials evaluate to the **same value at the secret point**, they produce the same commitment:
$$
C_{f_1} = C_{f_2}
$$ But the polynomials are different.
This means the Prover can:
- Commit to one polynomial
- Later pretend the commitment corresponds to a different polynomial
- Still pass verification

### What Security Property Is Broken?
This breaks the binding property of the commitment scheme.
Binding means:
> Once you commit to $a$ value, you cannot later change it.

If $a$ is known:
- A Prover can create multiple different polynomials
- All mapping to the same commitment
- And generate fraudulent proofs

At that point, KZG is no longer secure.

### Why Deleting $a$ Fixes Everything

- Knowing $a$ allows solving equations at the secret evaluation point
- Not knowing $a$ makes this computationally impossible
- The Discrete Log assumption ensures you cannot recover $a$ from $a·g$

So as long as:
- $a$ is generated securely
- $a$ is deleted forever
- At least one participant in the setup is honest

## Asymmetric Pairing Functions
An asymmetric pairing is a pairing where the two inputs come from different groups:
$$
e:G_1​×G_2​→G_T​
$$
- $𝐺_1$ and $G_2$ are distinct elliptic curve groups
- $G_T$ is the target group
- $g_1$ is a generator of $G_1$
- $g_2$ is a generator of $G_2$

This is the pairing model used in **real KZG deployments** (for example, in Ethereum), because it is more efficient and secure than symmetric pairings.

### Starting Point: The Core Equality
From the KZG construction, correctness depends on the identity:
$$
(a−b)⋅Q(a)=f(a)−d
$$
This comes directly from the quotient polynomial definition and is **true if and only if** the Prover’s claimed evaluation $f(b) = d$ is correct.

### Move Into the Group $G_1$
We now multiply both sides by the generator $g_1 ∈ G_1$:
$$(a−b)⋅Q(a)⋅g_1 = f(a)⋅g_1−d⋅g_1$$ Using commitments:
- $C_Q = Q(a)⋅g_1$
- $C_f = f(a)⋅g_1$

This becomes:
$$
(a−b)⋅C_Q = C_f −d⋅g_1
$$
At this point:
- All terms are elements of $G_1$
- The equality is correct
- But the Verifier cannot compute $a-b$ because $a$ is secret.

### Apply the Asymmetric Pairing
We now apply the pairing with $g_2 ∈ G_2$:
$$
e((a−b)⋅C_Q​,g_2​)=e(C_f​−d⋅g_1​,g_2​)
$$ This maps both sides into the target group $G_T$.

### Use Bilinearity to Remove the Secret Scalar

By bilinearity of the pairing:
$$
e((a−b)⋅C_Q​,g_2​)=e(C_Q​,(a−b)⋅g_2​)
$$ So we rewrite the equation as:
$$
e(C_Q​,(a−b)⋅g_2​)=e(C_f​−d⋅g_1​,g_2​)
$$ Now expand the scalar multiplication:
$$
(a−b)⋅g_2​=a⋅g_2​−b⋅g_2​
$$ This gives the final verification equation:
$$
e(C_Q, a⋅g_2 - b⋅g_2) = e(C_f-d⋅g_1, g_2)
$$

### Why the Verifier Can Check This

Even though the Verifier does not know $𝑎$:
- $a⋅g_2$ is included in the CRS for $G_2$
- $𝑏$ is chosen by the Verifier
- $g_1, g_2, C_f, C_Q,$ and $d$ are all known

So every term in the pairing equation is either:
- publicly known, or
- provided by the Prover, or
- part of the CRS

This allows the Verifier to fully check the equation without ever learning $𝑎$.

### Why Asymmetric Pairings Are Used in Practice
- More efficient than symmetric pairings
- Smaller CRS and faster verification
- Better security properties on modern curves
- Used by Ethereum KZG (e.g. BLS12-381)

### Unwavering Compactness

The KZG Polynomial Commitment Scheme provides fixed-size commitments and fixed-size evaluation proofs, no matter how large or complex the polynomial is. This means the size of the commitment and the proof does not grow as the polynomial degree increases, making KZG highly space-efficient.

In simple terms, when we commit to a polynomial using KZG, the commitment is always one single group element in the group $G$. Whether the polynomial has a small degree or a very large one, its cryptographic "footprint" stays the same. The same idea applies to evaluation proofs: the proof that shows a polynomial was evaluated correctly is also always of a constant size. This holds true even when verifying multiple evaluations at once in batch mode. Because both commitments and proofs have predictable, fixed sizes, KZG enables efficient storage and verification, which is especially important for real-world cryptographic systems.

## KZG Batch Mode

KZG commitments can also be opened and verified in batches. This means the Prover can prove multiple evaluations at once—whether at multiple points, across multiple polynomials, or a combination of both. This is commonly referred to as batch mode.

### Single Polynomial, Multiple Points
In batch mode, the Verifier asks the Prover to open a single polynomial $f(x)$ at several points.

The Verifier chooses a set of points:
$$
B = \{ b_1, b_2, b_3, \ldots, b_n \}
$$ where $n<t$, and $t$ is the degree of the polynomial $f(x)$.
For each point in $B$, the Prover computes:
$$
f(b_1)=d_1​,f(b_2​)=d_2​,…,f(b_n​)=d_n​
$$ and forms the set:
$$
D = \{d_1​,d_2​,d_3​,\ldots,d_n​\}
$$

### Constructing the Batch Proof
The Prover builds a polynomial:
$$
P(x)=(x−b_1​)(x−b_2​)…(x−b_n​)
$$ Since $n<t$, the polynomial $f(x)$ can be written as:
$$
f(x)=P(x)Q(x)+R(x)
$$ Here:
- $Q(x)$ is the quotient polynomial
- $R(x)$ is the remainder polynomial

This representation always exists; it does not require $f(x)$ to be exactly divisible by $P(x)$.

The Prover sends the commitment to $Q(x)$, denoted $C_Q$, along with the set of points $B$. Optionally, the prover may also send $R(x)$.

### What the Verifier Checks
For every $b_i ∈ B$, the polynomial $P(x)$ evaluates to zero. This means:
$$
f(b_i) = R(b_i)
$$ So the Verifier:
- Checks that the provided values $d_i$ match $R(b_i)$
- Uses these evaluations to reconstruct $R(x)$ (since its degree is less than $n$) using interpolation.

The verfier also computes:
- $P(x)$ and its commitment $C_P = P(a)⋅g$
- $R(x)$ and its commitment $C_R = R(a)⋅g$

### Final Verification Using Pairings:

The key equality to verify is:
$$
f(x)⋅g - R(x)⋅g = P(x)Q(x)⋅g
$$ Evaluated at the secret point $x=a$, this becomes
$$
C_f - C_R = P(a) \cdot C_Q
$$ Even though the Verifier does not know $a$, they can verify this relation using **pairings**:
$$
e(C_f - C_R, g) = e(C_Q, C_P)
$$ If this equality holds, the batch proof is valid.