author:Chen Zhijia, Meng Yize, Xie Qian, Jiang Zewu (Hash World)

Summary of the report:

Summary of the report:

Zero-knowledge proof is a probability-based verification method, and the verification content includes "factual statements" and "statements about personal knowledge". The verifier asks questions to the prover based on a certain randomness, and if they can give correct answers, it means that the prover has a high probability of having the "knowledge" he claims. Zerocoin (Zero Coin Protocol) uses zero-knowledge verification in the process of minting Zero Coins and redeeming Zero Coins to hide the sender and receiver information corresponding to a transaction. Zerocash (Zero Banknote Protocol) uses a more novel zkSNARKs technology , convert the transaction content that needs to be verified into proving that the product of two polynomials is equal, and combine homomorphic encryption and other technologies to perform transaction verification while protecting the hidden transaction amount. The disadvantage is that if the network receives an attack and overissues zero cash, it will not be able to detect or take measures; both Zerocoin and Zerocash require pre-set "trust settings", which have not achieved true "trustlessness". New technologies such as Intel SGX and zkSTARKs may solve the above problems, but they still need to be tested in practice.

1. The principle of zero-knowledge proof

Zero-knowledge proof is an encryption scheme originally proposed in papers by MIT researchers in the 1980s. “Zero-knowledge protocols are methods by which one party (the prover) can prove to another party (the verifier) ​​that something is true without revealing any additional information other than the fact that this specific statement is true. In other words, the hash value of the customer's password is stored on the web server. In order to verify that the customer actually knows the password, most websites currently use the method that the server calculates the hash value of the password entered by the customer and compares it with the stored result. But the disadvantage of this method is that the server can know the client's original password during calculation. Once the server is attacked, the user's password will be leaked. If zero-knowledge proof can be realized, then it can be done without knowing the client's password. , to verify the client's login, even if the server is attacked, the user's account is still safe because the client's plaintext password is not stored.

The basic zero-knowledge proof protocol is interactive, and the verifier needs to keep asking the prover a series of questions about the "knowledge" it has mastered. If they can give correct answers, then in terms of probability, the prover is indeed very good. May know what it claims to be "knowledge". For example, if someone claims to know the answer to a Sudoku puzzle, a zero-knowledge proof method is that the verifier randomly designates this time to check by column, row or nine-square grid, and does not need to see the specific position of the number pendulum for each test. It only needs to detect whether it contains 1-9 numbers. As long as the number of verifications is enough, then it can be believed with a high probability that the prover knows the solution of the Sudoku problem. However, such a simple method cannot make people believe that neither the prover nor the verifier has cheated. In the case of Sudoku, the two may have colluded in advance, so that the prover can pass the verification without knowing the answer. If they want to convince the third party, the verifier must also prove that their detection scheme is random each time and that they have not colluded with the prover.

Since it is difficult for third-party observers to verify the results of interactive zero-knowledge proofs, we need to pay extra effort and cost when we prove something to multiple people. Non-interactive zero-knowledge proofs, as the name suggests, do not require an interactive process, avoiding the possibility of collusion, but may additionally require some machines and programs to determine the sequence of trials: for example, in the example of Sudoku, through programs to Decide which time to test by row and which time by column, but this test sequence must be kept secret, otherwise the verifier may use this information if he knows the test sequence in advance, and prepares in advance, without knowing the real "knowledge" approved.

The content of zero-knowledge proofs can be summarized into two categories: "fact" statements: for example, to prove that "a specific graph can be tri-colored." or "a number N is a composite number"; statements about personal knowledge: for example, "I know coloring scheme for this particular graph" or "I know the factorization of N".

But not all problems have encryption schemes for zero-knowledge proofs. Goldreich, Micali and Wigderson gave theoretically valid ranges for zero-knowledge proof solutions. They found that there are known zero-knowledge proof schemes for decision problems (problems whose answer is only yes/no) whose solutions can be verified in polynomial time. It is only necessary to find the statement you want to prove in such an NP problem and convert it into an instance of the three-color problem, then you can use the existing protocol to realize zero-knowledge proof. Since the three-color problem is an NPC problem, any other NP problem can be transformed into an instance of this problem.

2. Application of zero-knowledge proof in blockchain

In the transactions on the blockchain, such as Bitcoin and Ethereum networks, in addition to using addresses to replace the real identities of both parties to the transaction, making the transaction partially anonymous, the sending and receiving addresses and amounts are known. It is possible to match the Bitcoin address with the real identity through various information on the network and interaction records in the real world, so there is a hidden danger of privacy exposure. Zerocoin has designed a brand-new idea, which cannot obtain the real identity of users through transaction history analysis. In Zerocoin, a certain value of the currency to be traded is consumed to generate a zerocoin with a unique serial number. Zero-knowledge proofs can verify that you actually spent the money without revealing which currency was spent. In order to transfer this money to others, logically we need to make this zero coin no longer spendable by others. The method of zero coin is to jointly maintain an invalidation list, which stores the serial numbers of all zero coins that have been spent. The miners use the zero-knowledge proof method when verifying the spending transaction. They do not need to know which zerocoin is spent, and can also verify whether the serial number of the zerocoin is in the invalidation list. Since the spend transaction does not include address and signature information, miners do not know the source of the zerocoin during the entire transaction process, so it is difficult to analyze the transaction history to obtain the user's identity.

In Zerocoin, the amount of the transaction can be known, but Zerocash, which uses zkSNARKs technology, can even hide the transaction amount. The only thing publicly recorded in the ledger is the existence of the transaction. It can be shown that zkSNARKs exist for all problems in NP. It introduces several innovative technologies and makes them usable in the blockchain. Most importantly, zkSNARKs reduce the size of proofs and the amount of computation required to verify them. Its process can be briefly described as.

1. Disassemble the program to be verified into logical verification steps, and disassemble these logical steps into arithmetic circuits composed of addition, subtraction, multiplication and division.

2. Transform the program that needs to be verified into verifying that the polynomial products are equal through a series of transformations, such as proving that t(x)h(x) = w(x)v(x).

3. In order to make the proof more concise, the verifier randomly selects several checkpoints s in advance, and checks whether the equality at these points is established.

4. Through homomorphic encoding/encryption, the verifier does not know the actual input value when calculating the equation, but it can still be verified.

5. A non-zero confidential value k can be multiplied on both sides of the equation at the same time, then when verifying that (t(s)h(s)k) is equal to (w(s)v(s)k), then It is impossible to know the specific t(s), h(s), w(s), v(s), so the information can be protected.

Different from Zerocoin's cryptographic primitive RSA accumulator, zkSNARKs technology is relatively new and has not been widely verified, so there are risks. At the same time, due to stronger anonymity, Zerocash's vulnerabilities are also more difficult to find. Compared with Zerocoin, Zerocash due to the transaction amount The information is also unknown, so if an attacker were to issue zero bills indefinitely, such a situation would be undetectable.

In addition, both Zerocoin and Zerocash require built-in generation parameters in advance. Users must trust that these parameters have not been leaked when using these networks, but once these parameters are leaked, the entire network will face a devastating blow. The complex trust setting makes Zerocash controversial, even if they design a set of "ceremonies" (such as recording the process of smashing the computer that stores the key) to prove themselves.

According to the zkSTARKs white paper, zkSTARKs is the first system that can complete blockchain verification without relying on any trust settings, and at the same time, the computing speed increases exponentially with the increase of the amount of computing data. It does not rely on public-key cryptography, and the simpler assumptions make it theoretically more secure, since its only cryptographic assumption is that hash functions (such as SHA2) are unpredictable (this assumption is also the basis for the stability of Bitcoin mining) , thus also making it quantum resistant. As a novel technology, like zkSTARKs, it needs to pass the test of time.

references:

references:

1. Zcoin Chinese Community, "Zcoin and Zcash: Similarities and Differences". http://www.zcoinchina.org/zcoin-and-zcash/https://z.cash/technology/zksnarks.html.

2. Zcash Team, "What are zk-SNARKs?"

4. Christian Reitwiessner，《zkSNARKs in a nutshell》，https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell/

5. Matthew Green，《Zero Knowledge Proofs: An illustrated primer》，https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/

3. Zerocoin Technology White Paper "A Cryptocurrency that Guarantees Accounting Privacy by Using the Zerocoin Protocol"http://www.sohu.com/a/224915382_117959

6. Lao Qian, "A Sudoku-caused tragedy: Zero-Knowledge Proof (Zero-Knowledge Proof)",

The copyright of the article is owned by Hash Future. If you need to reprint, please contact Hash Future staff.