Verifiable Delay Function (VDF) using Modular Square Roots

Verifiable Delay Function (VDFs) were first proposed by Dan Bohen et al [3], but it was Pietrzak [1] and Wesolowski [2] who then proposed the repeated squaring function to define the workload. With a VDF we can prove that a given amount of work has been done by a prover (Peggy). A verifier (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.

Let’s say we want to find the solution for three square roots of 6.561. The first square root with a 81, and then next square root will be 9, and then the last square root will be 3. In the case of a VDF, we use modulo operators of a prime number. To compute the modulo square root of 6 (mod 97) we get 54, as:

54 x 54 (mod 97) = 6

Dwork and Naor [5] created a VDF using the extraction of modular square roots. Given a challenge of x (with p ≡ 3 (mod 4)), we compute y= sqrt(x) as x^{(p+1)/4} mod p. This can be efficiently verified by checking that y² = x (mod p):

The coding is [here]:

package main



import (

 "fmt"
 "math/big"
 "os"
 "strconv"
   "crypto/rand"


)


type VDF_Sqrt struct {
 p *big.Int
}

func VDF_Sqrt_Function(p *big.Int) *VDF_Sqrt {
 return &VDF_Sqrt{
  p: p,
 }
}

// Test is a quadractic residue: A^((p-1)/2) % p. If 1 then A is a quadratic residue module of a prime number
func (v *VDF_Sqrt) quadraticResidue(x *big.Int) bool {
 // p-1/2
 xx := new(big.Int).Set(x)
 t := new(big.Int).Exp(xx, new(big.Int).Div(new(big.Int).Sub(v.p, big.NewInt(1)), big.NewInt(2)), v.p)
 return t.Cmp(big.NewInt(1)) == 0
}

func (v *VDF_Sqrt) Delay(iter int64, x *big.Int) *big.Int {
 var r *big.Int
 xx := new(big.Int).Set(x)

 for i := int64(0); i < iter; i++ {
  if !v.quadraticResidue(xx) {
   xx = xx.Neg(xx).Mod(xx, v.p)
  }
  r = xx.ModSqrt(xx, v.p)
 }
 return r
}


func (v *VDF_Sqrt) Verify(t int64, x *big.Int, y *big.Int) bool {
 var r *big.Int
 y_val := new(big.Int).Set(y)

 if !v.quadraticResidue(x) {
  x = big.NewInt(0).Mod(big.NewInt(0).Neg(x), v.p)
 }
 for i := int64(0); i < t; i++ {
  r = y_val.Exp(y_val, big.NewInt(2), v.p)
 }
 return r.Cmp(x) == 0
}

func main() {

 iterations := 100
 x_v := big.NewInt(5)
 bitsize:=256


 argCount := len(os.Args[1:])

        if (argCount>0)  {bitsize,_ = strconv.Atoi(os.Args[1])}
        if (argCount>1) {iterations,_= strconv.Atoi(os.Args[2])}
        if (argCount>2)  {x_v,_ = new(big.Int).SetString(os.Args[3],0)}

 prime, _ := rand.Prime(rand.Reader, bitsize)
 for {
  // Check prime = 3 (mod 4)
  val:=new(big.Int).Mod(prime,big.NewInt(4))
  
  if val.Cmp(big.NewInt(3))==0 { break }
  fmt.Printf("Prime (mod 4): %v\n",new(big.Int).Mod(prime,big.NewInt(4)) )
  prime, _ = rand.Prime(rand.Reader, bitsize)
 }

 fmt.Printf("%d square roots of %v (mod %v)\n", iterations,x_v,prime)
 fmt.Printf("Prime (mod 4): %v\n",new(big.Int).Mod(prime,big.NewInt(4)) )

 fmt.Printf("Prime: %v\n",prime) 
 fmt.Printf("No bits: %v\n",bitsize)


 sqrt := VDF_Sqrt_Function(prime)
 root_x := sqrt.Delay(int64(iterations), x_v)

 if (root_x==nil) {
  fmt.Printf("Cannot find root. Please try again")
  os.Exit(1)
 }

 fmt.Printf("\nRoot of x: %v\n", root_x)

 res := sqrt.Verify(int64(iterations), x_v, root_x)
 if res == true {
  fmt.Printf("Verified correctly")
 }

}

A sample run is a 128-bit prime is [here]:

10 square roots of 7 (mod 286662415157270157620664686254591514227)
Prime (mod 4): 3
Prime: 286662415157270157620664686254591514227
No bits: 128

Root of x: 169846084120880095905705395580851643450
Verified correctly

and for 256-bit primes [here]:

10 square roots of 7 (mod 113401331737645442342794130471437972389231418687647818053585633385401201670371)
Prime (mod 4): 3
Prime: 113401331737645442342794130471437972389231418687647818053585633385401201670371
No bits: 256

Root of x: 62860843514182295412027738434468799979314736521225645379354585973289812696071
Verified correctly

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] 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].

[4] Dwork, C., & Naor, M. (1992, August). Pricing via processing or combatting junk mail. In Annual international cryptology conference (pp. 139–147). Berlin, Heidelberg: Springer Berlin Heidelberg.