Zero knowledge proof

In the past year, there have been many applications of zero knowledge proof. In this tutorial, we will first learn the basic concept of zero knowledge proof, use circle to build arithmetic circuit, use snarkjs to realize the whole process of zero knowledge proof, and use these knowledge to realize the two-tier expansion scheme zk rollup.

Blockchain development tutorial link: Ethereum | Bitcoin | EOS | Tendermint | Hyperledger Fabric | Omni/USDT | Ripple

1. Arithmetic circuit: the core of zero knowledge proof

The implementation of zero knowledge program is different from other programs. First of all, the problem you want to solve needs to be transformed into a polynomial, and then into a circuit. For example, the polynomial x 3 + x +5 can be expressed as a circuit as follows:

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

The circuit compiler converts logic into circuits. Usually we don't need to design the basic circuit ourselves. If you need a hash or signature function, you can circomlib Found.

2. The generation and verification of evidence: the process of zero knowledge proof

Before running the zero knowledge verifier, we need to create a trusted setting, which requires a circuit and some random numbers. Once set up, a proof key and a verification key are generated for generating evidence and performing verification, respectively.

Once the proof / verify key pair is created, the proof can be generated.

There are two types of input: public and private. For example, if A transfers to B but does not want to disclose the account balance, then the account balance of A is private input, also known as Witness. The public input can be the addresses of A and B or the transfer amount, depending on your specific design.

Next, the certifier can use the proof key, public input and witness to generate evidence:

The final step is validation. Verifiers use public input, evidence, and verification keys to verify evidence.

The basic concepts of public input, witness (private input), proof key, verification key, circuit, evidence and their relationship are the basic concepts of zero knowledge proof that we need to understand before continuing the following tutorial.

3. The basic concept of circle: arithmetic circuit language

First, let's look at the syntax of Circom. The syntax of circle is similar to javascript and C, providing some basic data types and operations, such as for, while, >, array, etc.

Let's look at a specific example.

Assuming that X and y are confidential (i.e. witness), we do not want to expose the specific values of X and y, but we want to prove (x * y) + z == out, where z,out is the public input. If we assume out = 30, z = 10, then obviously (x*y) = 20, but this does not expose the specific values of X and y.

circom provides the following keywords to describe arithmetic circuits:

  • Signal: signal variable. The variable to be converted into circuit can be private or public
  • Template: template, used for function definition, like function in Solidity or function in golang
  • Component: component variable, which can be thought of as an object, while signal variable is a public member of the object

Rcom also provides operators for manipulating signal variables:

  • < = =, = = > these two operators are used to connect signal variables and define constraints at the same time
  • ←, →: these operators assign values to signal variables, but do not generate constraints
  • ===: this operator is used to define constraints

Well, these are the cyclom keywords that we need to know to continue our zero knowledge proof practice.

4. Using circom and snarkjs to realize the whole process of zero knowledge proof application

STEP 1: compile circuit file, generate circuit.json :

circom sample1.circom

STEP 2: create trusted settings and use the growth protocol to generate living_ key.json And verification_key.json

snarkjs setup — protocol groth

STEP 3: generate witness (private input). This step requires input, so you should save your input input.json , as follows:

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

Use the following command to generate a witness file witness.json :

snarkjs calculatewitness

STEP 4: use the following snarkjs command to generate evidence:

snarkjs proof

The result is proof.json , public.json . stay public.json Public input is included in, for example:

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

STEP 5: use the following snarkjs command to verify:

snarkjs verify

5. Zero knowledge proof practice case: zk rollup implementation

zk rollup is a two-tier solution, but it is different from other two-tier solutions. zk rollup puts all the data on the chain and uses ZK snark for verification. Therefore, there is no need for complex challenge games. In zk rollup, the user's address is recorded on the merkle tree of the smart contract, and the 3-byte index is used to represent the user's address (the original size of the address is 20 bytes), so zk rollup can increase the transaction throughput by reducing the data size.

For ease of understanding, in the following implementation of zk rollup, we intentionally ignore some details. For the original zk rollup tutorial, please refer to ZKRollup Tutorial.

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

1. Check whether the sender's account is on the merkle tree 2. Verify sender's signature 3. Update sender's balance and verify intermediate merkle root 4. Update receiver's balance and merkle root

The variables of the circuit program are defined as follows:

// 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;

In this case, almost all variables are private, no matter public key, account balance or signature, only merkle root and updated merkle root are public. path_element is the middle value of building merkle root, path_idx is an index array, which is used to store the index of each layer of merkle tree - a binary tree at this time, so there are only two branches left and right, 0 for left and 1 for right. The final path is like a binary string: 001011.

The following circle code checks to see if the sender exists:

//__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;

The above code is also relatively simple. Hash the sender's public key and account balance, use the middle value of merkle tree to calculate, and then get the merkle root( senderExistence.out ). Check whether the calculated merkle root is consistent with the input (account_root).

For simplicity, we omit the implementation of merkle tree and hash function. You can see HashedLeaf and GetMerkleRoot.

The following circle code checks the 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 as block chain transactions need to verify the sender's signature, in the above code, we first hash the message and then sign it, and then call the different package functions.

Update the sender 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 first two steps check the information from the sender's perspective, then update the sender's balance and calculate the new merkle root. Bottom line: newTreeExistence.out === new_sender_account_root; check the calculated merkle root and input (new_sender_account_root). With this check, forgery or incorrect input can be avoided.

The following code updates the receiver balance and the merkle tree:

//__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 is to update the receiver balance, calculate and output the new merkle root. Once the circuit is built, it's like a black box. If you enter the correct value, the output must be correct, so users can easily check to avoid malicious intermediaries. That's why we need to output something at the end of the circuit - in this case we're outputting merkle roots.

zk rollup aggregates many of these transactions and generates a single evidence to see the size of the data. In this tutorial, to make it easy to understand, we only deal with a single transaction, click [here] https://github.com/KimiWu123/Samples/blob/master/circom/rollupSample/rollup.circom) See the full code.

Original link: Introduction to zero knowledge proof application development - huizhi.com

Tags: JSON Blockchain Javascript github

Posted on Mon, 25 May 2020 06:50:39 -0700 by BSlepkov