Time Locked Puzzles and Proof of Work

Jul 29, 2018 · 5 min read

So how might we a lock down a file for a given amount of time or make sure that someone does not get their present until their birthday? Well one way is to get others to do some work, that you know will be done within a certain amount of time. If I know it will take you one hour to cut the grass in your garden, before I give you your reward, I will hope you will not be able to do it quicker than one hour.

Hashing

This method is defined here.

One method is to get the receiver to perform some work to find the encryption key. For example if we wanted to lock it down for one hour we could take a seed value, and then continually hash it for a given amount of time that we thing the recipient would required to generate the same key. This would then generate the same key, if the sender and recipient share the number of iterations of the hash used. We can then tell the receiver the seed value and the number of iterations they must use in order to compute the key, along with the encrypted message. The receiver must then compute the key and prove their work.

The method, though, is not perfect as the cost of the operation will vary with the clock speed of the processor. We will not be able to compute in parallel as the hashing operations must be done one at a time. The other side will still have a cost in the computation. The following is a sample run for a time to compute the key of 0.25 seconds:

And here is some sample code. We use SHA-256 to hash the seed.

In an extension to this, we could just define the hashed value, and let the receiver work out the number of times a seed value needs to be hashed to get the same value. In this case we search for a hashed version of the key here.

Squaring

This method is defined here.

Ron Rivest [paper] defined a puzzle which was fairly easy to compute [O(log(n))] and more difficult to solve [O(n2)]. For this we create a random value (a) and then raise it to the power of 2^t, and where t is the difficulty level.

The method, as outlined by Rivest [paper] defines the usage of a squaring process which increases the work to compute the key.

Now let’s say that Bob wants to make sure that Alice cannot open a message within a given amount of time. Initially Bob starts with two prime numbers (p) and (q) and determines (n):

n=p×q

We can also calclate PHI as:

PHI=(p−1)×(q−1)

Next we create an encryption key (K) and with a message (M) we encrypt:

Cm=Encrypt(K,M)

Next we select a random value (a) and a difficulty level (t), and compute a value of b which is added to the key (K):

CK=K+a^2{^t} (mod n)

Bob will then send {n,a,t,CK,Cm} to Alice, and get her to prove her work in order to decrypt the cipher message (Cm).

Alice then takes the values and computes the key with:

Key=CKa^2{^t} (mod n)

and which will have a workload dependent on the difficulty (t).

Bob, though, does not have the same workload at Alice, as he knows some or the original values. For him, he uses PHI to reduce the complexity:

ϵ=2^t (mod PHI)

And then the calculation of the value to find becomes:

b=a^e (mod n)

As an example, using a 3.5GHz Xeon process, we get the following timings to compute the work for Alice (with a=999):

And here is some sample code where we use SHA-256 to hash the seed:

Conclusions

Proof of work is one way to define a cost limit to those who might want to change something on a system. But, remember, work can be costly.

Written by

Written by