As seen in one of our previous articles, zkVMs are a powerful abstraction for achieving a generic proof system that can handle essentially any statement. This flexibility, however, comes with trade-offs.
In this two-part article, we analyze how zkVM-based approaches behave in our setting, namely proving Solana-like transactions in Parasol, and explore alternative approaches that we are developing in our engine.
In a network extension like Parasol, validating a transaction requires checking both authorization and state transitions. While the execution logic is relatively simple, signature verification is required for every transaction. As a result, proof generation cost becomes a dominant factor, making proof system design critical.
Today, we start by breaking down some of the shortcomings of existing zkVM solutions. In part 2, coming next week, we will introduce a different direction based on field-agnostic proof systems that better aligns with the underlying logic.
The setting
Proving the correctness of a Parasol transaction essentially amounts to asserting two statements:
- The CLOB logic was executed correctly.
- The transaction signature is valid.
In terms of proving times, the first item is much lighter than the second, as CLOB operations can be implemented in-circuit with simple arithmetic. On the other hand, verifying the signature involves a non-trivial amount of cryptographic operations.
To understand this, we need to dig a bit deeper and see exactly what's happening in the signature verification algorithm.
Solana (and thus Parasol) uses the EdDSA signature scheme. For those familiar with classical signature schemes, this is essentially an instantiation of the Schnorr signature scheme, with:
- the elliptic curve ed25519 for arithmetic.
- SHA-512 as the hash function.
In our estimations with the zkVM approach - and assuming a precompile for the hash function - we found that the biggest bottleneck for proof generation is the elliptic curve arithmetic. Thus, it makes sense to focus on optimizing this part first.
Let us break down the arithmetic costs involved in EdDSA signature verification:
- EdDSA signature verification requires computing two scalar multiplications on the curve ed25519, for random scalars.
- On average, each scalar multiplication requires ~384 curve operations (additions or doublings).
- In turn, each curve addition or doubling involves ~10 to 15 field operations in the base field of the curve.
In total, this can easily amount to around 8000 base field operations, and this is just for one signature. In the setting of curve ed25519, base field operations are additions and multiplications modulo $q = 2^{255} -19$, i.e. arithmetic operations in the prime field $\mathbb{F}_{q}$.
So far, the costs estimated above are a direct consequence of the choice of signature scheme. There is not much that we can do about this, as this is specified by Solana. However, there are further costs that depend on how we go about proving that this arithmetic was executed correctly. We focus on this next.
The problem of non-native arithmetic
Proof systems typically operate over a fixed finite field $\mathbb{F}_{p}$. To recall very succinctly, this means that to feed a statement to a proof system, we need to write the conditions we wish to enforce as a set of constraints involving arithmetic modulo $p$.
If $p = q$ from above, each base field operation in the signature verification algorithm would become one constraint in the circuit. Unfortunately, $p$ and $q$ will not match if we use a regular zkVM.
- As mentioned above, $q = 2^{255} -19$ is fixed by the EdDSA specification.
- On the other hand, most current zkVM solutions rely on small fields, like the BabyBear field ($p = 2^{31} - 2^{27} + 1$) or Mersenne31 field ($p = 2^{31} - 1$).
The fact that the circuit arithmetic does not match the statement arithmetic leads to an additional complication: non-native field arithmetic emulation, i.e. writing each modulo q operation as a set of modulo p operations.
This is typically handled by splitting each input into smaller limbs, doing the operation piece-wise, and then reconstructing the result. It can easily entail a 10x blowup in the size of the circuit, or bigger.
Why can't we just switch the field?
One could ask: why not adapt the zkVM to the EdDSA field? However, there are multiple challenges with this.
For starters, zkVM circuits - both for CPU operations and precompiles like hashes - have been designed and optimized to work with small fields. Without a significant redesign, just switching the field would render most of their optimizations useless.
But even more importantly, whilst the circuits could be adapted with enough effort, there are fundamental incompatibilities between the new field and the zkVM's underlying proof system.
The recursive aggregation phase of typical zkVMs is based on Reed–Solomon codes, which require very specific conditions to hold. In particular, a large power of $2$ (at least $2^{24}$ or higher, typically) must divide $p-1$ (or $p+1$ with some extra tricks).
This property is unlikely to hold for a random prime. BabyBear and Mersenne31 were chosen specifically because they satisfy this property. However, this was not a consideration when the curve ed25519 was proposed. It was chosen for its security and efficiency from the point of view of the signature scheme, but proof system compatibility was not a factor at the time. And so, unfortunately, no large power of 2 divides $q-1$ or $q+1$. This rules out FRI-based proof systems.
Unnecessary generality
zkVMs are very general proof systems because they can take any program, written in mostly normal code, and produce a proof of correct execution. They achieve this by compiling the program to a set of CPU instructions, for which the zkVM provides fine-tuned circuits.
This is very powerful when your application involves proving a lot of arbitrary code. However, this abstraction and generality come with a significant computational overhead. In our setting, we will mostly be concerned with proving correct signature verifications again and again. As previously mentioned, this boils down to elliptic curve arithmetic and hash computations. Thus, it makes sense to drop the complex machinery of the zkVM, and simply have specialized circuits for a small set of key operations.
Moreover, because zkVMs expect arbitrary programs, they do not exploit structure. We will not prove one signature at a time, we will prove many. So our circuits will be highly structured. It is possible to take advantage of this structure for further efficiency gains.
Final thoughts
We have seen that the main source of overhead is not just the complexity of the operations being performed, but how they are represented within the proof system.
This leads to a structural mismatch that becomes increasingly costly as we scale, and raises a natural question: can we design proof systems that more closely follow the structure of the computation?
In part 2, we will explore this direction through field-agnostic proof systems, which can be instantiated directly over our $\mathbb{F}_{q}$, thus solving the issue of non-native arithmetic.
