The author of this article, Dongze, is a small partner from the Ambi Technology Community. He is currently studying at Stanford University, and his research direction is cryptography. This series of articles comes from the author’s study notes on the famous Stanford course "CS 251: Cryptocurrencies and blockchain technologies". The instructor of the course is Dan Boneh, a master of cryptography.
After the last issue of the article was published, I was very surprised that so many friends liked it after reading it. So let's continue with this episode! This time, let's focus on SNARK.
I believe that friends who have read the previous article will be a little puzzled: why can we create a proof so briefly and prove a long message? I also had the same doubts before class, and even thought this was a "black technology", but I believe that after reading this article, you will know how to control this "black technology".
first level title
Four-step construction of SNARK
secondary title
The first step: determine the finite field
Before construction, we first need to determine a finite field (Finite Field) that can contain all the numbers we want to calculate. In layman's terms, we need to choose a very, very large number p, making sure that this number is larger than all the numbers in the problem we want to solve.
Friends who have learned about RSA cryptography before may be familiar with this concept. The finite field is to add a ceiling to all our numbers and determine the calculation space of the entire mathematical system. It is similar to that in a computer. If we want to create a variable that stores numbers, we need to think about whether we need a uint32_t (32 bits), or Same as a uint64_t (64 bit). All values that exceed the finite field will directly overflow and then go back and start from 0.
In the world of mathematics, there are actually many kinds of computing spaces that meet this characteristic. The most common one is the positive integer modulo a large prime number (integer mod p) used in the RSA algorithm. Finding a number p mentioned above is actually a large prime number, and then we can use it to generate a calculation space.
secondary title
Step 2: Build an Arithmetic Circuit
When we find a digital space, the next thing we need to do is to express the problem we want to prove to solve with mathematical operation circuits.
What is a mathematical operation circuit? Let's take a look at traditional logic circuits first.
The above figure describes a NAND gate (NAND) circuit. Without knowing too much about the usefulness of the circuit, what we can find is that the two sets of input signals pass through the two basic logic gates of AND and OR respectively. Basic logic gates like AND and OR are the basic building blocks of logic circuits, and we can implement any complex logic by splicing and stacking.
The same is true for mathematical operation circuits, except that the basic module has changed from logic gates to mathematical operations. Because addition and multiplication are the most basic mathematical operations, through addition and multiplication we can almost realize all other calculation methods, so we can choose "addition gate" and "multiplication gate" as the basic modules of our mathematical operation circuit. By superimposing arithmetic gates, we can build a "circuit" of complex polynomials.
In order to better understand the operation gate, let's try to convert the above NAND gate from a logic circuit to a mathematical operation circuit. (Assuming that Inp0 and Inp1 are the same as the original logic circuit, they still input 1/0 logic signals.)
Let's look at the AND gate first: AND is actually very simple, because the result of AND will be 1 only when both Inp0 and Inp1 are 1. We quickly discovered that a multiply gate would be a perfect replacement for an AND gate: the result of the multiplication will be 1 only if both inputs are 1.
After solving AND, let's convert NOT: NOT is actually very simple, because the input signal can only be 0 or 1, as long as the input signal is subtracted from 1, the result is the opposite. Note that there is a problem because we only have addition and multiplication, so if we need to implement subtraction, we need to multiply the input signal by a constant -1 first.
After such conversion, we have successfully converted a logic circuit into a digital logic circuit. At the same time, because we already know how to build AND and NOT, we can theoretically modularize these two parts and splice any complex logic.
Seeing this, you may feel that the arithmetic circuit is very simple, and the conversion to the logic circuit is also very straightforward. But in fact, this is because we have been assuming that the input of the arithmetic circuit is the same as the logic circuit, which is 0 or 1. In a real scenario, the input value of an operation gate can be very large (depending on the size of our finite field choice). so we have to find a wayConstraining the input to our operational circuit, so that it is not only functionally the same as the logic circuit, but also can only take the two numbers [0,1] in the input value.
But how to use arithmetic gates to represent such a relationship? Because the mathematical operation circuit is actually a complex polynomial (for example, the NAND circuit in the above figure becomes Out = 1 - Inp0 * Inp1), we can transform this question: can we create a polynomial,Only when an input satisfies the value range of [0,1], will it output 0?Finally, we found that there is such a polynomial that can satisfy this requirement:
The above string of expressions means that only when the number n is in this range, the following polynomial will output 0. In other words, we can connect the above-mentioned Inp0 and Inp1 to the operation circuit converted from this polynomial,As long as the output result of this operation circuit is 0, then we can be sure that the output of the above NAND operation circuit is also correct.
Some people may ask, the polynomial that limits the value above can only limit one input, but we have two inputs, how to limit their value range at the same time? In fact, the answer is very simple, just copy the same polynomial and add the two together.
With these two circuits, we only need to make sure that the output of the constraint circuit is 0, then the NAND gate circuit will work normally.
One thing to note is that because our logic gates are built from arithmetic gates, we will find that logicoperation is very slowsecondary title
Step 3: Convert to Provable Mathematical Operation Circuit
When we have the concept of a digital computing circuit, we can splice different circuit modules together to generate a computing circuit that can be used as a proof.
First, let's defineA digital operation circuit C(x, w) that can be used as a proof, the specific structure is as follows:
In simple terms, this circuit C has two sets of inputs.
The first set of inputs labeled x, we callpublic input, which means that everyone will know the value of x. This x generally expresses the characteristics of the problem you want to prove and some fixed environment variables.
The second set of inputs is labeled w, which we callsecret input, or also known as witness. This set of data is the answer to the party who actually submitted the proof, and only the party who submitted the proof will know it, and no one else can get it.
When we have a circuit of C, our goal isProve that C(x, w) = 0. In other words, given that A and B know that the output of the mathematical operation circuit C is 0, and the public input is x, A needs to prove that she knows the private input value w that constitutes this output.
If we substitute this concept of C(x, w) into the NAND gate example mentioned above, we will find that the NAND gate alone is not enough to be a circuit for proof. We can redefine the problem we want to prove:If we know that the output of a NAND gate is 0, and one of the inputs Inp0 is 1,A wants to prove that she knows the value of another input Inp1. In the process of this proof, it is not only necessary to ensure that the output of the NAND gate is correct, but also to ensure that all input values are within the range we agreed in advance.
We combine the scheme discussed above, connect the NAND circuit output and our value constraint circuit together to form an operation circuit C, x is Inp0, w is Inp1, and we constrain the output to 0, thus forming a complete NAND gate privacy Enter the certification system.
When we get the final proof circuit C, we can calculate the complexity of this operation circuit.
If we want to know how difficult a digital operation circuit C is, we can describe its complexity by how many operation gates there are in it. Generally speaking, we will use to express. Like the NAND proof circuit mentioned above, it is probably around 10.
secondary title
Step 4: Non-Interactive Short Proof System (SNARK)
When we have obtained the final proof circuit C and the corresponding x and w through the third step, our preparations are almost done. For the rest, we can hand over to the SNARK algorithm to generate and verify our proof.
First, let's look at the official definition of the entire non-interactive proof system.
A SNARK system often consists of three core algorithms: Setup, Prove and Verify.
Generate algorithm Setup:
The Setup algorithm will take our determined circuit C into a series of preprocessing (preprocessing), and then generate two sets of parameters. Sp is a parameter for the prover, and Sv is for the verifier. The purpose of these parameters is to facilitate both parties to generate and verify short proofs. In general, the complexity of the generation algorithm is proportional to the complexity of the circuit C, O(|C|).
Proof algorithm Prove:
There is no need to talk about the proof algorithm. The prover will use the Prove algorithm to generate a proof, and then send the proof to the verifier. The Prove algorithm will use almost all the data when regenerating the proof: the preprocessed data Sp, the public input x, and the private input w. The resulting proof has a very short space complexity: |Π| = O(log|C|).
Verification algorithm Verify:
The verification algorithm is also very straightforward. The verifier will use the Verify algorithm to verify the proof we received. This algorithm will return a value of 1/0, representing whether the verification is passed or not. In the verification process, in addition to the proof provided by the other party, we also need to preprocess the data and the public input x. The verification complexity is also very small, typically O(|x| + log|C|).
With these three algorithms, we can use a very simple diagram to describe the entire proof system.
first level title
Example: Input and output range of private transactions (Range Proof)
Friends who have read the previous article should still remember that if we want to conduct a private transaction (Confidential Transaction), we need to attach three sets of proofs at the end of the transaction:
The first group isPederson Promise, proving the mathematical relationship between the input and output.
The second group isinterval proof, it is necessary to prove that the values of input and output are all in the range of positive integers.
The third group isproof of ownership, to prove that the initiator of the transaction really has so many tokens as input.
The fulfillment of Pederson's promise has already been discussed in the previous article. Now that we understand the four-step construction of the short proof, we can see how to implement it in detailinterval proof。
First, we need to find aAppropriate math circuitto describe what we want to prove. (We use the finite field of positive integers by default, and choose a very large prime number p for modulo.)
If we have a number w, and we want to prove that this number w is not a negative number, then we can first prove that it must be in the range of positive integers. Because considering that the positive integers in the computer system generally do not exceed 256 bits, we can weaken the problem:Prove that a number w has a value between 0-2^256.(According to this condition, the prime number p selected by the finite field needs to be greater than 2^256.)
Now that we have determined the problem to be solved, we can start thinking about how to express this value relationship with addition and multiplication. Remember in the previous chapter, when we were talking about a value n between 0 and 1, we used n * (n - 1) = 0 to constrain this value range.In the same way, if we want the constraint to have a value between 0 and 5, we can constrain it with a longer series of multiplications:
Seeing this, you may already know how to constrain the value of w: we only need to use the same method to expand this equation, and multiply continuously from (w - 1) to (w - 2^{256}), not just OK?
It sounds simple, but careful friends will find that in the final circuit there will beThere are 2^256multiplication gate. With so many multiplications and no additions, the complexity of this circuit is already astronomical. Even if you run Setup, you may not know that you will run into the Year of the Monkey, so we say that the method of this constraint isnot realistic.
Then is there any way to constrain the space of this number w? we canCleverly use the structure of binary numbers.Since we want to stipulate that w is an integer and is greater than 0 but less than 2^256, then we can, in binary,Split w into 256 bits, and then constrain each bit separately.In this case, the size of the circuit we finally get will only be proportional to how many digits this number has, and will not be related to the maximum upper limit of this number. The complexity dropped by a large level all of a sudden.
How is it achieved? We first split w into 256 bits:
Because each bit is binary, we need to constrain the value space of each bit to 0 and 1:
This constraint requires 256 copies, one for each bit. When we have these constraints ready, we finally make sure that all the bits together can be restored to the original w:
We stitch together all the 256+1=257 constraint circuits mentioned above and combine them into one output. The final generated circuit is the circuit C that we can use to build the proof system. If the output of C is 0, then the number representing the input must satisfy:
This number is a positive integer that can be represented by a 256-bit binary number.
This 256-bit binary number is indeed a binary number. (can only take the value 0 or 1)
All these 256-bit binary numbers can be put together to restore the number entered.
By cleverly using the characteristics of binary,first level title
Example: Ownership of Private Transaction Inputs
After solving the interval proof, let's complete the last set of proofs of the private transaction: the proof of ownership, which proves that the input value of the private transaction is reasonable.
Friends who have read the previous article should know that we have talked about two systems for proof of ownership of private transactions:
The first solution is that a transaction can directly refer to the output of the previous transaction, but this will bring about a chicken and egg problem: the difficulty lies in how to create the first private transaction. The second solution is to attach another new proof under each transaction, proving that the account balance of the user who initiated the transaction really has that much money.
I want to emphasizeThe second proof scheme is to prove the account balance of the transaction initiator in the world state.
In many blockchain scenarios, the state of the entire world is a huge ledger. Each line of the ledger records the account balance of a certain user.
In order to represent the state of the entire world more conveniently, we often use the Merkle tree to turn the huge world ledger into a series of short and neat Merkle hash values. Whenever any balance of any account changes, this Merkle hash will change.
A Merkle tree is actually a binary tree. Each node will stitch together the values of the two child nodes below, and calculate the corresponding hash value as its own value. In order to facilitate the construction of the Merkle tree, we will first perform a hash calculation on the most original balance value, and then store their hash values at the bottom of the Merkle tree.
When we build a Merkle tree in this way, we can treat the output Merkle hash value as aCommitment: As long as the promise does not change, then the current state of the world must not change.In the blockchain, if we want to record the status of a long list of data, generally in order to save space, we will record the Merkle commitment of all data on the chain instead of storing the data itself on the chain.
After we have a commitment to the state of the world, the follow-up question is:If A is account 1 in the picture above, there are 5 yuan now. How does A prove to B that in the entire world state, her balance is really 5 yuan?
A very simple method is: A can submit the balance of all accounts to B, and then B will perform a Merkle commitment calculation by itself. As long as B's calculated commitment is equal to the current world state commitment, and A submits that her own account balance is indeed 5 yuan, B can believe that A really has 5 yuan.
It sounds like a very good method, but the problems with this method are obvious at a glance. There are hundreds of millions of users in this world. If A needs to submit a deposit balance of hundreds of millions of lines to B, let alone how B can effectively calculate this commitment, the network traffic alone will be exhausted. And such a proof method will expose the balance information of all users, and everyone is definitely not willing.
So how to effectively prove that the balance of account 1 belongs to the current world state? At this time, we can use the characteristics of the Merkle tree to construct the Merkle proof.
If we carefully observe the pruned Merkle tree in the above figure, we will find that as long as we prove that the balance of account 1 can form the final world state commitment with adjacent nodes in the Merkle tree, we can also prove the balance of account 1 It belongs to the current state of the world.
How to do it? Let's start with the balance of account 1,Go all the way up the Merkle tree.
With the balance of account 1, then we can calculate H1. After having H1, we found that we don't need to know the balance of account 0, as long as a value of H0 can be combined to generate H4. In the same way, we can finally generate the Merkle commitment of the vertex——H6 by combining with the value of H5. In the end, we only need to submit three things to complete this Merkle proof: the balance of account 1, H0, and H5. All remaining hash values can be calculated during the verification process. This is the Merkle proof.
We can greatly reduce the volume of the proof through Merkle proof, and we can also ensure that the balances of other users in the world state are not exposed during the proof process. Merkle proofs are very useful in cryptography, requiring only the size of n to prove that something is in a list of length N. We often use Merkle proofs to prove that a set of data belongs to a large file, a user belongs to a large organization, and so on.
After understanding the principle of Merkle proof, let's see how to prove that A can prove her balance in a private transaction.
The essence of a Merkle proof is that we canStarting from the value to be proved, the hash value is calculated all the way up, and is continuously merged with the hash values of adjacent nodes.But we found a very fatal problem: although we can hide other people's balance in the world state, we stillYou must expose your balance(Otherwise there is no way to calculate the first hash value H1). This is contrary to the essence of our private transactions!
At this time, you need to use the power of SNARK.secondary title
Step 1: Prove Balance Hash
In the first step, we use SNARK to prove that the balance of account 1 can get the hash value H1 after passing the hash function.
Since we want to hide the balance of account 1, we denote this number with w. Before applying SNARK, we also need to change the description method of the problem to make it more convenient to express with mathematical operation circuits:
Suppose A himself has a secret w = the balance of account 1. Both A and B know in advance the hash value H1 of account 1's balance (we can denote it by x). We can construct a mathematical operation circuit C: Hash(w) - x = 0. If C(x, w) = 0, then Hash(w) = x.
In order to simplify the representation, we use an abstract module to represent the hash function on the graph. In practice, we generally use the SHA256 hash function. After we get the final circuit C, we use the Setup algorithm to generate parameters, and then use the Prove algorithm to generate a short proof.
Through this step,We will get a public x and a proof, and the value of this x is the hash value of account 1's balance.secondary title
Step 2: Complete the Merkle proof from H1
The previous step allowed us to get H1, and also provided proof that H1 was really generated from the original world state. What we have to do now is to start from H1 and combine with adjacent H0 and H5 respectively to generate a new world state commitment. If we compare the generated commitment with the old commitment saved on the blockchain, then we can believe that the balance of account 1 is really in the world state.
To sum up, we have divided the proof of ownership into two steps, the first step is to prove that the secret w can be converted into x by the hash function, and then prove that the public x belongs to the Merkle tree of the entire world state.first level title
Summary of Private Transactions
Seeing this, everyone must have a general understanding of how private transactions are realized. Now let me summarize what A has to do if she wants to pay B a private transaction.
First, A needs to send to the whole networksubmit a private transaction, this transaction contains the initiator and payee of the transaction, but there is no quantity. The original quantity of input and output is replaced by a few strings of garbled characters.
Underneath this transaction, A needs to attach a Pederson commitment to prove that the input and output numbers add up to be equal.
Then A needs to append one more passInterval Proof Generated by SNARK(Range Proof), which proves that the input and output numbers are all positive integers greater than 0.
Finally, A needs to append aproof of ownership, which proves that she really owns an account w in which money is deposited. This proof of ownership is divided into two parts, one is the hash value proof generated by SNARK, and the other is a Merkle proof, which proves that the previous hash value really belongs to the state of the world.
to be continued
to be continued
For reasons of space, I will stop here this time. Presumably everyone has seen this, and has already understood the "proof" part of the zero-knowledge proof. You probably know what a mathematical operation circuit is, and then how do we convert real-life problems into circuits.
I believe many people will be curious, so how do the three algorithms of Setup, Prove and Verify work? In the next issue, let’s continue our deep dive to gain an in-depth understanding of the principles behind the SNARK proof system.
read more
As usual, a part of the reading list is given at the end of the article, and interested friends can learn more about it:
