The end-to-end gaming/autonomous world is one of the most important narratives in Web3. As of the end of October, the daily active users (DAU) of web3 games reached 5.3 million, showing huge market potential. Unlike Web2.5 applications, end-to-end games/autonomous worlds deploy the entire game logic on the blockchain, directly using the blockchain as the game server, ensuring that every user operation is truly executed on the chain, which brings significant advantages such as decentralization, trustworthiness, and composability, but traditional games still face major challenges such as performance bottlenecks, scalability, and privacy when embracing web3.
What is Nova
Nova [1] is a recursive proof system based on a folding scheme, designed specifically for R1CS, and can efficiently implement Incrementally Verifiable Computation (IVC). IVC is a cryptographic primitive that ensures the integrity of the entire execution process of a given computer program by proving the correctness of each step.
First, what is IC (Incremental Computation)? IC refers to the recursive application of the same function F to perform the computation, i.e., by inputting the initial state, the state is obtained after this iteration, as shown in Figure 1.a. If the function F also includes a verification circuit, then it becomes IVC (Incrementally verifiable computation). IVC allows the Prover to prove to the Verifier, and at each step, a succinct proof is generated to ensure that the computation process from the beginning to the i-th step is correct, as shown in Figure 1.b. It can be seen that this method can divide large computations/statements into smaller blocks, and then the repeated code blocks can be executed more efficiently.
Nova proposes a highly innovative folding scheme that merges two R1CS instances and their respective witness-instances into one. Compared to Snark-based IVC, Nova does not need to verify the previous Snark proof in each recursion, so it has the following features:
- No trusted setup
- No need for FFT operations or pairing-friendly elliptic curves
- Constant verification time
- Only for R1CS instances, will merge 2 R1CS instances into 1 R1CS instance
Why Nova
The prospects for web3 games are broad, but they also face many challenges. First, for real-time fast-paced games, the response time of operation instructions is usually in milliseconds, but most blockchains have not yet acquired the capability to support the running of high-performance games. Secondly, as the transaction volume increases, the blockchain may become congested, leading to delays and affecting the experience.
To solve these problems, we explored a method called Game Rollup. Game Rollup aggregates game operation instructions into the same circuit using the Groth16 proof system, and then generates a proof and uploads it to the chain for verification. With this approach, players can execute more operations before interacting with the blockchain, enjoy a longer gaming experience, and avoid waiting for on-chain confirmation for each operation.
Specifically, our Rollup circuit can also be represented in the IVC form:
where F is the turn function of the game.
Taking our 2048 game as an example, this is a classic puzzle sliding game adapted for the chain. The biggest challenge in designing 2048 is the design of the F function. Because in the 2048 game, there are four possible input instructions per round: up, down, left, and right. To accommodate these four inputs, the design of the F function (circuit) needs to be quite sophisticated, as it is fundamentally different from some 2048 logic implemented on the chain through smart contracts, which usually use simple if-statements (e.g., if up {}, else if down {}...).
Solana is a high-performance public chain that can provide relatively fast transaction confirmation speeds, but even so, the experience of the 2048 game [2] deployed on it still does not reach the ideal smoothness. In contrast, our Game Rollup-based approach provides a smoother gaming experience, which also proves the advantages of Game Rollup in improving game performance. However, this approach still has some limitations, as it is only a naive implementation of IVC:
- The prover requires Ω ( i *∣ F ∣ ) memory
- The proof is not incrementally updatable
Until we encountered and deeply studied Nova, we had a feeling of "better late than never", as it has broken through the limitations of Game Rollup and is expected to solve the performance bottlenecks and scalability issues in Web3 games. Here is a performance benchmark we did on the 2048 game using Game Rollup and Nova implementations:
Summary
Nova not only has superior performance, but also high memory efficiency, which is very important for large circuits, as Groth16 requires a large SRS and consumes a lot of memory. Nova can still run efficiently in low-memory environments. Currently, some ZKVMs have also started to build on Nova, such as Nexus [3]. We believe that Nova will bring unprecedented performance and scalability to Web3 games, becoming a key technology to drive the development of Web3 games. Zypher has established a close strategic partnership with Nexus and is actively collaborating to adopt Nexus' ZKVM based on the Nova system to create the next-generation on-chain decentralized application infrastructure.
References:
[1] https://eprint.iacr.org/2021/370
