Graph explorer

Local Distributed Verification

In the framework of distributed network computing, it is known that, for every network predicate, each network configuration that satisfies this predicate can be proved using distributed certificates which can be verified locally. However, this requires to leak information about the identities of the nodes in the certificates, which might not be applicable in a context in which privacy is desirable. Unfortunately, it is known that if one insists on certificates independent of the node identities, then not all network predicates can be proved using distributed certificates that can be verified locally. In this paper, we prove that, for every network predicate, there is a distributed protocol satisfying the following two properties: (1) for every network configuration that is legal w.r.t. the predicate, and for any attempt by an adversary to prove the illegality of that configuration using distributed certificates, there is a locally verifiable proof that the adversary is wrong, also using distributed certificates; (2) for every network configuration that is illegal w.r.t. the predicate, there is a proof of that illegality, using distributed certificates, such that no matter the way