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 $\Omega(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.
翻译:我们提出一个序列序列测试( POSW ), 只能通过对随机挑战随机的 O( log N ) 的随机质询来验证。 序列性测试是协议, 方便验证者对证明者是否连续执行一定数量的计算进行高效率的核查。 与 N 相比的序列计算次数, 与 mol( N) 平行的验证者必须使用 $\ Omega( N) 序列时间, 而核查者只能对O( log N) 随机挑战进行一次平行序列的计算。 我们提议一个 PoSW, 允许任何验证者( 即使是没有平行的验证者), 对单个挑战仅使用单次顺序计算进行核查。 所有现有的 PoSW 系统 [10、 5、 2 、 6] 都要求校验匹配随机或随机查询的序列。 然后, 验证者只能使用承诺方案( 如 Merkle room ) 向 O( orral road) 的对 O 的校验( ) 校验之前的 O 。