Proofs: Classical, Probabilistic, Succinct, and ZK

In everyday language, a “proof” of a statement S is an argument which demonstrates beyond a reasonable doubt that S is true.

In classical proof theory, a “proof” of a statement S demonstrates irrefutably that S must be true if the premises of the proof are true.

In the theory of probabilistic proofs, a “proof” of a statement S is something which a computationally bounded adversary has at most a negligible probability of producing unless the statement S is true. A negligible probability is one which is small enough that it might as well be zero for whatever purposes are relevant. It is this sense of “proof,” in the sense of probabilistic proofs, which is what is meant by “proof” in the rest of this paper (where not otherwise specified).

What constitutes a proof for me may or may not constitute a proof for you, and vice versa. What I would accept as a proof depends on what I would consider to be a negligible probability. Because the notion of a probabilistic proof is relative to a definition of “negligible probability,” there is not just a singular notion of probabilistic proofs. There are at least as many notions of probabilistic proofs as there are definitions of what constitutes a negligible probability.

Classical proof systems offer certainty that if the assumptions of a proof are true, then so is the statement it is proving. Probabilistic proof systems give up this advantage of certainty relative to assumptions. Even if the assumptions of a probabilistic proof are met, and the proof is valid, the statement being proven may still be false. This could be seen as a big issue with probabilistic proofs, but it could also be seen as not a big issue.

Classical proofs only provide certainty as applied to all possible worlds; they tell us that in any world where the premises are true, the conclusion would be true. In practice, the assumptions we make to prove things about the actual world introduce a non-negligible probability that our conclusions are false. What’s more important than the negligible probability that the statement proven by a probabilistic proof is false, even when the assumptions are met, is the non-negligible probability that the assumptions involved in the proof are not met.

By the foregoing reasoning, the theory of probabilistic proofs can be taken seriously as a branch of proof theory, and probabilistic proofs can in principle be used for proving facts about the actual world, even when the most rigorous guarantees of truth are required.

Probabilistic proof systems are better than classical proof systems for some use cases, because they have properties that no classical proof systems can have without greatly limiting their generality. These desirable properties are:

• succinctness: succinct proofs can be expressed more succinctly than the underlying facts used to make the proofs; and

• zero-knowledge: having a zero-knowledge proof does not make it easier to find the facts used to make the proof, compared to just knowing that the statement it proves is true.

A classical proof system cannot be a succinct proof system. In a classical proof, all of the underlying facts that make the conclusion true must be explicitly articulated in the proof, as assumptions and/or lemmas. This means that a classical proof based on a certain set of underlying facts cannot be expressed more succinctly than those facts themselves can be expressed. In order for proof systems to be succinct, they must be probabilistic.

Probabilistic proof theory is not an alternative to classical proof theory. Classical proof theory can do things that probabilistic proof theory cannot (currently) do. For example, classical proof theory can be used to verify the correctness of a (classical or probabilistic) proof theory.

Classical proof theory deals with truth preserving inferences. In a truth preserving inference, the probability or degree of truth does not decline in the conclusion relative to the premise. The inference “from ‘A and A’, infer ‘A’” is truth preserving, because if “A and A” is true, then “A” is also true, to the same degree or with at least the same probability. When one knows that some proofs are constructed using only truth preserving inferences, then regardless of the length of the chain of inferences, one may have as much confidence in the conclusion as one did in the premises.

Classical proofs can be checked by simple computer algorithms, such as by proof assistant software packages, which are also able to help construct computer-checkable proofs. Computer proof verification makes it more viable to use very long chains of inference in proofs and be confident that no human error occurred in the checking of the proofs.

Two of the key correctness properties of just about any proof theory are:

• soundness: one cannot make a valid proof of a false conclusion; and

• completeness: whatever truth preserving inferences exist in the language can be proven.

A “valid” proof is any proof which passes the checks of the proof checker algorithm. Soundness in classical proof theory means that there cannot ever exist a valid proof of a false conclusion. Soundness in probabilistic proof theory means that there is at most a negligible probability of finding a valid proof of a false conclusion. To say that a proof theory is sound means in other words that the proofs are truth preserving; and what “truth preserving” means depends on whether we are talking about a classical proof theory or a probabilistic proof theory.

Completeness does not mean that everything true in the language can be proven. By “the language” is meant the language or the type of statements of the proof theory in question. Completeness, in proof theory, refers not to the condition that every true statement in the language can be proven, but rather the condition that every semantically valid (i.e., truth preserving) inference is syntactically valid (i.e., can be proven).