Why Use a Proof System?

At its core, a proof system proves that a statement is valid. For example, it can prove that a function with a certain input results in a certain output, i.e. $C(x)=y$. To check the statement, we can do it either directly by computing $C(x)$ and comparing the result to $y$, or indirectly by verifying the proof. The verifier can benefit from the second option in terms of time and space, if the time to verify the proof is faster than the time to compute the function, or the size of the proof is smaller than the input to the statement.

This property of a proof system is often referred to as succinctness, and it is exactly why proof systems have seen wide adoption in the blockchain space, where computation on-chain is much more expensive compared to off-chain computation. Using a proof system, it becomes possible to replace a large collection of computation to be executed on-chain with a proof of execution of the same collection of computations and verifying it on-chain. This way, proofs can be generated off-chain using large machines and verified on-chain with much less computation.

But there are applications of proof systems beyond just blockchains. Generally speaking, it can be used as auxiliary data to verify that the computation of an untrusted party was done correctly. For example, when we delegate computation to an untrusted server, we can ask it to provide a proof along with the computation result that the result indeed came from running a specific computation. Another example could be to ask a server running an ML model to provide proof that it ran inference on the correct model. The size of the accompanying proof and the time to verify it will be negligible compared to the cost of running the computation, but we gain the guarantee that the computation was done correctly.

Another optional feature of proof systems is zero-knowledge, which means that the proof reveals nothing about the computation other than its validity. In general, the output $y$ of the computation $C(x)=y$ will be public (i.e. revealed to the verifier), but the input $x$ will be, without loss of generality, private from the verifier. With this feature, the intermediate values computed by the prover while computing $C(x)$ will also be hidden from the verifier.