The power of distributed verifiers in interactive proofs

Oded's comments

The most basic paradigm of proof systems presumes that the prover is more powerful than the verifier. In this work, this paradigm is interpreted by viewing a centralized system as more powerful than a distributed one.

The verifier is modeled as a network, and the underlying graph of this network plays two roles: (1) defining the communication channels between processors, and (2) being part of the input. In addition, each processor may obtain a local input, and the processors collectively verify claims (made by an external prover) regarding the graph and the collection of local inputs.

The main result is a transformation of verifier's programs for the standard interactive proof setting to programs for the distributed verifier of the current model. When reading the specific results, one should bear in mind that $n$ denotes the number of processors, and that the input length may be $n^2$ (since the input may contain a general $n$-vertex graph). Hence, some of the results are obatined by decomposing the original verifier into a sublinear (in $n^2$) module and a specific computation, applying the transformation to the former module and implementing the second module directly.

The original abstract

We explore the power of interactive proofs with a distributed verifier. In this setting, the verifier consists of n nodes and a graph G that defines their communication pattern. The prover is a single entity that communicates with all nodes by short messages. The goal is to verify that the graph G belongs to some language in a small number of rounds, and with small communication bound, i.e., the proof size.

This interactive model was introduced by Kol, Oshman and Saxena (PODC 2018) as a generalization of non-interactive distributed proofs. They demonstrated the power of interaction in this setting by constructing protocols for problems as Graph Symmetry and Graph Non-Isomorphism -- both of which require proofs of (n^2)-bits without interaction.

In this work, we provide a new general framework for distributed interactive proofs that allows one to translate standard interactive protocols (i.e., with a centralized verifier) to ones where the verifier is distributed with a proof size that depends on the computational complexity of the verification algorithm run by the centralized verifier. We show the following:

• Every (centralized) computation performed in time O(n) on a RAM can be translated into three-round distributed interactive protocol with O(log n) proof size. This implies that many graph problems for sparse graphs have succinct proofs (e.g., testing planarity).
• Every (centralized) computation implemented by either a small space or by uniform NC circuit can be translated into a distributed protocol with O(1) rounds and O(log n) bits proof size for the low space case and polylog(n) many rounds and proof size for NC.
• We show that for Graph Non-Isomorphism, one of the striking demonstrations of the power of interaction, there is a 4-round protocol with O(log n) proof size, improving upon the O(n*log n) proof size of Kol et al.
• For many problems, we show how to reduce proof size below the seemingly natural barrier of log n. By employing our RAM compiler, we get a 5-round protocol with proof size O(loglog n) for a family of problems including Fixed Automorphism, Clique and Leader Election (for the latter two problems we actually get O(1) proof size).
• Finally, we discuss how to make these proofs non-interactive arguments via random oracles.

See ECCC TR18-213.