SHPlonk
Presentation: https://www.youtube.com/watch?v=yc7sEg1QikU
Introduction
The KZG commitment was introduced in KZG10. The time required for commitment is proportional to the degree of the polynomial, and the commitment consists of a single element, which is for given .
The opening proof for a point is defined as:
Verification is performed using the following equation:
However, when proving over AIR, multiple polynomials need to be opened at and . In PLONK-based schemes that support custom gates, such as Halo2, polynomials must be opened at various opening points in different combinations. One of the efficient methods for proving in batch settings is SHPlonk, which was introduced in BDFG20.
Background
We'll now see how GWC19 opens multiple polynomials at multiple points. Let's start with simple cases.
Opening Multiple Polynomials at a Single Point
Suppose two polynomials, and , are opened at with corresponding values and .
The verifier provides to the prover.
The prover generates the following opening proof :
Where and .
Verification is performed using the following equation:
Where and are commitments of respectively.
This approach is almost identical to opening a single polynomial at a single point, with the only difference being the random linear combination applied to the polynomials before constructing the proof.
Opening a Single Polynomial at Multiple Points
Suppose a polynomial is opened at two points, and , with corresponding values and .
The prover generates the following opening proof :
Where is defined as:
Verification is performed using the following equation:
Where is the commitment of .
There are two key issues with this naive approach:
Increasing parameters: As the number of opening points increases, the required parameters also increase. For instance, in this case, is required.
Expensive group operation in : Operations in are computationally expensive, leading to higher gas consumption in on-chain, and inefficient in recursive proof generation.
To solve these issues, we modify the protocol as follows:
The prover generates 2 opening proofs, and :
Where and .
The verifier uses to verify the following equation:
The verifier can obtain by computing and respectively.
Proof.
By extracting the exponent components, it can be confirmed that the verification equation holds.
Now the number of required parameters is now constant, and the group operations in are eliminated.
Opening Multiple Polynomials at Multiple Points
In GWC19, a method that combines the previous techniques is proposed. Consider the following scenario:
is opened at with value .
is opened at with values .
is opened at with values .
The verifier provides to the prover.
The prover generates 2 opening proofs, and :
Where and .
Verification is performed with using the following equation:
The verifier can obtain by computing and respectively, where are the commitments of .
If there are polynomials of degree , and each polynomial is opened at points, the following holds:
size:
stands for "structure reference string".
Prover work:
To compute each division in , it takes operations.
To compute each proof , it takes operations.
Proof length:
Verifier work:
To compute all of , it takes operations.
Here, represents scalar multiplication in , represents addition or multiplication in , and denotes a pairing operation.
SHPlonk enables a smaller proof length and faster verifier work for this case.
Protocol Explanation
Version 1
To illustrate this scheme, let's use the same example as before. If we group the opening points, we can form two sets: and . The complete set of opening points is then .
The zero polynomial on is defined as:
The opening proof is constructed as follows:
The verifier provides to the prover.
The prover computes as follows:
Where and are defined as follows:
To verify the opening proof , the following steps are performed:
Compute and using :
Verify using the following equation:
The verifier can obtain by computing and respectively, where are commitments of .
Proof.
Extracting the exponent components from the above equation, we obtain:
Thus, the verification equation holds.
If there are polynomials of degree , and each polynomial is opened at points, the computational costs are as follows:
The number of opening sets :
size:
Prover work:
This doesn't account for computation of each , since they are normally small operations.
To compute all of , it takes operations.
To compute each , it takes operations.
To compute a proof , it takes operations.
Proof length:
Verifier work:
To compute all of , it takes operations.
To compute , it takes operations.
To compute each , it takes operations.
Here, represents scalar multiplication in , represents addition or multiplication in , and denotes a pairing operation.
Now the same issues mentioned in Opening a Single Polynomial at Multiple Points arise again. Since is the primary cause of these issues, we need to devise a more efficient approach—one that treats the opening as if it were occurring at a single point rather than points.
During the presentation, BATZORIG ZORIGOO asked a great question: "What happens if all polynomials are opened at ?" Since this simplifies to 1, both prover and verifier work can be reduced. However, there are two main issues:
Prover Complexity: The prover must evaluate the polynomials at every point in , which increases the number of opening points to .
ZK Proof Size: The ZK proof size increases because it must include all the opened values.
It's important to distinguish between two types of proofs here. The Proof mentioned earlier refers specifically to proving polynomial openings. However, in this context, the ZK Proof not only includes the opening proof but also contains commitments and the opened values themselves.
Version 2
Version 2 addresses the issues from the previous approach by introducing one additional proof.
The opening proofs are constructed as follows:
The verifier provides to the prover.
The prover computes as follows:
Where is defined as:
where and are defined as follows:
The verifier provides to the prover.
The prover computes as follows:
Where is defined as:
Here, is defined as:
The polynomial is crucial in solving the issues from the previous approach. Unlike , which vanishes at multiple points, this now vanishes at single point at because:
To verify the opening proofs, the verifier checks the following equation:
The verifier can obtain as follows:
Where are commitments of .
Proof.
Extracting the exponent terms from the above equation, we obtain:
Thus, the verification equation holds.
If there are polynomials of degree , and each polynomial is opened at most points, the computational costs are as follows:
The number of opening sets :
size:
Prover work:
To compute all of , it takes operations.
To compute each , it takes operations.
To compute and , it takes operations.
To compute , it takes operations.
To compute a proof , it takes operations.
Proof length:
Verifier work:
To compute all of , it takes operations.
Here, represents scalar multiplication in , represents addition or multiplication in , and denotes a pairing operation.
Optimization on Version 2.
When constructing , it can be "normalized", to save one of the scalar multiplications like below.
Then, the verification logic is changed accordingly:
The verifier can obtain as follows:
Notice that the rightmost part of the equation doesn't have scalar multiplication any more.
Conclusion
By summarizing the key metrics in the following table, we can see that SHPlonk demonstrates superior efficiency compared to GWC19.
GWC19
SHPlonk version 1.
SHPlonk version 2.
SHPlonk offers a more efficient proof system, balancing prover and verifier costs while keeping proof sizes minimal. Depending on the use case, Version 1 is preferable for minimizing proof length, whereas Version 2 provides a more scalable solution with constant parameters and a fixed number of pairing operations while removing scalar multiplications in .
References
Last updated