Share:

Zero-Knowledge Proofs: A General Understanding

Published on: Dec 15, 2021

Dec 15, 2021

Introduction

Over the years, banks became quite a crucial part of the lifestyle. They provide the best user experience possible. They have all sorts of information and it helps in smoothing the process. With Blockchain this changed drastically. While it offers immutability, transparency, and decentralization, we face another problem. If someone knows your address, they will be able to access all ledger entries. How much amount you are sending to whom. Which is not ideal. So what we need is a way to hide this data but also be able to verify that the data is not false. This is where zero-knowledge proofs come into the picture.

Goldwasser, Micali & Rackoff introduced the general concept of zero-knowledge proofs. They considered a prover proving a theorem to a verifier with probabilistic polynomial time. Zero-knowledge proofs are a powerful tool in the field of cryptography. This publication covers the general concept along with some of the well-known techniques.

Zero-Knowledge Proofs

Zero-knowledge proofs are probabilistic assessments that help in proving something without disclosing the actual information. By probabilistic assessment, it means that the revealed information doesn’t have as much certainty as simply revealing the actual answer would.

Let’s understand it a bit more clearly with examples.

For example, suppose there are 100 keys out of which one unlocks the door. Now, A can prove to B that A knows which key is the right one, without showing the key itself.

Another simple and used widely example proves to a colorblind person that two balls are of different colors without sharing the colors.

Suppose a prover wants to prove that a verifier has two balls of different colors. Now, we will assume that one ball is red and the other one is green. The verifier hides the balls behind his back. Verifier then shows the prover one ball at a time. Asks whether he swapped the ball or not. The prover sees the ball, gives an answer and then the verifier repeats the process. The prover is then telling the verifier what he already knows and not giving out any other additional information.

Now there is a chance that prover doesn’t know the answer, he may guess the answer and get it right. So the prover and verifier repeat the process multiple times, hence increasing the probability of the prover being honest. Because if the prover doesn’t know the answer, what are the chances that he’d guess it right every time? The more times the process is repeated, the more chances of prover just guessing the answer are decreased. So it provides confirmation that the prover knows the answer and is honest and is not faking it.

We make use of zero-knowledge proofs, in familiar tools like digital signatures. By signing a message, we prove that we know the private key that corresponds to a widely-known public key, but we don’t give away any information about the private key itself. As a matter of fact, public-key encryption works because it’s is zero-knowledge protocol. If signatures were to reveal information about your private keys, then bad actors may impersonate you by analyzing your signatures and recovering your private key.

A proof is zero-knowledge if it has the following 3 properties

Completeness: If the information is true, It should convince the verifier that the prover has the data.
Soundness: If the information is false, It shouldn't convince the verifier that the prover has the data.
Zero-knowledge: Except for the face that prover either has or doesn't have the information, no other information should be shared with the verifier.

While the properties sound intuitive, it took decades of research to define them.

A Zero-knowledge proof can be interactive or non-interactive. In non-interactive proofs, the proof is generated and made public. Now, anyone can check to verify it. In contrast interactive proofs, the prover and verifier exchange information back and forth to reach the decision that the prover is honest or not.

"You can define what it means to be zero-knowledge, what it means for knowledge not be leaked without defining what is knowledge"
- Alon Rosen

Types Of Zero-Knowledge Proofs

Zero-knowledge proofs may be interactive or non-interactive.

Interactive Proofs

In interactive proofs, the prover makes use of mathematical probability to convince the verifier.

Non-Interactive Proofs

In non-interactive proofs, as the name suggests, Non-interactive zero-knowledge proof does not require an interactive process. Meaning, the prover can generate all the challenges at once, and the verifier(s) can later respond. This restricts the possibility of collusion. However, it requires additional hardware or machines and software to calculate the proofs.

Why Zero-Knowledge Proofs?

ZKPs have different methods of implementation, some may be a bit complex but with time, implementations with simple cryptography come forward. Hence making ZKPs a crucial but simple concept that provides security in the form of encryption. Other than that, zero-knowledge proofs reduce the size of transactions as well.

ZK Implementations:

There are different approaches for zero-knowledge proofs. Each approach has its own value. ZK SNARKS, ZK STARKS & Bulletproofs are some of the more popular ones. We will look into these in this section.

Zero-Knowledge SNARKS Proofs:

Snarks or Succinct Non-Interactive Arguments of Knowledge are a type of proof system which uses the zero-knowledge technique.

In the early days of zero-knowledge proofs which goes back all the way to the 1980s-1990s, the proofs were massive in size. That is what sparked the need for succinctness or the S of SNARKS. ZK-SNARKS cannot be used for every or any problem. The problems need to be in a certain format and for that specific format, computation takes place. The format form is the “quadratic arithmetic problem” i.e. QAP.

For input, a corresponding solution also known as a witness can be created.

So, for ZK SNARKS a polynomial problem is first encoded in QAP i.e. t(x) u(x) = w(x) v(x), where only correct computation enables equality. The prover wants to convince the verifier that this equality holds.

Random sampling ensures succinctness i.e. t(s)u(s) = w(s)v(s), where the verifier chooses a secret s to reduce the problem from multiplying polynomials and verifying polynomial function equality to simple multiplication and equality check on numbers. This reduces both the proof size and the verification time tremendously.

A simpler explanation would be that there must exist some common parameters between prover and verifier so that they can communicate via zero-knowledge.

If the subverted prover is compromised, fake proofs can be made but since they are zero-knowledge proofs, it is undetectable.

Zero-Knowledge STARKS

STARKS or Succinct Transparent Arguments of Knowledge can be referred to as an upgrade to SNARKS. In SNARKS, if the secret s used for random sampling is compromised, then proofs can be forged. Other than that, SNARKS needs a setup as a common point between prover and verifier. It seems impossible to trust someone to sample the randomness in P2P systems. Hence SNARKS need trusted third-party setups. STARKS however removes this trusted third-party setup with a transparent setup by using Hash functions.

STARKS avoids the need for elliptic curves, hence simplifying cryptographic assumptions by relying on hashes and information theory. This makes them post-quantum secure. However, this results in an increased size of the proof. STARKS are based on PCP theorem and Fiat Shamir Heuristic & are logarithmic in size.

Bulletproofs:

Bulletproofs are non-interactive zero-knowledge proofs that require no trusted setup. However, verifying takes more time than SNARK proofs. They were essentially created to implement confidential transactions in bitcoin. Confidential transactions encrypt the amount sent in a transaction and contain cryptographic proof that the transaction is valid.

Bulletproofs are based on discrete log assumptions.

We can prove something is in a range without revealing that "something". This is the concept of Range proofs. In range proofs, I can decompose a number into some number of bits. Commit to each bit and send each commit along with the proof. The proof is that each bit is either 0 and 1. It’s a homomorphic commit so the verifier can verify. They are called linear proofs based on the Sigma protocol. But for 64bit range proofs, the proof is 4kb which is way too large for a transaction.

All three ways to implement zero-knowledge are quite popular for different reasons. To get a generic understanding of why they are different here is a table with key differences.