Distributed proofs are mechanisms enabling the nodes of a network
to collectively and efficiently check the correctness of Boolean
predicates on the structure of the network (e.g. having a
specific diameter), or on data structures distributed over the
nodes (e.g. a spanning tree). We consider well known mechanisms
consisting of two components: a

*prover* that assigns a

*certificate* to each node, and a distributed algorithm
called

*verifier* that is in charge of verifying the
distributed proof formed by the collection of all certificates.
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 to
establish perfect tradeoffs between the

*size of the
certificate* stored at every node, and the

*number of
rounds* of the verification protocol.