论文标题
单晶可验证的验证验证验证工作
Single-Query Verifiable Proof-of-Sequential-Work
论文作者
论文摘要
我们提出了一个顺序证明工作（POSW），对于每个随机挑战，只能对随机Oracle进行单一查询进行验证。序列证明是协议的协议，可促进验证者有效地验证摊子是否依次执行了指定数量的计算数。用n表示poly（n）并行性的供奉献者表示$ω（n）$ - 顺序时间，而验证者验证o（log n） - 使用o（log log n）并行性的时间时，则使用$ω（n）$ - 顺序时间。我们提出了一个POSW，该POSW允许任何验证者，甚至没有并行性的验证者，都可以在单个挑战上使用单个顺序计算来验证。所有现有的POSW [10，5，2，6]授权供奉献者根据查询的n圈计算随机甲骨文的一系列响应。然后，供奉献者使用承诺方案（例如，默克尔根（类似）承诺）提交了此序列，在POSW中预定了这一序列。现在，验证者要求供奉献者在计算的序列中为t随机选择的检查点（称为挑战）提供一组证明。验证者从这些证据中查找了花费O（log n）查询的每一个证明的承诺。只有当验证者拥有O（log n）并行性[6]时，才能将其简化为一轮查询。我们的POSW中的验证者不需要并行性，而是对随机甲骨文使用单个查询，以验证每个t挑战的挑战。关键观察是，在先前的作品中，承诺计划本身需要O（log n）Oracle查询来验证。
We propose a proof-of-sequential-work (PoSW) that can be verified with only a single query to the random oracle for each random challenge. Proofs-of-sequential-work are protocols that facilitate a verifier to efficiently verify if a prover has executed a specified number of computations sequentially. Denoting this number of sequential computations with N , the prover with poly(N) parallelism must take $Ω(N)$-sequential time while the verifier verifies the computation in O(log N)-sequential time using upto O(log N) parallelism. We propose a PoSW that allows any verifier, even the one with no parallelism, to verify using just a single sequential computation on a single challenge. All the existing PoSWs [10, 5, 2, 6] mandate a prover to compute a sequence of responses from a random oracle against N-rounds of queries. Then the prover commits this sequence using a commitment scheme (e.g., Merkle root (like) commitment) predefined in the PoSWs. Now the verifier asks the prover to provide a set of proofs against t randomly chosen checkpoints, called challenges, in the computed sequence. The verifier finds out the commitment from each of these proofs spending O(log N) rounds of queries to the oracle. It can be reduced to a single round of queries only if the verifier owns O(log N) parallelism [6]. The verifier in our PoSW demands no parallelism but uses a single query to the random oracle in order to verify each of the t challenges. The key observation is that the commitment schemes themselves in the prior works demand O(log N ) oracle queries to verify.
