WTF is Zero-Knowledge Proof

Yet another “WTF” post, in the previous post we talked about blockchain’s DApp. In this article, I try to explain the mysterious Zero-Knowledge Proof and its current application

Zero-Knowledge Proof, or Zero-Knowledge Protocol, is a probabilistic-based verification method that includes “fact-like statements” and “statements about personal knowledge”. The verifier asks the prover based on certain randomness. If the correct answer is given, the prover has a high probability of possessing what he claims to be “knowledge.” Zero-Knowledge Proof can verify that you did spend the money without revealing which currency was spent.

Being able to answer a question of “Does a user have enough money to send to another user” without knowing who the user is, or exactly how much they have, is one of the primary use cases for Zero-Knowledge Proofs in blockchain. — Demiro Massessi

Why It Matters?

Data privacy is one of the most important subjects nowadays. Protection of personal data related to the identity of individuals (date of birth, bank statements, transaction histories, education credentials) is vitally important and will continuously increase in importance. In the era of technology, we are generating truly mind-boggling amounts of data like never before and the data that we are constantly creating about ourselves is up for grabs. Big companies like Google and Facebook have leveraged on our data to become tech giants that dominate the world today. However, the recent breakthroughs in cryptography and the rise of blockchain enable a new way to help protect our data and identity, even from organizations that we interact with. Zero-Knowledge Proof may be the answer.

The Principle of Zero-Knowledge Proof

Zero-Knowledge Proof is an encryption scheme originally proposed by MIT researchers in the 1980s. Zero-Knowledge Proof agreement is a method by which one party (certifying party) can prove that something is true to the other party (verifying party). Except for the fact that this specific statement is true, no additional information is disclosed.

For example, current websites store the hash value of the user’s password in their web servers. In order to verify that the client actually knows the password, most websites currently use the method of hashing the password input by the client and comparing it with the stored result.

Zero-Knowledge Proof can protect user’ account from leakage. if Zero-Knowledge Proof can be realized, then the client password is unknown to anyone but can still authenticate the client login. When a server is attacked, the user’s account is still secure because the client’s password is not stored in the web server.

Interactive Zero-Knowledge Proof

The basic of Zero-Knowledge Proof protocol is interactive. It requires the verifier to constantly ask a series of questions about the “knowledge” the prover possess.

source: Introduction to Zero Knowledge Proof: The protocol of next generation Blockchain

For example, if someone claims to know the answer to a Sudoku puzzle, a Zero-Knowledge Proof is that the verifier randomly specifies to verify by column, row, or nine squares. Each test does not need to know the specific answer but only needs to detect whether number 1 to 9 are included. As long as the number of verifications is enough, it is possible to believe that the prover knows the solution of the Sudoku problem. However, such a simple way does not make people believe that both the prover and the verifier are not falsified. In the case of Sudoku, the two may be colluded in advance, so that the prover can pass the verification without knowing the answer. If they want to convince a third party, the verifier must also prove that the verification process is random and that it does not leak the answer to the prover. Thus, it is difficult for a third party to verify the results of interactive Zero-Knowledge Proof; extra effort and cost are needed to prove something to multiple people.

Non-interactive Zero-Knowledge Proof

Non-interactive Zero-Knowledge Proof, as the name implies, do not require an interactive process, avoiding the possibility of collusion, but may require additional machines and programs to determine the sequence of experiments.

For example, in the case of Sudoku, the program decides which column or row to verify. The verification sequence must be kept secret, otherwise, the verifier may pass the verification sequence without actually knowing the real “knowledge”.

The Zero-Knowledge Proof Application on the Blockchain

Both Bitcoin and Ethereum networks use public addresses to replace the true identity of the party, making the transactions partially anonymous; only the sending and receiving addresses, and the amount are known to the public. However, it is possible to find out the real identity of the address through various kinds of information available on the blockchain such as interaction records and thus there is a hidden danger of privacy exposure.

Zero-Knowledge Proof, the sender, the recipient, and other transaction details can remain anonymous while guaranteeing the transactions are valid.

ZCash may be one of the most well-known blockchain projects that have successfully implemented Zero-Knowledge Proof. Zcash implements a modified version of ZKP called zk-SNARKS, which stands for ‘Zero-Knowledge Succinct Non-Interactive Argument of Knowledge’.

zk-SNARK

The zk-SNARK technology reduces the size of the proofs and the amount of computation required to validate them. It is able to prove that the conditions for a valid transaction have been satisfied without revealing any crucial information about the addresses or values involved.

zk-SNARK converts the transaction content that needs to be verified into a proof that two polynomial products are equal, combined with homomorphic encryption and other advanced techniques to protect the hidden transaction amount while performing transaction verification. Its process can be briefly described as:

1. Disassemble the code into verifiable logical verification steps, then disassemble these steps into an arithmetic circuit consisting of addition, subtraction, multiplication, and division.
2. Conduct a series of transformations to convert the code to be verified into a polynomial equation, such as 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 to check whether the equations at these points are true.
4. By homomorphic encoding/encryption, the verifier does not know the actual input value when calculating the equation, but can still verify.
5. On the left and right hand sides of the equation, multiply a secret value k that is not equal to 0. when verifying that (t(s)h(s)k) is equal to (w(s)v(s)k), The specific t(s), h(s), w(s), and v(s) cannot be known, so the information can be protected.

One of the pitfalls of current zk-SNARK implementation is that the parameters need to be built-in in advanced. If these parameters are leaked, the entire network would face a devastating blowout. As a result, users must trust that are not leaked when using these networks.

Possible solutions include the use of modern “trusted execution environments” like Intel SGX and ARM TrustZone. For Intel’s SGX technology, the private key is safe even if the application, operating system, BIOS, or VMM is compromised. In addition, a recent whitepaper reveals it’s innovation in zero-knowledge cryptography: ZK-STARKs (Zero-Knowledge Scalable Transparent ARguments of Knowledge).

According to the zk-STARK white paper, zk-STARK is the first system to achieve blockchain verification without relying on any trust settings, while the computational speed is exponentially accelerated as the number of computational data increases. It does not rely on public key cryptosystems, and simpler assumptions make it theoretically more secure because its only encryption assumption is that hash functions (such as SHA2) are unpredictable. It will take time for technology like Zero-Knowledge Proof and zk-S(T|N)ARK to be tested and adopted.