  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.
