How Can I Get You To Do a Difficult Piece of Maths …

How Can I Get You To Do a Difficult Piece of Maths …

And Check You Have Complete It, Without Actually Computing It? Meet Verifiable Delay Functions

Let’s say I want you to do some work, and you show me the result. But, I don’t want to actually do the work, but still, check it. With this, we can use a difficult mathematical calculation that must be done in a certain way, and where there are no shortcuts. One way is to compute:

and where we need to compute g times g time g … for 2^T times. There is no shortcut with parallel processing. We then need to find a way for Peggy (the prover) to prove her work, and Victor (the verifier) to check the work in a simple way.

Verifiable Delay Function (VDF)

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 Wesolowski 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
# import hashlib

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=24
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
if (x>100): x=100

N=libnum.generate_prime(bits)

x=3

print (f"x={x}, T={T}, N={N}")

print (f"Challenge. L={L}")

y=do_work(x,T,N)

q=pow(2,T,N)//L

r=pow(2,T,N)%L
print (f"q={q}")
print (f"r={r}")

pi=pow(x,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(x,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, T=10, N=254965212704684994675822688735349549753
Challenge. L=116
q=8
r=96

Prover computes y=32458177501682064707796249637766588138
Prover send pi=6561 and y=32458177501682064707796249637766588138

Verifier computes r=96
Verifier computes y=32458177501682064707796249637766588138

Prover has done the work

Applications

In many areas of blockchain we need to prove that entity can perform work for us, and for this to require a given amount of computation. A VDF is a perfect way for this to happen, but for the verifier to not have to do the actual work. In this way, we have a Proof-of-Work method, and which can be used to prove that nodes are willing to invest their workload in creating a reliable consensus. IOTA is one infrastructure that is implementing VDF for their infrastructure [here][3]:

References

[1] Pietrzak, K. (2018). Simple verifiable delay functions. In 10th innovations in theoretical computer science conference (itcs 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

[2] Wesolowski, B. (2019, May). Efficient verifiable delay functions. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (pp. 379–407). Springer, Cham.

[3] Attias, V., Vigneri, L., & Dimitrov, V. (2020). Implementation study of two verifiable delay functions. Cryptology ePrint Archive.

[4] Boneh, D., Bonneau, J., Bünz, B., & Fisch, B. (2018, August). Verifiable delay functions. In Annual international cryptology conference (pp. 757–788). Springer, Cham.