# A Practical Guide on Trustless Fully On Chain Game

# 1. Introduction of TFOC

This is a follow-up note on the progress of supporting trustless browser game developpment in web3. (The initial work is presented at https://www.youtube.com/watch?v=dLZbfTWLGNI with notes available on https://delphinuslab.com/wp-content/uploads/2023/04/zksummit-presentation-zkwasm-game-1.pdf)

With the further development of web3, fully onchain games have once again come into our view. They claim that they are better in Decentralization, Transparency, Trustless and Community Governance. However, FOC games also inherit the blockchain’s dilemma regarding Decentralization, Security, Scalability. That implies the difficult task of balancing game content, interactive frequency, decentralization, trustless and community fairness are the thorny issues of game developpers in FOC narrative.

Thus, ages ago, game developpers compromises the architecture and introduced a best practise architecture which is broadly referred as web2.5 game architecture.

More precisely, Web2.5 is a catch-all term referring to a blend of web3 and traditional games. Web2.5 emphasis on the contents of the game play since the believe that the main audience of the game is still rooted in web2. Meanwhile, they add the ingredients of web3 (NFT, tokenomics, play to earn) to their games so that their game can stand out.

A standard web2.5 game architecture might looks like the following:


On the left-hand side is the gameplay engine which controls the game state machine and reacts to the user activities. On the right side, it reacts to certain parts of the game state change and tracks the most valuable data on chain.

The game play mostly are running in a centralized game server while the most valuable data (NFT, token rewards, records, etc) are tracked in a blockchain.

The advantage of this setup is that the game server can run in a centralized mode that handles huge amout of user transactions with in seconds. Aslo the centralized server can handle complex and continuous gaming play which are usually too costy to be processed in a native blockchain.

However, in this setup, the communication channel between the game engine and the onchain protocol is usually secured via signatures thus not trustless. Also, the game content can be altered with no governance which might sometimes affect the vested interest of existing players (through a game economics update, content update or even reward system update).

Moreover, the onchain data can hardly check that the data passed to the blockchain is a valid consequence of the gameplay. The server can take the advantage of its role to behave differently for certain users(e.g. maintanier's account or projects' private account).

Since the web2 game is usually excel on its content and game play, it is acceptable to hand over the balance and fairness to the game provider. However when the web2 game decide to enter the ecosystem of web3, it may need to attract crypto native players who cares a lot more about of the economics, ownership and value capturing during the game play. For such players, they not only enjoy the process of achieving rich results through gaming, but also hope that the outcomes they achieve in games can have lasting significance and even possess the attribute of appreciating in value. Conversely, this enduring appreciation effect makes players take their choices in the game more seriously. This means that the cost of thought and decision-making by players in the game is higher, further deepening their expectations of fairness and predictability in the game rules.

Eventually, the player will demands the that they can some how control over “web3-ness” of a game: the fairness and trustless is enforced not by the game maintainer but by the infurastrusture of the game setup: **A more decentralized, fully on-chain game.**

A naive response to this is to move everything on the left to the right onto the chain so that the architecture could look like the following.


Obviously this results a lots of degression of the gameplay:
1. User has to sign their game play everytime they make a movement.
2. The size of the game engine running on the blockchain is restricted.
3. Huge gas fees need to be paid.
4. The frequency of user interaction needs to be reduced to fit the blockchain TPS limit.

Does that mean we have to give up the complex but rich content to pursuit the fully on-chain philosophy?

The answer is probably "**Yes**" before the spawn of zero-knowledge virtual machine technology. However, based on the fact that ZKVM has now been extensively studied and developed, we have "the third approach" which is to combine the fully on-chain games with trustless computation. **But how?**

A ZKVM, short for Zero-Knowledge Virtual Machine, is a concept that combines zero-knowledge proofs with virtual machine technology. To understand it, let's break down the two components:


1. Zero-Knowledge Proofs (ZKPs): These are cryptographic methods that allow one party to prove to another party that they know a value (e.g., a secret key), without revealing any information about that value. ZKPs enable privacy and security in transactions or interactions, as they can verify the truth of a statement without sharing the actual data.

2. Virtual Machine (VM): A VM is a software emulation of a physical computer. It runs an operating system and applications, much like a physical computer, but is entirely software-based. VMs are used extensively in cloud computing and for running multiple operating systems on a single physical machine.

Combining these, a Zero-Knowledge Virtual Machine would be a virtualized environment that can execute programs or contracts while providing the privacy and security benefits of zero-knowledge proofs. This means that we can run the game engine (or game server) inside the zkVM and use the zkVM to generate ZK proofs to proveto the blockchain that the execution result of the state different data is enforced by the game logic. Thus, there will be no way for the game server to tweak the data it send to the underlying blockchain.

The combined architecture of an FOC game might look like the following:


We call this Trustless Fully On Chain Game: **TFOC**.

# 2. Develop Consideration in TFOC

## 2.1 Must-knows before you start
Game development is considered difficult for its technical complexities, creative challenges, and project management issues. When apply the tech of ZKVM to a TFOC we should carefully consider the overhead introduced.

**Technical Complexity:** The logic of a game needs to be separated apart from the visualization of the game and the logic needs to be deterministic for the ZKVM to generate a proof. Moreover, since the proof is generated on the segments of the executions, the game developper needs to separate the gameplay into execution segments and synchronize the execution with onchain contract regularly.

**Art and Design:** In general, artists and designers are not affected as it is not part of the logic that needs to be proved. The visualization is based on the global state of the game, and the UIUX is used as a tool to collect actitivies of the player.

**Over all User Experience:** Unlike FOG, users do not have to sign their transactions everytime they make a movement, which enhance the possibiliby of creating "Frequent Interaction Type Games", which refers to a category of games that require or encourage continuous or very regular engagement from players.

However, restricted by the proof generation time of ZKVM, high frequent interaction is still not feasable for TFOC game running in ZKVM. For example,
Real-Time Strategy (RTS) and Multiplayer Online Battle Arenas (MOBA), Where players must continually manage units, resources, and strategies to outplay opponents, are unlikely to be supported.

In contrast, simulation and farming Games, where players need to regularly manage resources, markets, or characters to achieve real-time growth or progression, fit the TFOCG very well.

Interactive Story Games and Visual Novels, which may not require constant physical interaction but engage players through decision points that shape the story, encouraging frequent engagement to see the outcomes of their choices.

**Monetization and Sustainability:** The game content is usually envolving during to capture and maintain players. This makes the logic of the gameplay being dynamic thus affects the program runs in the ZKVM. A consequenc of this is that the verification contract might change and needs update.

There are two way to avoid frequently changing the ZK verification contract.
1. **Change of Game Play:** Abstracting a protocol layer for your gameplay and defining those dynmaic features of the game to be **rules**. Once you have that, you can store your set of rules on chain and commit those rules into a anonchain hash. Meanwhile, when the game engine ris uning the game logic, it can first check that the hash of the current rule set matches the commitment and then bbehaveaccordinly.

2. **Change of the Settlement:** The rewarding system could be a separate layer out of the game play itself. We can treat all the rewarding algorithms are callbacks of certain events of generated in the game play. By doing so, we can put the rewarding callbacks onchain and invoke those callbacks based on the game events.

For example we have the following game routine:

zkgame {
    // Game logic
    output(events)
}

where it generates events which will become instances of the proof of the execution. Following this, we can add the callbacks in the contract as follows:

function verify(
        bytes calldata events_data,
        uint256[] calldata proof,
        uint256[] calldata verify_instance,
        uint256[] calldata aux,
        uint256[][] calldata instances,
        RidInfo calldata ridInfo
    ) public {
        ...
        // Check the events_data pins to a has in the instances
        require(instances.events_hash = hash(events_data))
        
        // Performs the zk verification
        verifier.verify(proof, verify_instance, aux, instances);

        // Call the callbacks to handle the rewarding logic for events
        uint256 sideEffectCalled = perform_txs(events_data, ridInfo.batch_size);

        ...
    }

## 2.2 Where to put your game logic
There are primarily two locations for implementing the main game logic: in the front-end or on the server-side.

Positioning the game logic in the front-end simplifies the game's architecture compared to a client-server (CS) structure. This approach allows the front-end to simulate gameplay and generate a zero-knowledge proof (zk-proof) once the execution trace is established. Subsequently, it employs either a local zk-prover or a remote proving service to produce the ZK proof for the Zero-Knowledge Virtual Machine (ZKVM). This proof is then uploaded to the underlying blockchain to trigger the settlement contract.

In contrast, puting the game logic in the server-side offloads the game simulation and interaction between users into a more dedicated component (Game Server). This could improve the overall game experience in the following aspects.

**More Synchronized Gameplay:** Server-side simulation ensures that all players experience the game world in a synchronized manner. This is crucial for multiplayer games, where consistent game states across all connected clients are essential for a coherent and competitive experience.

**Better Resource Management:** The front-end can focus on content rendering and UIUX, while the server can serve as a centralized sequencer and merkle tree storage provider.

For a single player PVE game, (or multiplayer pvp game) that does not require historical data and has simpler sequencing logic, putting everything in the front end is a good choice. For complicated game like multiplayer SLG or AW game, a server-side game simulator performs better.

## 2.3 Pick the game development framework
Since we are combining traditional game development with ZKVM, we need to consider carefully on the tooling.

1. We need to decide whether we are going to use traditional programming language like C#, rust, C, C++, Go to develop the game or we are going to use a ZKVM specific language. If we want to use a traditional programming language, then the back end bytecode of those language are usually mips, wasm, riscV, or x86. Since there are not many zkVM supports thos bytecode, we can pick Risc0 as the underlying zkVM if your programm can be compiled into riscV bytecode or pick zkWASM as the underlying zkVM if it can be compiled to WASM. WebAssembly (WASM) is a low-level bytecode format that serves as a target for compilation of high-level languages like C, C++, Rust, and more. It's designed to enable code written in these languages to run on the web at near-native speed. WebAssembly provides a way to run performance-critical code in web browsers without sacrificing the security or speed of web applications. It's a key part of the modern web technology stack, complementing JavaScript by allowing developers to utilize languages other than JavaScript for web development.

2. Once the programming language is picked, we can choose a game engine based on top of the language we choose. If you select a ZKVM specific language, then you might need to create your own game development framwork since there might not exist mature framework for that language. If you are using rust, C, typescript, then there are plenty of framwork you can choose, among which we recommend unity and cocos2D.

3. We need to estimate the proof generation cost. Usually the proof cost is measured by the proving time of 1 million instructions. Thus it depends on the execution trace of the game play (number of insturctions for each game play transaction), the word size of the backend bytecode, and the proving performance of the ZKVM. For simple instruction set, there are zkVMs that can generates proof of 1 million instructions in several seconds (Miden: https://0xpolygonmiden.github.io/miden-base/). For complex instruction set (RISCV 32bit, WASM 64bit), zkVM can generate 1 million instructions in 12s in GPU (Risc0 https://www.risczero.com/) to around 30 (zkWASM https://github.com/DelphinusLab/zkWasm) seconds in GPU.

# 3. Using MVC for FOC Game in ZKWASM
## 3.1 Brief of MVC
The Model-View-Controller (MVC) pattern, while traditionally associated with web and enterprise application development, can also be applied to game development, albeit with some adaptations. Here's how the MVC components might be interpreted in the context of game development:

**Model:**
In game development, the Model represents the game's data and logic. This includes the game state (like the score, level, and player stats), game objects, and the rules that govern the game world. The Model is responsible for managing the data and the state of the game, and it typically doesn't have any knowledge about how this data will be presented or displayed.

**View:**
The View in game development is concerned with presenting the game state to the player. This involves rendering the game graphics, playing sounds, and displaying UI elements like scores, health bars, and menus. The View observes the Model and updates the visual and auditory representations of the game world to the player. In many game engines, this might be encapsulated within the rendering engine and the UI system.

**Controller**
The Controller interprets user input from keyboards, mice, gamepads, or other input devices, and translates it into actions within the game. For instance, when a player presses a button to make the character jump, the Controller would handle this input and communicate the action to the Model. The Controller in a game acts as a mediator between the input devices and the game logic.


Applying MVC in Game Development has considerable benefits:
1. Separation of Concerns: MVC can help in organizing code and separating the game logic from the user interface, which can make the development process more manageable and the code more maintainable.
2. Flexibility: MVC can allow different views to be created for the same model. This can be useful in games that offer multiple perspectives or need to support various display modes.
3. ZK friendly: By separating game logic from presentation, the model is the only part needs to be trustlessly executed. By putting the model into ZKWASM, the core game mechanics is natually proved as the game runs.

## 3.2 Arrange game engine in ZKWASM

Suppose that the controller is connected to Model with a set of model handlers. It follows that we can put an command encoding/decoding layer for the controller and handlers as follows:

struct GlobalState {
    ... // Define your game state here
}

enum ControllerTag {
    A,
    B,
    C
}

/// The controller in MVC
fn controller_A (c) {
    let handler_cmd = encode(A, c);
    model.handle(handler_cmd)
}
fn controller_B (c) {
    let handler_cmd = encode(B, c);
    model.handle(handler_cmd)
}
fn controller_C (c) {
    let handler_cmd = encode(C, c);
    model.handle(handler_cmd)
}

/// The model in MVC
fn handler(command) {
    match command {
        A => {},
        B => {},
        C => {},
    }
}

/// View 
fn render(global_state: GlobalState) {
    // display your game UI based on global state
}

## 3.3 Generate the proof of the game play
We can treat part of the game play as a sequence of controller calls to the handler. Thus the ZK proof of the trustless execution of the game play is a zkproof of the following code

fn execution(cs: Vec<command>) {
    for command in cs {
        global_state = handler(command);
    }
}

During the gameplay, it is hard to tell what is the last command sent out by the controller and it is hard to put all the command handling into one single ZK proof. Thus the best practical is to split the commands into parts and generate proof of of them and then batch them together to generate single proof for futher verification on chain.


**Remark:** Notice that there are two missing part in the above approach:
1. How to make sure the state between each execution segment is continuous
2. How to handle multi-player scenarios when controllers from different game client intereference between each other.

In the following chapter we will give a brief introduction of the multi-player sequenceing and data accessibillity. Since each topic could go a lot deeper we plan to provide more detailed content in other separate notes.

# 4. Sequencing User Transactions in Multi-player Game

In the context of modular blockchains, a sequencer is a component or node responsible for ordering transactions before they are finalized on the blockchain. Modular blockchain architecture separates the different layers of blockchain functionality — such as execution, consensus, and data availability — into distinct components. This approach aims to enhance scalability, security, and efficiency by allowing each layer to be optimized independently.

When develop a multi-player games, we also needs a component to help ordering the transactions among different users. Thus we reuse the terminology of sequencing as we do in modular blockchains.

Since a game requires small latency, it is better to choose a centralized sequencer that produces quick ordering results. The game engine can also stay closely with the sequencer to fetch the ordered transaction simutaniously.

## Single-player transaction protocol:
Here we describe a transaction protocol from a player perspective. In a user transaction, the user describes his inputs and proves the identity of himself via public and witness inputs which can have the following layouts.

**The public inputs:**

**The witness inputs:**

**The transaction process logic:**

pub fn zkmain() -> i64 {
    let mut hasher = Sha256::new();

    // get the command length
    let commands_len = unsafe {wasm_input(0)};
    
    // processing all commands and 
    // hash the commands for furture signature verification
    for _ in 0..commands_len {
        let command = unsafe {wasm_input(0)};
        hasher.update(command.to_le_bytes());
        step(command);
    }
    let msghash = hasher.finalize();
    let pk = unsafe {BabyJubjubPoint {
        x: U256([
                wasm_input(0),
                wasm_input(0),
                wasm_input(0),
                wasm_input(0),
        ]),
        y: U256([
                wasm_input(0),
                wasm_input(0),
                wasm_input(0),
                wasm_input(0),
        ]),
    }};
    zkwasm_rust_sdk::dbg!("process sig\n");

    let sig = unsafe {JubjubSignature {
          sig_r: BabyJubjubPoint {
              x: U256([
                      wasm_input(0),
                      wasm_input(0),
                      wasm_input(0),
                      wasm_input(0),
              ]),
              y: U256([
                      wasm_input(0),
                      wasm_input(0),
                      wasm_input(0),
                      wasm_input(0),
              ]),
          },
          sig_s: [
              wasm_input(0),
              wasm_input(0),
              wasm_input(0),
              wasm_input(0),
          ]
    }};
      
    let msghash_u64 = [
        u64::from_be_bytes(msghash[24..32].try_into().unwrap()),
        u64::from_be_bytes(msghash[16..24].try_into().unwrap()),
        u64::from_be_bytes(msghash[8..16].try_into().unwrap()),
        u64::from_be_bytes(msghash[0..8].try_into().unwrap()),
    ];
      
    sig.verify(&pk, &msghash_u64);

# 5. Cost Analysis
## 5.1 Cost Overview
In a ZKVM based trustless FOCG, the cost of maintaining mainly comes from the ZK proof genration, fast data rpc service, call data access service and onchain verification and settlement fee.

## 5.2 Proof Cost:
To begin with, ZKVM runs the application and generates an execution trace. This trace is fundmental as the ZKVM needs to proof
1. The trace enforces the semantics of the bytecode that is supported by the ZKVM.
2. In general the ZKVM itself is stateless. To support stateful storage for Game, they utilize the idea of Merkle proofs that turns the proof of data setting and getting into Merkle proofs.
3. ZKVMs usually split the execution trace into multiple segments and generate proofs for them separately. These proofs will be batched together to generate a single verifiable proof in the end.

Suppose that the ZKVM we utilize uses precompiled circuits as sycalls or host APIs in ZKWASM to handle merkle proofs. The overall cost of generating the ZK proof is the following:

**Proof Cost = ZKVMGuestProofCost + MerkleProofCost + BatchProofCost**

In general, the first and third part does not introduce extra cost except pure ZK proving. However the second part is subtle, as it needs the support of some data storage service.

Recall that the merkle proof consists of the following parts:

**1. Setup of a Merkle Tree:**
We abstract the global data into blocks and hash them individually. These hashes become the leaf nodes of the target tree. After that, pairs of leaf nodes are hashed together to form the next level of nodes, and this process is repeated upwards until there is only one hash at the top, known as the Merkle root. The Merkle root is a unique representation of all the data blocks in the tree.

**2. Data Inclusion Proof:** The proof consists of the specific data block in question, its hash, and a small number of additional hashes from the Merkle tree. These additional hashes are the minimum necessary to allow the verifier to independently compute the Merkle root of the dataset.

**3. Verifying the Proof:** The verifier, who knows the Merkle root of the dataset but not necessarily all the data it contains, uses the provided data block and additional hashes to reconstruct the path of hashes up to the Merkle root. If the computed Merkle root matches the known Merkle root, the proof is valid, confirming that the data block is indeed part of the dataset and has not been tampered with.

To maintain a ZKGAME that is stateful, a merkle data DB is needed to track the leaves of the Merkle tree and provide quick data querying service. This service is not feasible to be fully hosted on chain since the data alteration frequency is very high and the accessing (Read/Write) demand is high.

Once an transaction is finished, the call data and the final state（represented by the new merkle tree root) need to be accessable. This is usually achieved via a DA layer or onchain txdata storage.

## 5.3 Data Costs:
Based on the analyst given by Blade Dao Games, ZKWASM, Eth Storage, as well as references to BNB greenfield storage cost calculator (https://dcellar.io/pricing-calculator), google cloud storage pricing (https://cloud.google.com/products/calculator), we concluded that the cost of running a 5,000 people (non-stop playing) on-chain game using zk co-processor approach, should result in a cost of ~90k usd per month.

Here is how Blade Dao estimate it: They turn the user events published in Unity to server into binary code, and run it within ZKWASM, a ZKVM that support WASM bytecode developed by Delphinuslab. Then ZKWASM will generate the execution trace and post the compressed trace to the DA layer, meanwhile we will post the trace hash on chain with a digital signature for immutability.

Based on the test run by ETHstorage and zkwasm, running a wasm binary for a second will generate 1 million lines of trace with each line sized in 40 bytes.

We can choose to prove all the traces on-chain, or we save the traces and only prove it if the user chooses to challenge the results.

1. **ZK Approach by proving all the traces**
If we choose to prove all the traces, then 1 million bytecodes takes roughly 25 seconds on a single RTX4090 graphics card which might cost 0.5 cent (The cost is 2000M instruction per USD). In such a solution, the cost mainly comes from the proving power fee, the on-chain verification fee and call data storage fee for DA. Using this approach to support a multi-player game with 100 billions of trace per hour will cost about 50 USD an hour (36,000 USD a month) as proving cost.
2. **Fraud Proof Approach**
Assume 5000 players play on average 2 hours non-stop; every player generate 86.4 billion lines of trace per hour. Then it’s 60 seconds * 60 minutes * 2 hours * 5000 players * 1million bytecode = 36,000,000,000,000 lines of traces. As tested by ETHstorage and zkwasm, every trace is 40 bytes. It follows that for a game of 5k players (with average online duration of 2 hours), 1,440 TB of storage is consumed per day. If we compress the trace at a reasonable rate of 10x, everyday we will consume 144 TB google cloud storage, this converts to 4,320 TB for a month and the cost is estimated at 90,120 USD / month (at Archive storage tier, at standard storage tier which allows more data access frequencies, it’ll be 185k / month). Additionally, the monthly cost of storing signature data on BNB Greenfield per GB is 0.0001 BNB, which is roughly $0.03 in USD. In this approach, observation nodes can check the consistency of the trace and trigger a ZKFraud proof to report a dishoest transaction.

We conclude that the total cost is roughly on-par for running a game at high player counts, as compared to running a DDOS resistant server.

# 6. Content Upgrade and Mod Protocol
A successful game often features dynamic content, necessitating regular updates to its engine. This appears to contradict the "code is law" philosophy prevalent in the crypto-native community. However, there are potential solutions to this challenge. By employing a design pattern that places maintainable rules on the blockchain, it's possible to ensure that upgrades or modifications to the gameplay adhere to these fundamental rules. Given the complexity of this topic within game architecture, the following diagram serves as a concise explanation.