Zero Knowledge Proof

Headshot

Eden Block

• Categories:

What are zero-knowledge proofs?

Zero-knowledge proofs are an effective way of ensuring anonymity for users of decentralized applications. Zero-knowledge proofs have a high theoretical potential to improve security and privacy in blockchain applications. Blockchain transactions are connected to wallet addresses. Usually, all participants of the blockchain are able to see the details of the transactions. While transactions cannot be directly connected to one person, all the transaction associated with each user address are visible. While transparency is fine for some use cases, many don’t like the inherent traceability, especially when transactions involve sensitive data such as medical history. Zero-knowledge proofs allow data to be verified but not seen. Users can verify whether or not the data of the transaction is valid, but not display the actual information of the transaction.

 

In short “Zero-knowledge proofs are defined as those proofs that convey no additional knowledge, other than the correctness of the proposition in question.” (2) Resulting, one person can provide a zero knowledge proof to another person to show that (s)he has the information, without displaying the actual information.

 

The following three conditions have to be met by a zero-knowledge proof:

 

zK-Snarks

zK-Snark stands for “Zero-Knowledge Succinct Non-Interactive Argument of Knowledge,” (3) and they allows the prover to prove to the verifier that certain data is valid, without having to reveal the details of the computation. For example, one could prove possession of a secret key, without giving the verifier the secret key. Another example would be to show the validity of the hash of a random number. Only one party knows the hash, “the prover could convince the verifier that there indeed exists a number with this hash value, without revealing what it is.” (3) Ultimately, the hash of any data can be provided in combination with other information to show that a one party has the information it claims to have without revealing the raw data.

 

In the case of zK-Snark, the proof length will only be 188 bytes, no matter what they are proving, and can be generated in milliseconds. Furthermore, instead of sending messages back and forth between prover and verifier; the proof is generated within a single message sent from prover to verifier. This is called a ‘non-interactive’ construction. Currently, in order to generate non-interactive proofs, which are short enough to post on the blockchain, an initial setup phase is required between verifier and prover, in which a common reference string (shared randomness) is generated. In contrast, interactive zero knowledge proofs require both parties, the verifier and the prover, to be in direct contact with each other and exchange information. Examples are provided below.

 

There are several options on how one participant can prove that his/her output is correct. The first option is that several users process the calculation and compare the results. Ultimately, the result which was provided most often would be considered correct. This technique is based on trustless computing. (9) Imagine Anna has limited computing power and is therefore asking an online friend, Bob, to make the computation for her and provide her with the answer. Anna has no way of proving that the data provided by Bob is correct and Bob has no incentive to accurately answer Anna’s question; he will receive her reward anyway, whether or not he provides her with the right output. To ensure that Anna receives the right outcome, she could ask ten friends to complete the computation for her instead of one. The correct answer is the answer that the majority of friends provide; those who answer correctly are rewarded. This process is more expensive, since Anna would have to pay all ten friends; however, she can be assured that she will receive a more accurate outcome.

 

Another strategy would be to use interactive zK-snarks. For example, because Bob does not want to make the computation before he verifies that Anna has sufficient funds to reward him, Anna can provide Bob with her wallet address and Bob can see the funds in the address. However, he will not know, based on the address, that the wallet belongs to Anna. Every address has a private-public key pair (the public key is usually the wallet address. This has been discussed in a previous article). To check whether or not Anna is indeed the owner of the wallet, Bob can sign a secret message with Anna’s public key, which generates the hash of the secret message. Anna will be the only one with the private key associated with the public key and thus, will be able to decrypt Bob’s message. Once Anna obtains the plaintext of Bob’s message, she can either respond with an answer to a question stated by Bob in the message, or respond with the message itself. Ultimately, this proves to Bob that Anna is indeed the owner of the wallet.

 

In contrast, to the above example of an interactive proof, Anna can generate a non-interactive zero-knowledge proof. Anna can create message M and compute the hash of the message with her public key. If Anna gives Bob the hash, the message, and the public key, he can confirm that the hash was created from the message by the private key for Anna’s address. (10)

 

Non-interactive zero-knowledge proofs also allow Anna to verify the correctness of a single computation without actually running the computation herself (or outsourcing to ten friends). First, Bob has to break down the problem into smaller steps, represented in arithmetic circuits, through AND, OR, NOT and by basic arithmetic operations (addition, subtraction, division, multiplication). Then, he has to compute a quadratic equation of polynomials. Bob wants to convince the verifier, Anna, that his equation holds “if and only if the program is computed correctly.” (7) The equation can look something like this: t(x) h(x) = w(x) v(x). Afterwards, Anna will choose a secret evaluation point in the program ‘s’, which only she knows and not Bob. He reduces “the problem from multiplying polynomials and verifying polynomial function equality to simple multiplication and equality check on numbers.”(7) After Anna inserted her secret point ‘s’ into the shared function t(x) h(x) = w(x) v(x), it will result into t(s)h(s) = w(s)v(s). Now Anna will share t(s)h(s) = w(s)v(s) with Bob. Note that Bob does not know Anna’s secret ‘s’. Bob will choose an encryption function ‘E’ to encrypt t(s)h(s) = w(s)v(s). After the encryption he will receive E(t(s)), E(h(s)), E(w(s)), E(v(s). Then Bob multiplies the encrypted function with a random value to receive t(s)h(s) k = w(s)v(s) k’. Anna can now verify “the correct structure without knowing the the actual encode values.” (7) Ultimately, having t(s)h(s) = w(s)v(s) is identical to “t(s)h(s) k = w(s)v(s) k for a random secret number k (which is not zero)”  (7) Note that if network participants only receive “numbers (t(s)h(s) k) and (w(s)v(s) k), it is impossible to derive t(s)h(s) or w(s)v(s).” (7) Without knowing the random value chosen by Bob, nobody else in the network would be able to derive the function with the verifier’s secret point t(s)h(s) or w(s)v(s).

 

In simple terms, in order to prove to Anna that the computation is correct, Bob must break down the computation into simple equations. With this simplified equation, he creates a series of functions. Next, these functions are shared with Anna. Anna creates a secret number which she puts in the function. She shares this result with Bob. Bob, of course, knows the function but not the number. Bob encrypts the output provided by Anna. He then chooses a random number and multiplies the output by this new number. Anna can then take this result, compare it to her secret number, and verify that the original computation is correct.

 

The downside of non-interactive zk-snarks is that they require a secret setup to generate a shared randomness between all parties involved. If someone else has access to the shared randomness, they will be able to generate false proofs which look valid to the verifier. To prevent this, Zcash generates the randomness through a multi-party ceremony (outlined in applications under Zcash).

 

Application

Zcash

Makes use of a zK-Snarks proof; Zcash allows transactions to be fully encrypted and fully verifiable.

 

In Zcash, a function is used which verifies the validity of a transaction according to the network’s consensus rules. “In Bitcoin, transactions are validated by linking the sender address, receiver address, and input and output values on the public blockchain. Zcash uses zk-SNARKs to prove that the conditions for a valid transaction have been satisfied without revealing any crucial information about the addresses or values involved. The sender of a shielded transaction constructs a proof to show that, with high probability:” (3) Ultimately, Zcash is able to show that the input and output values of a transaction, as well as the sender and receiver address, are correct, without revealing the actual transaction details. This is done through the implementation of zk-Snarks.

 

Every zero-knowledge proof in Zcash has to fulfill the following properties:

 

Bitcoin keeps track of unspent transaction outputs to determine if the transactions are spendable. In Zcash the equivalent is called a commitment. “Spending a commitment involves revealing a “nullifier.” Zcash nodes keep lists of all the commitments that have been created, and all the nullifiers that have been revealed. Commitments and nullifiers are stored as hashes, to avoid disclosing any information about the commitments, or which nullifiers relate to which commitments.” (3) In contrast to Bitcoin, in Zcash the transaction output is not publicly visible, only the hashed information is.

 

“When a shielded transaction is spent, the sender uses their spending key to publish a nullifier.” (3) The nullifier is the hash of a secret number from an existing commitment, which has not been spent. The nullifier provides the zero-knowledge proof, ensuring that the assets detailed in the commitment have not been spent and demonstrating that the owner of these assets is authorized to spend them. The hash of the nullfier cannot be part of a list of nullifiers, which is held by each node in the network.

 

Multi-Party Ceremony

“In addition to the spending keys used to control addresses, Zcash uses a set of proving and verifying keys to create and check proofs.” These are generated in the multi-party ceremony and shared between all participants on the network. For each transaction, the sender uses the proving key to verify their input. Miners can then check the transaction by following the consensus rules and then can verify the prover’s computation with the verifying key.

 

Benefits

The main benefit of the Zcash process is that the computational work is offloaded to the creator of the transactions. The system requires minimal effort from the miner and verifier. This might be useful to prevent DDoS attacks and the like. In addition, creating a transaction can take up to 40 seconds, whereas verifiers need only a few milliseconds to check every transaction. This allows for high network throughput. Lastly, fully encrypted transactions allow for higher privacy and network security.

 

Summary/Conclusion

Zero-knowledge proofs allow provers to demonstrate the validity of data to verifiers; without having to share the data itself. Computations have to adhere to Completeness, Soundness and Privacy. This can be achieved through computations such as with zK-Snarks; whereby the prover shares the solution of an algebraic problem with the verifier. Commitments are used to keep track of unspent transaction outputs; spending these involves a “nullifier.” Multi-party ceremonies are used to create proving and verifying keys.

 

Ultimately, zero-knowledge proofs allow for a wide range of blockchain applications which require private data. In particular, this could be applications that maintain medical data or adhere to certain regulations.

 

Sources

  1. https://medium.com/@argongroup/on-zero-knowledge-proofs-in-blockchains-14c48cfd1dd1
  2. http://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/The_Knowledge_Complexity_Of_Interactive_Proof_Systems.pdf
  3. https://z.cash/technology/zksnarks.html
  4. https://www.coindesk.com/zk-snarks-everywhere-ethereum-privacy-tech-hits-tipping-point/
  5. https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell/
  6. https://z.cash/
  7. https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell/
  8. https://en.wikipedia.org/wiki/Zero-knowledge_proof
  9. https://medium.com/@snark.network/snark-zk-snark-trustless-computing-54055e1d0b8d
  10. https://www.iacr.org/archive/asiacrypt2010/6477343/6477343.pdf
  11. https://medium.com/@snark.network/snark-zero-knowledge-proofs-b88c40e188a