Time Locked Puzzles and Proof of Work

Time Locked Puzzles and Proof of Work

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:

Message:	The quick brown fox
Keyseed:	12345

Encryption key:		6CUlrN1BZPz9ytTrKHDGsbLEj20a15stop5S_0ktCMk=
Encrypted value:	gAAAAABbCdAfteG9dAUdmQgqHoY4hby9moK51-qYTRlYXpO7Ghbev6GqDFsadulgmZvgHVUv6mRwE9SRcbF2-UVnDW_KzJs7GHX9ffcZ-btIH-pKP5ubOSE=

Decyption key:		6CUlrN1BZPz9ytTrKHDGsbLEj20a15stop5S_0ktCMk=
Decrypted value:	The quick brown fox

Key time (secs):		0.25
Iterations:		76109

Time to encrypt: 0.724999904633
Time to decrypt: 0.219000101089

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

import datetime
import time
import hashlib
import base64
from cryptography.fernet import Fernet
import sys

message="hello"
keyseed = "12345"
timeout=0.5

def generate_by_time(seed, delta):
    end = time.time() + delta.total_seconds()
    h = hashlib.sha256(seed).digest()
    iters = 0

    while time.time() < end:
    	h = hashlib.sha256(h).digest()
        iters += 1

    return base64.urlsafe_b64encode(h), iters

def generate_by_iters(seed, iters):
    h = hashlib.sha256(seed).digest()
    for x in xrange(iters):
        h = hashlib.sha256(h).digest()
    return base64.urlsafe_b64encode(h)

def encrypt(keyseed, delta, message):
    key, iterations = generate_by_time(keyseed, delta)
    encrypted = Fernet(key).encrypt(message)
    return iterations, encrypted,key

def decrypt(keyseed, iterations, encrypted):
    key = generate_by_iters(keyseed, iterations)
    decrypted = Fernet(key).decrypt(encrypted)
    return decrypted,key

print "Message:\t",message
print "Keyseed:\t",keyseed

delta = datetime.timedelta(seconds=timeout)

t1 = time.time()
iters, encrypted,key = encrypt(keyseed, delta, message)
print "\nEncryption key:\t\t",key
print "Encrypted value:\t",encrypted

t2 = time.time()
decrypted,key = decrypt(keyseed, iters, encrypted)

t3 = time.time()

print "\nDecyption key:\t\t",key
print "Decrypted value:\t",decrypted

print "\nKey time (secs):\t", timeout
print "Iterations:\t\t", iters

print "\nTime to encrypt:", t2 - t1
print "Time to decrypt:", t3 - t2

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=CK−a^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)

Message:	The quick brown fox
Keyseed:	12345
Key: WZRHGrsBESr8wYFZ9sx0tPURuZgG2lmzyvWpwXPKz8U=
Keyval: 40517827634140982427891826463487354397562163067645485726320510288945209855941

Bob sends this as the puzzle
N:	5808519655638548297258092061418259166774543092617038796300914729783059570485346403807454618287525932811499665099257674691573742312634492877501558241926510855265445655865943438821912402793071410193718769033138895292899984621735782974450454023113374373918673037042253066818942089671557106505473585751547903422068492120948273678721315120463641764405010804880764577517991306650182004053654755677171480098164870018127440284136797039199208818583865459976018367716791615092378912189828151394009348523859513336870704003245896134059043428841497988022873465729540129905401323861892790008954081042521197986890397363455472811639
a:	101
t:	1
CK:	40517827634140982427891826463487354397562163067645485726320510288945209866142
Encrypted:	gAAAAABbCrlEUvLDQQX6gIiGqA81TTHzm5rD4Y6c4I5X5-qnkhGzqC8lOojkzmmy4cIJ3WXIn9aKO_5P3VY21ScNDf0wtOsTXo93-GbmwF6-_hBtyInh6g8=

Alice receives and now computes

Key guess= 40517827634140982427891826463487354397562163067645485726320510288945209855941
Decrpyted: The quick brown fox

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

t=8     0.000999927520752 seconds
t=16    0.208999872208 seconds
t=18    2.0 seconds
t=20    26.7730000019 seconds

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

import datetime
import time
import hashlib
import base64
from cryptography.fernet import Fernet
import sys
from base64 import b64decode
import struct
import random

message="hello"
keyseed = "12345"
a = random.randint(99999,999999)
t= 8

def tost(i):
  result = []
  while i:
    result.append(chr(i&0xFF))
    i >>= 8
  result.reverse()
  return ''.join(result)

print "Message:\t",message
print "Keyseed:\t",keyseed

p=75184456329323393981453160999168869619896388565246270326667621020749883434526629149123313289822093813309128973674541785507146180116583118006552309466590981238828120901809218798591532127897713278598850326780359769279464340716666681725354754726329143696440538687112219849324721464631600820710676683650403820541
q=77256921699294288099751913986725879141470275753142260831695319390868938092522018978912165340760059157501314281329434440243543281733706145540078343592028736575027896004544593182243130855408638162095082271337507750610446164552740816661833414846974163466111988532153163988528271485739448606877973413411116622979

n = p*q

PHI = (p-1)*(q-1)

h = hashlib.sha256(keyseed).digest()
key=base64.urlsafe_b64encode(h)

encrypted = Fernet(key).encrypt(message)

print "Key:",key
keyval = int(b64decode(key).encode('hex'), 16)

print "Keyval:",keyval
CK = ((keyval) + a**(2**t)) % n

print "\n\nBob sends this as the puzzle"
print "N:\t",n
print "a:\t",a
print "t:\t",t
print "CK:\t",CK
print "Encrypted:\t",encrypted

print "\n\nAlice receives and now computes"

t1 = time.time()

Key = (CK - a**(2**t)) % n
t2 = time.time()

val=tost(Key)
Keyguess = base64.urlsafe_b64encode( val)

print "\nKey guess (int):",Key
print "Key guess:",Keyguess

decrypted = Fernet(Keyguess).decrypt(encrypted)

print "Decrypted:",decrypted 
print "Time for Alice to compute:",t2-t1

#print "\n\n--------Bob's calculation---------------------"
#t1 = time.time()
#eps = (2**t) % PHI
#b =(a**eps) % n
#t2 = time.time()
#print "Bob\'s value", b
#print "Time for Bob to compute:",t2-t1

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.