Implement fflonk opening for the 'basic' scheme

[swasilyev]

https://eprint.iacr.org/2021/1167.pdf suggests an alternative to the currently used (aggregated KZG with linearization, introduced in vanilla PLONK) means of opening the PIOPs.

For the 'basic' scheme current implementation employs 4 data polynomials (aka columns, aka registers), that contain per-coordinate affine representations of 2 arrays of the points: registered public keys aka 'the keyset', and their accumulator (partial sums vector, in other words) used to compute the apk. On top of that there are 4 constraint polynomials, with the first pair representing the incomplete SW affine addition formulas, and the other -- the bounding constraints, that guarantee that the accumulator starts with the given point h (there's no affine representation for 0), and ends with the alleged apk + h.

With regular KZG commitments it results in communication in 2G (group elements aka compressed BW6 affine points) for the keyset commitment that rotates less often, and 2G to commit to the apk accumulator in each proof. All the 4 constraints are aggregated into the single one C of degree up to 4n-3, where n is the max supported keyset size. We prove that the constraints satisfy by committing to the quotient polynomial of the aggregated constraint over the multiplicative domain of size n: q(X) = C(X) / X^n - 1 and opening C(X) - q(X)(X^n - 1) to 0 at a random point z. Opening q takes 1G+1F for the commitment and the evaluation. To compute C(z) each data polynomial needs to be opened at the random point z at least, and the accumulator polynomials -- additionally, in the "shifted" point zw (as we constraint 2 consecutive values). That would result in 6F (BW6 scalar field elements) to pass these data polynomials evaluations, but the 'linearization trick' also described in the original PLONK paper trades the 2 evaluations in the "shifted" points for the single evaluation of the "linearization polynomial" r in the "shifted point", commitment to r is reconstructed by the verifier as a linear combination of the commitments it knows. Finally all the openings can be attested with only 2 KZG proofs, as openings at the same point are aggregated.

Thus the communication cost the 'basic' scheme is 2G (for keyset commitments) per a keyset,
and additionally per a proof:

• 3G -- commitments to the accumulator and quotient,
• 6F -- evaluations of keys_x, keys_y, acc_x, acc_y and q at z, plus r(zw), and
• 2G -- for 2 KZG opening proofs.

Given that for BW6 (not differently from Cocks-Pinch) curves the base field occupies twice as many bits as the scalar field, and a point is roughly compressed to a single coordinate, we have G~2F or 16F per proof, that is 16 * 48 = 768 bytes for BLS12-377.

A prototype implementation is https://github.com/w3f/fflonk