Mint your Kanji NFTs using Zero Knowledge Proof here! (Rinkeby)
You can find the full source code here.
How is ZK Proof different?
In traditional authentication protocol, the server knows the password (or one of its representation e.g. its salted hash) of the client’s login.
With Zero Knowledge Proof (ZKP), we can prove the client knows the password, but never reveals to the server what it is. The client gives a “proof” to the server, and the server can use it to verify the client knows the password. In our Kanji NFT ZKP example, we have 3 passwords and the server doesn’t know which of the 3 password the client knows. The server only knows that the client has knowledge of one of the them.
There are different types of ZKP, and different cryptographic proving systems within each type. In this post, we will focus on one of the popular types used in blockchain application, the zk-SNARK (zero knowledge-Succinct Non-interactive ARguments of Knowledge).
This post serves as an introduction to transform a trivial problem statement into a circom circuit.
Circom Circuits
In order for a problem to be represented in a form understandable by zk-SNARKs, we have to write a special type of program (called circuit). A circuit is basically a list of conditions, called constraints, that the inputs and outputs to the circuit, called signals, must obey.
Circom is a language and compiler that allows us to design such a circuit. It compiles the circuit into the Rank-1 Constraint System (R1CS) form, a form commonly used in ZKP protocols.
Because these circuits are in fact finite field arithmetic circuits, there are important rules they must abide by:
- All constraints must be either a constant value, linear expression, or a quadratic expression
- Addition, subtraction and multiplication are the only operations allowed (i.e. no divsion, power, etc)
Note that in ZKP parlance, here the minters are called the “prover”, as they are the one trying to prove that they know the password. And the minting smart contract is called the “verifier”, as it is the one verifying the proof that the minter submits. If and only if the verifier succeeds, the smart contract will continue with the minting process.
It can be said that circuits transforms a cryptographic problem into a programming problem that is easier to solve.
Problem Transformation
Let’s state the problem that we are trying to solve:
How can we proof that we know a password, drawn from a set of passwords, without revealing the password we know?
We will make the following assumptions:
-
our password,
user password, is drawn from a pool of 3 passwords -
we are given the 3 passwords hashes,
passwordHashed1,passwordHashed2,passwordHashed3(but of course besides the password we know, we don’t know what the other 2 passwords are) -
we are given the hash function used for hashing the passwords
If we are given 1 passwordHashed, then to prove that we know the password, we have to show that hash(user password) is the same as passwordHashed given to us. i.e.:
As we are given 3 passwordHashed, we have to show that hash(user password) must equal to 1 of the 3 passwordHashed. To say this in another way, we have to show that userPasswordHashed is the same as passwordHashed1, or passwordHashed2, or passwordHashed3.
In arithmetic circuit, this constraint can be represented with multiplication. Thus rearranging (1) and repeating it for the other 2 passwordHashed, we get a final constraint:
Let’s go through an example to see how this constraint work. Let’s assume that userPasswordHashed is the same as passwordHashed2. Since they are equal, (userPasswordHashed - passwordHashed2) would be equal to 0. Thus, regardless of what the other 2 expressions involving passwordHashed1 and passwordHashed3 computes to (we obviously know they are non-zero), the whole RHS of (2) would equal to 0, and the constraint is satisfied.
With our initial problem transformed in a constraint, we are now ready to write it in a Circom circuit.
Circom Code
Let’s take a look at our Circom code.
First we define signals which act as inputs to our circuit.
// public
signal input passwordHashed1;
signal input passwordHashed2;
signal input passwordHashed3;
// private
signal input userPassword;
// intermediate
signal out1;
signal out2;
signal out3;
signal final1;
signal final2;
We have three public signals, passwordHashed1, passwordHashed2, passwordHashed3, that are the hashes of the 3 passwords and generated by the verifier. Then we have a private signal, userPassword, which is the password that the user inputs and does not want the verifier (or anyone) to know. We also define five other intermediate signals which are entirely derived from the input signals. As we will see, intermediate signals help us with creating the constraints.
With that said, let’s look at our simple circuit.
include "../../../node_modules/circomlib/circuits/poseidon.circom";
component hasher = Poseidon(1);
hasher.inputs[0] <== userPassword;
out1 <== (hasher.out - passwordHashed1);
out2 <== (hasher.out - passwordHashed2);
out3 <== (hasher.out - passwordHashed3);
final1 <== out1 * out2;
final2 <== final1 * out3;
final2 === 0;
First we define our hash function, hasher, that we will use to compute the hash of our password. It is the same hasher used to generate the 3 passwordHashed given to us by the Verifier. component means we are creating our instance of Poseidon, which is another piece of circom code that is included in the circom library circomlib. Thus we just need to include it and we don’t need to write that ourselves.
Instead of using a more common hash function, such as SHA-256 used in Bitcoin, or Keccak-256 used in Ethereum, we are using a more ZK friendly hash function call Poseidon. This allows us to generate a final circuit with less constraints that will decrease the proof generation and verification time.
We then feed userPassword into the hasher where the output can be retrieved with hasher.out.
Next we have our 3 out expressions where if our hashed password is the same as one of the 3 hashes, then the expression would equal to 0.
In order to get around Circom’s limitation to quadratic equation for a constraint, we first compute final1 that is product of out1 and out2. Then we multiply it with out3, which we call final2, and equate it to 0. This completes our equation (2).
With the above Circom circuit, we can compile it and use it to mint NFTs!
We will do this in our next post, so stay tuned!