  Distributed proofs are mechanisms enabling the nodes of a network to
collectivity and efficiently check the correctness of Boolean predicates on the
structure of the network, or on data-structures distributed over the nodes
(e.g., spanning trees or routing tables). We consider mechanisms consisting of
two components: a \emph{prover} assigning a \emph{certificate} to each node,
and a distributed algorithm called \emph{verifier} that is in charge of
verifying the distributed proof formed by the collection of all certificates.
  In this paper, we show that many network predicates have distributed proofs
offering a high level of redundancy, explicitly or implicitly. We use this
remarkable property of distributed proofs for establishing perfect tradeoffs
between the \emph{size of the certificate} stored at every node, and the
\emph{number of rounds} of the verification protocol. If we allow every node to
communicate to distance at most $t$, one might expect that the certificate
sizes can be reduced by a multiplicative factor of at least~$t$. In trees,
cycles and grids, we show that such tradeoffs can be established for \emph{all}
network predicates, i.e., it is always possible to linearly decrease the
certificate size. In arbitrary graphs, we show that any part of the
certificates common to all nodes can be evenly redistributed among these nodes,
achieving even a better tradeoff: this common part of the certificate can be
reduced by the size of a smallest ball of radius $t$ in the network.
  In addition to these general results, we establish several upper and lower
bounds on the certificate sizes used for distributed proofs for spanning trees,
minimum-weight spanning trees, diameter, additive and multiplicative spanners,
and more, improving and generalizing previous results from the literature.
