Degree-Bound Proof for KZG Polynomial Commitments

1. Why Degree-Bound?

Bounding the degree of polynomials is vital for two primary reasons:

• Efficiency: Generating an SRS is computationally expensive and time-consuming. If a user wants to commit to a polynomial of a smaller degree, it's inefficient to generate a new SRS tailored to that degree.

• Universality: Having a universal SRS that can be used for multiple polynomial commitments of varying degrees is extremely desirable. This eliminates the need for trust set up for every new application or every time the polynomial's degree changes.

Thus, by bounding the degree, we can utilize a pre-existing, trusted KZG SRS without going through the process of generating a new one.

2. Protocol Overview

The main crux of this protocol is to bridge the gap between the degree of the polynomial

$f(x)$ and the degree of the SRS,

$D$. Here's how this protocol achieves this:

Protocol Steps:

1. Polynomial Degree Shift: Given a polynomial

   $f(x)$ of degree
   $d$, we create a shifted polynomial
   $f_{\text{up}}(x)$ by elevating the degrees of
   $f(x)$ such that it matches with the higher degrees of the SRS. Effectively,
   $f_{\text{up}}(x)=f(x)\times x^{(D-d)}$.

2. Challenge Generation: The verifier, wanting to ensure the degree of the original polynomial, sends a random challenge number,

   $r$.

3. Opening the Polynomial: The prover evaluates both the original polynomial and the shifted polynomial at the challenge point

   $r$, resulting in
   $f(r)$ and
   $f_{\text{up}}(r)$.

4. Verification:

   • The verifier checks that:
     
     $[f(r)\times r^{(D-d)}=f_{\text{up}}(r)]$
     If this equation holds, it confirms that the original polynomial's degree is as claimed.
   • Furthermore, the verifier also checks the KZG openings for both evaluations to ensure their correctness.

If all these checks pass, the degree-bound proof is considered successful, ensuring that the original polynomial is of degree

$d$ or lower, and utilizing the larger SRS of degree

$D$ was legitimate.