Maths & Logic for Zero-knowledge Proofs (simplified) — Part 1

A primer for understanding the mathematical insights used to build ZK.

The purpose of this series is to follow the trail of insights that led to the development of various zero-knowledge protocols. The series will focus on real-life applications and implications of these protocols.

While reading, focus on the questions posed.

Questions to answer

- What is the need for zero-knowledge proof systems? (Read 1)

- What can be called as a proof? What is the difference between a “good” or “bad” proof? (Read 2 and 3)

- Keeping in mind the limits of current computers (computing power, memory space, etc.), how can we measure if these proof systems are feasible? (Read 4)

1. Need for Zero-Knowledge

Example : Suppose you are a consulting business and you outsource your data analytics computations to a cloud computing service provider.

How can you verify that the computations were honestly performed (no dropped data, malicious input, etc.)?

What guarantees do you have on the analysis that you receive?

Zero-knowledge proofs guarantee honesty.

You can be assured that all computations were correctly performed. That there has been no malicious input. Ultimately you can blindly trust your business partners and their activities.

2. What is a Proof?

In common parlance, proof is any method for establishing the truth. Presented with a piece of fact or evidence for establishing the truth (proof), the emphasis is always on the verification process [1], i.e. how we can establish the accuracy of the proof, have the calculations for the proof been done honestly, what guarantees can we get about the proof.

The usual method for establishing the truth (creating proofs) is to take axioms (fundamental truths) and infer propositions from these axioms. If the process of inference is accurate (truth leading to other truths) and is verifiable, then the inferred propositions are also said to be true.

In terms of computers, proofs are mechanisms that can verify the authenticity and accuracy of computations (recall your cloud computing partner), i.e. verifiable computations.

3. Proof Systems

How do we measure the quality of a proof? Is it a “good/honest” proof or “bad/malicious” proof?

While verifying a proof, ensure the following 2 parameters are met:

1. Completeness : Genuine proofs must pass the verification. If a genuine proof exists, accept it.
2. Soundness : If no genuine proof exists, reject all proofs.

Before moving on, please keep in mind the following notations:

Formally, the above parameters are encoded as follows:

Source [2]

4. NP Proof Systems

To implement the above proof systems on actual computers, we also need to consider other feasibility factors besides the two parameters mentioned above. So let’s update the our list of parameters:

While verifying a proof, NP proof systems ensure these 3 parameters:

1. Completeness : If a genuine proof exists, accept it.
2. Soundness : If no genuine proof exists, reject all proofs.
3. Efficiency : Verification function should run on polynomial time (aka function is fast)

Source [2]

This ends the part 1 of this series.

Next part will explore actual examples for proof systems and how well they perform on the 3 parameters we mentioned.

Sources :

[1] Goldreich, O. (2001, January 1). Foundations of Cryptography: Basic Tools.

[2] The 9th BIU Winter School on Cryptography | BIU Cyber Center. (2018, August 5). The 9th BIU Winter School on Cryptography | BIU Cyber Center. https://cyber.biu.ac.il/event/the-9th-biu-winter-school-on-cryptography/