In cryptography, zero-knowledge proofs have been around for a while but have gained more popularity lately due to their use in privacy and security in Blockchain. Blockchain was designed to be used for the use of Bitcoin (Nakamoto, 2008) and was only later realized to have a potential for other areas. Bitcoin was the first cryptocurrency and was definitely not the last. Although Blockchains, such as Bitcoin, offers many advantages in terms of being a decentralized ledger, cryptocurrencies which make use of zero-knowledge proofs offer a competitive edge.

A proof is when a prover demonstrates evidence that a statement is true. In cryptography, we can find non-Interactive proofs. Non-Interactive proofs can prove a “true” statement but cannot prove a “false” statement. An extension of non-interactive proofs is interactive proofs. Interactive Proof systems have a prover and verifier who communicate with each other so as for the prover to prove to the verifier the validity of a certificate. The prover receives an input, performs the computation and outputs a polynomial proof certificate. The certificate is sent to the verifier and the verifier validates it in deterministic polynomial time. An Interactive Proof System has two requirements; Soundness and Completeness.

The theory of NP-completeness states that if the proof is true (certificate is valid), the honest verifier will be convinced of its validity. The theory of NP-soundness states that if the proof is false (certificate is invalid), the prover will not be able to prove its validity to the verifier. The verifier receives the certificate and information about the calculation from the prover. As one may deduct, this does provide a level of vulnerability due to privacy and security issues. Zero-knowledge proofs also have the completeness and soundness requirements. Apart from these two requirements, zero-knowledge proofs have an additional requirement; privacy. To add a level of privacy, a witness is introduced for the prover to prove to the verifier that the proof is valid without exposing the information in the entire blockchain.

Zero-knowledge proofs can be used in cryptography where privacy and security are of highest priority. One simple example to understand zero-knowledge proofs in simple terms is when there is a blind person and two bowling balls of two different colours; white and black. In this case, the blind person is the verifier. We will act as the prover. Our job is to prove to our friend that both balls are of different colour without telling our friend the colours of the bowling balls. The blind person places the balls behind his back and takes turns showing either ball. We would have to tell the blind person whether or not the balls have been swapped. This experiment is repeated several times and given a high percentage of correctness, the blind person is convinced that the bowling balls are of different colour without telling the blind person the actual colour of the bowling balls. (K, 2017)

 

An example of zero-knowledge proofs

We can display zero-knowledge proofs by using the example below.

Mary wants to pay John 100 euros

In Blockchain, the transaction is replicated to each node.

The prover, that is, the node which would like to perform the transaction, needs the witness to provide additional information to create the proof. The proof is then sent to the verifiers in order to be accepted as valid or invalid. The additional information can be the preimage of a hash function or the location of the Merkle-tree node. Each of the nodes in the blockchain work on verifying the transaction (i.e. that Mary has enough money to complete the transaction). This process is known as mining and the nodes which verify the transaction are known as miners.

One of Zero-knowledge proofs’ most iconic supporters is Edward Snowden. (Young, 2018) Edward Snowden is a software developer who was a subcontractor for the National Security Agency (NSA). Upon finding private surveillance media, Snowden realized the government was lying to the entire nation of the United States of America regarding privacy. He leaked documents regarding the lies told by the government about privacy and security and although he has been charged with breaking the Espionage Act, most people fully support his actions. It is no surprise that Snowden would be behind in supporting Zero-knowledge proofs; a protocol which facilitates transaction security and privacy.

 

Zk-SNARKs
Zk-SNARKs is a zero-knowledge protocol which has been adopted by several different blockchains, such as ZCash (the first cryptocurrency to adopt zk-SNARKs) and Ethereum (since September 2017). The zero-knowledge proof zk-SNARKs, stands for Zero-Knowledge, Succinct, Non-interactive, Argument of Knowledge. Succinct means that the proof is small and this makes this proof quick to be verified. Zk-SNARKs is known as non-interactive as there is no constant communication from the prover to the verifier, and instead, the prover sends information to the verifier once. Argument means that the proof is computationally sound. The witness fits in with the zk-SNARKs proof with the term of Knowledge. In zk-SNARKs, public key cryptography is used as part of its algorithm to protect the transaction’s privacy and security. Zk-SNARKs makes for an interesting subject and we will devote an article just to this topic in the near future. (Reitwiessner, 2016)

 

Zk-STARKs
A newer protocol has been introduced to market. Recently we have heard the zero-knowledge proof, zk-STARKs, being thrown around in Blockchain conversations. The acronym ZK-STARKs stands for Succinct, Transparent, Argument of Knowledge. Zk-STARKs promises to maintain the level of privacy and security and improve scalability from the zk-SNARKs protocol. In zk-STARKs, the proof is attached to the block in blockchain. Then the proof is executed each time rather than having to rerun the transaction. It is expected that ZK-STARKs will replace zk-SNARKs in Z-Cash. (keep0n.steemin, 2017) Zk-STARKs offers several advantages over zk-SNARKs, such as higher scalability rates, not needing a setup phase (which in turn, reduces costs), and is considered to be quantum resistant as it does not make use of private-public key pairs. (Luciano, 2018)

 

Zk-SNARKs and zk-STARKs are far more complex than as described in this article. Here, we have just briefly just scratched the surface. Both these protocols deserve to be discussed on their own and we will definitely be revisiting these topics in the future. Zero-knowledge protocols add a level of privacy to transactions and are definitely at the start of revolutionizing Blockchain technologies.

 

 

References

K, L. (2017, November 23). How to prove that you know something, without revealing it? Zero-knowledge proofs, ZCash, Ethereum. Retrieved from Hackernoon: https://hackernoon.com/how-to-prove-that-you-know-something-without-revealing-it-zero-knowledge-proofs-zcash-ethereum-43ce35d4d1c5
keep0n.steemin. (2017, October 1). Zk-STARKs??? New Take on Zcash Tech. Retrieved from steemit: https://steemit.com/crypto/@keep0n.steemin/zk-STARKs-new-take-on-zcash-tech
Luciano, A. (2018, June 25). ZK-STARKs — Create Verifiable Trust, even against Quantum Computers. Retrieved from Medium: https://medium.com/coinmonks/zk-STARKs-create-verifiable-trust-even-against-quantum-computers-dd9c6a2bb13d
Nakamoto, S. (2008, October 31). Bitcoin: A Peer-to-Peer Electronic Cash System. Retrieved from Bitcoin: https://bitcoin.org/bitcoin.pdf
Reitwiessner, C. (2016, December 5). zkSNARKs in a nutshell. Retrieved from Ethereum Blog: https://blog.ethereum.org/2016/12/05/zkSNARKs-in-a-nutshell/
Young, J. (2018, January 10). Anonymous Cryptocurrencies: Why Edward Snowden Supports Zero-Knowledge Proofs. Retrieved from Binary District: https://journal.binarydistrict.com/anonymous-cryptocurrencies-why-edward-snowden-supports-zero-knowledge-proofs/

 

Display image: https://cdn-images-1.medium.com/max/800/1*25Qdt_ysMwFghFXVWjqG3g.png