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.
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.
Last semester at Stanford, I followed Dan Boneh to learn blockchain and digital currency related technologies. Different from the previous courses, this year's course has added a new chapter called zero-knowledge proof. Adorable Dan and his master phd Ben Fisch gave us classes in turn, and it took two weeks to finish explaining the origin, concept and realization of zkSNARK of zero knowledge.
foreword
foreword
After writing the first draft, when I shared it with my friends Proofread, I found that many friends reported that the background knowledge was not enough. So I added this extra section before I started, marking the background reading needed to understand this article:
After reading the preface, we can start the text.
first level title
Shortcomings of Bitcoin
If you are familiar with Bitcoin, you should know that on the Bitcoin network, every transaction is public.
If A wants to pay B a sum of money, then A will announce to the whole network with a loudspeaker that she wants to create a new transaction (Tx), and the beneficiary of this transaction is B’s public key (P2PK), Or a hash of the public key (P2PKH). As long as B sees the transaction, he can use his private key to sign a digital signature to prove that he is really the owner of the public key, thus spending the money.
When A submits the transaction to pay B, as a bystander M on the network, she can only see a string of garbled address aaaaa to pay x coins to a string of garbled address bbbbb. Then when B sent money to C, he could only see that bbbbb sent a sum of money to ccccc. We can see that transactions in Bitcoin are strongly connected. Although we don't know who sent the money to whom, we can find many transaction chains by following the vines.
If every user just sends money back and forth obediently, Bitcoin is actually relatively safe.
Once a user sees through it, doesn’t want to play anymore, and wants to cash out on the exchange, then the transaction information of the entire chain will be exposed. Exchanges often have a KYC (Know Your Customer) policy, and each user who exchanges digital currency and legal currency must undergo real-name authentication. Once C withdraws money from the address of ccccc and runs away, the exchange has grasped the fact that bbbbb has sent money to C. If C is suspected of money laundering, at this time, you only need to wait quietly for B to cash out, and then catch it.
There are already many companies in the United States doing transaction chain analysis on Bitcoin, such as Chainalysis.
first level title
Anonymous vs. Pseudonymous
Our understanding of privacy is actually divided into two types.
The first is Anonymous, which means that users do not need to disclose any information related to themselves. It is like a confession wall in a school. You will never know who wrote it, anyway, the words are written on it.
The second is pseudonymous (Pseudonymous), which means that users post information through a pseudonym created by themselves, such as Tieba. If you don’t know the user well, you can’t establish a connection from the screen name to the real name, and you don’t know the person who posted the post. who is it.
From this analysis, Bitcoin is actually a pseudonym mechanism: each user will randomly generate their own public key (pseudonym), and receive money through the public key address. This is like the four people A/B/C/D respectively aliasing as Xiaoming/Xiaohong/Ergou/Xiaogang to trade anonymously online, as long as D reveals his identity in any link (such as in the exchange cash withdrawal), then the relationship between Xiaoming/Xiaohong/Ergou and D will be exposed immediately.
first level title
secondary title
CoinJoin
Since A's payment to B will be seen by others, and C's payment to D will also be seen by others, someone thought of saying that simply throwing all four people, ABCD, into one transaction. Because Bitcoin transactions can have multiple inputs and outputs, a bystander will see that in a transaction, both aaaaa and ccccc put x coins into it, and then bbbbb and ddddd receive money. In this way, even if the exchange knows that these addresses correspond to ABCD four people, it is difficult to tell who received money from whom.
What if the two sets of transactions are still too easy to identify? Two is not enough for four, four is not enough for eight, and so on. Combine the transactions of various people together to confuse the public and make it impossible to track. This is CoinJoin.
What are the disadvantages of CoinJoin? In fact, mixing multiple transactions cannot perfectly prevent people from being caught by others, it can only be said that it reduces the probability of being caught all the way. And there is another very important point, if you want to mix AB and CD transactions, then their transaction volume must be the same. If A pays B 10,000 coins, and C pays D one coin, we only need to look at the input and output, and we can immediately split a CoinJoin transaction into two independent transactions. Therefore, mixing and matching transactions with similar transaction amounts is also a difficulty that cannot be ignored when CoinJoin is implemented.
secondary title
Confidential Transaction (private transaction/CT)
Since it is so troublesome to hide who I am, people start to think: if we don't hide the public key involved in the transaction, we can also hide the amount of the transaction. When A sends money to B, even if B is exposed, the whole network will not know how much money A gave B.
If this operation can be realized, then we can even use Bitcoin to pay wages. Everyone can only see that your monthly salary arrives, but they don't know how much you earn.
To realize the method, we must first understand a special encryption algorithm: homomorphic encryption.
In one sentence, homomorphic encryption is a special encryption algorithm that allows ciphertext to maintain its original mathematical properties.
We can assume that there is an encryption method E, if E is additively homomorphic, then E(a) + E(b) = E(a+b). Conversely, if multiplication is homomorphic, then E(a) x E(b) = E(axb).
Since this article is a popular science article about zkp, we will not understand the specific implementation method in detail. We just need to understand that both the elliptic encryption equation and the large number module in RSA have certain homomorphic properties.
Pederson Commitment
Moving on to the topic of hidden volume. If A has a balance of 100 coins and pays 10 coins to B, then the transaction looks like this:
Combined with the additive homomorphism mentioned above, if we have an additive homomorphic encryption method E, we can convert this transaction into:
As long as the first number is equal to the sum of the last two numbers, a bystander will not see the trading volume in the end, but he has to admit that A really gave part of the money to B, and then part of the money was returned to A . This method is called Pederson Commitment (Pederson Commitment), which hides the data itself, but proves the relationship between the data.
Negative Number Vulnerabilities
After reading this, some friends will find a huge loophole: Although Pederson promised to prove the relationship between numbers, he did not limit the value range of any number! That is to say, A can play tricks, submit a transaction, say that he wants to pay -100 coins to B, and then "find" himself 200 coins. In this way, the equation still holds. A can use this to print money infinitely, thus destroying the entire system.
How to avoid the existence of negative numbers? In addition to Pederson's promise, we need another set of proofs to prove that the numbers in all transactions are positive. In other words, the numbers in all transactions are limited to the range (Range Proof) from 0 to 2^256 (the maximum value of a positive integer).
It sounds not difficult, and the easiest way is undoubtedly to disclose all these figures. But this defeats the premise of hiding transaction volume. So we have to find another proof method, that is, not to expose the original numbers, but also to prove their characteristics (the value is between 0 and 2^256). Does that sound like a point? Don't worry, let's look at another question.
ownership loophole
Before we go any further, I want to quickly point out that there is actually a huge loophole in this protocol: unknown ownership.
Friends who know about Bitcoin may know that when creating a Bitcoin transaction, you need to provide the UTXO Txid of the input transaction, so that you can quickly verify whether A who is going to pay B really has the money .
But now, we haven't mentioned anything about pointing to the previous transaction. That is to say, because the whole network does not know how much A spends, so A can simply change the input number to tens of thousands and tens of thousands, and then call all of them to himself and secretly mint coins for himself.
how to solve this problem? There are two options.
The first solution is to continue to introduce the transaction mechanism of Bitcoin, and use the output of the last private transaction as the input of the transaction. This kind of thinking is a bit like the transformation of the problem. I use the result of the previous transaction for this transaction, so as long as the previous transaction is ok, my transaction is also ok.
This is a chicken and egg problem, how to create the first private transaction without problems?
We can convert ordinary coins into private outputs through a special transaction. The input of this transaction is an existing transaction id (Bitcoin UTXO), and then the output becomes a private output. In this way we conjure the earliest eggs. (ZCash's shielded transaction is this principle)
The second scheme is to prove that the input of A really belongs to A. In systems like Ethereum, there is a concept of World State. The world state is the current balance and status of all users and smart contracts on the entire chain. Generally, a complete node will keep the entire world state (large in size), while a light node only needs to save the Merkle Commit of the world state.
In addition to submitting the Pederson commitment and interval proof, we provide an additional proof to prove that the number entered in the transaction is consistent with the balance of A in the original world state. We can use Merkle Proof to achieve this proof.
But if we submit the Merkle Proof directly, all bystanders can see A's transaction input, which violates the premise of private transactions. So again: we still need to borrow the mysterious algorithm mentioned above - it can not only hide the answer itself (the balance of A), but also prove that this number really belongs to the state of the world.
ZCash: All Anonymous
When the concept of CT was proposed, many people were dissatisfied with the status quo and couldn't help feeling: It would be great if they could even hide their own names.
So the concept of ZeroCoin/ZeroCash was put forward: based on CT, but with the addition of a new mechanism, which can make the transaction users anonymous. Now the bystander C who was eating melons was really stunned. He saw a string of garbled characters floating on the Internet, but he had no idea what it was, but he had to believe it was true.
ZCash is a digital currency implemented based on the ZeroCoin/ZeroCash protocol, which can achieve fully anonymous transactions. I won’t go into too much introduction here, but I still rely on the old cryptography tools: Pederson promises, interval proofs, Merkle proofs, and the black magic we’ve been talking about: those that don’t expose the answer itself. prove.
first level title
Zero Knowledge Proof (zkSNARK)
I believe that after reading the above, everyone has a general understanding of the problem we want to solve.
We want to prove the relationship between numbers, such as 0 <= a <= 2^256, or SHA256(x) = y. But we don't want to expose these numbers, such as a and x above. How to build a system to achieve this?
Before talking about this topic, I want to change my thinking and split this topic into two parts: zero knowledge (zk) and proof (SNARK).
secondary title
Proof (SNARK)
Let's start with the proof.
The full name of SNARK is Succinct Non-interactive ARgument of Knowledge. This noun consists of three dimensions:
Short (Succinct): The proof itself should be short enough, and it is best to verify that the proof is O(logN) or even O(1) complexity.
Non-interactive: There is no interaction in the overall process, that is to say, the prover can throw a large string of garbled codes on your table and then leave, and you can verify his proof by verifying the string of garbled codes later.
Expression of Knowledge (Argument of Knowledge): This thing is relatively obscure. But the general meaning is that what you want to prove must be able to express knowledge (Proof of Knowledge). The proof of PoK involves a more abstract concept of extractor (Extractor). For specific content, please refer to Mr. Guo Yu's article. But in one sentence, what you prove is valuable and obtained through calculation, not messing around with other things.
After reading the definition, we will find that just being able to implement SNARK is already very strong, especially in terms of brevity.
We can immediately think of an application: if a third-party organization stores a large amount of (PB-level) data in its own database. If government agencies want to audit their databases to ensure that there is no problem with each data point, under normal circumstances, they may have to read line by line, read every PB of data, and see the end of time. At this time, SNARK suddenly appeared. The size and time of O(1) or O(logN) fully proved that there is no problem with each data in this huge database. It is a little exciting to think about it. Most people think this is completely impossible: How can the accuracy of tens of millions of numbers be verified with just a few numbers?
secondary title
Zero knowledge (zk)
Let's go back to zero knowledge (zero knowledge).
In fact, zero-knowledge is just an additional requirement on the basis of this SNARK proof: the entire proof itself cannot reveal any data related to the answer to be proved. The official definition of the concept of zero knowledge is very obscure, introducing the concept of a simulator (Simulator). For a detailed introduction, you can refer to Mr. Guo Yu’s article, and I’ll just mention it here. In one sentence, no matter how clever a hacker is, he can't extract any information related to the answer itself no matter how he looks at the zero-knowledge proof.
Going back to the concept of this government audit database, we can assume that this database is the company's tax payment situation. The government must ensure that the tax data must be accurate, but for companies, they don't want inspectors to see their daily business flow, because it may involve commercial secrets. At this time, a mere SNARK is not enough, we need zkSNARK to achieve:
secondary title
Applications of Zero-Knowledge Proofs
With zkSNARK, what can we do?
The first thing is that the above-mentioned private transaction (Confidential Transaction) can be realized. ZCash's private transaction mechanism is implemented based on zkSNARK. In this way, digital currency transactions become much safer.
The second thing is that we can use this technology to better solve the problem of blockchain efficiency. Now there are undoubtedly several methods for blockchain scaling: sacrificing consensus strength to increase the speed of block generation, enabling side chains, or offline point-to-point channels similar to Lightning.
In fact, there is another idea called Rollup. The concept of Rollup is probably that the load on the main chain is too large, so we open a few more small servers, which can also receive transactions, do transaction authentication, and then batch all the transactions accumulated over a period of time Update to the main chain. However, if the update process still needs to send a large amount of transaction information to the main chain, the meaning of this Rollup does not exist, and it will not reduce any load on the main chain. At this time, SNARK comes in handy: through SNARK (it can be zk or not), the Rollup server can submit a very short proof to the main chain, proving that a large number of transactions are all right, and the main chain only needs to follow the final As a result, add or subtract some UTXOs and you're done. Through ZK Rollup, we can greatly reduce the load on the main chain and outsource more verification to other places.
The third thing, we can really realize the transaction to the third party.
Suppose A is doing machine learning research, but does not have a good computer, so she plans to outsource the task of training the model to B. After three days, B told A that he finished the run and needed to ask A to pay first before providing her with the trained model. A is worried that B does not have an honest training model, but randomly generates some random numbers and packs it, so he wants B to verify the model to A before paying. B is worried that A will secretly copy the model after getting it, and then block him directly without paying money.
Faced with this kind of problem, the traditional solution is to entrust a third party, or design a smart contract on the chain to complete the verification and exchange of data and currency. Now with zkSNARK, B can directly submit a zkSNARK for model training to A, proving that he really ran for three days honestly and was not cheating. A After the quick verification is passed, you can transfer the money with confidence.
The fourth thing, we can completely transfer data ownership.
Assuming that the bank's account balance database is a SQL table, then 100 million customers will have 100 million rows of records. Every year, banks need to spend a lot of money to maintain such a large data system. If everyone can move their own row of records locally and maintain their own account data, then the bank will not need to spend a penny. The reason why banks don't do this is because users are very likely to tamper with their own data for profit, turning 100 yuan into 1 million.
zkSNARK can just guarantee that there will be no problems with the data itself. We can imagine a distributed bank, where everyone's deposit balance is stored in their own computer. When A wants to transfer money to B, she needs to submit a zkSNARK to the whole network to prove that the balance in her account is deducted correctly, so as to ensure that A honestly deducts the transfer amount from her own balance. When B enters the account, he will also submit a zkSNARK corresponding to the balance increase.
to be continued
to be continued
For reasons of space, I will stop here this time. Presumably seeing this, everyone has a deeper understanding of why zero-knowledge proofs are needed and how powerful zero-knowledge proofs are.
At the beginning of the next article, I will write a little more in-depth, mainly discussing the specific structure of zkSNARK.
read more
read more
If you want to know more about the content mentioned in this article, I have collected a Reading List and put it below. Interested friends can read it.
Friends who are interested in zero-knowledge proofs are welcome to add WeChat Xiaoan @SECBIT (id: secbit_xiaoanbi) into the group discussion
