Mastermind zkApp Example Series: A Step-by-Step Guide to Building zkApps on Mina

Learn how to design and implement robust zkApps through exploring Mastermind architectures and API usage.

image

Since our beginnings in the summer of 2024, the Exploration Team has had the sole goal of supporting you, the developer community, by providing the examples, tutorials, and tools you need to build. That's why we've created the Mastermind series, a 5-level example of building the Mastermind game where each iteration demonstrates an SDK feature and pattern that you can adapt to your own use cases.

The game itself is simple - a code master selects a 4-digit secret code, and the codebreaker tries to guess the code. With each round, the codebreaker submits a 4-digit guess. The code master responds by telling the codebreaker if they've guessed any of the digits correctly and whether or not those digits appear in the same position as they do in the code.

We settled on Mastermind because it's a natural candidate for ZK - the code must stay a secret but the zkApp still needs to reason about the characteristics of the code to determine whether or not the codebreaker has guessed correctly. In each level, we highlight a different architectural pattern or primitive for building with o1js.

In summary, the mastermind zkApp series is structured as follows:

  • Level 1: Setting up the foundations
  • Level 2: Storing the game history state using packing techniques
  • Level 3: Storing the game history state using the Indexed Merkle Map API
  • Level 4: Storing the game history state using the Offchain Storage API
  • Level 5: Integrating recursion into the game

Note: Each level is represented as a separate branch in this repository.

Level 1: Setting up the foundation

Level 1 shows the most basic version of the game, and all subsequent levels build upon it to demonstrate changes in architectures and APIs. It's implemented as a smart contract with no off-chain storage but still highlights some important patterns. We introduce the pattern of storing a hash of secret data on a contract and then requiring users to submit the private data in method calls which the contract can then verify against the hash. The data stays private because it's never published on-chain, but the user can't execute the contract with fake data because it's verified against the hash during method execution! We also highlight the three approaches to smart contract state initialization. These cover the scenarios where you need to initialize a contract with non-zero but hardcoded state, dynamic state supplied by the user, or are starting with all of your state set to zero.

Level 1 does more than simply showcase a Mastermind game implementation. It aims to help developers grasp the fundamentals of zkApps, covering architectural design, security considerations, best practices, and relevant APIs.

Level 2: Storing the game history state using packing

In this level, we get into optimizing the usage of on-chain storage space. Mina zkApp accounts are limited to 8 fields of storage, and you may be able to avoid the complexities of off-chain storage by packing your data into those fields. We demonstrate storing the game history by serializing the 4-digit clues and 4-digit guesses into their respective packedClueHistory and packedGuessHistory fields. Since a Field is 2²⁵⁵ bits, and the largest 4-digit guess, 9999, only takes 14 bits to represent (as 10011100001111), we can fit up to 18 guesses or clues in one Field on-chain! We also highlight dynamic indexing for retrieving the latest guess from the on-chain packed state and dynamic updating for updating the packed clue history with its corresponding clue.

Unpacking the histories yields an array of fields and because indexing or updating such an array by a Field-based index (e.g., turnCount) requires a unique approach, these operations must be handled differently. This level explains these nuances in detail.

Level 3: Storing the game history state using the Indexed Merkle Map API

Level 3 is where things start to get trickier - we give you your first taste of off-chain storage with IndexedMerkleMap. In this version of the game, a state commitment is stored on-chain but the data itself is stored off chain. The users construct an IndexedMerkleMap containing the guesses and clues submitted over the course of the game, but only the root of the map is stored on-chain. When a method is called which needs to access the off-chain state, the user passes in the full map as a method parameter, and the smart contract verifies that the map has the same root as the one that's been stored on-chain. This way, the contract itself doesn't need to store all of the application data, but the users are guaranteed to be acting on the same data that the contract is expecting. This is the foundation for some more advanced patterns but is often not adequate for production applications because it introduces a race condition.

When many users invoke zkApp methods to update the Merkle Map and its corresponding root, each user commits to a previous root to verify the integrity of off-chain storage. However, because transactions are sequenced by block producers and may occur in a different order than expected, the root can be updated prematurely relative to other transactions. This discrepancy can lead to concurrency issues during root updates, and this is where Level 4 steps in to resolve the issue.

Level 4: Storing the game history state using the Offchain Storage API

This level is built with the experimental off-chain storage API. Where level 3 had us directly managing off-chain state in our own data structure, level 4 has Mina archive nodes tracking off-chain state and sequencing state updates using actions and reducers. The off-chain storage API lets multiple users act on the same state at the same time without the concurrency problem caused by managing a state commitment without a reducer, but this API will change when we roll out v2. We hope to provide more intuitive APIs for off-chain state management in the V2 APIs, and eventually a more comprehensive solution with [Project Untitled].

Note: While this example does not focus on concurrency issues, as the game is fundamentally interactive and sequential, it serves as a reference for addressing such concerns in applications where concurrency matters.

Level 5: Integrating recursion into the game

In Level 5, we return to the basic version of the game which does not store guess or clue history. Instead, we highlight one of o1js's most powerful features - recursive proving. Recursive proof generation is where you generate a proof for one circuit, and then you verify that proof in another circuit. You can do this as many times as you want, so it's a powerful tool to have when faced with limited circuit sizes.

Compared to Level 1, this implementation delegates certain statements such as proving a valid guess or clue to external ZkPrograms instead of handling them directly within the zkApp. By leveraging proof composability, the design showcases how to modularize provable code into external ZkProgram proofs.

This is referred to as recursion because the zkApp method, which already generates its own proof, now also verifies an externally generated proof. In essence, one proof validates another, embodying the concept of recursion.

This implementation goes a step further by showcasing the general use cases for recursion. Dive in and explore more details here!

Summary

The Mastermind series is our way of making concepts like off-chain storage and recursion accessible by presenting them in an engaging game. Each level comes with unit tests, so we encourage you to gain some hands-on experience by cloning the repo, running the tests, and editing the code yourself.

We are excited about the feedback we’ve received so far! Developers have shared how helpful these examples are in bridging the gap between theory and practice. In the coming weeks, we will be releasing videos for each level, which will break down the examples and help you apply these patterns to your own projects. We can’t wait to see what you will build!

If you have any questions or feedback, feel free to tag the o1-exploration-team on the Mina zkapps-developers Discord channel.

undefinedundefined