How to build a zero-knowledge DApp

View on GitHub

Zero-knowledge proofs were first introduced in the year 1985 as a solution to security problems. However, it was not until recently that they aroused special interest in the field of blockchains due to the solution they offer to scalability problems.

Currently, there is an upward trend in the application of this technology in some decentralised applications thanks to the fact that its properties are useful to developers in order to create more secure and private applications.

This post offers an introduction to how to develop an application capable of generating and validating zero-knowledge proofs in the context of the Connect Four game in order to demonstrate to a verifier that a prover has information about the game without having to reveal it.

In this article

Overview

A monorepository with Turborepo that has three main workspaces has been developed in order to create this application.

Firstly, a zk-SNARK circuit developed with the library Circom, secondly, a Hardhat development environment of smart contracts written in Solidity language (which act as verifiers of the proofs) and, lastly, a web application authored in TypeScript and developed with Next.js.

Since the application consists of a two-player game, a reinforcement learning agent has also been introduced for modeling in PyTorch a game policy capable of acting as one of the players.

In the diagram below I try to specify as much as possible the workflow of this application, which I will explain in detail in the course of the following sections.

What is a zk-DApp?

A zk-DApp is a decentralised application with the particularity that it offers the option of generating and validating zero-knowledge proofs. This type of proof responds to a protocol that makes it possible for a verifier to ensure the validity of a statement made by a prover, without the prover having to reveal information that is considered private.

There are different types of zero-knowledge proofs, although in our case we will focus on the type zk-SNARK, acronym for zero-knowledege Succinct Non-interactive ARgument of Knowledge, which has the following properties:

  • zero-knowledge: The verifier has no knowledge of the proof except whether it is valid or not.

  • succinct: the size of the proof is small and therefore its verification time is reduced.

  • non-interactive: does not require interaction between the prover and the verifier beyond a single round of communication.

  • argument of knowledge: proof consisting of a cryptographic assertion that the prover's assertion is valid.

zk-SNARK Circuit

The zk-SNARK proofs can only be generated directly from a finite field F_p arithmetic circuit, i.e., a circuit capable of performing addition and multiplication operations in a finite field of a given size.

Therefore, all operations are calculated modulo a specific value, for example, it is needed in Ethereum to operate with arithmetic circuits F_p taking the prime number:


The conversion of a computational problem to an arithmetic circuit is not always apparent or evident although, in most cases, it is feasible. The main idea is to reduce this problem to a series of equations.

Therefore, in this context we can say that the verifier of the proof will be able to cryptographically verify that the prover knows information that satisfies a system of equations.

In Circom, these equations are called constraints and must only be quadratic equations of the type a * b + c = 0, being a, b andc linear combinations of signals, i.e., a constraint must have only one multiplication and one addition of a constant.

The signals are the inputs and outputs of the circuits, the calculation of which results in the witness vector, therefore any output is also an input to the witness vector. The witness is, then, the set of circuit signals (input, intermediate and output) and is used to generate the proof.

In short, Circom will help us create a system of restrictions. These constraints are called Rank 1 constraints (R1CS).

The circuit will have two main tasks, on the one hand, (i) generate the proof, for which the restrictions are introduced and, on the other hand, (ii) calculate the witness, for which the intermediate signals and the output are resolved.

As each restriction or equation must have a multiplication, implementing the problems in this way is somewhat complex, so much so that sometimes auxiliary signals are required that may or may not be restricted but to which a value must be assigned.

In Circom it is considered dangerous to assign a value to a signal without generating a constraint to it, since a system can be underconstrained and solve tests that are not well designed, so normally both will be done unless it is an expression that cannot be included in a restriction.

For this reason, Circom contains operators for signal assignment, for generation of constraints and, in addition, operators that do both:

  1. If we want to write an equation that only assigns the result of a multiplication to a signal we will have to write c <-- a * b.

  2. If we only want to restrict the signal c to be the result of the multiplication of a and b, we will write the expression c === a * b.

  3. Finally, if we want to do both things at the same time we can implement it with the equation c <== a * b, which will compute the multiplication of a and b and assign and restrict the result to c.

Next, I will introduce the Circom circuit for generating zero-knowledge proofs about information about a given game of the game of Connect Four.

Circuit implementation

Our circuit will be used to generate the witness and the proof for a game that has already finished being the result victory for one of the players.

With this circuit the prover will be able to prove to the verifier that he knows the winner and the winning combination without having to reveal this information.

The circuit must fulfill the following purposes:

  • ensure that each of the cells on the board has the value 0, 1 or 2.

  • ensure that there is only one winner and that is the winner that is entered as input.

  • ensure that the winning combination corresponds to the combination entered as input.

To do this, three private inputs are defined: the observation of the board, the winner (1 or 2) and an array with the indices of the four consecutive counters.

apps/circuits/connect-four.circom

As we can see, a template is used in Circom to create a generic circuit, in which other templates can be instantiated. However, the term main will be used to define the main circuit or component, which serves as the entry point.

To ensure that the cells have correct values, an auxiliary circuit, called AssertIsZeroOneOrTwo, has been instantiated in a for iteration to which we pass the value of each cell on the board::

apps/circuits/connect-four.circom

The equation that solves this problem is the polynomial of degree three (x - 0) * (x - 1) * (x - 2) = 0, however, since we can only use quadratic equations in Circom, we first assign the result of (x - 0) * (x - 1) to isCounterZeroOrOne and then multiply it by (x - 2) and restrict the result to zero, making sure that the input x can only be 0, 1 or 2.

apps/circuits/connect-four.circom

If we execute the script pnpm run print:constraints we will obtain all the constraints of the circuit, which will help us better understand how the circuit works and debug our implementation.

We will focus on the first two constraints that correspond to the first iteration of the for loop for row = 0 and col = 0, i.e., the check that the cell in the upper left margin of the board equals 0, 1 or 2:

Considering the finite field of operations in our arithmetic circuit, these equations are equivalent to:

As main.board[0][0] equals the input signal in, and doing a simple algebra exercise, we would have the following equations, which correspond to the restrictions of the circuit AssertIsZeroOneOrTwo:

For the proof to ensure that there are only four consecutive counters on the board, we must implement an algorithm that iterates through columns and rows for each possible orientation (horizontal, vertical, diagonal and anti-diagonal).

For example, for horizontal orientation we would have the following implementation.

apps/circuits/connect-four.circom

Then, there are iterations by row and column and it is checked that the three horizontally oriented cells following the indexes in that iteration have the same value. To do this, we assign an instance of the Circom circuit isEqual to a component to which we pass two inputs, one for each counter we compare.

This way we ensure that if there are four consecutive horizontal counters, they have the same value. As we have previously restricted the values of the board to 0, 1 or 2, it could be the case that the four counters had the same value but it was zero, which would not be a winning combination, but rather four empty cells.

To ensure that the value of the cells is not zero, in lines 25, 26 and 27 the value of one of the cells and zero are passed to a circuit isEqual and we add the output (which must be a zero for there to be four consecutive counters) to the condition of the following if statement.

This statement will increase the variable horizontalWinner by one and will assign the indices of the consecutive counters to the array checkedWinningCoordinates.

The circuit implements this logic with the other orientations, for which the only difference consists of editing the indices of the iterations and the board and, thus, referring to the desired cells for each orientation.

To complete the circuit we must ensure that there is only one winner, which is the winner specified in the private entry and that the winning combination also corresponds to the private entry of the circuit, as we can see in the following code.

apps/circuits/connect-four.circom

Circuit testing

Circom also facilitates the library circom_tester which allows us to test the circuit in JavaScript (or TypeScript) language by abstracting the circuit using the function wasmTester:

apps/circuits/connect-four.test.ts

The goal of testing is to ensure that the circuit is successful by calculating a witness from valid inputs (inputs that correspond to the values on the board) and that it is not successful when the inputs, or at least one of them, that are not valid.

For example, to ensure the success of the circuit in passing valid inputs we implement the following code in a Mocha describe and we check the generation of the witness:

apps/circuits/connect-four.test.ts

As we can see, this test should be successful because there is only one winning combination on the board, whose user corresponds to the specified winner as well as its coordinates or array indices.

In addition, three other tests are implemented in which an attempt is made to generate a witness using invalid inputs.

Finally, the test result can be checked with pnpm run test --filter=circuits.

File generation

To obtain witness and proof on the device, we need the generation of a circuit wasm binary file in format and a proving key in format zkey, which will also serve to generate the PLONK verifier written in Solidity (which we will use to verify the proofs from the application).

The PLONK scheme allows us to produce the proving key without having to organize a trusted setup ceremony to get random values that allow us to establish a secure zero-knowledge proving system.

This scheme also needs a reliable configuration ceremony, however, instead of being a specific one, it is a universal and updateable one.

You can find more information about the PLONK scheme in this post from iden3's blog and in this publication.

In summary, you can use existing Perpetual Powers of Tau files, this link lists those of Hermez, and get the valid ptau file for the number of restrictions that our circuit has.

To generate the proving key we will also need a file in format r1cs (rank-1 constraint system) of our circuit.

Both the file in format wasm, for the calculation of the witness, and the r1cs, can be obtained by running the script pnpm run compile (or pnpm run compile --filter=circuits) which uses the circom compiler with some options for generating files:

The script circom compile will show the number of nonlinear constraints:

In order to know which ptau file to use we can start by using the file that supports a number of restrictions immediately above the number of nonlinear constraints, i.e., ptau for the power of 10 (2^10 restrictions at most), and proceed to try to obtain both the proving key and the PLONK verifier.

We will use the script pnpm run generate for this, which will invoke the following scripts consecutively:

I understand that starting with version 0.7.0 of SnarkJS (up to at least the current one, that is, 0.7.2) the specification of at least one public signal is needed, be it a public input or the definition of an output of the main circuit, after a refactoring of the template used for the generation of verifiers in Solidity language.

If there are none, the argument with the array of public signals in the verifyProof function will be assigned a length of zero (Array with zero length specified) by default.

Running this script will show the following output:

The chosen ptau file that supports upt to 1024 constraints falls short given that, as we can see above, the computation done in the PLONK scheme for the constraints gives a count of 1050, so we will use the power of 11.

After editing the script to use the correct ptau file we will be able to successfully generate the proving key and the PLONK verifier.

There is a web application called zkREPL which is very useful during circuit development since it allows us to compile and test a circuit in seconds without installations or managing dependencies.

Smart contracts

Once we have the verifier contract, which is generated from a SnarkJS PLONK verifier template, we need to develop a contract that serves as a link between the web application and the deployed PLONK verifier.

That is, our application will call this contract, which in turn will make a call to the verifier. Once our contract gets a result, it will emit an event with it, our UI will get it so it can be displayed.

As we can see in the constructor function, below, in order to deploy this contract we must first deploy the verifier and give this contract its address.

apps/contracts/src/ZKConnectFour.sol

This way, when we need to verify a proof our contract can call the function verifyProof of the verifier, as we can see in line 27, and then emit an event with the result.

The verifier contract generation script generate:verifier-contract in the workspace circuits saves this contract in apps/contracts/src.

Deployment of contracts

Finally, contracts are deployed on the network Sepolia with the purpose of giving functionality to the web application once it is deployed.

User interface

The game simulation has been implemented in TypeScript language using Next.js and allows a user to play a game of Connect Four in three modalities, user against AI model, AI model against user and user against user. In this section I will explain how I have developed this interface.

Game logic implementation

When choosing a game mode in the initial menu, either the component UserVsAIBoard or UserVsUserBoard are rendered. We will focus on the component UserVsAIBoard to explain the logic of the application since it also includes an inference session to predict an action on the board.

This component includes two hooks, useAI and useGameOver, to deal with the turns of the AI model and to try to capture the moment in which the game ends (whether in a draw or victory), respectively.

apps/web/src/components/board/user-vs-ai-board.tsx

Additionally, we have the component Board to display the dashboard which will also allow the user to formalize a game choice.

The hook useGameOver contains two effects with which it is checked, every time their dependencies change, whether there is a winner or if there is a tie.

apps/web/src/hooks/use-game-over.tsx

In the event that the game ends, a state is updated that persists in the application through Redux Toolkit. The state contains the board, game status, mode, turn, number of counters played and the winner. This way, the state in any component can be retrieved with the hook useAppSelector without having to write props in cascade.

During each user turn, each cell on the board will act as an enabled button whose click event will consist of validating its position on the board and, in the event that it is a legal position for a counter, the board will be updated in the state and the turn will be switched.

apps/web/src/components/board/cell.tsx

To deal with the logic of alternation in consecutive turns, in AI's turn the function predict is invoked in an effect of the hook useAI as we can see below:

apps/web/src/hooks/use-ai.tsx

This application makes use of an ONNX model deployed in the web application which is the result of a reinforcement learning exercise in which a DQN agent has been trained to optimize a neural network, with convolutional layers at the input and fully connected at the output, that results in a game policy for both turns.

I have written a Jupyter notebook in which I try to explain, step by step, how to carry out this task.

getPrediction provides a column index from which the row index where to place the counter is calculated. To obtain this prediction, the library onnxruntime-web is used which allows performing inferences in real time on the device using a language that is not common in the field of data science, as in this case TypeScript.

As we saw in the code useAI above, getPrediction is the entry point for creating a model inference session. We can see the code of this function below.

apps/web/src/utils/get-prediction.ts

This function has three tasks, (i) obtain a version of the board as Float32 typed tensor, (ii) pass it on to runConnectFourModel to get an array with the model predictions for each column and, finally, (iii) ensure with the function getPredictedValidAction that the valid action (as of the last observation on the board) with the highest probability of success, within every action there is in the array, is chosen.

This last operation could be avoided and the game implemented in such a way that if the model made a mistake and gave a greater margin of success to a column index in which no more counters fit, the game was declared over and the opposing player the winner. .

In our case, the game has been coded so that the valid action with the highest probability among the model predictions is taken.

The input that our model admits has the dimensions [1, 2, 6, 7] referring to the number of observations (batch size), the number of channels of the convolutional network, the observation space and the action space.

As we can see, to obtain the appropriate tensor from the observation of our board of dimensions [6, 7], not only must we add an additional dimension for the number of samples, but we must also add another for the number of channels.

The result will be the transformation of the board into a double binary matrix that indicates the positions of each player's counters.

For example, this transformation would result in converting the board a on the boards b and c, corresponding to player 1 and player 2, respectively:

a

b

c

The logic for this transformation in TypeScript is implemented in the function getBoardTensor which consists of a series of iterations for the concatenation of all the values and their subsequent conversion to a typed tensor.

apps/web/src/utils/get-prediction.ts

To obtain an inference from our ONNX model, we must first create the ort.InferenceSession passing the route to the model and a session configuration object, then the inference is performed.

apps/web/src/utils/get-prediction.ts

Finally, we obtain the index of the valid prediction with the maximum value in the array of values from the model inference, as we see below in the functiongetPredictedValidAction:

apps/web/src/utils/get-valid-actions.ts

Proof generation and verification

Once the game is over and as long as one of the players has emerged victorious and the user is connected to the Sepolia network, the application will give the user the option, enabling the button Verify, to generate and verify the zero-knowledge proof.

The component that is rendered when the button is enabled uses two hooks from the library Wagmi, useBlockNumber, to obtain the number of the current block of the Sepolia network and useContractWrite, to transfer the proof to the verification contract.

apps/web/src/components/others/enabled-verify-button.tsx

The handler of the event by clicking on this button mainly generates the witness and the zero-knowledge proof using the function generateProof and returns the proof and a subset of the witness only with public signals and the exit. Subsequently, it makes a transfer to the verification contract with an adaptation of this information.

apps/web/src/components/others/enabled-verify-button.tsx

The library SnarkJS allows us to calculate all the public signals of the circuit and the proof in the same function (fullProve) using the inputs to the circuit, the filewasm and the proving key, these last two files previously generated during the file generation in the circuits section above.

Finally, we obtain the calldata using the function exportSolidityCallData, from which we obtain the representation of the proof and the public signals in hexadecimal for the transfer to the contract.

apps/web/src/utils/generate-proof.ts

Once the transfer has been made and a result has already been obtained from the hook to obtain the block number, we proceed to obtain the events emitted by the contract:

apps/web/src/components/others/enabled-verify-button.tsx

If useBlockNumber obtains a successful result and returns the number of the current block, only events will be obtained from that block in the Sepolia network, otherwise from its genesis (BigInt(0)).

To get these emitted events I have implemented a hook which invokes the function to get the contract events periodically every pollInterval, as long as it is allowed by the control variable shouldStopPolling.

apps/web/src/hooks/use-events.ts

In our case, the fetching of events will stop once the result has been obtained in the event issued from our transaction with the proof or once a period of time has expired.

apps/web/src/hooks/use-events.ts

The countdown logic simply consists of an effect with a setTimeout which is set to 30 seconds:

apps/web/src/hooks/use-events.ts

Finally, the result obtained from the contract or an error message will be displayed in a modal window:

apps/web/src/hooks/use-events.ts

To improve the user experience, the achievement of all this series of actions is informed to the user of the application through toast messages in a margin of the screen using the hook useToast (which we can find in the workspace ui in packages), as we can see below in the case of obtaining events.

apps/web/src/hooks/use-events.ts

Public API

As we mentioned previously, this application makes use of an Infura node service to obtain information from the Sepolia network. Thus, avoiding errors induced by request limitation (rate limiting) using only the public provider.

In order not to leak to the client the API key, which Infura provides, an API route as a serverless function has been implemented which allows us to insert the key on the server side.

For this, a jsonRpcProvider is set in the context of Wagmi whose endpoint is this route.

apps/web/src/components/providers.tsx

Additionally, the key security settings have also been edited by using allowlists to create a list in which access to the Infura service is only granted using this key if the call is to the contract address.

Every time the application makes a query to the Sepolia network, the jsonRpcProvider request will be captured by a handler in our API route, which will send a new request, this time to the Infura endpoint, now with the key PROJECT_ID.

apps/web/src/pages/api/sepolia.ts

Finally, the handler of the API route returns the response from the Infura provider to the request initially made by the Viem library (which Wagmi uses behind the scenes).

To get an idea of what the flow of requests to the Infura provider is like after finishing a game and generating the proof to be verified, we see below a screenshot with the logs from the server after clicking on Verify:

We see that five requests are made in total, the first to obtain the number of the current block (eth_blockNumber), after which the call is made to the contract to verify the proof (eth_call) and finally three requests to obtain the events emitted by the contract (eth_getLogs).

First, we can verify that the URL to which the requests are directed is the API route that we configured earlier.

We see below that the block request returns the hexadecimal number 0x470259, which corresponds to block 4653657.

The payload of the call to the contract includes the arguments required by the function verifyProof of the smart contract, i.e. the proof and the public signals. The response includes the result 0x, which is simply an empty value.

Once the transaction has been made (whose call to the contract has resulted in the emission of an event ProofVerification) and a result has been obtained from the hook useBlockNumber, we proceed to obtain the events emitted from the block number 4653657.

The first two requests obtain responses with an empty array, that is, they do not contain events:

For this reason, a third request is made, which returns a single event.

The application compares the hash of the transaction (transactionHash) that includes this event with the hash of the transaction of the call to the contract and, since it is the indicated event, no more requests are made.

At this point, the application displays a message with the verification result. If 30 seconds had passed and the event corresponding to the proof verification transaction had not been obtained, no further requests would have been made and a message would have been displayed informing the user.

Application deployment

This web application has been deployed in Vercel and can be accessed at this link. If you want to learn how to deploy a Turborepo monorepository in Vercel you will find information in this article.


Related posts

DeFi

How to build a DEXs analytics application

Introduction to obtaining and representing DEXs data using TheGraph and React.js

Traceability

Introducing Olive Oil Trust

Introduction to a series of posts about Olive Oil Trust

DeFi

End-to-end guide to creating an ERC-20 token-specific DApp

Decentralized application to operate with a mintable ERC-20 token

Traceability

Introducing Olive Oil Trust: smart contracts

Olive Oil Trust smart contracts are implemented in order to adopt a set of rules...

Microservices

Approach to a microservices-based architecture bank application

A microservices-based architecture bank application that includes back-end and front-end applications, as well as a...

Traceability

Introducing Olive Oil Trust: front end

Next.js application that gives support to members and customers in Olive Oil Trust, and reduces...


Ready to #buidl?

Are you seeking collaboration on a Web3 project or a developer to join your team?. Then, do not hesitate to contact me by e-mail or on my LinkedIn profile. You can also find me on GitHub.