FRI with Bootleproof-IPA Verkle Trees for "non-native" arithmetic and shrinking reference string size

FRI is a polynomial commitment scheme which is parameterized by a vector-commitment scheme. In other words, FRI is a compiler that takes a vector-commitment scheme and gives you a polynomial commitment scheme.

Briefly, FRI lets you open a polynomial \(p\) by committing to a vector of evaluations of \(p\), and then commiting to vectors of a bunch of evaluations of a bunch of polynomials related to \(p\), and then opening all these commitments at some random locations.

If your vector-commitment scheme lets you batch openings, then you can batch all the opening proofs required by FRI into a single vector-commitment opening proof, for both prover time and proof-size reductions.

Heretofore, most FRI systems have used Merkle trees for the vector commitment scheme. However, this has a few drawbacks

• opening proofs are large and not batchable
• verifying Merkle paths is somewhat expensive, especially in a circuit

A nice alternative idea is to use Verkle trees as your vector commitment. Specifically, in the Mina context, we would use a Verkle tree based on our inner-product-argument-based polynomial commitment scheme. In this way, you can use a single inner-product-argument to do all the vector openings required by FRI, which gives a large reduction in proof size and cost of verifying a FRI-proof in a circuit.

Then, one could instantiate PLONK with this IPA-Verkle-tree FRI PCS.

The benefits of this over directly instantiating PLONK with the straight IPA PCS are two:

1. Say the branching factor of the Verkle tree is \(2^k\). Then using a depth \(d\) Verkle-tree we can commit to polynomials of degree up to \(2^{kd}\) (roughly) with a reference string of size \(2^k\) and IPAs with \(k\) rounds.

   On the other-hand, using the IPA PCS directly, you can only commit to polynomials of degree less than \(2^k\). In this way, we can use a small reference string to handle large circuits.

2. We can put values of whatever field \(\mathbb{F}\) we like in the leaves of the Verkle tree, yielding a FRI-based PCS for polynomials over \(\mathbb{F}\), and ultimately a SNARK for \(\mathbb{F}\) arithmetic. On the other hand, for the IPA PCS, we can only commit to polynomials with coefficients in the scalar field of our chosen elliptic curve.

Thanks to Kostas Chalkias, Harjasleen Malvai, and Bobbin Threadbare for the initial idea.