Verkle Tries and Zero-Knowledge Proofs: Technical Analysis

Introduction

Verkle trie will be using Banderwagon curve (https://hackmd.io/@kevaundray/BJ2-L6Nzc), which is defined over scalar field of BLS12-381, which are a family of pairing-friendly elliptic curves, for proving verkle-proofs associated with a VPT.

One of the key advantage of verkle trie over merkle is that the proof size does not depend upon the width of the trie, though it depends upon the depth of trie, as the number of commitments to be included in verkle proof increases as the depth of to prove node increase.

The main problem that can be encountered here by prover is combining(folding) of all these pedersan-style commitments for batch reduction, the technique of Multi Scalar Multiplication(MSM) is used for this purpose, it involves:
- Multiplication of a curve point with a scalar(doubling)
- Adding of result for getting a folded commitment
A key point to note here is that all these MSM operations will involve native arithmetics of elliptic curve based SNARK optimized for BLS12-381 scalar field.

The problem here is, the computational cost of MSM increases with the number of terms involved(say $k$ -commitments are required to be passed to verkle proof for proving the current node), for example:
- For a 256 bit integer, in a brute force approach: $256 * k$ adds + $256 * k$ doubles
- These numbers can be reduced using techniques like:
  - Combining doubling and adding in MSM process
  - Using 4 bits at a time for doubling and adding
  - Named optimization techniques:
    - Stratus method
    - Batch-inversion with sliding window
    - Yao's algorithm
    - Pippenger's algorithm
The main challenge lies here will be in balancing the efficiency of MSM operations with the constraints of ZK-circuits, which might limit the use of certain advanced MSM algorithms mentioned above.

Another bottleneck is number of arithmetics performed by the verifier in the scalar field of Banderwagon curve for folding claimed evaluations(which are to be proved), these arithmetics are linearly dependant on number of commitments to be evaluated(sent by the prover), and we're unsure of this number of arithmetics, this number will depend upon the underlying batching and opening protocol used, currently we're using:
- PCS multiproofs
- Alternative: Multipoint, multipolynomial batched openings

As we've seen till now, that folding of commitments through MSM is performed by the prover in native field of elliptic curve based SNARK optimized for BLS12-381, and verifiers work is done in native field of Banderwagon.

The problem which will be encountered here is, in many ZkPs especially those optimized for a specific curve (like BLS12-381), arithmetic in other fields (like Banderwagon's scalar field) isn't natively supported, this means we can't directly perform these operations in our proof system, research needs to be done on methods for performing these operations between the two fields, some methods that can be used for this are:
- Precomputed look-up tables
- Casting
- Range proofs
- Limb decomposition

Although, this is not a new problem though, SNARKs that enable recursive proofs like:
- Plonky1 developed by Polygon
- Pickles by Mina
- Halo systems
These ZKPs enable recursion by using a pair of elliptic curves, where the base field of one curve is the scalar field of the other, and vice versa, same obstacle is faced in these systems, when verifying a proof from the previous cycle, you need to perform arithmetic in a field that isn't native to the current curve. This is similar to the problem we face with Verkle proofs, where we need to perform arithmetic in Banderwagon's scalar field.

This problem is tackled by forwarding parts of proof verification to next cycle, that is to defer some computations to the next proof in the cycle. However, this deferral mechanism itself requires some non-native arithmetic to prove correct storage of deferred computations, ex: You might need to prove you've correctly encoded the deferred computation in a format the next proof can use. This challenge parallels the issue faced in Verkle proofs, where arithmetic in Banderwagon's scalar field is needed but isn't native to the main proving system (assumed to be BLS12-381 based).
Unlike cycle-of-curve systems, Verkle proofs can't easily defer this arithmetic as it's central to the verification process. Consequently, both scenarios cannot entirely avoid non-native arithmetic, necessitating efficient simulation methods within the proving system. This requirement adds complexity and potential performance overhead to proof generation and verification, highlighting the challenges in making Verkle proofs efficiently ZK-friendly.

There are some potential techniques that are currently used to tackle the problem of performing arithmetic in non-native fields, we can encode the arithmetic operations as operations on the elliptic curve itself, which can be performed in the native field:
- For addition: $x + y = z$ in the non-native field can be translated to $[x] G + [y] G = [z] G$ on the curve
- For multiplication: $x * y = z$ can be checked as $[x] [y] G = [z] G$
Where $G$ is a generator point and $[n] G$ represents scalar multiplication. This works due to the homomorphic property of elliptic curves. However, this approach isn't without drawbacks. The additional curve operations, particularly scalar multiplications, can be computationally expensive.

Another bottleneck is size of the finite fields used by the prover, curves using larger field sizes, such as the 384-bit fields associated with curves like those in the BLS12-381 family may not perform as fast as compared to smaller field counterparts, such as:
- Goldilocks: $2^{64} - 2^{32} + 1$
- BabyBear: $2^{31} - 2^{27} + 1$
- Mersenne fields: $2^{31} - 1$ or $2^{127} - 1$
These smaller size fields allow for faster computations, making them suitable for ZkEVM design.

However, not all elliptic curves are compatible with these small-field optimizations. The Banderwagon curve, used in Verkle trees, is an example of a curve that doesn't efficiently leverage these small fields. While it's possible to design curves like EcGFp5 that work well with small fields, Bandersnatch lacks this advantageous structure. Despite this limitation, elliptic curve-based systems can still be competitive in terms of performance, as evidenced by systems like Barretenberg (256 bit elliptic curve) developed by Aztec is competitive with plonky2.