How to maintain anonymity while keeping transactions valid in blockchain applications: An article on zero-knowledge proofs
Zero-knowledge proofs for anonymous blockchain transactions.
In the complex field of cryptography, zero-knowledge proofs provide a unique solution to a seemingly contradictory task: proving knowledge of a certain information without revealing the information itself. This encryption method involves two parties: the prover and verifier. The prover’s goal is to prove that they possess certain information (which we call x) without revealing any data about x itself. The verifier only learns the simple fact that the prover has this knowledge from the interaction. Most importantly, the verifier does not gain any additional information about x.
For example, when Xiao Ling and Xiao Shi are playing an escape room game, Xiao Ling tells Xiao Shi that he has cracked the password of a certain “treasure box”. However, Xiao Ling does not want to share the answer directly, nor does he want to open the treasure box in front of Xiao Shi. So how can he prove to Xiao Shi that he really solved the puzzle and knows the password to the treasure box?
He asks Xiao Shi to write a string of characters that only she knows on a piece of paper, and sign her name. Then, he puts the paper through the crack of the treasure box.
Xiao Ling then opens the treasure box and takes out the paper that Xiao Shi put in, showing it to Xiao Shi who verifies that the string and signature are correct. This proves that Xiao Ling does indeed know the password to the treasure box, and that the paper is indeed taken out from the treasure box.
The decryption process was not known to Xiao Shi, while Xiao Ling proved that he had cracked the password to the treasure box.
- On the Justice of the Web3 System from the Perspective of “Th...
- Exclusive Interview with the Founder of Starknet: Looking Up to the...
- ERC-6551: The Next Trend for NFTs
Zero-knowledge proof
In cryptography, a zero-knowledge proof (ZKP) or zero-knowledge protocol is a method that allows a prover to convince a verifier of the truth of a statement or assertion without revealing any information about the statement or assertion itself or any other information. The concept of zero-knowledge proof was first introduced in a paper titled “The Knowledge Complexity of Interactive Proof Systems” by Shafi Goldwasser, Silvio Micali, and Charles Rackoff, professors at MIT and cryptography experts. The algorithm concept laid the foundation for modern cryptography.
Zero-knowledge proofs have two additional attributes: succinctness and zero-knowledge. Succinctness allows the verifier to accept the correctness of a large computation without having to compute the statement or assertion themselves. Zero-knowledge ensures that no data about the input is leaked.
Zero-knowledge proofs are essential for ensuring the privacy and security of many encryption protocols. They are a safeguard against potential information leaks and are the invisible armor of the Crypto world. The application of this knowledge can be extended to different fields, including blockchain technology and secure authentication systems, where the protection of sensitive data is of utmost importance.
Wide Range of Applications
Blockchain and Cryptography: Blockchain technologies, like Zcash, use zero-knowledge proofs to protect transaction privacy. A person can prove they have enough Crypto currency to make a transaction without revealing the exact amount of their funds. This ensures privacy while also ensuring transaction integrity. Identity Verification and Authentication: Zero-knowledge proofs can also be used to confirm identity without revealing unnecessary information. For example, a person can prove they are over 18 without providing their exact date of birth, or prove their identity without sharing sensitive data like passwords. This minimizes the risk of identity theft or unauthorized access.
Secure Multi-Party Computation (SMPC): Zero-knowledge proofs can facilitate complex interactions between multiple parties, where each party can prove they are following an agreed-upon protocol without revealing the specific details of their input. This is effective in many areas such as protecting privacy in data mining, secure voting systems, and more. Network Security: Zero-knowledge proofs can provide improved security protocols, such as secure password policies. It can verify if a user’s proposed password meets certain security standards without letting the server know or record the actual password. Since passwords are not stored anywhere, this can prevent potential misconduct. Sharing Data while Protecting Privacy: Zero-knowledge proofs can be used to prove that certain data meets specific requirements without revealing the data itself, which is particularly important in fields such as healthcare or finance. These fields have strict regulations on data privacy, but sharing information in a secure and privacy-protecting way may bring huge benefits, such as promoting the development of healthcare. Zero-knowledge proofs have already released new technological possibilities in blockchain. This can be seen from various Layer 2s, such as ZKSync and Polygon’s zkEVM. However, this is only a subset of the blockchains created by zero-knowledge proofs.
How to Represent a Proof
In this section and the rest of the article, we will focus on proofs constructed using the PLONK proof system.
PLONK is a zero-knowledge proof system whose full name is:
“Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge,” which stands for “Permutations over Lagrange bases for global non-interactive knowledge arguments.”
Essentially, PLONK is a general-purpose, updatable encryption proof system, which allows for efficient verification and scalability within blockchain systems and other distributed networks. The idea behind PLONK is to construct a general and updatable proof system. In the context of zero-knowledge proof systems, “general” means that it can be used for any type of computation; “updatable” means that the encrypted reference string (a piece of data used to generate and verify proofs) can be securely updated over time.
PLONK is notable for its efficiency and simplicity, and has become a popular choice for projects and companies that require secure, private transaction systems. Compared to other systems, it uses fewer constraint conditions per gate (the basic unit of computation, which we will refer to as a “gate” from here on), which makes it faster and more scalable. Vitalik Buterin has published a more comprehensive description of PLONK. 【Copy the link to the browser to view the original text https://vitalik.ca/general/2019/09/22/plonk.html】
Proof
Before proving a statement, we first represent the statement using a circuit. A circuit encodes values in a computation together with two types of additional data:
1. Operations: e.g., multiplication and addition computations over input data2. The order in which operations are executed
To encode this data, a PLONKish circuit is represented as a set of vectors and constraint conditions. Constraint conditions are relationships that must be followed by units in vectors, where two types of constraint types exist: gate constraints and copy constraints, representing operations and their order in the circuit, respectively.
There are multiple methods for expressing a circuit depending on the gates and circuit architecture used.
Representing a Statement as a Circuit
Suppose we have two gates: one multiplication gate and one addition gate. The multiplication gate is represented as a length-3 vector |a|b|c|. If this gate is selected, it will constrain c to be equal to a*b. Similarly, the addition gate is represented as a length-3 vector, and if the addition gate is selected, c will be equal to a+b. Using these gates, let’s represent the dot product between two vectors (a, b) and (c, d). To do this, we need to perform the following computations:1. Compute a*b using the multiplication gate2. Compute c*d using the multiplication gate3. Compute ab+cd using the addition gateThis can be represented using vectors.
Note that the output of the first and second multiplication gates is the input value of the addition gate. This data is separately encoded from the AND gate’s constraint in our circuit. This is referred to as a copy constraint. So why are circuit constraints important? Without constraints, a malicious prover could input any values they like into the circuit. For example, the prover could replace ab+cd with aba*b. Like in smart contracts, constraints must be verified by the proof system before use.
Proof Statements
Now that we can represent statements using a circuit, how does a prover convince a verifier that the proof is valid? In the case of the PLONK system, the prover must convince the verifier that the gate constraints and copy constraints are satisfied. For copy constraints, this is done by performing permutation checks.
Substitution checks were first proposed by Bayer-Groth, and further developed by Gabizon, Williamson, and Ciobotaru in the PLONK paper. To prove gate constraints, a quotient polynomial must be computed.
Intuitively, permutation checks show that if copy constraint entries are permuted, the circuit remains the same. Permutation Checks
If for all positions i of b, there exists a position σ(i) in a that is equal to a, we say that a vector a is associated with vector b by permutation σ. We represent this as σ(a)=b. Given two vectors a=(a,b,…,c), b=(a’,b’,…,c’), and permutation σ, we want to determine if σ(a)=b. This can be done as follows:
Represent the vectors as a’=((a,1),(b,2),…,(c,n)) and b’=((a’,σ(1),(b’,σ(2)),…,(c’,σ(n)) ). This encodes the vectors with respect to the permutation σ.
Rewrite the vectors as polynomial vectors: a”=((a+1X),(b+2X),…,(c+nX)) and b”=((a’+σ(1)X), (b’+σ(2)X),…, (c’+σ(n)X+γ))
Checking if a” and b” as multisets are equivalent can be done by randomly choosing γ to show that $(a+1X+γ)(b+2X+γ)….(c+nX+γ) = (a’+σ(1)X)+γ)(b’+σ(2)X+γ)….(c’+σ(n)X+γ)$.
By randomly choosing a β, we can use the Schwartz-Zippel lemma to check if these polynomials are equivalent. If they are equivalent as polynomials, then the sets a” and b” as multisets are equivalent. If they are not equivalent polynomials, then a” and b” are not equivalent multisets.
In conclusion
Although zero-knowledge proofs are a complex topic, their applicability is continuously growing. In this article, we have provided an intuitive explanation of how zero-knowledge proofs work. In the future, the CertiK team will delve deeper into the applications of zero-knowledge proofs and how to optimize their circuits for new use cases.
