Hands-on Your first ZK application!

Let’s Do It!

Photo by Clem Onojeghuo on Unsplash

It was a big growth of zkp applications in the past year. Zk rollup proposed at the end of 2018 and currently being developed by Matter Labs. Matter Labs just published ZK Sync two month ago(2019/12), which solves the the latency issue when generating proofs. In addition, iden3 and ConsenSys also have their own zk rollup projects. A proposal in the Ethereum Research Forum called Account-Based Anonymous Rollup is based on the idea of zk rollup and also achieve anonymity. Semaphore is a signal system based on zero-knowledge proof. The sender can broadcast an arbitrary string without revealing his/her identity. Semaphorejs is an upgraded version of Semaphore and completes the entire concept, from front-end web pages to back-end services. Zk-STARKs is still very new, just published less than two years ago, and they cooperated with 0x early last year to launch a decentralized exchange based on zk-STARKs.

On the academic side, many papers were published in the second half of last year. Using DARK compiler can make SNARKs transparent (without trusted setup). Some SNARKs can have universal and updateable trusted setup(MARLIN, SONIC, PLONK, etc.). Recursive SNARKs is also an amazing ones. The field is moving so fast, it’s hard to keep up. Here is a great post about the comparison among different SNARKs. Another one to give an overview of all ZKPs by Eli Ben-Sasson, you have to read it!

We don’t talk about any mathematics here, only introduce the basics required for implementation. We use circom in this article, a language developed by iden3, to help write arithmetic circuits. With circom, it is easier to implement zero-knowledge proof programs. Let’s introduce some basic concepts first.

Arithmetic Circuits

The implementation of the zero-knowledge program is different from the other programs. Firstly, the problem/issue that you want to solve needs to be converted into circuits. (actually, the problem is converted into a polynomial and then circuits). For example, a polynomial x³ + x +5 will turn into circuits like this

sym_1 = x * x // sym_1 = x² 
sym_2 = sym_1 * x // sym_2 = x³ 
y = sym_2 + x // y = x³ + x 
~out = y + 5

Circom compiler turns the logic into circuits. You don’t need to deal with the circuits yourself. If you require hashing or signature functions, you could find them in circomlib.

Generate/Verify Proofs

We need to create a trusted setup before running zkp programs. The creation of a trusted setup requires circuits and some random numbers. Once the setup is finished, a proving key and a verification key will be generated. As the name implies, one is required for generating proofs, and the other is required for verification. (These two keys are different from public/private keys in ECC).

More knowledge is required for generating a trusted setup for production, refer to the Ceremony of ZCash for more details.

Once the proving key and the verification key is created, then generate proofs!

There are two kinds of inputs, public and private. For example, A transfers to B but doesn’t want to reveal the balance, then the balance of A is the private input, also called witness. The public inputs could be addresses of A and B or the amount, it totally depends on your design.

Then, provers generate proof by the proving key, public inputs and witness.

The final step, verification!

Verifiers verify the proof by public inputs, the proof and the verification key.

Public input, witness(private input), proving key, verification key, circuits, proof and their relations are the thing you need to know in this section!

Circom 101

First, introduce the syntax of circom. According to the document, circom uses the syntax of js and C. So, there are basic operations/data types, like for, while, >>, array.

Here is an example written in circom.
Assume that x, y are our secrets (which is witness) and we don’t want to disclose x and y, but need to prove that (x * y) + z == out (z, out are public inputs). Let’s say out = 30, z = 10, you will know (x * y) = 20, but you won’t know what each of x and y is.

Here, introduce the keywords in circom.
signal：the variable will be converted into circuits, with following properties:
. private：private input（witness）. Default is public
template：keyword for function declaration, like function in Solidity or func in golang.
component：There is no any explanation in the document. It’s a variable type but the assignment is a function. You can assign values to the variables inside the function with keyword signal. You can also imagine that component variables are class objects and signal is the public member in the class.

There are extra operators to operate signal variables.
<==, ==>：These two operators are used to connect signals and at the same time imply a constraint.
←, →：These operators assign values to signals but do not generate any constraints.
===：This operator defines a constraint.

Therefore, <==： ，← + ===

Those are keywords you need to know before starting. Here is the tutorial for install circom/snarkjs, we need this in the following sections.

Circom Commands

Step 1. Compile circuit files. circuit.json will be generated after this step.

circom sample1.circom

Step 2. Create trusted setup. proving_key.json and verification_key.json will be generated.（use protocol ‘groth’）

snarkjs setup — protocol groth

Step 3. Generate witness. Input is required in this step so put your inputs in input.json in json format as below.

// input.json
{“x”:3, “y”:5, “z”: 100}

Generate witness. witness.json will be generated.

snarkjs calculatewitness

The final step, generate proof. Once it’s finished, proof.json、public.json will be generated. Public input will be in the public.json.

// public.json
{
  “115”, // → out
  “100” // → z:100
}

Generate proof

snarkjs proof

Call ‘verify’ for verification.

snarkjs verify

Above are basic commands to generate proof. Following is an advanced example to understand how to actually use circom to write a zkp program.

Example

Here, let’s implement zk rollup！

Photo by pixpoetry on Unsplash

zk rollup is a layer 2 solution, it’s not like other layer 2 solutions. zk rollup put all the data on chain, and verify by zk-SNARKs. Therefore, there is no complicated challenge game. In zk rollup, users’ addresses are recorded in a merkle tree of smart contract, using index (3 bytes) to represent the user’s address (The original size of an address is 20 bytes). By reducing the data size to increase TPS, you can refer to my previous post for more details.

To make the examples easy to understand, a lot of details are skipped. (This example is based on ZKRollup Tutorial)

First, there is a merkle tree to record accounts. The account content contains (public key, balance). The content of each transaction is (sender’s index, receiver’s index, amount). The process is as follows

1 Check the sender account is in the tree (check existence)
2 Verify sender’s signature
3 Update the balance of the sender and verify the intermediate merkle root
4 Update the balance of the receiver and then update the merkle root

0. Variables Declaration

  // account tree
  signal input account_root;
  signal private input account_pubkey[2];
  signal private input account_balance;  
  // new account root after sender's balance is updated
  signal private input new_sender_account_root;  
  // tx
  signal private input tx_sender_pubkey[2]
  signal private input tx_sender_balance
  signal private input tx_amount
  signal private input tx_sender_sig_r[2]
  signal private input tx_sender_sig_s
  signal private input tx_sender_path_element[levels]
  signal private input tx_sender_path_idx[levels]
  signal private input tx_receiver_pubkey[2]
  signal private input tx_receiver_balance
  signal private input tx_receiver_path_element[levels]
  signal private input tx_receiver_path_idx[levels]
  
  // output new merkle root
  signal output new_root;

Almost all the variables in this case are private, from public key, balance, signature …etc, only merkle root and updated merkle root are public. path_element are intermediate values for constructing the merkle root, path_idx is an index array to store the index of every layer in the merkle tree (it’s a binary tree so only left or right, 0 means left, 1 means right. The final path is like a binary string, 001011)

1. Check Sender existence

  //__1. verify sender account existence
 component senderLeaf = HashedLeaf();
 senderLeaf.pubkey[0] <== tx_sender_pubkey[0];
 senderLeaf.pubkey[1] <== tx_sender_pubkey[1];
 senderLeaf.balance <== account_balance; 
 component senderExistence = GetMerkleRoot(levels);
 senderExistence.leaf <== senderLeaf.out; 
 for (var i=0; i<levels; i++) {
     senderExistence.path_index[i] <== tx_sender_path_idx[i];
     senderExistence.path_elements[i] <== tx_sender_path_element[i];
 }
 senderExistence.out === account_root;

We can see how component works here, component senderLeaf = HashedLeaf();. HashedLeaf() is assigned to senderLeaf , using <== to assign the public key and the balance to the values(pubkey[0], pubkey[1], balance those are signal type) in HashedLeaf(), and to generate circuits. The hash value would be senderLeaft.out。

This snippet is simple, hash sender’s public key and balance, calculate with intermediate values of the merkle tree and then get merkle root( senderExistence.out). Check the calculated merkle root is the same as input (account_root).

For simplicity, skip the implementation of merkle tree and hash function, you can check the implementation HashedLeaf and GetMerkleRoot.

2. Check Sender’s signature

  //__2. verify signature
  component msgHasher = MessageHash(5);
  msgHasher.ins[0] <== tx_sender_pubkey[0];
  msgHasher.ins[1] <== tx_sender_pubkey[1];
  msgHasher.ins[2] <== tx_receiver_pubkey[0];
  msgHasher.ins[3] <== tx_receiver_pubkey[1];
  msgHasher.ins[4] <== tx_amount
      
  component sigVerifier = EdDSAMiMCSpongeVerifier(); 
  sigVerifier.enabled <== 1;
  sigVerifier.Ax <== tx_sender_pubkey[0];
  sigVerifier.Ay <== tx_sender_pubkey[1];
  sigVerifier.R8x <== tx_sender_sig_r[0];
  sigVerifier.R8y <== tx_sender_sig_r[1];
  sigVerifier.S <== tx_sender_sig_s;
  sigVerifier.M <== msgHasher.out;

Just like blockchain transactions, needed to be signed to prove you are the sender. In this snippet, we hash the message first and then sign the hashed message. I encapsulate everything into functions so it’s very similar with the first part, just invoking different functions.

Signature scheme in SNARKs is EdDSA, not ECDSA.

3. Update Sender’s Balance and Check the New Merkle Root

 //__3. Check the root of new tree is equivalent
 component newAccLeaf = HashedLeaf();
 newAccLeaf.pubkey[0] <== tx_sender_pubkey[0];
 newAccLeaf.pubkey[1] <== tx_sender_pubkey[1];
 newAccLeaf.balance <== account_balance - tx_amount;
 
 component newTreeExistence = GetMerkleRoot(levels);
 newTreeExistence.leaf <== newAccLeaf.out;
 for (var i=0; i<levels; i++) {
   newTreeExistence.path_index[i] <== tx_sender_path_idx[i];
   newTreeExistence.path_elements[i] <== tx_sender_path_element[i];
 } newTreeExistence.out === new_sender_account_root;

The previous two step is to check the information from the sender’s side. After those checking, we update sender’s balance and calculate the new merkle root. The bottom line, newTreeExistence.out === new_sender_account_root; , is to check the calculated merkle root and the input one(new_sender_account_root) is the same. By this checking, prevent from users’s fake/incorrect inputs.

4. Update Receiver’s Balance and Merkle Root

 //__5. update the root of account tree
 component newReceiverLeaf = HashedLeaf();
 newReceiverLeaf.pubkey[0] <== tx_receiver_pubkey[0];
 newReceiverLeaf.pubkey[1] <== tx_receiver_pubkey[1];
 newReceiverLeaf.balance <== tx_receiver_balance + tx_amount;
 
 component newReceiverTreeExistence = GetMerkleRoot(levels);
 newReceiverTreeExistence.leaf <== newReceiverLeaf.out;
 for (var i=0; i<levels; i++) {
  newReceiverTreeExistence.path_index[i]<==tx_receiver_path_idx[i];
  newReceiverTreeExistence.path_elements[i] 
  <==tx_receiver_path_element[i];
 }
 
 new_root <== newReceiverTreeExistence.out;

The last step, update the receiver’s balance, calculate a new merkle root and output the new merkle root.
Once the circuits were made, it’s just like a black box. If you input correct values, the output must be correct. So, it’s easy for users to check the values to prevent from malicious middle man. That is the reason why we need to output something in the end of circuits (in our case is merkle root).

zk rollup aggregates many above transactions and generates a single proof to reduce data size. To make the example easy to understand, only process a single transaction here. Here is the link to the complete sample code, and other circom examples.

Conclusion

Circom is a very new language, not many libs supported now, many functions needed to implement by ourselves. Fortunately, iden3 implements many hash, signature functions and other hash or merkle tree functions could be found in Semaphore or other zk rollup implementations. Calling different functions to complete your application, just like building blocks. It’s not difficult from an implementation point of view (in spite of lack of documentation, reading source code is required). The most difficult part for our engineers is there are many cryptography knowledge we need to know before we implement.

In addition, the choice of hash function is also very important. How to reduce the complexity of the circuits, but also ensure sufficient security, is another topic.

In addition to circom, ZoKrates is also another language to help write arithmetic circuits. Both of these tools can generate smart contracts that can verify zero-knowledge proof. Then, for dapp developers just inherit this contract, construct your own business logic. How to generate the verifiable contract and how to interact with the contract is not the scope of this post, may have another article to explain it. Just before I finished this article, Matter Labs just released Zinc, another language to implement circuits.

Any feedback or mistakes that need correcting are welcomed.

Thanks for Chih-Cheng Liang’s review

Get Best Software Deals Directly In Your Inbox