https://eprint.iacr.org/2018/623.pdf

vdf.py

from Crypto.Util.number import *
from hashlib import sha256
import random

# https://eprint.iacr.org/2018/623.pdf
# vdf implementation using rsa as hidden order group

n = getPrime(512) * getPrime(512)
T = 2**20


def Hprime(bits, seed):
    return getPrime(bits, randfunc=random.Random(seed).randbytes)


def compute(n, g, l, T):
    # compute g^floor(2^t // l)
    # https://eprint.iacr.org/2018/623.pdf section 4.1 algorithm 4
    x = 1
    r = 1
    for _ in range(T):
        b = 2 * r // l
        r = 2 * r % l
        x = pow(x, 2, n) * pow(g, b, n) % n
    return x


def vdf_eval(n, g, T):
    y = g
    for _ in range(T):
        y = pow(y, 2, n)
    l = Hprime(20, str(g) + str(y))
    pi = compute(n, g, l, T)
    return y, pi


def vdf_verify(n, g, y, pi, T):
    l = Hprime(20, str(g) + str(y))
    r = pow(2, T, l)
    lhs = pow(pi, l, n) * pow(g, r, n) % n
    return lhs == y


g = 48763
y, pi = vdf_eval(n, g, T)
print(vdf_verify(n, g, y, pi, T))