Probabilistically checkable proofs (PCPs) allow encoding a computation so that it can be quickly verified by only reading a few symbols. Inspired by tree codes (Schulman, STOC'93), we propose tree PCPs; these are PCPs that evolve as the computation progresses so that a proof for time $t$ is obtained by appending a short string to the end of an accepting proof for time $t-1$. At any given time, the tree PCP can be locally queried to verify the entire computation so far.

We construct tree PCPs for non-deterministic space-$s$ computation, where at time step $t$, the proof only grows by an additional ${poly}(s)\cdot t^\varepsilon$ bits, and the number of queries made by the verifier to the overall proof is ${poly}(s)\cdot t^\varepsilon$, for an arbitrary constant $\varepsilon>0$.

Tree PCPs are well-suited to proving correctness of ongoing computation that unfolds over time, in particular in a distributed setting where the computation is carried by mutually untrusting generations.
They may be thought of as an information-theoretic analog of the cryptographic notion of incrementally verifiable computation (Valiant, TCC'08).

To obtain tree PCPs, we present the first results establishing strong local testability and local correctability for tree codes, and construct a tree code that achieves both properties simultaneously.

Probabilistically checkable proofs (PCPs) allow encoding a computation so that it can be quickly verified by only reading a few symbols. Inspired by tree codes (Schulman, STOC'93), we propose tree PCPs; these are PCPs that evolve as the computation progresses so that a proof for time $t$ is obtained by appending a short string to the end of the proof for time $t-1$. At any given time, the tree PCP can be locally queried to verify the entire computation so far.

We construct tree PCPs for non-deterministic space-$s$ computation, where at time step $t$, the proof only grows by an additional $poly(s,\log(t))$ bits, and the number of queries made by the verifier to the overall proof is $poly(s) \cdot t^\epsilon$, for an arbitrary constant $\epsilon > 0$.

Tree PCPs are well-suited to proving correctness of ongoing computation that unfolds over time. They may be thought of as an information-theoretic analog of the cryptographic notion of incrementally verifiable computation (Valiant, TCC'08). In the random oracle model, tree PCPs can be compiled to realize a variant of incrementally verifiable computation where the prover is allowed a small number of queries to a large evolving state. This yields the first construction of (a natural variant of) IVC in the random oracle model.