Proof of Sequential Work

Say you’re a researcher and you have just made a groundbreaking discovery that solves a massive problem in your field of research. Excited about the discovery, you want to share it with the world at an important conference to be held in six months. What if you don’t trust any third party to escrow your work until then? Will you simply wait and risk someone else beating you to it? You need a way to prove that you reached the solution today, in case someone else publishes the same discovery sometime between today and the day of the conference.

Proofs of sequential work (PoSW) were first introduced in [MMV13]¹. PoSW is a type of protocol that, given a time parameter T (delay), outputs a proof that allows one to prove that s/he performed a sequential work that took about T time units. This proof can be used to prove that a specific event occurred some duration of time ago. Let’s break down this term:

Proof

Given the output of the protocol (i.e., the proof) and a time parameter T, there should be an easy way to validate the output — meaning, to validate that the event indeed occurred about T time ago. The validation process should satisfy a few requirements:

• Efficiently verifiable — validating the proof should be faster than generating the proof.
• Publicly verifiable — anyone should be able to validate the proof; it shouldn’t be based on some ‘secret’ that is only known to the validator.
• Non-interactive — validating the proof shouldn’t require communication with any node.

of

Sometimes a preposition is just a preposition.

Sequential

When it comes to the time it takes to generate the proof, there should be no advantage in using parallel computing. This means basically that there are no shortcuts; generating a proof that something occurred T time units ago should roughly take… drumroll… T time units!

Work

The way to create the required delay when generating the proof, with T as the time parameter, is by doing a CPU-intensive calculation that is composed of T-repeated iterations. By setting the number of iterations, one can schedule the time that the overall calculation will take.

A common application for PoSW is a timestamping scheme, which allows one to prove that a document was created at a certain point in the past. It can be used by inventors who want to protect their inventions, like in the example above, or by financial analysts who want to be able to prove that they successfully predicted a particular trend.

In Spacemesh, we use PoSW as part of our protocol to validate that a node has allocated disk space for a certain time duration. This property allows the node to participate in “a lottery” to become eligible to add a block to the mesh. We call it PoET — Proof of Elapsed Time. The way it will be achieved is by having special purpose nodes, within the Spacemesh network, that will function as PoET service providers and will be incentivized to do the heavy lifting on behalf of the nodes. The PoET nodes will be implemented in a way that will allow the network to utilize a single sequential work execution to serve multiple nodes at the same time. Each node in the network will be able to ask any of the PoET nodes for a proof of sequential work and to use it, along with a proof of its own unique storage commitment, to prove that it has allocated storage for a certain duration of time. More details on our implementation will appear in a future article.

The original construction of PoSW, as described in [MMV13]¹, uses a special type of graph called depth-robust graph — a directed acyclic graph with N vertices with low in-degree with the property that it maintains a depth of Ω(N) even if a constant number of vertices were removed from the graph. To prove that it has done required computational work, the prover constructs labelling of the vertices of a depth-robust graph G, where each vertex v should be labeled with

where

are all vertices that have edges pointing to v. It then sends the verifier a short commitment to this labelling through a Merkle tree computed using a collision-resistant hash function. During the verification, the prover is then asked to reveal the labels of few randomly chosen vertices v along with their in-neighbors, and the verifier checks that

holds for each such vertex v. Intuitively, if the prover can pass this check for a large fraction of vertices v, due to depth-robustness of G, the labelling constructed by the prover must have a hash chain of length Ω(N), and the prover must have used time proportional to Ω(N) sequential evaluations of the hash function. This construction doesn’t follow the “Non-interactive” rule; the paper describes how to evolve this construction to a non-interactive protocol, which has been left outside the scope of this post. One issue with [MMV13]¹’s construction is that it has rather high space complexity of O(T), where T is the time period parameter, and it doesn’t scale for large T. [CP18]² proposes an improved PoSW, based on [MMV13]¹’s construction, that replaces the depth-robust graph with a graph based on a Merkle tree. In this construction the prover requires only O(log(N)) space.

For the purpose of our PoET service, we can also use a verifiable delay function (VDF), which is a relaxation of unique PoSW. In a VDF, the proof of challenge (x,T) has two parts (y,π), where y is a deterministic function of x that needs T sequential time to compute, and π is a proof that y was correctly computed. [Pie18]³ introduces a VDF that when given (N,x,T) where N is a large number for which its factorization is unknown, x is a randomly chosen challenge and T is the time parameter, the prover calculates

and π, which a group of hints that allows the verifier to validate y much faster than it takes to generate y. Calculating

is basically running T iterations of squaring the result of the previous iteration, starting with x. π is generated according to the following principle — in order to convince the verifier that

the prover first sends

to the verifier. Now

together with

imply

The only thing we have achieved at this point is to reduce the time parameter from T to

at the cost of having two statements instead just one to verify. It can be shown that the verifier can merge those two statements in a randomized way into a single statement

that satisfies

if the original statement

was true, but is almost certainly wrong (over the choice of the random exponent r if the original statement was wrong, no matter what μ the malicious prover sent. This subprotocol is repeated log(T) times — each time halving the time parameter — until the verifier can trivially verify correctness of the claim.

Stay tuned for more posts regarding our PoET service as we move forward with implementing it. If you’re eager to learn more about our PoET implementation, or even better, if you’re eager to help us build it, please drop by https://github.com/spacemeshos/go-spacemesh and say hello.

References:
1. [MMV13] Mohammad Mahmoody, Tal Moran, and Salil P. Vadhan. Publicly verifiable proofs of sequential work.
2. [CP18] Bram Cohen and Krzysztof Pietrzak. Simple proofs of sequential work.
3. [Pie18] Krzysztof Pietrzak. Simple Verifiable Delay Functions.