This article is from: BFTF（ID：bftf2018）text
This article is from:
, Author: Wu Qiong.
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. The zero-knowledge proof system consists of two parts: the prover who declares that a certain proposition is true and the verifier who confirms that the proposition is indeed true. The proof is performed through the interaction between these two parts. At the end of the zero-knowledge protocol, the verifier only confirms if the proposition is true. However, if the prover asserts a false proposition, it is entirely possible for the verifier to discover the error.
Here we give a very classic example of zero-knowledge proof to help you understand:
Ali Baba was caught by the robbers. In order to save his life, he had to prove to the robbers that he had the password to open the stone gate.
At the same time, the password cannot be told to the robber. He came up with a solution, let the robbers leave his arrows first,
The distance is far enough that the robber cannot hear the password, and the distance is close enough that Ali Baba cannot escape under the robber's bow and arrow.
If the robber raises his left hand, Alibaba will use the password to open the stone gate, and if he raises his right hand, the stone gate will be closed.
It was at this distance that Ali Baba showed the robbers the opening and closing of the stone gate. If the gate can be opened and closed correctly every time, it is confirmed that Alibaba does know the password of Shimen.
This whole process is zero-knowledge proof, that is, the prover can convince the verifier that a certain assertion (Alibaba knows how to open the Shimen) is correct without providing any useful information (the password of the stone gate) to the verifier.
From this we can summarize three properties of zero-knowledge proofs:
If the statement is true, honest verifiers (ie: verifiers who follow the protocol correctly) will be convinced of this fact by honest provers.
If the statement is false, it does not rule out the probability that the cheater can convince the honest verifier that it is true.
If the statement is true, the purpose of the prover is to prove to the verifier and make the verifier believe that he knows or has a certain message, and during the proof process, he cannot leak any content about the proven message to the verifier.
Satoshi Nakamoto creatively proposed Bitcoin and built a decentralized trading platform, thus removing the long-term trust and dependence on third-party trading platforms, but at the same time, Bitcoin needs to broadcast all transactions to the network The security of the entire system is ensured by reaching a consensus through all nodes, that is to say, all people can see all transactions on the network, and the original Bitcoin protocol does not specify the address of the sender and receiver of the transaction. Any processing will lead some careful attackers to analyze the corresponding relationship between the address and the actual person by analyzing the transaction characteristics of an address and combining some actual information, which will bring great hidden dangers to the privacy of users . Based on this, several well-known privacy coins have been derived, among which zero-knowledge proof has played a very important role.
ZCash
Let's introduce several blockchain systems that use zero-knowledge proofs.
first level title
As an anonymous cryptocurrency project, ZCash only existed as an encrypted anonymous layer of Bitcoin at first, and later became an independent cryptocurrency because of its excellent privacy. Like Bitcoin, the total amount of ZCash is also 21 million. The difference is that it can achieve true anonymity - you don't even need to know how much money the other party has to complete the transaction.
So how does ZCash achieve true anonymity and privacy protection?
Utilizes zk-SNARK technology, that is, zero-knowledge proof technology: Even if the source and flow information of the currency is completely confidential, the zero-knowledge proof technology can still verify that the user who spends money really owns the currency.
When using ZCash digital currency for transactions, it will automatically encrypt the original data of the transaction; at the same time, the individual transaction does not need ZCash nodes to save data, but only needs zk-SNARK to prove its "consumption power". This is mainly reflected in two points in the transaction process. One can allow others to verify the validity of the transaction (or smart contract function call) without knowing the specific transaction content. Second, the details of the transaction can also be recorded on the public blockchain. Eliminate.
In this way, the two parties to the transaction seem to never appear, and the actual transaction has been completed. As people who eat melons, they only know that a transaction has occurred, but they cannot track the currency flow. In this way, a true "anonymous transaction" is realized.
secondary title
homomorphic hiding
Example:
Homomorphic hiding can realize zero-knowledge proof to a certain extent.
Example:
A has two secret numbers x and y, and needs to prove to B that the sum of these two numbers is 7, and only needs to perform the following three steps:
A calculates f(x), f(y), and sends it to B;
Because the function f(x) satisfies additive homomorphism, B can calculate f(x+y) through f(x), f(y);
B independently calculates f(7), and verifies that f(x+y)=f(7).
polynomial blind verification
Polynomial blind verification uses the property of additive homomorphism to polynomials. (The mathematical concepts here are relatively strong, so you can only do a superficial understanding)
Suppose A knows a polynomial P of the highest degree d, and B wants to know E(P(s)) corresponding to some s:
We hope that during the verification process, A only knows P, but not s, and B only knows s, but not P. This can be achieved in the following way:
For each index of s, B calculates E(1), E(s), ..., E(sd), and sends it to A;
A knows all the coefficients of the polynomial, can calculate P(s) by using the homomorphic property, and send it back to B;
KCA (Knowledge of Coefficient Test and Assumption) and full polynomial blind verification.
The polynomial blind verification method provided above has a fatal problem, that is, B cannot verify that A really uses the polynomial P(s) to calculate the result, that is to say, it cannot prove that A really knows the polynomial P(X). KCA continues to improve the above verification.
In short, through additive homomorphism, we can implement additive hiding, allowing B to verify the value of x+y without knowing x and y. Furthermore, through polynomial blind verification, we can let B verify the P(s) corresponding to any given s without exposing the polynomial P(X).
Arbitrary computations converted to polynomial proofs.
The final step of the verification process.
Monero
first level title
Monero
Monero, as a representative of the current encrypted digital currency, applies extremely ingenious cryptography technology to ensure the privacy of transactions.
Two properties of Monero:
Unlinkability: It is impossible to prove that two transactions were sent to the same person, that is, it is impossible to know who the recipient of the transaction is.
Untraceability: It is impossible to know who the sender of the transaction is.
Technical implementation of Monero:
Stealth Addresses
In Monero, each time the sender wants to initiate a transaction, it first uses the receiver's public key information to calculate a one-time temporary intermediate address, and then sends the amount to this intermediate address, and the receiver then uses his public-private The key information can be used to find the transaction and spend it. In this way, other users on the network, including miners, cannot determine who the intermediate address belongs to, but they can still verify the validity of the transaction. Since this address is one-time, every Every time it is regenerated randomly, the attacker will not be able to make any association with the real sender and receiver.
Assuming that Alice wants to transfer an account to Bob, it will be very stressful for Bob, because he needs to scan all the transactions on the blockchain, and then calculate and compare the corresponding information to find the transaction sent to him. Monero proposes an improved solution for this, that is, Bob can hand over half of his private key (a, B) to a third party, thereby authorizing the third party to help check all transactions belonging to Bob on the blockchain, and also It relieves Bob's pressure, but in the end only Bob can spend.
One-time Ring Signature (one-time ring signature)
In short, what ring signatures do is to mix the signer's public key with another set of public keys (but don't know the private key), and then sign the message, so that for the signature verifier (anyone can verification), it is impossible to distinguish which public key in the mixed set corresponds to the real signer.
The entire process of the ring signature technology used in Monero:
The first step, key generation (GEN)
The signer first randomly selects a private key x, and then calculates the corresponding public key. At the same time, another public key is calculated. This public key I is called a "key image". For each signature, this key image is unique, so it is also used later to determine whether the signature has appeared before.
The second step, signature (SIG)
First, the signer randomly selects a public key set containing n elements, and then mixes it with his own public key to generate a mixed set S. Assuming that the subscript of the mixed signer’s public key in S is s, then his The public key is Ps. Then the signer randomly selects {qi, i = 0,...,n} and {wi, i=0,...,n,i!=s} from [1, l-1], and then Compute a non-interactive challenge.
The non-interactive here is relative to the challenge in the interactive zero-knowledge proof. In the interactive mode, the challenge is a value randomly selected by the verifier, and because in the blockchain, both parties to the transaction can only pass the blockchain. To transfer information, but not to interact directly, so non-interactive zero-knowledge proof is chosen here. The reason for this challenge is to avoid situations where the prover forges evidence to deceive the verifier.
The third part, signature verification (VER)
To verify the validity of the signature, the verifier first calculates and then verifies. If the equality is true, then run LNK to verify whether the signature has been used; if the equality is not true, the signature is illegal.
The fourth step, repeat check (LNK)
This requires the system to maintain a collection of images containing all signatures, and then for each new signature, by judging whether its image is in the collection, it is judged whether the signature has appeared before. Note that before this step, the signature verification process of the previous step must be passed.
