Summary of Nexus zkVM costs

Most of instructions of the Nexus VM instruction set can be implemented quite efficiently requiring less than 2000 constraints in total. The main exception are memory operations, which require expensive Merkle proof computations. More precisely, in the case of a memory update, one needs to compute 3 Merkle proofs, one to read the current instruction from memory, one to read the current contents of the memory location, and one to update that memory location. Since each of these Merkle proofs require about 4300 constraints, as indicated in the memory checking costs section, the total cost of a memory update is about 13000 constraints.

Since the current version of the Nexus VM uses a universal model of computation, the total cost of each proof accumulation step ends up being around 15000 constraints, which is quite inefficient. However, we expect to significantly improve these costs by using better memory checking techniques and a non-uniform model of computation. The use of precompiles also has the pontential to significantly improve the efficiency of the Nexus Proof System.