Using zero-knowledge for a secret state
There are no secrets on the blockchain. Everything that is posted on the blockchain is open to everybody to read. This is necessary, because the blockchain is based on anybody being able to verify it. However, games often rely on secret state. For example, the game of minesweeper makes absolutely no sense if you can just go on a blockchain explorer and see the map.
The simplest solution is to use a server component to hold the secret state. However, the reason we use blockchain is to prevent cheating by the game developer. We need to ensure the server component's honesty. The server can provide a hash of the state, and use zero-knowledge proofs to prove that the state used to calculate the result of a move is the correct one.
After reading this article you will know how to create this kind of secret state holding server, a client for showing the state, and an onchain component for communication between the two. The main tools we use will be:
| Tool | Purpose | Verified on version |
|---|---|---|
| Zokrates | Zero-knowledge proofs and their verification | 1.1.9 |
| Typescript | Programming language for both the server and the client | 5.4.2 |
| Node | Running the server | 20.18.2 |
| Viem | Communication with the Blockchain | 2.9.20 |
| MUD | Onchain data management | 2.0.12 |
| React | Client user interface | 18.2.0 |
| Vite | Serving the client code | 4.2.1 |
Minesweeper example
Minesweeper is a game that includes a secret map with a minefield. The player chooses to dig in a specific location. If that location has a mine, it's game over. Otherwise, the player gets the number of mines in the eight squares surrounding that location.
This application is written using MUD, a framework that lets us store data onchain using a key-value database and synchronize that data automatically with offchain components. In addition to synchronization, MUD makes it easy to provide access control, and for other users to extend our application permissionlessly.
Running the minesweeper example
To run the minesweeper example:
Make sure you have the prerequisites installed: Node, Foundry,
git,pnpm, andmprocs.Clone the repository.
1git clone https://github.com/qbzzt/20240901-secret-state.gitInstall the packages.
1cd 20240901-secret-state/2pnpm install3npm install -g mprocsIf Foundry was installed as part of
pnpm install, you need to restart the command-line shell.Compile the contracts
1cd packages/contracts2forge build3cd ../..
Start the program (including an anvil blockchain) and wait.
1mprocsNote that the startup takes a long time. To see the progress, first use the down arrow to scroll to the contracts tab to see the MUD contracts being deployed. When you get the message Waiting for file changes…, the contracts are deployed and further progress will happen in the server tab. There, you wait until you get the message Verifier address: 0x.....
If this step is successful, you will see the
mprocsscreen, with the different processes on the left and the console output for the currently selected process on the right.
If there is a problem with
mprocs, you can run the four processes manually, each in its own command line window:Anvil
1cd packages/contracts2anvil --base-fee 0 --block-time 2Contracts
1cd packages/contracts2pnpm mud dev-contracts --rpc http://127.0.0.1:8545Server
1cd packages/server2pnpm startClient
1cd packages/client2pnpm run dev
Now you can browse to the client, click New Game, and start playing.
Tables
We need several tables onchain.
Configuration: This table is a singleton, it has no key and single record. It is used to hold game configuration information:height: The height of a minefieldwidth: The width of a minefieldnumberOfBombs: The number of bombs in each minefield
VerifierAddress: This table is also a singleton. It is used to hold one part of the configuration, the address of the verifier contract (verifier). We could have put this information in theConfigurationtable, but it is set by a different component, the server, so it's easier to put it in a separate table.PlayerGame: The key is the player's address. The data is:gameId: 32-byte value that is the hash of the map the player is playing on (the game identifier).win: a boolean that is whether the player won the game.lose: a boolean that is whether the player lost the game.digNumber: the number of successful digs in the game.
GamePlayer: This table holds the reverse mapping, fromgameIdto player address.Map: The key is a tuple of three values:gameId: 32-byte value that is the hash of the map the player is playing on (the game identifier).xcoordinateycoordinate
The value is a single number. It's 255 if a bomb was detected. Otherwise, it is the number of bombs around that location plus one. We cannot just use the number of bombs, because by default all storage in the EVM and all row values in MUD are zero. We need to distinguish between "the player haven't dug here yet" and "the player dug here, and found there are zero bombs around".
In addition, communication between the client and server happens through the onchain component. This is also implemented using tables.
PendingGame: Unserviced requests to start a new game.PendingDig: Unserviced requests to dig in a specific place in a specific game. This is an offchain table, meaning that it does not get written to EVM storage, it's only readable offchain using events.
Execution and data flows
These flows coordinate execution between the client, the onchain component, and the server.
Initialization
When you run mprocs, these steps happen:
mprocsruns four components:The
contractspackage deploys the MUD contracts and then runs thePostDeploy.s.solscript. This script sets the configuration. The code from github specifies a 10x5 minefield with eight mines in it.The server starts by setting up MUD. Among other things, this activates data synchronization, so that a copy of the relevant tables exists in the server's memory.
The server subscribes a function to be executed when the
Configurationtable changes. This function is called afterPostDeploy.s.solexecutes and modifies the table.When the server initialization function has the configuration, it calls
zkFunctionsto initialize the zero-knowledge part of the server. This cannot happen until we get the configuration because the zero-knowledge functions have to have the width and height of the minefield as constants.After the zero-knowledge part of the server is initialized, the next step is to deploy the zero-knowledge verification contract to the blockchain and set the verifiee address in MUD.
Finally, we subscribe to updates so we'll see when a player requests either to start a new game or to dig in an existing game.
New game
This is what happens when the player requests a new game.
If there is no game in progress for this player, or there is one but with a gameId of zero, the client displays a new game button. When the user presses this button, React runs the
newGamefunction.newGameis aSystemcall. In MUD all calls are routed through theWorldcontract, and in most cases you call<namespace>__<function name>. In this case, the call is toapp__newGame, which MUD then routes tonewGameinGameSystem.The onchain function checks that the player does not have a game in progress, and if there isn't one adds the request to the
PendingGametable.The server detects the change in
PendingGameand runs the subscribed function. This function callsnewGame, which in turn callscreateGame.The first thing
createGamedoes is create a random map with the appropriate number of mines. Then, it callsmakeMapBordersto create a map with blank borders, which is necessary for Zokrates. Finally,createGamecallscalculateMapHash, to get the hash of the map, which is used as the game ID.The
newGamefunction adds the new game togamesInProgress.The last thing the server does is call
app__newGameResponse, which is onchain. This function is in a differentSystem,ServerSystem, to enable access control. Access control is defined in the MUD configuration file,mud.config.ts.The access list only allows a single address to call the
System. This restricts access to the server functions to a single address, so nobody can impersonate the server.The onchain component updates the relevant tables:
- Create the game in
PlayerGame. - Set the reverse mapping in
GamePlayer. - Remove the request from
PendingGame.
- Create the game in
The server identifies the change in
PendingGame, but does not do anything becausewantsGameis false.On the client
gameRecordis set to thePlayerGameentry for the player's address. WhenPlayerGamechanges,gameRecordchanges too.If there is a value in
gameRecord, and the game hasn't been won or lost, the client displays the map.
Dig
The player clicks the map cell's button, which calls the
digfunction. This function callsdigonchain.The onchain component performs a number of sanity checks, and if successful adds the dig request to
PendingDig.The server detects the change in
PendingDig. If it is valid, it calls the zero-knowledge code (explained below) to generate both the result and a proof that it is valid.The server calls
digResponseonchain.digResponsedoes two things. First, it checks the zero knowledge proof. Then, if the proof checks out, it callsprocessDigResultto actually process the result.processDigResultchecks if the game has been lost or won, and updatesMap, the onchain map.The client picks up the updates automatically and updates the map displayed to the player, and if applicable tells the player if it's a win or a lose.
Using Zokrates
In the flows explained above we skipped over the zero-knowledge parts, treating them as a black box. Now let's crank it open and see how that code is written.
Hashing the map
We can use this JavaScript code to implement Poseidon, the Zokrates hash function we use. However, while this would be faster, it would also be more complicated than just using the Zokrates hash function to do it. This is a tutorial, and so the code is optimized for simplicity, not for performance. Therefore, we need two different Zokrates programs, one to just calculate the hash of a map (hash) and one to actually create a zero-knowledge proof of the result of the dig in a location on the map (dig).
The hash function
This is the function that calculates the hash of a map. We'll go over this code line by line.
1import "hashes/poseidon/poseidon.zok" as poseidon;2import "utils/pack/bool/pack128.zok" as pack128;
These two lines import two functions from the Zokrates standard library. The first function is a Poseidon hash. It takes an array of field elements and returns a field.
The field element in Zokrates is typically less than 256 bits long, but not by much. To simplify the code, we restrict the map to be up to 512 bits, and hash an array of four fields, and in each field we use only 128 bits. The pack128 function changes an array of 128 bits into a field for this purpose.
1 def hashMap(bool[${width+2}][${height+2}] map) -> field {
This line starts a function definition. hashMap gets a single parameter called map, a two dimensional bool(ean) array. The size of the map is width+2 by height+2 for reasons that are explained below.
We can use ${width+2} and ${height+2} because the Zokrates programs are stored in this application as template strings. Code between ${ and } is evaluated by JavaScript, and this way the program can be used for different map sizes. The map parameter has a one location wide border all around it without any bombs, which is the reason we need to add two to the width and height.
The return value is a field that contains the hash.
1 bool[512] mut map1d = [false; 512];
The map is two-dimensional. However, the pack128 function does not work with two-dimensional arrays. So we first flatten the map into a 512-byte array, using map1d. By default Zokrates variables are constants, but we need to assign values to this array in a loop, so we define it as mut.
We need to initialize the array because Zokrates doesn't have undefined. The [false; 512] expression means an array of 512 false values.
1 u32 mut counter = 0;
We also need a counter to distinguish between the bits we already filled in map1d and those we haven't.
1 for u32 x in 0..${width+2} {
This is how you declare a for loop in Zokrates. A Zokrates for loop has to have fixed bounds, because while it appears to be a loop, the compiler actually "unrolls" it. The expression ${width+2} is a compile time constant because width is set by the TypeScript code before it calls the compiler.
1 for u32 y in 0..${height+2} {2 map1d[counter] = map[x][y];3 counter = counter+1;4 }5 }
For every location in the map, put that value in the map1d array and increment the counter.
1 field[4] hashMe = [2 pack128(map1d[0..128]),3 pack128(map1d[128..256]),4 pack128(map1d[256..384]),5 pack128(map1d[384..512])6 ];
The pack128 to create an array of four field values from map1d. In Zokrates array[a..b] means the slice of the array that starts at a and ends at b-1.
1 return poseidon(hashMe);2}
Use poseidon to convert this array to a hash.
The hash program
The server needs to call hashMap directly to create game identifiers. However, Zokrates can only call the main function on a program to start, so we create a program with a main that calls the hash function.
1${hashFragment}23def main(bool[${width+2}][${height+2}] map) -> field {4 return hashMap(map);5}
The dig program
This is the heart of the zero-knowledge part of the application, where we produce the proofs that are used to verify dig results.
1${hashFragment}23// The number of mines in location (x,y)4def map2mineCount(bool[${width+2}][${height+2}] map, u32 x, u32 y) -> u8 {5 return if map[x+1][y+1] { 1 } else { 0 };6}
Why map border
Zero-knowledge proofs use arithmetic circuits, which don't have an easy equivalent to an if statement. Instead, they use the equivalent of the conditional operator. If a can be either zero or one, you can calculate if a { b } else { c } as ab+(1-a)c.
Because of this, a Zokrates if statement always evaluates both branches. For example, if you have this code:
1bool[5] arr = [false; 5];2u32 index=10;3return if index>4 { 0 } else { arr[index] }
It will error out, because it needs to calculate arr[10], even though that value will be later multiplied by zero.
This is the reason we need a one location wide border all around the map. We need to calculate the total number of mines around a location, and that means we need to see the location one row above and below, to the left and to the right, of the location where we're digging. Which means those location have to exist in the map array that Zokrates is provided.
1def main(private bool[${width+2}][${height+2}] map, u32 x, u32 y) -> (field, u8) {
By default Zokrates proofs include their inputs. It does no good to know there are five mines around a spot unless you actually know which spot it is (and you can't just match it to your request, because then the prover could use different values and not tell you about it). However, we need to keep the map a secret, while providing it to Zokrates. The solution is to use a private parameter, one that is not revealed by the proof.
This opens another venue for abuse. The prover could use the correct coordinates, but create a map with any number of mines around the location, and possibly at the location itself. To prevent this abuse, we make the zero knowledge proof include the hash of the map, which is the game identifier.
1 return (hashMap(map),
The return value here is a tuple that includes the map hash array as well as the dig result.
1 if map2mineCount(map, x, y) > 0 { 0xFF } else {
We use 255 as a special value in case the location itself has a bomb.
1 map2mineCount(map, x-1, y-1) + map2mineCount(map, x, y-1) + map2mineCount(map, x+1, y-1) +2 map2mineCount(map, x-1, y) + map2mineCount(map, x+1, y) +3 map2mineCount(map, x-1, y+1) + map2mineCount(map, x, y+1) + map2mineCount(map, x+1, y+1)4 }5 );6}
If the player hasn't hit a mine, add the mine counts for the area around the location and return that.
Using Zokrates from TypeScript
Zokrates has a command line interface, but in this program we use it in the TypeScript code.
The library that contains the Zokrates definitions is called zero-knowledge.ts.
1import { initialize as zokratesInitialize } from "zokrates-js"
Import the Zokrates JavaScript bindings. We only need the initialize function because it returns a promise that resolves to all the Zokrates definitions.
1export const zkFunctions = async (width: number, height: number) : Promise<any> => {
Similar to Zokrates itself, we also export only one function, which is also asynchronous. When it eventually returns, it provides several functions as we'll see below.
1const zokrates = await zokratesInitialize()
Initialize Zokrates, get everything we need from the library.
1const hashFragment = `2 import "utils/pack/bool/pack128.zok" as pack128;3 import "hashes/poseidon/poseidon.zok" as poseidon;4 .5 .6 .7 }8 `910const hashProgram = `11 ${hashFragment}12 .13 .14 .15 `1617const digProgram = `18 ${hashFragment}19 .20 .21 .22 `అన్నీ చూపించు
Next we have the hash function and two Zokrates programs we saw above.
1const digCompiled = zokrates.compile(digProgram)2const hashCompiled = zokrates.compile(hashProgram)
Here we compile those programs.
1// Create the keys for zero knowledge verification.2// On a production system you'd want to use a setup ceremony.3// (https://zokrates.github.io/toolbox/trusted_setup.html#initializing-a-phase-2-ceremony).4const keySetupResults = zokrates.setup(digCompiled.program, "")5const verifierKey = keySetupResults.vk6const proverKey = keySetupResults.pk
On a production system we might use a more complicated setup ceremony, but this is good enough for a demonstration. It's not a problem that the users can know the prover key - they still cannot use it to prove things unless they are true. Because we specify the entropy (the second parameter, ""), the results are always going to be the same.
Note: Compilation of Zokrates programs and key creation are slow processes. There is no need to repeat them every time, just when map size changes. On a production system you'd do them once, and then store the output. The only reason I am not doing it here is for the sake of simplicity.
calculateMapHash
1const calculateMapHash = function (hashMe: boolean[][]): string {2 return (3 "0x" +4 BigInt(zokrates.computeWitness(hashCompiled, [hashMe]).output.slice(1, -1))5 .toString(16)6 .padStart(64, "0")7 )8}
The computeWitness function actually runs the Zokrates program. It returns a structure with two fields: output, which is the output of the program as a JSON string, and witness, which is the information needed to create the a zero knowledge proof of the result. Here we just need the output.
The output is a string of the form "31337", a decimal number enclosed in quotation marks. But the output we need for viem is a hexadecimal number of the form 0x60A7. So we use .slice(1,-1) to remove the quotation marks and then BigInt to run the remaining string, which is a decimal number, to a BigInt. .toString(16) converts this BigInt into a hexadecimal string, and "0x"+ adds the marker for hexadecimal numbers.
1// Dig and return a zero knowledge proof of the result2// (server-side code)
The zero knowledge proof includes the public inputs (x and y) and results (hash of the map and number of bombs).
1 const zkDig = function(map: boolean[][], x: number, y: number) : any {2 if (x<0 || x>=width || y<0 || y>=height)3 throw new Error("Trying to dig outside the map")
It's a problem to check if an index is out of bounds in Zokrates, so we do it here.
1const runResults = zokrates.computeWitness(digCompiled, [map, `${x}`, `${y}`])
Execute the dig program.
1 const proof = zokrates.generateProof(2 digCompiled.program,3 runResults.witness,4 proverKey)56 return proof7 }
Use generateProof and return the proof.
1const solidityVerifier = `2 // Map size: ${width} x ${height}3 \n${zokrates.exportSolidityVerifier(verifierKey)}4 `
A Solidity verifier, a smart contract we can deploy to the blockchain and use to verify proofs generated by digCompiled.program.
1 return {2 zkDig,3 calculateMapHash,4 solidityVerifier,5 }6}
Finally, return everything that other code might need.
Security tests
Security tests are important because a functionality bug will eventually reveal itself. But if the application is insecure, that is likely to remain hidden for a long time before it is revealed by somebody cheating and getting away with resources that belong to others.
Permissions
There is one privileged entity in this game, the server. It is the only user allowed to call the functions in ServerSystem. We can use cast to verify calls to permissioned functions are only allowed as the server account.
The server's private key is in setupNetwork.ts.
On the computer that runs
anvil(the blockchain), set these environment variables.1WORLD_ADDRESS=0x8d8b6b8414e1e3dcfd4168561b9be6bd3bf6ec4b2UNAUTHORIZED_KEY=0x5de4111afa1a4b94908f83103eb1f1706367c2e68ca870fc3fb9a804cdab365a3AUTHORIZED_KEY=0x59c6995e998f97a5a0044966f0945389dc9e86dae88c7a8412f4603b6b78690dUse
castto attempt to set the verifier address as an unauthorized address.1cast send $WORLD_ADDRESS 'app__setVerifier(address)' `cast address-zero` --private-key $UNAUTHORIZED_KEYNot only does
castreport a failure, but you can open MUD Dev Tools in the game on the browser, click Tables, and select app__VerifierAddress. See that the address is not zero.Set the verifier address as the server's address.
1cast send $WORLD_ADDRESS 'app__setVerifier(address)' `cast address-zero` --private-key $AUTHORIZED_KEYThe address in app__VerifiedAddress should now be zero.
All MUD functions in the same System go through the same access control, so I consider this test sufficient. If you don't, you can check the other functions in ServerSystem.
Zero-knowledge abuses
The math to verify Zokrates is beyond the scope of this tutorial (and my abilities). However, we can run various checks on the zero-knowledge code to verify that if it is not done correctly it fails. All of these tests are going to require us to change zero-knowledge.ts and restart the entire application. It is not sufficient to restart the server process, because it puts the application in an impossible state (the player has a game in progress, but the game is no longer available to the server).
Wrong answer
The simplest possibility is to provide the wrong answer in the zero-knowledge proof. To do that, we go inside zkDig and modify line 91:
1proof.inputs[3] = "0x" + "1".padStart(64, "0")
This means we'll always claim there is one bomb, regardless of the correct answer. Try to play with this version, and you'll see in the server tab of the pnpm dev screen this error:
1 cause: {2 code: 3,3 message: 'execution reverted: revert: Zero knowledge verification fail',4 data: '0x08c379a00000000000000000000000000000000000000000000000000000000000000020000000000000005000000000000000000000000000000000000000000000000205a65726f206b6e6f776c6564676520766572696669636174696f66e206661696c'7 },
So this kind of cheat fails.
Wrong proof
What happens if we provide the correct information, but just have the wrong proof data? Now, replace line 91 with:
1proof.proof = {2 a: ["0x" + "1".padStart(64, "0"), "0x" + "2".padStart(64, "0")],3 b: [4 ["0x" + "1".padStart(64, "0"), "0x" + "2".padStart(64, "0")],5 ["0x" + "1".padStart(64, "0"), "0x" + "2".padStart(64, "0")],6 ],7 c: ["0x" + "1".padStart(64, "0"), "0x" + "2".padStart(64, "0")],8}
It still fails, but now it fails without a reason because it happens during the verifier call.
How can a user verify the zero trust code?
Smart contracts are relatively easy to verify. Typically, the developer publishes the source code to a block explorer, and the block explorer verifies that the source code does compile to the code in the contract deployment transaction. In the case of MUD Systems this is slightly more complicated, but not by much.
This is harder with zero-knowledge. The verifier includes some constants and runs some calculations on them. This doesn't tell you what is being proved.
1 function verifyingKey() pure internal returns (VerifyingKey memory vk) {2 vk.alpha = Pairing.G1Point(uint256(0x0f43f4fe7b5c2326fed4ac6ed2f4003ab9ab4ea6f667c2bdd77afb068617ee16), uint256(0x25a77832283f9726935219b5f4678842cda465631e72dbb24708a97ba5d0ce6f));3 vk.beta = Pairing.G2Point([uint256(0x2cebd0fbd21aca01910581537b21ae4fed46bc0e524c055059aa164ba0a6b62b), uint256(0x18fd4a7bc386cf03a95af7163d5359165acc4e7961cb46519e6d9ee4a1e2b7e9)], [uint256(0x11449dee0199ef6d8eebfe43b548e875c69e7ce37705ee9a00c81fe52f11a009), uint256(0x066d0c83b32800d3f335bb9e8ed5e2924cf00e77e6ec28178592eac9898e1a00)]);కాపీ
The solution, at least until block explorers get around to adding Zokrates verification to their user interfaces, is for the application developers to make available the Zokrates programs, and for at least some users to compile them themselves with the appropriate verification key.
To do so:
Create a file,
dig.zok, with the Zokrates program. The code below assumes you kept the original map size, 10x5.1 import "utils/pack/bool/pack128.zok" as pack128;2 import "hashes/poseidon/poseidon.zok" as poseidon;34 def hashMap(bool[12][7] map) -> field {5 bool[512] mut map1d = [false; 512];6 u32 mut counter = 0;78 for u32 x in 0..12 {9 for u32 y in 0..7 {10 map1d[counter] = map[x][y];11 counter = counter+1;12 }13 }1415 field[4] hashMe = [16 pack128(map1d[0..128]),17 pack128(map1d[128..256]),18 pack128(map1d[256..384]),19 pack128(map1d[384..512])20 ];2122 return poseidon(hashMe);23 }అన్నీ చూపించు
1// The number of mines in location (x,y)2def map2mineCount(bool[12][7] map, u32 x, u32 y) -> u8 {3 return if map[x+1][y+1] { 1 } else { 0 };4}56def main(private bool[12][7] map, u32 x, u32 y) -> (field, u8) {7 return (hashMap(map) ,8 if map2mineCount(map, x, y) > 0 { 0xFF } else {9 map2mineCount(map, x-1, y-1) + map2mineCount(map, x, y-1) + map2mineCount(map, x+1, y-1) +10 map2mineCount(map, x-1, y) + map2mineCount(map, x+1, y) +11 map2mineCount(map, x-1, y+1) + map2mineCount(map, x, y+1) + map2mineCount(map, x+1, y+1)12 }13 );14}అన్నీ చూపించు
123. Compile the Zokrates code and create the verification key. The verification key has to be created with the same entropy used in the original server, [in this case an empty string](https://github.com/qbzzt/20240901-secret-state/blob/main/packages/server/src/zero-knowledge.ts#L67).34```sh copy5zokrates compile --input dig.zok6zokrates setup -e ""
Create the Solidity verifier on your own, and verify it is functionally identical to the one on the blockchain (the server adds a comment, but that's not important).
1zokrates export-verifier2diff verifier.sol ~/20240901-secret-state/packages/contracts/src/verifier.sol
Design decisions
In any sufficiently complex application there are competing design goals that require trade-offs. Let's look at some of the tradeoffs and why the current solution is preferable to other options.
Why zero-knowledge
For minesweeper you don't really need zero-knowledge. The server can always hold the map, and then just reveal all of it when the game is over. Then, at the end of the game, the smart contract can calculate the map hash, verify that it matches, and if it doesn't penalize the server or disregard the game completely.
I didn't use this simpler solution because it only works for short games with a well defined end state. When a game is potentially infinite (such as the case with autonomous worlds), you need a solution that proves the state without revealing it.
As a tutorial this article needed a short game that is easy to understand, but this technique is most useful for longer games.
Why Zokrates?
Zokrates isn't the only zero-knowledge library available, but it is similar to a normal, imperative programming language and supports boolean variables.
For your application, with different requirements, you might prefer to use Circum or Cairo.
When to compile Zokrates
In this program we compile the Zokrates programs every time the server starts. This is clearly a waste of resources, but this is a tutorial, optimized for simplicity.
If I were writing a production-level application, I'd check if I have a file with the compiled Zokrates programs at this minefield size, and if so use that. The same is true for deploying a verifier contract onchain.
Creating the verifier and prover keys
Key creation is another pure calculation that needn't be done more than once for a given minefield size. Again, it is done only once for the sake of simplicity.
Additionally, we could use a setup ceremony. The advantage of a setup ceremony is that you need either the entropy or some intermediate result from each participant to cheat on the zero-knowledge proof. If at least one ceremony participant is honest and deletes that information, the zero-knowledge proofs are safe from certain attacks. However, there is no mechanism to verify that information has been deleted from everywhere. If zero-knowledge proofs are critically important, you want to participate in the setup ceremony.
Here we rely on perpetual powers of tau, which had dozens of participants. It is probably safe enough, and much simpler. We also don't add entropy to the during key creation, which makes it easier for users to verify the zero-knowledge configuration.
Where to verify
We can verify the zero-knowledge proofs either onchain (which costs gas) or in the client (using verify). I chose the first, because this lets you verify the verifier once and then trust that if doesn't change as long as the contract address for it stays the same. If verification was done on the client, you'd have to verify the code you receive each time you download the client.
Also, while this game is single player, a lot of blockchain games are multi-player. onchain verification means you only verify the zero-knowledge proof once. Doing it in the client would require each client to verify independently.
Flatten the map in TypeScript or Zokrates?
In general, when processing can be done either in TypeScript or Zokrates, it is better to do it TypeScript, which is a lot faster, and does not require zero-knowledge proofs. This is the reason, for example, that we don't provide Zokrates with the hash and make it verify that it is correct. Hashing has to be done inside Zokrates, but the match between the returned hash and the hash onchain can happen outside it.
However, we still flatten the map in Zokrates, whereas we could have done it in TypeScript. The reason is that the other options are, in my opinion, worse.
Provide a one dimensional array of boolean to the Zokrates code, and use an expression such as
x*(height+2) +yto get the two dimensional map. This would make the code somewhat more complicated, so I decided the performance gain isn't worth it for a tutorial.Send Zokrates both the one dimensional array and the two dimensional array. However, this solution doesn't gain us anything. The Zokrates code would have to verify that the one dimensional array it is provided really is the correct representation of the two dimensional array. So there wouldn't be any performance gain.
Flatten the two dimensional array in Zokrates. This is the simplest option, so I chose it.
Where to store maps
In this application gamesInProgress is simply a variable in memory. This means that if you server dies and needs to be restarted, all the information it stored is lost. Not only are players unable to continue their game, they cannot even start a new game because the onchain component thinks they still have a game in progress.
This is clearly bad design for a production system, in which you'd store this information in a database. The only reason I used a variable here is because this is a tutorial and simplicity is the main consideration.
Conclusion: Under what conditions is this the appropriate technique?
So, now you know how to write a game with a server that stores secret state that doesn't belong onchain. But in what cases should you do it? There are two main considerations.
Long running game: As mentioned above, in a short game you can just publish the state once the game is over and have everything verified then. But that is not an option when the game takes a long or indefinite time, and the state needs to stay secret.
Some centralization acceptable: Zero-knowledge proofs can verify integrity, that an entity is not faking the results. What they can't do is ensure that the entity will still be available and answer messages. In situations where availability also needs to be decentralized, zero-knowledge proofs are not a sufficient solution, and you need multi-party computation.
Acknowledgements
- Alvaro Alonso read a draft of this article and cleared up some of my misunderstandings about Zokrates.
Any remaining errors are my responsibility.