Explain the Evolution of Poof

To explain the term "zero knowledge proof", we first need to define "proof", "knowledge", and then we can proceed to explain what "zero knowledge" means.

To know the popular ZK-SNARK (Zero-Knowledge Succinct Non-interactive ARguments of Knowledge), the distinction between "arguments" and "proof" is also need to be elaborated.

proof system

if the part of history is too long to read, you can directly read the subtitles

The 'subtitles' are listed as follows:

  1. Ancient Greece: Proof == insight Mathematical proof is originate from ancient Greece, where the axiom and logic is found，for example, Goldbach conjecture

    Ever since Leibniz in the 17th century, people have dreamed of a mechanical way to do this automatically, rather than relying on a stroke of genius

  2. Early twentieth century: Proof == symbolic reasoning

    A symbolic system for formalizing logic is defined. The proof is the reasoning process written in the symbolic language of formal logic

    Unfortunately, Godel's proof of Godel's incompleteness theorem in 1931 and Turing's proof of the undecidability of Turing's machine stopping problem in 1936 put to rest once and for all the centuries-old illusion that no axiomatic system, however elaborate, could capture all the truth.

  3. 60s: Proof == program It is true that the use of computers can effectively help the mathematician's mind to reach more unknown spaces, but finding proof is still the most challenging work and verifying proof has to be a simple mechanical and limited work, because of the natural asymmetry.

  4. 80s: Proof == interaction Goldwasser, Micali and Rackoff [GMR85] proposed "The knowledge complexity of interactive proof systems." (交互式证明系统中的知识复杂性). GMR85 introduced the notion of interactive proofs, where the verifier verifies the correctness of a statement, by interacting with the prover and by using randomness. As was shown later by Lund, Fortnow, Karloff, Nisan, and Shamir [LFKN90, S90], interactive proofs seem to be much more powerful than standard proofs, as every language in PSPACE can be verified efficiently via an interactive proof, whereas only languages in NP can be verified efficiently via a standard proof. More specifically, [LFKN90, S90] showed that any language that can be computed in space s has an interactive proof where the verifier runs in time poly(s,n), where n is the instance size. Unfortunately, the running time of the prover in such proofs is exponential in s. (In these original works the running time was 2{O(s2)}, and this was later improved to be 2^{O(s)} by [GKR08]).

    A few years after interactive proofs were introduced, Ben-Or, Goldwasser, Kilian, and Wigderson [BGKW88] introduced the notion of multi-prover interactive proofs (MIPs). In this model, there are several provers that are proving a statement to a single polynomial time verifier, and the assumption is that these provers do not communicate with each other during the proof. [BGKW88] showed that whatever can be proved with k provers can also be proved with only two provers. Soon after the model of MIP was introduced, Fortnow, Rompel and Sipser [FRS94] noticed that MIPs can be converted into probabilistically checkable proofs (PCPs). (We note that the work of [FRS94] was done before the notion of PCPs was formally defined. However, they notice that the verifers can be replaced with an oracle, and that given this oracle, a probabilistic verifier can efficiently decide the language.)

    PCPs are proofs which can be verified by a probabilistic verifier by reading only a few bits of the proof.

    Two element have been added to the notion of proof: probabilistic and interactive. You are willing to accept that small statement with the small probability of error and the notion of interaction. So here we have interactive proof, PCPs, MIPs（can only need two provers）. However, there three approach are not practical (for cloud computation delegation). Interactive proofs can only be applied to LOG SPACE languages. In addition, the resulting proof has many rounds of interaction. PCPs requires the verifier to store the entire PCP, and in many settings the verifier is space bounded and cannot store such a long string. Using MIPs requires the existence of two clouds that do not interact with each other, and we prefer not to make such an assumption, since our starting point is that we do not trust the cloud, and hence do not trust that the clouds will not interact.

    Cryptographic assumptions empowers ZK. However, the resulting protocols are not (interactive) proofs, as they do not satisfy the usual soundness condition, but rather satisfy a weakened version: The requirement is that only computationally bounded cheating provers cannot convince the verifier of the validity of incorrect statements (whereas an all powerful adversary may be able to cheat). A protocol that satisfies such a computational soundness condition is called an interactive argument(as opposed to an interactive proof), a notion that was introduced by Brassard, Chaum and Crepeau [BCC88]. The motivation behind such a definition is the belief that in real life adversaries are not all powerful.

arguments and proofs of knowledge

From the discrete math, it can be known that an argument is a list of statements called premises followed by a statement called the conclusion. (We allow the list of premises to be empty). We say that an argument is valid if the conjunction of its premises implies its conclusion. In other words, validity means that if all the premises are true, then so is the conclusion. Validity of an argument does not guarantee the truth of its premises, so does not guarantee the truth of its conclusion. The validity of an argument only guarantees that the conclusion will be true if the premises are.

Due to the following three reasons, an alternative way of showing that an argument is valid, called a proof, is proposed

First, the truth table can get quite large. Second, checking the validity of an argument mechanically by constructing a truth table is almost completely unenlightening Lastly, while truth tables suffice to check the validity of statements in the propositional calculus, they do not work for the predicate calculus

A proof is an argument that applies one or more: sound reasoning methods.

Proofs: A proof of an argument is a list of statements, each of which is obtained from the preceding statements using one of the rules of inference T1, T2, S, C, or P. The last statement in the proof must be the conclusion of the argument.

Q: What does a proof actually have to do with the validity of an argument? A: On the one hand, a proof establishes the validity of an argument. A proof does show that an argument is valid. Every valid argument in propositional calculus has a proof. In other words, an argument is valid if and only if there is a proof of it.

zk proof vs zk argument

Zero-knowledge protocols come in several flavors, depending on how one formulates the two security conditions:

  1. the zero-knowledge condition, which says that the verifier “learns nothing” other than the fact the assertion being proven is true,

    In statistical zero knowledge, the zero-knowledge condition holds regardless of the computational resources the verifier invests into trying to learn something from the inter-action. In computational zero knowledge, we only require that a probabilistic polynomial-time verifier learn nothing from the interaction.

  2. the soundness conditions, which says that the prover cannot convince the verifier of a false assertion.

    Similarly, for soundness, we have statistical soundness, a.k.a. proof systems, where even a computationally unbounded prover cannot convince the verifier of a false statement (except with negligible probability), and computational soundness, a.k.a. argument systems [BCC88], where we only require that a polynomial-time prover cannot convince the verifier of a false statement.

It is useful to distinguish between zero-knowledge proofs, with statistical soundness, and zero-knowledge arguments with computational soundness. In general, proofs can only have computational zero-knowledge, while arguments may have perfect zero-knowledge.

In a proof, the soundness holds against a computationally unbounded prover and in an argument, the soundness only holds against a polynomially bounded prover. Arguments are thus often called "computationally sound proofs". A zero knowledge argument is just a zero knowledge proof that has computational soundness rather than statistical soundness.

It's worth noting that the terms are often used interchangeably in recent literature. Papers may still uses "proof" to mean "argument"

References

  1. 初识「零知识」与「证明」
  2. The Evolution of Proofs – Windows On Theory
  3. soundness - what is the difference between proofs and arguments of knowledge? - Cryptography Stack Exchange
  4. 6. Arguments and Proofs
  5. 《逻辑的引擎》
  6. SZKargs-focs.pdf
  7. [BCC88] Gilles Brassard, David Chaum, Claude Crépeau: Minimum Disclosure Proofs of Knowledge. J. Comput. Syst. Sci. 37(2): 156-189 (1988).
  8. Introduction to Zero Knowledge - Alon Rosen - YouTube