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

Ashish
Ashish
Oct 8, 2018 · 7 min read

One of the most important and at the same time very counterintuitive, primitives for cryptographic protocols are so called zero-knowledge proof or protocols (of knowledge).

A Zero knowledge proof or Zero knowledge Protocol is a method where one party can prove (prover) to another party (verifier) without revealing knowledge of secret itself. In other words we can say a zero-knowledge proof protocol allows one party, usually called PROVER, to convince another party, called VERIFIER, that PROVER knows some facts (a secret, a proof of a theorem,…) without revealing to the VERIFIER ANY information about his knowledge (secret, proof,…).

Proof of Identity: — Zero Knowledge proofs can be used for identification. Identification schemes in general, then “traditional” secret-key and public-key schemes and finally zero-knowledge schemes. Identification schemes are methods by which a user may prove his or her identity without revealing knowledge that may be used by an eavesdropper to impersonate the user.

The traditional form of identification is by use of a secret key, password or pin, but this scheme is extremely insecure since they are easy to guess, for example, through an exhaustive search. Recently, biometric parameters like fingerprints, retinal scans or facial recognition are used, but they are not comfortable, and they give value to body parts, which can have many disadvantages. Another common scheme is using digital signatures and public-key cryptography. An identification scheme consists essentially of two separate stages

• Initialization

  • Operation

In public-key identification schemes, during the first stage each user generates a private key and a public key. A Trusted Authority is required to ensure the link between each user and his public key. At the end of the operation stage the verifier can accept or reject the identification.

A Zero Knowledge protocol must satisfy the three conditions:

  • Completeness: If a statement is true and both parties follow the same protocol correctly, then the verifier naturally becomes convinced
  • Soundness: If statement is false, the verifier will almost certainly not be convinced (Probabilistically Checkable Proof constructions rely on repetition until probability of falsehood or plain coin flip luck approaches zero).
  • Zero-knowledge: If the statement is true, no verifier learns anything other than the fact that the statement is true.

EXAMPLE:

Let’s take a simple example to simplify the zero knowledge proof and how it works is the switching of two glasses of soda, one glass is filled with Pepsi and other with coke. Both of these glasses are identical manner in all ways, there is no way to distinguish the one that contains Pepsi other one has coke.

However one party (Prover) claims they can distinguish which glass has Pepsi and which glass has coke perfectly but without revealing their conclusions. Thus they need to prove to other party (verifier) that they know which glass contains coke without actually telling you which glass it is.

One way to do this would be to blindfold the verifier and you can then decide to switch the glasses or leave them as they were. Once the blindfold is off, ask if the glasses were switched or not. If they are able to distinguish if you switched the glasses or not then it means they know how to distinguish between the two. However, it may have been a lucky guess.

Do it multiple times and the probability of ‘guessing’ the correct position of sodas will drop to 0.5. If they still get it correct successively, then it shows that the verifier actually knows how to distinguish the two without revealing how they did it.

TYPES OF ZERO-KNOWLEDGE PROOF

  • INTERCATIVE ZERO-KNOWLEDGE PROOF: — 1ST Invention, multiple messages between Prover and Verifier.
  • NON-INTERCATIVE ZERO-KNOWLEDGE PROOF: — less interaction required between Prover and Verifier.

Data Exchange: These proofs reveal only the data that Alice wants to be revealed: in this case, the minimum balance instead of the actual one. In effect what Alice is proving is that “I, Alice, have the knowledge of my statement of balance (as of a certain date and time) signed by the bank that you, the auction house, have trust in. Using that knowledge, I prove to you that I have at least the amount you are looking for.”

Thus, ZKPs allow Alice to satisfy the wishes of a verifier (the auction house) without exposing information the details of her private life to neither the verifier or the mutually trusted source of information (the bank).

ZKP advantages:

  • Zero knowledge transfer as the name suggest
  • Computational efficiency- No Encryption
  • Based on problem like discrete logarithms and integer factorization
  • No degradation of the protocol

ZK- SNARK: Data privacy is the most important thing now days. Let’s talk about the ZK-SNARK. As the name suggest ZK stands for Zero-Knowledge and SNARK stand for “Succinct Non-Interactive Argument of Knowledge”.

Zk-SNARK is an acronym for ‘Zero-Knowledge Succinct Non-Interactive Argument of Knowledge’.

ZERO-KNOWLEDGE: if the statement is true, a verifier does not learn anything beyond the fact that the statement is true.

SUCCINT: It indicates that the zero-knowledge proof can be verified quickly. This includes proofs with statements that are large. With previous zero-knowledge protocols, the prover and the verifier had to engage in multiple rounds of communication in order to validate a proof.

NON-INTERACTIVE: It means that the verifier does not have to interact with the Prover in order to validate a zero-knowledge proof. Instead, the Prover can publish their proof in advance, and a verifier can ensure its correctness.

ARGUMENT OF KNOWLEDGE: A computationally sound proof: soundness holds against the Prover that leverages polynomial-time, i.e. bounded computation. The proof cannot be constructed without access to the witness (the private input needed to prove the statement).

ZK- SNARK TRANSACTION:

In incorporating zk-SNARKS into the Zcash blockchain, the function that determines the correctness of a transaction, in accordance with consensus rules, must return the answer of whether or not that transaction is valid, without disclosing any of the information with which it performed calculations. This is accomplished by encoding some Zcash consensus rules into zk-SNARKs themselves.

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:

  • The input values sum to the output values for each transaction.
  • The sender proves that they have the private keys of the input, which gives a user the authority to spend.
  • The private spending keys of the input are cryptographically linked to a signature that pertains to the entire transaction, in a manner in which a transaction cannot be modified by a party who did not know these private keys.

FUTURE APPLICATIONS OF ZK-SNARKS:

  • Creating shielded transactions in Zcash is only one example out of many possible applications of zk-SNARKs. Theoretically, you can use a zk-SNARK to verify any relation without disclosing inputs or leaking information.
  • Zcash’s implementation of zk-SNARKs can be added to any existing distributed ledger solution as a Zero-knowledge Security Layer for enterprise use cases.

You can also explore the various tutorials written by me on Blockchain Technology.

Coinmonks

Coinmonks is a non-profit Crypto educational publication. Follow us on Twitter @coinmonks Our other project — https://coincodecap.com

Ashish

Written by

Ashish

A passionate researcher in the field of Blockchain, Crypto and computer networks, love to read about science, always ready to learn something new

Coinmonks

Coinmonks

Coinmonks is a non-profit Crypto educational publication. Follow us on Twitter @coinmonks Our other project — https://coincodecap.com

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade