Recently there is a rise in discussion about the potentials of ZKP — Zero Knowledge Proofs in crypto. Jumping on the bandwagon, I decided to learn circom and try to implement Conway’s Game of Life as a zkSNARK circuit, as well as use the circuit in an NFT smart contract.

In this post I will write briefly about the technologies in use, present my circuit, and explain how it works.

You can view the code here: https://github.com/rubydusa/proof-of-life

For the purposes of this post, a Zero-Knowledge-Proof means a mathematical proof that a piece of data upholds a set of constraints, without revealing what that piece of data is, and without revealing anything else about it.

a zkSNARK — Zero Knowledge Succinct Non-Interactive Argument of Knowledge is a type of a Zero Knowledge Proof that requires a single interaction between the prover and verifier, and is short.

Circom is a programming language to write programs (called circuits) that take a set of inputs, and describe constraints about them, as well as having one, many or no outputs.

Using these constraints, you can generate proofs that you know a set of inputs that uphold the constraints as well as verify proofs.

In this post I will show an NFT contract that mints a token anytime someone provides a proof that they have a solution to the following problem:

Find a Game of Life grid state such that after N iterations, the grid state matches some predefined state:

For a finite grid state of life, I’ll be using the wrapped variant:

To clarify, whenever I say “solution” I refer to grid states that apply to the problem aforementioned .

Duplicate Solutions are not allowed.

ZKPs allow us to keep the solutions private after submission, prevent frontrunning, and create large puzzles of this sort.

This section will cover implementation details and explain the architecture of the project:

The Circuit

The circuit is parameterized over N — number of iterations, W — grid width, H — grid height.

It has three outputs:

• out — the state of the grid after N iterations
• solutionHash — the hash of “out”, required so the contract can verify it is not a duplicate solution
• hash — the hash of “address” combined with “solutionHash”, required in order to prevent frontrunning (more on that later)

And two inputs:

• address (public) — the address of the prover
• data (private) — the solution to “out”

The grid state is represented as a single* 254 bit-number, and broken down to a W×H bit matrix. Then, the life algorithm is applied N times and the output is constrained to be whatever happens to be the result.

*In the actual circuit it is extended to support grids that have more than 254 cells by patching together the bits of a sequence of 254 bit-numbers

The Verifier Contract

In order to verify proofs on-chain, we need to compile our circuits into solidity contract templates. These contracts have a single public function that take proof data as an input, and return a boolean value indicating whether the proof is valid or not.

In the case of the groth16 protocol, the function signature looks like this:

function verifyProof( 
uint[2] memory a,    uint[2][2] memory b,    uint[2] memory c,    uint[4] memory input) public view returns (bool r)

Since I’m not a cryptographer I’m not able to explain the details of a, b, and c — think of them as “the private part” of the proof, and the input parameter consists of the public inputs and outputs of the circuit.

Note that outputs are also part of the verification input, as the contract is only responsible for validating a proof, not computing it.

The NFT Contract

The NFT contract inherits from ERC721Enumerable, and has these additional storage variables:

uint256 public prizenum;mapping(uint256 => bool) public proofs;IGroth16Verifier public verifier;

• prizenum — The sought-after grid state
• proofs — A mapping to keep track of already submitted solutions
• verifier — The address of the verifier contract

And it adds an external function “mint” that mints a token when provided with a unique proof:

function mint(uint256 solutionHash,uint256 hash,uint256[2] memory a,uint256[2][2] memory b,uint256[2] memory c) external {require(!proofs[solutionHash], "GOLNFT: Solution already exists!");require(verifier.verifyProof(a, b, c, [solutionHash,hash,prizenum,uint256(uint160(msg.sender))]), "GOLNFT: Invalid proof");_safeMint(msg.sender, totalSupply());proofs[solutionHash] = true;}

If we were to not care about keeping the solutions private, we could have simply simulated the execution of life inside a solidity smart contract and it’d be much less burden.

So why use ZKPs in the first place?

The problem with the aforementioned approach is that malicious actors could steal solutions to the puzzle by listening to broadcast transactions. A malicious actor would simply copy the calldata, submit a transaction with a higher gas fee and reap the rewards:

A hash commitment scheme where a user commits to a hash of a solution before submitting it, and gets punished if he fails to submit the solution within some time-frame would be better, but has major flaws:

1. If the cost of commitment is too high it would prevent users with insufficient capital from participating
2. If the cost of commitment is too low, malicious actors can front-run commitments and intentionally lose money if it’s beneficial for them to gatekeep tokens

We are able to prevent this by requiring the transaction caller to provide the hash of his address combined with his solution. The verfier contract is able to verify that the public address and the private solution match the provided hash.

Now, if a frontrunner tries to steal a solution, him calling the mint function with the same inputs would fail since his address won’t match the hash.

If we even disregard frontrunning, there is another major benefit of using ZKPs: scalability. Verification is constant time and as a result the gas used in the verifier contract is bounded. Alternatively, implementing life in solidity for large grids with a large number of iterations would probably consume the gas limit many times over.

The downside is that groth16, the zkSNARK protocol in use requires a circuit-specific trusted setup — which means that in order to deploy the application into some chain you’ll need to conduct a trusted setup ceremony beforehand.

A trusted setup is an essential source of randomness used in the proof generation and verification processes and if it’s created by a single party, that party is able to forge false proofs, unless they discard the “secret key” that enables them to do so (hence trusted).

A trusted setup ceremony is a method for multiple parties to create a trusted setup such that as long as a single party is honest (discards their part of the “secret key”) the trusted setup is secure.

I’m planning on creating a react site for demonstration purposes. If you have any questions about the project feel free to ask and contact me at https://twitter.com/rubydusav

New to trading? Try crypto trading bots or copy trading