Hands-on Your first ZK application! – Kimi Wu
// 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. 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.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. 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_amountcomponent 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. 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.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.
//__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++)
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.
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
Published at Thu, 06 Feb 2020 05:48:09 +0000
{flickr|100|campaign}
