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 page, we will implement the Pietrzak method. With a Verifiable Delay Function (VDF) we can prove that a given amount of work has been done by a prover (Peggy). A verifer (Victor) can then send the prover a proof value, and compute a result which verifies the work has been done, with the verifier not needing to do the work, but can still prove the work has been done. This is the interactive version (and where Victor sends Peggy a challenge). It can also be made non-interactive, and where Peggy can create her own challenge and proof [Proof of Time and Space article][VDF article].
Verifiable Delay Function (VDF)TheoryVDFs were first proposed by Dan Bohen et al [4] in 2018, but it was Pietrzak [1] and Wesolowski [2] who then proposed the repeated squaring function to define the workload. In this page, we will implement a simple version of the Wesolowski method. For this, the work the verifier (Victor) would like the prover (Peggy) to do is defined by a time value (\(T\)), a base (\(x\)) and a random prime number (\(N\)). We initially compute \(g\) from a hash of \(x\): \(g=H(x)\) This then gives us the proof of work to be completed: \(y=g^{2^{T}} \pmod N\) This work can only be done in a sequential way, and where the Peggy cannot implement a parallel processing method to reduce the time to compute. So how do the verifier proven that the prover has done the work, without actually computing the value of \(y\). For this, the Victor sends a challenge value of \(L\). Peggy then computes: \(val=\frac{2^T}{L} \pmod N\) This is much faster than computing \(y=g^{2^{T}}\). The value of \(val\) then gives a quotient (\(q\)) and a remainder (\(r\)). Peggy then computes: \(\pi=g^q \pmod N\) Peggy then sends \(y\) (the work value) and \(\pi\). Victor computes: \(r=2^T \pmod L\) and checks that the following is the same as the value of \(y\) that Peggy sent: \(y_{new}=\pi^L \times g^r \) Thus, because the hashing method used is non-invertible, Peggy cannot precompute the work (if \(x\) has a large enough range), and must rebuild the base value each time she is challenged. CodingThe coding is: 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=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") A sample is: 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 |
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 [link].
[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 [link].
[3] Attias, V., Vigneri, L., & Dimitrov, V. (2020). Implementation study of two verifiable delay functions. Cryptology ePrint Archive [link].
[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 [link].