论文标题
PCP中的分布式验证器
Distributed Verifiers in PCP
论文作者
论文摘要
传统的证明系统涉及一个由资源的验证者与功能强大（但不受信任的）供养者进行通信。分布式验证器证明系统是一个新的证明模型家族，涉及一个验证者节点网络，该网络与单个独立摊贩进行通信，该模型可以访问验证者的完整网络结构。供者的任务是说服网络图的某些全局属性的所有验证者。此外，可以给出每个验证者在计算过程中需要验证的一些输入字符串。允许验证者节点与节点交换恒定距离，并在某些计算后接受 /拒绝输入。 由于各个节点仅限于本地视图，因此可能需要与供奉献者进行通信，以证明有关节点网络图的全局属性，而该节点的网络图只有供供节点才能访问。在这个模型系统中，整个模型在且仅当每个单个节点都接受时接受输入。 分布式验证器证明系统家族中有三个模型：$ \ mathsf {lcp} $，$ \ mathsf {dip} $，以及我们提出的$ \ mathsf {dpcp} $，其基本差异来自验证者和验证者之间的通信类型。在本文中，我们将首先在$ \ mathsf {lcp} $和$ \ mathsf {dip} $ space中进行过去的工作，然后再在我们的$ \ mathsf {dpcp} $ system中显示属性和证明。
Traditional proof systems involve a resource-bounded verifier communicating with a powerful (but untrusted) prover. Distributed verifier proof systems are a new family of proof models that involve a network of verifier nodes communicating with a single independent prover that has access to the complete network structure of the verifiers. The prover is tasked with convincing all verifiers of some global property of the network graph. In addition, each individual verifier may be given some input string they will be required to verify during the course of computation. Verifier nodes are allowed to exchange messaged with nodes a constant distance away, and accept / reject the input after some computation. Because individual nodes are limited to a local view, communication with the prover is potentially necessary to prove global properties about the network graph of nodes, which only the prover has access to. In this system of models, the entire model accepts the input if and only if every individual node has accepted. There are three models in the distributed verifier proof system family: $\mathsf{LCP}$, $\mathsf{dIP}$, and our proposed $\mathsf{dPCP}$, with the fundamental difference between these coming from the type of communication established between the verifiers and the prover. In this paper, we will first go over the past work in the $\mathsf{LCP}$ and $\mathsf{dIP}$ space before showing properties and proofs in our $\mathsf{dPCP}$ system.
