Single-point KZG verification is actually computing a product of 2 pairings. In the single point case, each pairing has one side fixed that allows to exploit a common batching technique: taking a linear combination with random coefficients. It is an extension of Bellare et al., section 3.3 Small Exponent Test to pairings. @daira gives a clear explanation of the technique as applied to Groth16 in appendix B.2 of zcash spec. There's also a direct application of Schwartz–Zippel lemma written down as a proof in some texts like, section 3.1. Also the same technique is used in plonk, p. 12, to batch-verify 2 (aggregated) openings in different points.
KZG counterpart of Halo2 PC accumulation scheme
PCD from accumulation paper, section 8, describes the same computation as an accumulation scheme for KZG. The only difference is that there are 2 parties in Halo: one executing the aggregation, and the other -- verifying the aggregation by re-executing.
What is the difference to Halo Infinity private aggregation scheme? In this scheme proofs of each opening are also aggregated to produce a valid proof of the aggregate opening, while In Halo Infinity the proof for the aggregate is computed from scratch, that at least means that someone should keep track of the aggregate polynomial behind the aggregate commitment.
swasilyev
commented
2 years ago
Efficient batch verification
Single-point KZG verification is actually computing a product of 2 pairings. In the single point case, each pairing has one side fixed that allows to exploit a common batching technique: taking a linear combination with random coefficients. It is an extension of Bellare et al., section 3.3 Small Exponent Test to pairings. @daira gives a clear explanation of the technique as applied to Groth16 in appendix B.2 of zcash spec. There's also a direct application of Schwartz–Zippel lemma written down as a proof in some texts like, section 3.1. Also the same technique is used in plonk, p. 12, to batch-verify 2 (aggregated) openings in different points.
KZG counterpart of Halo2 PC accumulation scheme
PCD from accumulation paper, section 8, describes the same computation as an accumulation scheme for KZG. The only difference is that there are 2 parties in Halo: one executing the aggregation, and the other -- verifying the aggregation by re-executing.
What is the difference to Halo Infinity private aggregation scheme? In this scheme proofs of each opening are also aggregated to produce a valid proof of the aggregate opening, while In Halo Infinity the proof for the aggregate is computed from scratch, that at least means that someone should keep track of the aggregate polynomial behind the aggregate commitment.