Diving Deeper into Zero-Knowledge Proofs (Part 2)

“Knowing Nothing proves everything”
The Economic Times on Zero Knowledge Proofs

Following up to the previous post about Zero-Knowledge Proofs, we will be talking about them in much more detail.

If you haven’t read the post preceding this one, please do hear over there to make the most out of this one.
Two Men on an Island - An Introduction to Zero-Knowledge Proofs and What Follows (Part - 1)

In Part 1, we saw a brief introduction to Zero-Knowledge Proofs or ZKPs as they are commonly referred, along with a simplified understanding of how ZKPs work. In principle, a ZKP is an outcome that ensures one is able to provide ownership or possession of certain information, without effectively giving out any data about the said information. To put that into perspective, we discussed a hypothetical story of two men on a treasure hunt in a remote island, each holding one-half of the means to reach the treasure.

Assuming that you’re reasonably affirmative on the understanding of the philosophy of ZKP, we will move ahead to see how ZKPs can be calculated, the different methods by which one can calculate them, and some of their uses, until finally, we move on towards the final part of the series where we will be focusing on real-world applications of ZKPs.

It must be noted that the concept of ‘proof’ in ZKP is different from the traditional mathematical concept. Mathematical proofs are strict, using either self-evident statements or statements obtained from proofs established beforehand. ZK proofs are more similar to the dynamic process used by humans to establish the truth of a statement throughout the exchange of information.

Classification of ZKPs

ZKPs, with their apparent need in the virtual world, are immensely useful in everyday application. But the use of ZKP differs based on the number of participants involved. For a small group or a few million people, ZKPs are able to successfully transmit the said communication.

Interactive ZKP

Being one of the most used forms of ZKP, interactive ZKPs are exactly what the name says. The parties involved in proof have to interact with each other, affirming along the way about their satisfaction about the proof provided. Most Interactive ZKP involve a small number of parties, as it is not feasible to constantly ask for affirmation from a large group of participants. The example we used about two men on an Island falls under this category. To make sure “I” communicate the proof to “You”, I used an interactive method of probabilistically ensuring the ownership, i.e., taking trips around the island and reaching the starting point.

Source: TopRankBlog

To quote the definition, “An interactive proof protocol is complete if, given an honest prover and an honest verifier, the protocol succeeds with overwhelming probability (i.e., the verifier accepts the prover’s claim). The definition of overwhelming, of course, depends on the application, but generally implies that the probability of failure is not of practical significance.”

Non-Interactive ZKP

To break down the problem of mass communication, Non-Interactive proof have to be formulated. A Non-Interactive ZKP is a special kind of proof that does that involve constant verification on the other end. Say one has to communicate to the entire blockchain network about a transaction you just performed but do not wish to disclose information about the transaction, its receiver, etc., one has to use some form of Non-Interactive ZKP.

Non-interactive ZKPs are used when large number of participants are involved and most importantly, when one needs to give a proof without the need for constant interaction.

Ways by which ZKPs can be Solved

zk-SNARKs

Zero-Knowledge Succinct Non-Interactive ARgument of Knowledge or zk-SNARKs is one of the most used privacy concept within the cryptodevelopers community. As the name suggests, SNARKS are probabilistic means of assessing and arguing about the validity of a particular information. In simple words, zk-SNARKs present Proof-of-Knowledge in the form of a secret key, that could only be generated if the person claiming ownership has the information in the first place.

Source: MayContainMath

One of the most simple forms of zk-SNARK is the verification of a hash. If a person has to prove they are in possession of a certain number, he can hash that number using any of the hashing algorithms. Since that hash is a representation of a particular set of information, it can be verified that the hash belongs to the predetermined number when the number comes out.

Even though it wasn’t the first to use an iteration of zk-SNARKs, the cryptocurrency Zcash was responsible to popularize the protocol. Ethereum followed up in 2017 when they forked the chain to allow the option of using zk-SNARKs when creating smart contracts.

zk-STARKS

Source: Game of Thrones

“zk-STARKs were created by Eli-Ben Sasson, a professor at the Technion-Israel Institute of Technology. As an alternative version of zk-SNARK proofs, zk-STARKs are, generally, considered a more efficient variant of the technology - potentially faster and cheaper depending on the implementation. But more importantly, zk-STARKs do not require an initial trusted setup (hence, the “T” for transparent).”

Binance Academy

zk-STARKs were created to fill the gaps of zk-SNARKs. It is quite tough to communicate how zk-STARKs improve zk-SNARKs without getting a bit technical, but I will try my best to tone it down.

zk-SNARKs are non-interactive proofs that give ownership information to a large group without the need to interact with the proof. To do this, the private keys of the proof have to be created and attached to the string of the proof to ensure it is true and fair. The private key is the only part of the SNARK proof that stays behind the eyes of the public. Even though zk-SNARKs are proven to be quite effective, a vested party with enough resources can manipulate the loophole by creating similar proofs, hiding the private key.

zk-STARKs fixes the loophole by using randomness instead of private keys to generate the proof. By this mechanism, all information regarding the proof is public and thus, the resilience against the proof is increased. Another advantage is that zk-STARKs are known to be Quantum resistant. As there is no cryptographic asymmetry due to the use of public/private keys, Quantum computers cannot be used to crack the protocol.

Although the proof is undergoing constant updates, zk-STARKs have a prospective future ahead.

Right now, no public blockchain has integrated zk-STARKs. Though, it is likely that they will find themselves in Zcash or Monero over the coming years and possibly Ethereum, also.

Coincentral

Bullet Proofs

Screenshot 2019-04-24 at 2.04.41 PM 1.png

One of the latest additions to the privacy based cryptographic protocols, Bulletproofs were proposed by Stanford’s Applied Cryptography Group (ACG) in December 2017 in an academic paper. Bulletproofs are “a new zero-knowledge argument of knowledge system, to prove that a secret committed value lies in a given interval.” The bulletproof name is credited to Shashank Agrawal for describing them as being “short like a bullet, with bulletproof security assumptions.”

The proofs of bulletproofs are much shorter than other range proofs. Bulletproofs also does not require a trusted setup. They are especially suited for the distributed and trustless nature of blockchains and can create substantial long-term cost savings, enormous space savings, lower fees, and faster verification times than current implementations of range proofs. Monero states that they have reached an 80% reduction in transaction size utilizing bulletproofs which leads to an 80% reduction in fees as well.

(I apologize for using words that stand out of the general level of understanding, but that was the best I could do without messing up the explanation.)

Places where ZKP can be used

A Blockchain where privacy is of utmost value can make use of ZKPs to ensure the trestles flow of value without the propagation of any information other than the ownership of the said value. Zcash and its predecessor, Zcoin make use of zk-SNARKS to ensure the safety of privacy along with the transmission of information and value.
Peer to Peer communication is when two parties communicate with each other without any intermediary in between. They might communicate P2P for several reasons; to stay away from prying eyes, to exchange sensitive information, to transfer value without much attention. ZKPs prove to be the best means for parties to have a truly private mechanism to communicate and transact.
Voting is also an essential part of every democracy from that of a country down to the shareholder participation of a company. Hence, with nations moving towards digitization and with the proliferation of security tokens, the demand for secure and anonymous voting solutions is bound to increase. ZKPs are bound to make an appearance here.

It is clear that both zk-SNARKS and zk-STARKs appeal to the growing concern in regards to privacy. Within the cryptocurrency world, these protocols have great potential and may be a groundbreaking avenue towards mainstream adoption.

In the last part of the series, we will dive into real world applications of ZKPs, where they are currently used and where they can be used. Please do let us know if you would like use to cover anything else other than what we have planned.