As a senior researcher in the NuLink project, I have been working on cryptography and privacy-preserving. There has been an interesting topic in this area for many years which is ZKP(zero knowledge proof ). It recently caused a lot of attention in the community because there are so many interesting scenarios that can be discussed. For example, Zcash. I would like to use a series of articles to introduce this super interesting topic.

Today will be the first one. Through a simple story, I will introduce what is zero knowledge proof and its properties. In the later posts, I will give a strict formalized definition of ZKP and a generic theoretical construction of NP language zero knowledge proof. In the end I will introduce the development, classification, representative schemes and comparison of this technology in recent years. Hopefully you will like this series of posts.

NuLink network is a decentralized solution for privacy-preserving applications developers to implement best practices and best of breed security and privacy. The NuLink platform provides endpoint encryption and cryptographic access control. Sensitive user data can be securely shared from any user platform to cloud or decentralized storage and access to that data is granted automatically by policy in Proxy Re-Encryption or Attribute-Based Encryption. In this process, it is necessary to ensure the availability of the data. Availability here literally means the data is something the end users want and can be used. There is a cryptographic technology that can help us solve this problem, called zero knowledge proof. As the name implies, zero knowledge proof allows you to fully prove that you are the owner of certain data without leakage information, that is, the “knowledge” to the outside world is “zero”.

A simple example, “ How does the prover prove that he knows the solution of the Sudoku game without revealing the answer?”. The methods are as follows: The prover records the answers on a set of cards in order, and cover them. The verifier can choose to pick up the cards by row or column or block, and then open it to verify that each pile of cards is 1–9. Suppose this behavior is repeated 100 times. If all the answers are correct, then the prover indeed knows the solution, otherwise, he needs to guess the rules in which verifier to pick up cards. Then his answer will be wrong several times. The whole proof process does not help the verifier to get the answer. This is an example of zero knowledge proof. Next, we will give an informal definition of proof system and zero knowledge property. Roughly speaking, a reasonable proof system should satisfy the following two properties,

Completeness: If both the prover and the verifier honestly execute the instructions specified by the proof system, then the verifier will accept the proof with a high probability for all true statements.

Soundness: For any prover with any wrong statement, the verifier rejects it with a high probability.

From the perspective of security, the properties of proof system only involve the problem of protecting the verifier from deception. Next, we will give the roughly definition of zero knowledge, which is a property related to prover security.

Zero knowledge: For the verifier, at the end of the proof, he does not gain any additional “knowledge”: everything he observes in the proof can be simulated by a simulator without interaction with the verifier.

Obviously, the above definitions are not rigorous. This is just for readers to quickly understand these concepts. In order to further explore ZKP technology, we need to understand the formalized definitions of commitment, language, proof system, zero knowledge proof system, completeness, soundness and zero knowledge in cryptography. In the next article, we will introduce these definitions. The highlight is the concept of Simulator, which is an interesting concept that can help us define zero knowledge.

‍