---
# System prepended metadata

title: Exploring Zk-friendliness of verkle

---

# Exploring Zk-friendliness of verkle

* 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-friednly 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) and adding of result for getting a folded commitment.A key point to note here is that all these MSM operations will involve native artihmatics 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 we will perform addition and doubling for each bit, this will lead to 256*k adds + 256*k doubles, these numbers are high, but can be reduced further, for example some naive techniques for operations reduction we may use: combining doubling and adding in MSM process, which leads to making doubling cost trivial, and main cost will be of 256k adds, also we may consider 4 bits at a time for doubling and adding instead of 1-bit a time. There are some named techniques that may used for these optimizations like Stratus method, batch-inversion with sliding window, Yao's algorithm and 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 bottlneck is number of arithmatics performed by the verifier in the scalar field of Banderwagon curve for folding claimed evaluations(which are to be proved), these arithmatics are linearly dependant on number of commitments to be evaluated(sent by the prover), and we're unsure of this number of arithmatics, this number will depend upon the underlying batching and opening protocol used, currently we're using PCS multiproofs: PCS multiproofs(https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html) but there are other altervatives like Multipoint, multipolynomial batched openings(https://hackmd.io/f6ShwcCLTfmClTmmmMUjuA?view).
* As we've seen till now, that folding of commitments through MSM is performed by the prover in native field of ellitic curve based SNARK optimized for BLS12-381, and verfiers 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(https://eprint.iacr.org/2020/315.pdf), casting(https://eprint.iacr.org/2022/1470), range proofs(https://eprint.iacr.org/2024/430) and limb decomposition.
* Altough, this is not a new problem though, SNARKs that enable recurssive proofs like plonky1 developed by (tag polygon), pickles by (tag Mina) and Halo systems encounters same scenario, these ZKPs enable recurssion 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 tecniques that are curretnly 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, the equation x + y = z in the non-native field can be translated to [x]G + [y]G = [z]G on the curve, where G is a generator point and [n]G represents scalar multiplication. This works due to the homomorphic property of elliptic curves. Similarly, multiplication x * y = z can be checked as [x][y]G = [z]G, utilizing nested scalar multiplication, 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 fiels 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 (231 - 227 + 1), or 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 https://eprint.iacr.org/2022/274 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)https://github.com/AztecProtocol/barretenberg developed by tag aztec is competitie with plonky2.
* What is the potential ZkEVM design then? A mix of using a BLS12-381 based proof for verifying Verkle proofs, and a proof over a smaller field for other zkEVM logic such as proving standard EVM operations and data access, hashing, signature verification, contract calls etc. there are some problems with this approach though, only known efficient way to communicate between two proof systems is through hashing to group, and there should be a way to compute this hash efficiently in both fields, which may lead to computation in the non-native field of any of the two-proof system, since we have to select a field for hash computation. and we're again back to our previous problem.