How Can I Send You A Christmas Present, But For You Not To Cheat and Open It?
How Can I Send You A Christmas Present, But For You Not To Cheat and Open It? … Time-lock Puzzles and Proof of Work
So how might we make sure that someone does not open their present until Christmas Day? Well, one way is to get them to do some work to open it, and that we know it will only be done within a certain amount of time — such as with the days there are until Christmas. So, let’s look at an area called Proof of Work, and where Victor (the verifier of the work) wants Peggy (the prover of the work) to do some work for him. We have all seen the effects of Proof of Work within the Bitcoin network, but let’s see if there are better methods. The first method we will look at is hashing something multiple times— and which is a task that can normally only be done in a sequential way, so you could put away your GPUs for just now.
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.
# https://asecuritysite.com/encryption/pow?Length=10
import base64
from cryptography.fernet import Fernet
from datetime import timedelta
from time import time
from hashlib import sha256
message="hello"
keyseed = "12345"
timeout=0.5
def generate_by_time(seed, delta):
end = time() + delta.total_seconds()
h = sha256(seed.encode()).digest()
iters = 0
while time() < end:
h = sha256(h).digest()
iters += 1
return base64.urlsafe_b64encode(h), iters
def generate_by_iters(seed, iters):
h = sha256(seed.encode()).digest()
for x in range(iters):
h = 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.encode())
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 = timedelta(seconds=timeout)
t1 = time()
iters, encrypted,key = encrypt(keyseed, delta, message)
print ("\nEncryption key:\t\t",key)
print ("Encrypted value:\t",encrypted)
t2 = time()
decrypted,key = decrypt(keyseed, iters, encrypted)
t3 = 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²{^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²{^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: 580851965563854829725809206141825916677454309261703879630091472978305957048534640380745461828
7525932811499665099257674691573742312634492877501558241926510855265445655865943438821912402793071
4101937187690331388952928999846217357829744504540231133743739186730370422530668189420896715571065
0547358575154790342206849212094827367872131512046364176440501080488076457751799130665018200405365
4755677171480098164870018127440284136797039199208818583865459976018367716791615092378912189828151
3940093485238595133368707040032458961340590434288414979880228734657295401299054013238618927900089
54081042521197986890397363455472811639
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:
# https://asecuritysite.com/encryption/pow2?Length=10
import datetime
import time
import hashlib
import base64
from cryptography.fernet import Fernet
from base64 import b64decode, b64encode
import random
message="hello"
keyseed = "12345"
a = random.randint(99999,999999)
t= 8
print ("Message:\t",message)
print ("Keyseed:\t",keyseed)
p=75184456329323393981453160999168869619896388565246270326667621020749883434526629149123313289822093813309128973674541785507146180116583118006552309466590981238828120901809218798591532127897713278598850326780359769279464340716666681725354754726329143696440538687112219849324721464631600820710676683650403820541
q=77256921699294288099751913986725879141470275753142260831695319390868938092522018978912165340760059157501314281329434440243543281733706145540078343592028736575027896004544593182243130855408638162095082271337507750610446164552740816661833414846974163466111988532153163988528271485739448606877973413411116622979
n = p*q
PHI = (p-1)*(q-1)
h = hashlib.sha256(keyseed.encode()).digest()
key=base64.urlsafe_b64encode(h)
encrypted = Fernet(key).encrypt(message.encode())
print ("Key:",key)
keyval = int(b64decode(key).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()
print ("\nKey guess (int):",Key)
Keyguess = base64.urlsafe_b64encode( Key.to_bytes(32,byteorder='big'))
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
Verifiable Delay Functions
But let’s say that Victor doesn’t want to use up his computing power to do the same work as Peggy. For this we can create a proof that the work has been completed, without him doing it. For this we can use a Verifiable Delay Function (VDF) where we can prove that a given amount of work has been done by Peggy. Victor can then send the Peggy a proof value, and for her to compute a result which verifies the work has been done, without Victor needing to do the work.
VDFs were first proposed by Dan Bohen et al [4], but it was Pietrzak [1] and Wesolowski [2] who then proposed the repeated squaring function to define the workload. In this article, we will implement the Pietrzak method:
In this case, Victor would like Peggy to do is defined by a time value (T), a base (x) and a random prime number (N):
This work can only be done in a sequential way, and where Peggy cannot implement a parallel processing method to reduce the time to compute. So how does Victor prove that Peggy has done the work, without actually computing the value of y. For this, the Victor sends a challenge value of L. Peggy then computes:
This is much faster than computing the actual work that Peggy has done. The value of val then gives a quotient (q) and a remainder (r). Peggy then computes:
Peggy then sends y (the work value) and π. Victor computes:
and checks that the following is the same as the value of y that Peggy sent:
If the values are the same, Victor has proven that Peggy has computed the right value — and undertaken the work — without Victor having to compute the value that Peggy computed. Victor does know that the answer is correct, though.
The coding is [here]:
import sys
import hashlib
import libnum
def do_work(x,T,N):
for i in range(1,T):
po=pow(2,T,N)
return(pow(x,po,N))
x=3
T=8
bits=32
L=18
if (len(sys.argv)>1):
x=int(sys.argv[1])
if (len(sys.argv)>2):
T=int(sys.argv[2])
if (len(sys.argv)>3):
bits=int(sys.argv[3])
if (len(sys.argv)>4):
L=int(sys.argv[4])
if (T>100): T=100
N=libnum.generate_prime(bits)
g = hashlib.sha256(str(x).encode())
g=int.from_bytes(g.digest(), 'big')
print (f"x={x}, g={g} T={T}, N={N}")
print (f"Challenge. L={L}")
y=do_work(g,T,N)
q=pow(2,T,N)//L
r=pow(2,T,N)%L
print (f"q={q}")
print (f"r={r}")
pi=pow(g,q,N)
print (f"\nProver computes y={y}")
print (f"Prover send pi={pi} and y={y}")
r=pow(2,T,L)
ynew=(pow(pi,L,N)*pow(g,r,N))%N
print (f"\nVerifier computes r={r}")
print (f"Verifier computes y={ynew}")
if (y==ynew):
print("\nProver has done the work")
And here is a sample run [here]:
x=3, g=35293215426786447154857697798367884701614677727176325092965345248689205321678 T=8, N=2568170051
Challenge. L=18
q=14
r=4
Prover computes y=186404701
Prover send pi=1696446846 and y=186404701
Verifier computes r=4
Verifier computes y=186404701
Prover has done the work
The VDF method has been applied into areas of where consensus is required, such as in the Chai and IOTA networks. It is much more efficient and fairer on consensus nodes that the Bitcoin method defined by Satoshi Nakimoto.
Conclusions
Proof of work is one way to define a cost limit to those who might want to change something on a system. If an adversory wants to change the consesus on a transaction, we need to make sure it will be too costly to do so. If the computing resource required to ‘bully’ the rest of the network, then it will limit the chances to change the consensus. With Bitcoin, we have setup an infrastructure where the rich get richer, and where successful miners can reinvest their gains into improving their mining abilities, and, perhaps, take over the network consensus on their own.