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.
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.
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:
user password, is drawn from a pool of 3 passwords
we are given the 3 passwords hashes,
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
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
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.
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,
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 <== 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
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
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!