ZK Mastermind using Noir

Gameplay

The game has two players, a code master and code breaker.

The code master generates 4 secret digits in a set sequence. Digits can be between 1-9 and the digits must all be different. Then, each turn, the code breaker tries to guess the code master's digits, who then gives the number of matches.
If the matching digits are in their right positions, they are "hits", if they in different positions, they are "blows".

Example:

Code master private solution: 4 2 7 1
Code breaker's public solution: 1 2 3 4
Answer: 1 hit and 2 blows. (The hit is "2" in the second position, the blows are "4" and "1".)

The code breaker wins by guessing the secret sequence in a set number of attempts. In the example above, if the maximum number of attempts is not yet reached and in the next round the code breaker guessed the exact sequence "4 2 7 1" they will have 4 hits and win the game.

There are many variations of Mastermind (this implementation is one of them). More information on the game can be found here: https://en.wikipedia.org/wiki/Mastermind_(board_game).

Requirements

• Noir is based upon Rust, and we will need to Noir's package manager nargo in order to compile our circuits. Further installation instructions for can be found here.
  • If there are troubles installing nargo due to the C++ backend, replace the aztec_backend dependency in the nargo crate's Cargo.toml with this line:

  aztec_backend = { optional = true, git = "https://github.com/noir-lang/aztec_backend", rev = "d91c69f2137777cec37f692f98d075ae10e7a584", default-features = false, features = [
      "wasm-base",
  ] }
  

• The typescript tests and contracts live within a hardhat project, where we use yarn as the package manager.

Development

Start by installing all the packages specified in the package.json

yarn install

After installing nargo it should be placed in our path and can be called from inside the circuits folder. We will then compile our circuit. This will generate an intermediate representation that is called the ACIR. More infomration on this can be found here. p in nargo compile p is simply the name of the ACIR and witness files generated by Noir when compiling the circuit. These will be used by the tests.

cd circuits/
nargo compile p

We use these three packages to interact with the ACIR and aztec backend. @noir-lang/noir_wasm, @noir-lang/barretenberg, and @noir-lang/aztec_backend.

@noir-lang/noir_wasm is used to serialize the ACIR from file.

let acirByteArray = path_to_uint8array(path.resolve(__dirname, '../circuits/build/p.acir'));
let acir = acir_from_bytes(acirByteArray);

It is also possible to instead compile the program in Typescript. This can be seen inside the test file.

let compiled_program = compile(resolve(__dirname, '../circuits/src/main.nr);
const acir = compiled_program.circuit;

Then @noir-lang/barretenberg is used to generate a proof and verify that proof. We first specify the ABI for the circuit. This contains all the public and private inputs to the program and is generated by the prover. In the case of our typescript tests, each test acts as both the prover and the verifier, and only passes if the proof passes verification.

These values in the abi are all calculated inside the test file for each test, but they are written out here.

let abi = {
    guessA: 1, 
    guessB: 2,
    guessC: 3,
    guessD: 4,
    numHit: 2,
    numBlow: 1,
    solnHash: "0x08e8e119c5ed9b689501697af6c475e1e12d3ae4528b67ea596ad7a23a8b13c2",
    solnA: 1,
    solnB: 3,
    solnC: 5,
    solnD: 4,
    salt: 50,
}

We will then construct our prover and verifier from the ACIR, and generate a proof from the prover, ACIR, and newly specified ABI.

let [prover, verifier] = await setup_generic_prover_and_verifier(acir);

const proof = await create_proof(prover, acir, abi);

The verify_proof method then takes in the previously generated verifier and proof and returns either true or false. A verifier also needs to accept the circuits public inputs in order to be valid. Our prover prepends the public inputs to the proof.

const verified = await verify_proof(verifier, proof);

Solidity Verifier

Once we have compiled our program and generated an ACIR, we can generate a Solidity verifier rather than having to use the verifier provided by nargo or Noir's typescript wrapper.

In the scripts folder you will find a script for compiling a program and generating the Solidity verifier. You can call it using the command below (assuming you are in the root directory of the project).

npx ts-node ./scripts/generate_sol_verifier.ts

Running tests

The tests show both the method of compiling the circuit using nargo and in Typescript. The tests also show how to complete proof verification using Typescript as well as with the Solidity verifier. Thus, to have all tests pass, it is necessary you follow all the commands listed or change the tests to your preferred method of compilation and/or proof verification.

This command will compile the Solidity verifier within the contracts folder and run all tests inside ./test/mm.ts.

npx hardhat test