ZK-Friendly Trace

This graph shows an overview of the existing zkEVMs. As you may know, they put everything, including the selectors for opcodes, the values, and the states, in a huge table or a state machine, and they have some smaller circuits or secondary state machines to prove different properties of the EVM.

However, this way, the small circuits have to prove that the operations and the values they use are consistent with those in the big table, we call this lookup. The overhead of lookup is very significant and it’s so time-consuming, as you can imagine when you just simply throw everything in a bag and try to find a specific one. It is never an easy task, not to mention you have to find every single thing once and do ZKP for this.

In fact, technically, let's say you have ten thousand rows in the big table, you need to commit to 3 polynomials of degree ten thousand. And these computations cannot be conducted parallelly. One of the most important bottlenecks of the existing zkEVMs is that the trace is not zk-friendly. Thus, we decided to create another form of trace, that is zk-friendly, to fundamentally solve this problem.

Similar to the existing zkEVMs, we have many sub-provers to prove different opcodes and different properties of the EVM, and sometimes, we need to prove some consistencies between the states included in the different sub-provers. However, we don't have a big table that is messy and has a lot of wasted space. Instead, we have small ones, and our trace places everything in the right place in advance. This makes the lookup here easier because the values are all well-categorized. Two sub-provers, let's say A and B only need to lookup the state table_AB to prove the consistency between them. By doing this, we are able to save a ton of time with no need to commit to the enormous polynomials.

What's even better is that, in our design, we can easily apply parallel computing here, to make our proof generation even faster.

By the way, the circuits are different from the circuits in the existing zkEVMs in many ways, so it is not easy for the existing projects to imitate our solutions.