Many people have popularized the idea that succinct proofs and zeroknowledge proofs are a type of moon math. In this post, our goal is to present a simple proof system that can provide an introduction and intuition to this space. Perhaps surprisingly, the only tool we will use is the Theorem that nontrivial degreeatmost$d$ polynomials over a field have at most $d$ roots.
Start with Succinctness, add Zero Knowledge later
The traditional CS educational approach typically first shows a zeroknowledge scheme related to proving 3colorability of a graph (also see MIT demo or Vipul Goyal’s notes), or proving the existence of a Hamiltonian cycle (see notes of Boaz Barak, or Sanjam Garg). A good resource to learn more is the 9th BIU Winter School on Cryptography and Zero Knowledge.
Since Colorability, Hamilonicity and Satisfiability are all NPcomplete problems, the advantage of this approach is that it immediately gives very general Zero Knowledge results via Karpbased reductions to any problem in NP.
Succinct proofs are often taught at a later phase and in connection to the PCP theorem. A good resource to learn these foundations is Alessandro Chiesa’s course on Foundations of Probabilistic Proofs.
In this post, we take a different approach whose goal is to provide a simple and selfcontained construction that can provide intuition for later constructions. We start with a seemly seemingly useless problem, one that is solvable in polynomial time, and discuss a solution in a nonstandard virtual cloud communication model. Perhaps surprisingly, we will show in later posts that this simple problem is the basis of more general results in this area.
The setting
We will assume two parties: a Prover, and a Verifier.
The Prover has an input $S=\langle s_0,\dots,s_{d1}\rangle $ which is a vector of say $d=10^{10}$ field elements (so $s_i \in \mathbb{F}_p$). It will be important to assume that $p$ is large relative to $d$ (so $p \gg d$). All the Prover wants to do is prove to the Verifier this simple boolean fact:
Is $S$ the allzero vector or not?
We will assume the only way the Prover and Verifier can interact is via a special communication channel we will call the virtual cloud:

The Prover has to commit to its input $S$ by uploading a degreeatmost$(d1)$ polynomial $g(x) = \sum_{i\in[0,d1]} s_i \prod_{j\in[0, d1], j\ne i} \frac{x  j}{i  j}$ to the virtual cloud. Note that for all $0\leq i \leq d1$ we have $g(i) = s_i$. This polynomial $g$ is the Lagrange interpolation of $S$.

The Verifier is allowed to query the virtual cloud by sending it an element $r$ and the virtual cloud responds back with $g(r)$, the evaluation of $r$ on $g$.
A nonsuccinct solution, with no error
How can the Verifier be sure that $S$ is allzero and hence $g$ is the zero (trivial) polynomial?
Observe that when $S$ is allzero then $g$ is the (trivial) zero polynomial! But if $S$ is not allzero then the fundamental theorem of arithmetic adapted to finite field polynomials says that $g$ has at most $d1$ roots. So the verifier has a simple way to distinguish: it can query $d=10^{10}$ distinct points and check if they are all zero.
This solution is not succinct as it requires the Verifier to send $d$ queries. Can the Verifier use less queries? Can the Verifier query just one point?
A succinct solution, with small error
We will now use the fact that we are working over the field $\mathbb{F}_p$ where $p\gg d$. By now, it should be quite clear how the Verifier can get a succinct proof that $S$ is allzero or not.
The Verifier chooses a uniformly random element $r \in_R \mathbb{F}_p$ and queries the virtual cloud just once with $r$:
 Clearly, if $g(r) \neq 0$, then $g$ is not the trivial polynomial, so $S$ is not allzeros.
 What if $g(r)=0$? Then, we use the Theorem that, if $g$ is nonzero, then it has at most $d1$ roots to say: If $r\in_R \mathbb{F_p}$ and $g(r)=0$, then the probability that $g$ is nonzero is at most $(d1)/p$ (where $p$ is the size of the field).
We can choose $p\gg d$, so the error probability is as low as we want. So if $g(r)=0$, then the Verifier declares that $S$ is allzero.
That’s it! This is a very succinct proof: instead of querying $d=10^{10}$ points, the Verifier can succinctly query just one (local) point and learn about a (global) property $S$ (with a small error probability).
At the core of this succinct proof is the power of randomization: by accepting a small probability of error, it is possible to prove $g(r) \neq 0$ using one query instead of $d$ queries. Quite remarkably, this mathematical fact can be boosted to much more general succeint proofs (with small error).
Adding Zero Knowledge
The Prover managed to prove that $S$ is not zero using a succinct proof. Clearly, if $g=0$ then we know everything about $S$. However, when $g\neq 0$, what if we would also want the Verifier to learn nothing about $S$ other than that it’s not allzero?
The Verifier can query for some $0 \leq i \leq d1$, receive back $g(i)=s_i$, and hence learn some $s_i \in S$, so the first thing we need to do is restrict the Verifier to query a random element $r$ that is outside of $\{0,\dots,d1\}$.
Even that may leak information, for example, for $d=2$, the vector $S$ is of size $2$ and $g$ is a degree one polynomial (such that $g(0)=s_0$ and $g(1)=s_1)$. If the Verifier queries, say $r=10$, it learns the value of $g(10)$. Since $g$ has degree 1, the Verifier has learned some linear relation between $s_0$ and $s_1$! As a concrete example, if $g(10)=1$ then the Verifier has learned that it cannot be the case that $s_0=1$ and $s_1 \neq 1$.
To make sure the adversary can learn nothing about $S$, the Prover extends its vector $S$ with one more field element $t$. Given $S$, let $S’=\langle s_0,\dots,s_{d1}, t\rangle $ be the extended vector. If $S$ is the allzero vector, then the Prover sets $t=0$. Otherwise the Prover chooses $t$ uniformly at random. So instead of the polynomial $g$ of degree $d1$, the Prover now commits to a polynomial $g’$ of degree $d$ such that for all $0\leq i \leq d1$, $g’(i)=s_i$ and $g’(d)=t$. Using an argument that is similar to the one in our secret sharing post, it can be seen that for any nonzero vector $S$, given a uniformly distributed $t$ in $\mathbb{F}_p$, the Verifier’s view, $g’(r)$, for any $r>d$, is uniformly distributed in $\mathbb{F}_p$. Hence the only information the Verifier gains from the protocol, the Verifier could have simulated locally without any interaction. So the Verifier gains no information at all.
In our example above, for $S=2$, $g’$ will now be a degree two polynomial, such that $g’(0)=s_0, g’(1)=s_1, g’(2)=t$ where $t$ is uniform. Since for any $s_0$ and $s_1$, and for any $r>2$, the distribution of $g’(r)$ is uniform, the Verifier learns nothing about $S$.
So the Verifier queries a random point $r$ uniformly in $[d+1,p1]$. If $g(r) \neq 0$ then the Verifier has a proof that $S$ is not the allzero vector. If $g(r)=0$ then the Verifier has a proof that $S$ is most likely the allzero vector. The probability of error is at most $d/(p(d+1))$ (if $S$ is not the all zerovector, then $g’$ has at most $d$ roots and the Verifier samples $r$ uniformly from $p(d+1)$ elements).
So we have shown a way for the Verifier to obtain a succinct zeroknowledge proof!
Removing the strange virtual cloud communication channel
A major complaint against this scheme is the strange communication mechanism.
 First, it required the Prover to upload the polynomial $g$. This naively seems to be a nonsucculent operation and requires some trusted cloud to store a lot of information. Luckily, we will show in a later post how cryptographic tools can implement this succinctly over a standard communication channel.
 Secondly, it required the virtual cloud to respond to a query $r$ with the value $g(r)$. This may seem to require a trusted computing cloud. Luckily again, we will show in a later post how cryptographic tools can implement this functionality over a standard communication channel.
 Finally, recall that we needed $d\ll p$. There is sometimes a challenge in forcing the Prover to use a degreeatmost$d$ polynomial and not one of higher degree. Again we will see techniques in later posts to force the Prover to use a low degree polynomial.
Acknoledgments
We thank Radu Grigore for pointing out typos and helping improve this post.
Please answer/discuss/comment/ask on Twitter.