Single-Query Verifiable Proof-of-Sequential-Work

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. 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 [6, 3, 1, 4] 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 as 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 [4]. 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. So our PoSW asks the prover to undergo an additional efficient binary operation x on the responses from the random oracle against N -rounds of queries. The cumulative result of x, represented as a map f , on all such responses serves the purpose of the commitment. The verifier verifies this cumulative result.