Different Polynomial Commitments at different opening points
We have already established that we can group together the openings of any homomorphic polynomial commitment scheme when they correspond to the same point. Now, we are extending this capability to include different points as well.
This method works well if there are few points, because calculating Kβ is costly (usually πΎ is a subgroup of the π½π points on an elliptic curve over π½π , and calculating πΎβ needs a multi exponentiation on this group).
Here below is the description of the batching algorithm in Plonk:
Circuit Encoding:
For each circuit instance π:
Polynomial Commitments:
For each circuit instance i:
Create polynomial commitments for the wire polynomials of the circuit instance.
Constraint System:
For each circuit instance π:
Define a set of constraints that enforce the correctness of the circuit instance.
Each constraint represents a gate in the circuit instance and relates the input and output wires.
Express the constraints as polynomial equations for circuit instance π.
Low-Degree Extension:
For each circuit instance π:
Extend the wire polynomials of circuit instance π to a higher degree using low-degree extension techniques.
Let π€{π,π} (π₯) represent the extended wire polynomial π€{π,π} of circuit instance π.
Evaluation of Constraints:
For each circuit instance π:
Evaluate the constraint polynomials of circuit instance π at specific points using the extended wire polynomials.
Random Polynomial Construction:
For each circuit instance π:
Construct a random polynomial that satisfies the constraints of circuit instance π.
Let ππ (π₯) represent the random polynomial for circuit instance π.
Batching:
Aggregate the wire polynomials, constraint evaluations, and random polynomials of all circuit instances into a single set of polynomials.
Concatenate the wire polynomials, constraint evaluations, and random polynomials of all circuit instances into larger polynomials.
Opening and Proof Generation:
Open the commitments to the aggregated wire polynomials and random polynomials.
Verify that the openings are consistent with the computed evaluations for the aggregated polynomials.
Generate a proof of knowledge that the commitments were constructed honestly for the aggregated polynomials.
Opening of Commitments: ππππ(πΆπππππ‘(π€{π,π} ))
Proof of Knowledge: πππππ(. . . )
Verification:
Verify the proof of knowledge and the consistency of the openings for the aggregated polynomials.
Check that the constraint evaluations and the constraint equations match for the aggregated polynomials.
Validate the correctness of all circuit instances and the integrity of the aggregated proof.
Note that the above steps provide an algebraic representation of the batching algorithm in PLONK. It assumes that the commitments, constraint evaluations, and random polynomials can be aggregated and concatenated appropriately.
The exact implementation details may vary based on the specific polynomial commitment scheme and cryptographic operations used in PLONK. By batch processing multiple circuit instances, the batching algorithm in PLONK reduces the number of commitment openings and proof generation steps required, resulting in improved efficiency and scalability.
It allows for generating a single proof that can simultaneously validate the correctness of multiple circuit instances. Since PLONK relies on general polynomial commitment schemes (here only the Kate commitment scheme was presented), it is quite flexible and can be used for proof carrying data constructions such as Halo2 proving framework.