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.

Let be a set of commitments and a set of points in 𝔽𝑝 . To open the commitments on the Z𝑖 :

1. A prover sends the individual proofs as well as the evaluations .
2. A verifier chooses random numbers and computes and checks that:

   

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 𝑖: Encode the circuit instance as an arithmetic circuit with variables representing the wires of the circuit instance.
Polynomial Commitments:	For each circuit instance i: Create polynomial commitments for the wire polynomials of the circuit instance. Let represent the commitment to wire polynomial of 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 𝑖. Let represent the constraint equation 𝑘 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. Let represent the evaluation of constraint 𝑘 for circuit instance 𝑖.
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.