A Survey of Two Verifiable Delay Functions

Dan Boneh Benedikt Bünz Ben Fisch

August 22, 2018

Abstract
A verifiable delay function (VDF) is an important tool used for adding delay in decentralized
applications. This short note briefly surveys and compares two recent beautiful Verifiable Delay
Functions (VDFs), one due to Pietrzak and the other due to Wesolowski. We also provide a
new computational proof of security for one of them, and compare the complexity assumptions
needed for both schemes.

1 What is a Verifiable Delay Function?

A verifiable delay function (VDF) [12, 3] is a function f : X → Y that takes a prescribed time to
compute, even on a parallel computer. However once computed, the output can be quickly verified
by anyone. Moreover, every input x ∈ X must have a unique valid output y ∈ Y.
In more detail, a VDF that implements a function X → Y is a tuple of three algorithms:
• Setup(λ, T ) → pp is a randomized algorithm that takes a security parameter λ and a time
bound T , and outputs public parameters pp,
• Eval(pp, x) → (y, π) takes an input x ∈ X and outputs a y ∈ Y and a proof π.
• Verify(pp, x, y, π) → {accept, reject} outputs accept if y is the correct evaluation of the VDF
on input x.
If (y, π) ← F (pp, x) then Verify(pp, x, y, π) = accept, for all x ∈ X and pp output by Setup(λ, T ).
A VDF must satisfy three properties. We state these properties informally and refer to [3] for a
complete definition:
• -evaluation time: algorithm Eval(pp, x) runs in time at most (1 + )T , for all x ∈ X and
all pp output by Setup(λ, T ). We will explain how to measure run time in the next section.
• Sequentiality: a parallel algorithm A, using at most poly(λ) processors, that runs in time
less than T cannot compute the function. Specifically,
 for a random x ∈ X and pp output by
Setup(λ, T ), if (y, π) ← Eval(pp, x) then Pr A(pp, x) = y is negligible.
• Uniqueness: for an input x ∈ X , exactly one y ∈ Y will be accepted by Verify. Specif-
ically, let A be an efficient algorithm that given pp as input, outputs (x, y, π) such that
Verify(pp, x, y, π) = accept. Then P r[Eval(pp, x) 6= y] is negligible.
VDFs have many applications. They are useful for constructing a verifiable randomness beacon,
and they provide a “proof of elapsed time” for certain blockchain designs [7]. We refer to [3, Sec. 2]
for a survey of their applications.

1
2 Two Verifiable Delay Functions
A VDF is based on a computational task that cannot be sped up by parallelism. Exponentiation
in a group of unknown order is believed to have this property, and was previously used by Rivest,
Shamir, and Wagner [15] to construct a time-lock puzzle. The two recent VDF proposals, one due
to Pietrzak [14] and the other due to Wesolowski [16], similarly make use of the serial nature of
this task.
Both VDF constructions operate as follows:

• The setup algorithm Setup(λ, T ) outputs two objects:

– A finite abelian group G of unknown order – we will discuss concrete groups in Section 6;
– An efficiently computable hash function H : X → G that we model as a random oracle.

We set the public parameters pp to be pp := (G, H, T ).

• The evaluation algorithm Eval(pp, x) is defined as follows:

T)
– compute y ← H(x)(2 ∈ G by computing T squarings in G starting with H(x),
– compute the proof π as described later,
– output (y, π).

We measure running time in terms of the number of group operations in G needed to compute the
function. It is believed that computing y requires T sequential squarings in G even on a parallel
computer with poly(λ) processors, as required for sequentiality. As we will see, computing the
proof π increases the running time to (1 + )T , as needed for -evaluation time. In practice one
might set T = 230 and  = 0.01.
The remaining question is how a public verifier Verify(pp, x, y, π) can quickly check that the
T
output y is correct, namely that y = H(x)(2 ) . This is where the proposal of Pietrzak and the
proposal of Wesolowski differ. They give two different public-coin succinct arguments for proving
that the output y is correct. Thanks to the public-coin nature of these arguments they can be
made non-interactive using the Fiat-Shamir Heuristic [4, Sec. 19.6.1].

Proving correctness of the output y. To state the problem more abstractly, let us use the
following notation:

• let g := H(x) ∈ G be the base element given as input to the VDF evaluator;
T
• let h := y ∈ G be the purported output of the VDF, namely h = g (2 ) ;

• T > 0 is a publicly known quantity.

T)
The VDF evaluator needs to produce a proof that a given tuple (G, g, h, T ) satisfies h = g (2 in G.
More precisely, we need a succinct public-coin interactive argument for the language
n T
o
LEXP := (G, g, h, T ) : h = g (2 ) in G . (1)

2
2.1 Wesolowski’s succinct argument
Wesolowski [16] presents the following succinct public-coin interactive argument for the language
LEXP defined in (1). Specifically, given a tuple (G, g, h, T ) as input, the prover and verifier engage
T
in the following protocol to prove that h = g (2 ) in G. We let Primes(λ) be the set containing the
first 2λ primes, namely 2, 3, 5, 7, etc.

0. The verifier checks that g, h ∈ G and outputs reject if not,

1. The verifier sends to the prover a random prime ` sampled uniformly from Primes(λ),

2. The prover computes q, r ∈ Z such that 2T = q` + r with 0 ≤ r < `, and sends π ← g q

to the verifier.

3. The verifier computes r ← 2T mod ` and outputs accept if π ∈ G and h = π ` g r in G

We note that the protocol works equally well when the exponent 2T is an arbitrary integer e, not
necessarily a power of two. The verifier just needs a quick way to compute r := e mod `.

Non-interactive variant. When the protocol is made non-interactive using Fiat-Shamir the
prover first generates ` by using a hash function that maps the input (G, g, h, T ) to an element
of Primes(λ). The analysis will assume that this hash function is a random oracle. The prover
computes π ← g q as in step (2) above, and outputs this π ∈ G as the proof. The verifier computes `
the same way as the prover and decides to accept or reject as in step (3) above. Overall, the proof
π is a single element in G.

Verifier efficiency. The verifier needs to compute r ← 2T mod `, which only takes log2 T mul-
tiplications in Z/`. Beyond that, the verifier only computes two small exponentiations in G.

Prover efficiency. The prover needs to compute π = g q ∈ G where q = b2T /`c. Because T is
large, we cannot write out q as an explicit integer exponent. Nevertheless, we can compute π = g q
in at most 2T group operations and constant space using the long-division algorithm, where the
quotient is computed in the exponent base g.
π ← 1 ∈ G, r←1∈Z
repeat T times:
b ← b2r/`c ∈ {0, 1} and r ← (2r mod `) ∈ {0, . . . , ` − 1}
π ← π2gb ∈ G
output π // this π equals g q

The running time can be reduced to about T group operations using a windowing method where
we process k bits of 2T per iteration, for some parameter k ≥ 1, say k = 5.
In Appendix A we describe an extension that lets us speed up the computation of g q by a factor
of s using s processors. Hence, the VDF output and the proof π can be computed in total time
approximately (1 + 1s )T with s processors and space s. Wesolowski [16] shows that with space 2k
one can further speed-up the computation by a factor of k.

3
 0. The verifier checks that g, h ∈ G and outputs reject if not,

1. If T = 1 the verifier checks that h = g 2 in G, outputs accept or reject, and stops.

2. If T > 1 the prover and verifier do:

T /2
(a) The prover computes v ← g (2 ) ∈ G and sends v to the verifier. The verifier
checks that v ∈ G and outputs reject and stops, if not.
T /2 T /2
Next, the prover needs to convince the verifier that h = v (2 ) and v = g (2 ) ,
T
which proves that h = g (2 ) . Because the same exponent is used in both equali-
ties, they can be verified simultaneously by checking a random linear combination,
namely that
T /2 )
v r h = (g r v)(2 for a random r in {1, . . . , 2λ }.

The verifier and prover do so as follows.

(b) The verifier sends to the prover a random r in {1, . . . , 2λ }.
(c) Both the prover and verifier compute g1 ← g r v and h1 ← v r h in G.
(d) The prover and verifier recursively engage in an interactive proof that
(2T /2 )
(G, g1 , h1 , T /2) ∈ LEXP , namely that h1 = g1 in G.

Figure 1: Pietrzak’s succinct argument for (G, g, h, T ) ∈ LEXP

2.2 Pietrzak’s succinct argument

Pietrzak [14] presents a different succinct public-coin interactive argument for the language LEXP
defined in (1). Specifically, given a tuple (G, g, h, T ) as input, the prover and verifier engage in a
T
recursive protocol shown in Figure 1 to prove that h = g (2 ) in G. For simplicity, we assume that T
is a power of two in which case the protocol takes log2 T rounds. The protocol can be adjusted to
handle arbitrary T , including a T that is not a power of two [14].

Non-interactive variant. When the protocol is made non-interactive using Fiat-Shamir the
prover generates the challenge r in every level of the recursion by hashing the quantities (G, g, h, T, v)
at that level, and appends v to the overall proof π. Hence, the overall proof π contains log2 T ele-
ments in G.

Verifier efficiency. At every level of the recursion the verifier does two small exponentiations in
G to compute g1 and h1 for the next level. Hence, verifying the proof takes about 2 log2 T small
exponentiations in G.

Prover efficiency. The prover needs to compute the quantity v at every level of the recursion.
We let v1 , r1 be the values of v and r at the top level of the recursion, v2 , r2 the values at the next

4
level, and so on. Unwinding the recursion shows that these quantities are:
T /2 )
v1 = g (2
 T /4 r1 3T /4
(2T /4 ) T /4 )
v2 = g1 = (g r1 v1 )(2 = g (2 ) g (2 )

 T /8 r1 r2  3T /8 r1  5T /8 r2 7T /8

(2T /8 ) T /8 ) T /8 )
v3 = g2 = (g1r2 v2 )(2 = (g r1 r2 v1r2 v2 )(2 = g (2 ) g (2 )
g (2 )
g (2 )

(2T /16 ) T /16 ) 3T /16 ) 5T /16 ) 15T /16 )

v4 = g3 = a power product of eight elements g (2 , g (2 , g (2 , . . . , g (2 .

The pattern that emerges suggests an efficient way to construct the proof π. When the VDF
T (i·T /2d )
evaluator first computes the VDF output h = g (2 ) it stores 2d group elements g (2 ) for

i = 0, . . . , 2 − 1 as they are encountered along the way. Later, as it constructs the proof π, these 2d
d

stored values let it compute the group elements v1 , . . . , vd needed for the proof using a total of about
2d small exponentiations in G. The prover computes the remaining elements vd+1 , vd+2 , . . . , vlog T
from scratch by raising gd+1 , gd+2 , . . . , glog T to the appropriate exponents. This step takes a total
of T /2d multiplications in G. Hence, the total time to compute the proof is about 2d + T /2d , which
suggests that d = 21 log2 T is optimal. Hence, the VDF output and the proof π can be computed in
total time approximately (1 + √2T )T .

3 Security assumptions needed to prove soundness

To analyze security of these interactive arguments for LEXP we rely on two complexity assumptions:
the low order assumption and the adaptive root assumption. We prove security of Pietrzak’s
argument in groups where the low order assumption holds. We prove security of Wesolowski’s
argument in groups where the adaptive root assumption holds. We discuss the relation between
these assumptions in Section 4.

Notation. In what follows we use x ←R

S to denote an independent uniform random variable over
the set S, and use y ← A(x) to denote the random variable that is the output of a randomized
R

algorithm A on input x. We say that a function f : Z → R is a negligible function of λ if

|f (λ)| = o(1/λd ) for all d > 0.

3.1 Security of Pietrzak’s succinct argument

Let GGen(λ) be a randomized algorithm that outputs the description of a group G of unknown
order. The low order assumption says that it is hard to find a low order element in a random group
output by GGen(λ).
Definition 1. We say that the low order assumption holds for GGen if there is no efficient
algorithm A that takes as input the description of a group G generated by GGen(λ), and outputs
a pair (µ, d) where µd = 1 for 1 6= µ ∈ G and 1 < d < 2λ . We say that A outputs a low order
element µ in G. More precisely, the advantage
 
d λ G← R
GGen(λ),
LOadvA,GGen (λ) := Pr µ = 1, 1 6= µ ∈ G, 1 < d < 2 , :
(µ, d) ←
R
A(G)

is a negligible function of λ.

5
 The following theorem proves soundness of Pietrzak’s succinct argument using the low order
assumption. The proof is given in Section 5.

Theorem 1. Suppose the low order assumption holds for GGen. Then Pietrzak’s succinct argument
has negligible soundness error.

Concretely, let A be an algorithm that succeeds with probability  in the following task: A takes
a description of G ←R
GGen(λ) as input, outputs a tuple (G, g, h, T ) 6∈ LEXP where 1 ≤ T < 2t
is a power of two, and convinces the verifier to incorrectly accept this tuple. Then there is an
algorithm B, whose running time is about twice that of A, that breaks the low order assumption
for GGen with advantage at least 0 = (2 /t) − (/2λ ). Hence if 0 is negligible then so must be .

Necessity of the low order assumption. The low order assumption is necessary for soundness
of the protocol – if the assumption does not hold for GGen then the protocol becomes insecure.
To see why, let G ← R
GGen(λ) and let µ ∈ G be a known element of order d > 1 (i.e., low order is
broken). Let (G, g, h, T ) ∈ LEXP . Then the tuple (G, g, hµ, T ) 6∈ LEXP will be incorrectly accepted
T /2
by the verifier with probability 1/d. To do so the prover sends v ← g (2 ) µ ∈ G which causes
the tuple (G, g, hµ, T ) to be incorrectly accepted whenever the verifier chooses an r satisfying
r + 1 ≡ 2T /2 (mod d). This happens with probability 1/d, which is non-negligible when d is small.
Note that when r + 1 ≡ 2T /2 (mod d) we have that (G, g r v, v r (hµ), T /2) ∈ LEXP , which is why
the tuple (G, g, hµ, T ) is incorrectly accepted
Note that if the group G contains no low order elements other than the identity, then the low
order assumption holds unconditionally, as does soundness of Pietrzak’s succinct argument. We
discuss this further in Section 6.

3.2 Security of Wesolowski’s succinct argument

For the next assumption recall that Primes(λ) denotes the set of first 2λ positive integer primes.

Definition 2. We say that the adaptive root assumption holds for GGen if there is no efficient
adversary (A1 , A2 ) that succeeds in the following task. First, A1 outputs an element w ∈ G and
some state. Then, a random prime ` in Primes(λ) is chosen and A2 (`, state) outputs w1/` ∈ G.
More precisely, the advantage
 
G← R
GGen(λ),
 ` (w, state) ←
R
A1 (G), 
ARadv(A1 ,A2 ),GGen (λ) := Pr u = w 6
= 1 : 
 ` ← Primes(λ),
R 
u ← A2 (`, state)
R

is a negligible function of λ.

The advantage is always at least 1/|Primes(λ)|. Indeed, if the adversary (A1 , A2 ) correctly
guesses ` ∈ Primes(λ) ahead of time, then A1 would output w ← u` , for some u ∈ G, and A2 would
output this u. This is why we must choose the set Primes(λ) to be sufficiently large. The reason
we cannot choose ` uniformly in some interval, but must choose it from Primes(λ), is because a
random ` in {1, . . . , 2λ } has a reasonable chance of being a smooth integer. The adversary can then
win by having A1 output w ← uB where B is a product of small prime powers up to some bound k,

6
and having A2 output uB/` . This works whenever ` is a k-smooth integer. Choosing ` as a prime
number eliminates this attack.
The following theorem proves soundness of Wesolowski’s succinct argument using the low order
assumption. The proof is given in Section 5.

Theorem 2 (Wesolowski [16]). Suppose the adaptive root assumption holds for GGen. Then
Wesolowski’s succinct argument has negligible soundness error.

Concretely, let A be an algorithm that succeeds with probability  in the following task: A
takes G ← R
GGen(λ) as input, outputs a tuple (G, g, h, T ) 6∈ LEXP , and convinces the verifier to
incorrectly accept this tuple. Then there is an adversary (B1 , B2 ) whose combined running time
is about the same as the running time of A plus the time to compute T squarings in G. This
(B1 , B2 ) breaks the adaptive root assumption for GGen with the same advantage  that A breaks
soundness.

Necessity of the adaptive root assumption. The adaptive root assumption is necessary for
soundness of the protocol – if the assumption does not hold for GGen then the protocol becomes
insecure. To see why, let (A1 , A2 ) be an adaptive root adversary and let G ←R
GGen(λ). To break
the protocol using (A1 , A2 ) choose an arbitrary g ∈ G, fix some T , and run (w, state) ← A1 (G),
T
where w 6= 1. Let h ← g (2 ) . Now, let’s see how to convince the verifier to incorrectly accept the
tuple (G, g, wh, T ) 6∈ LEXP . The verifier outputs a random ` ∈ Primes(λ) and we need to produce
a π such that wh = π ` g r where 2T = q` + r and 0 ≤ r < `. To do so, we run A2 (`, state) to a get
u ∈ G such that u` = w. Then π := ug q is a valid proof because
T)
π ` g r = (ug q )` g r = u` g q`+r = u` g (2 = wh,

as required.

Security of the non-interactive variants. While Theorems 1 and 2 analyze the interactive
variants of the protocols, security of the non-interactive variants follows by appealing to a general
theorem that shows that a public-coin computationally sound protocol remains computationally
sound, in the random oracle model, after it is made non-interactive using the Fiat-Shamir heuristic.

4 Comparison of the two protocols

Each proof system has its own strengths and no one dominates the other. The proof system of
Wesolowski [16] produces shorter proofs (one group element versus log2 T elements) and proof
verification is faster (two exponentiations versus 2 log2 T ). However, the proof of Pietrzak [14] has
two advantages discussed below.
√
Prover efficiency. For the VDF application, Pietrzak’s prover is more efficient. It takes O( T )
group operations to construct the proof, where as for Wesolowski it takes O(T ). Both provers
parallelize well and can be sped up by a factor of s using s processors, for a moderate value of s.

7
Comparison of the assumptions. If Wesolowski’s protocol is secure then so is Pietrzak’s, but
the converse is not known to be true. The reason is that if the adaptive root assumption holds
then so must the low order assumption. In other words, adaptive root is potentially a stronger
assumption than low order.
To show that the adaptive root assumption implies the low order assumption we show the
converse – if low order is broken then so is adaptive root. Let G ←
R
GGen(λ) and let 1 6= µ ∈ G
d
be a public element satisfying µ = 1 for a known d > 1 (i.e., low order is broken). To break the
adaptive root assumption, the adversary A1 outputs µ, and when given a random prime number
−1
` ∈ Primes(λ), adversary A2 computes µ1/` as µ(` mod d) . This works as long as d is not a multiple
of `, which only happens with negligible probability.

5 Security proofs
Proof of Theorem 2. We construct an adaptive root adversary (B1 , B2 ) that uses A. When
B1 is initialized with input G, it runs A(G) and gets back (G, g, h, T ) 6∈ LEXP . Algorithm B1 then
T T
outputs w ← h/g (2 ) ∈ G, state ← (G, g, h, T, w) and exits. Note that because h 6= g (2 ) we have
that w 6= 1, as required of an adaptive root adversary.
Next, a random ` ∈ Primes(λ) is chosen and B2 (`, state) is activated. Let 2T = q` + r with
0 ≤ r < `. Algorithm B2 sends the ` it was given to A, and A outputs π ∈ G. Now, B2 outputs
u ← π/g q ∈ G and exits. If A outputs a valid proof, namely π satisfies h = π ` g r , then
T)
u` = (π/g q )` = π ` g r /g q`+r = h/g (2 = w.

Hence, (B1 , B2 ) succeeds in breaking the adaptive root assumption with the same advantage as A
succeeds in breaking soundness, as required.

Proof of Theorem 1. We use a forking argument to construct an adversary B that breaks the
low order assumption using A.
Recall that 2t is an upper bound on the value T output by A. Let A(G, r0 , . . . , rt−1 ; R) denote
an execution of A with random tape R, where r0 , . . . , rt−1 are the verifier’s challenges at each level
of the recursion. The adversary A outputs the protocol transcript which is a sequence of t + 1
tuples:
(P0 , v0 ), . . . , (Pt , vt )
where Pi = (G, gi , hi , T /2i ) is the input to the recursion at level i, and vi is the prover’s message
ri−1 ri−1
at level i. Recall that gi ← gi−1 vi−1 and hi ← vi−1 hi−1 for i = 1, . . . , t. Here we assume T = 2t ,
t
but if T < 2 then we replicate the last pair (Plog2 T , vlog2 T ) to get a full transcript of t + 1 tuples.
Next, define the following probabilistic experiment EXP:

1. choose a random tape R for A.

2. choose uniform r0 , . . . , rt−1 in {1, . . . , 2λ }.

3. run A(G, r0 , . . . , rt−1 ; R) to get (P0 , v0 ), . . . , (Pt , vt ).

4. if P0 6∈ LEXP but Pt ∈ LEXP (i.e., the verifier incorrectly accepts P0 ) then:

8
 • let j be the lowest index for which Pj 6∈ LEXP but Pj+1 ∈ LEXP .
• choose fresh uniform rj0 , . . . , rt−1
0 in {1, . . . , 2λ }.
• run A(G, r0 , . . . , rj−1 , rj0 , . . . , rt−1
0 ; R) to get (P , v ), . . . , (P , v ), (P 0 , v 0
0 0 j j
0 0
j+1 j+1 ), . . . , (Pt , vt ).
0
• if Pj+1 ∈ LEXP and rj 6= rj0 , output (gj , hj , T /2j+1 , vj , rj , rj0 ) and stop.

5. in all other cases output fail.

Let E be the event that EXP does not output fail. When
E happens we have Pj 6∈ LEXP and
0
Pj+1 , Pj+1 ∈ LEXP . Therefore, if EXP outputs g, h, T̂ , v, r, r0 we have that
2T̂ ) T̂ ) 0 T̂ ) 0
h 6= g (2 and (g r v)(2 = vr h and (g r v)(2 = v r h. (2)

Re-arranging terms of the two equalities on the right we get

 T̂
r T̂ )
 T̂
r 0 T̂
g (2 ) /v = h/v (2 and g (2 ) /v = h/v (2 ) . (3)

Dividing the left equality by the right we obtain

T̂ 0
g (2 ) /v)r−r = 1.
T̂
Hence µ := g (2 ) /v is an element of order at most 0 < |r − r0 | < 2λ in G.
2T̂ T̂ T̂
Let’s see why µ 6= 1. By (2) we have h 6= g (2 ) and therefore either h 6= v (2 ) or v 6= g (2 ) . But
T̂
then by (3) it must be that v 6= g (2 ) . Hence µ 6= 1 and µ is of order at most d := |r − r0 |.
To summarize, algorithm B runs experiment EXP, and if it does not fail, it outputs (µ, d). This
shows that when event E happens, algorithm B succeeds in breaking the low order assumption. It
remains to determine how likely is event E to happen. Fortunately this has already been worked
out in the generalized forking lemma of Bellare and Neven [1, Lemma 1]. An application of their
lemma shows that if A succeeds in fooling the verifier with probability , then event E happens
with probability at least (2 /t) − (/2λ ), as required.

6 Concrete groups
The RSA group. Let GGen be an algorithm that outputs an odd integer N with an unknown
factorization. Computing the order of the multiplicative group G := (Z/N )∗ is as hard as factor-
ing N , and therefore G can be used as a group of unknown order. However, the low order assumption
is trivially false in such groups because (−1) ∈ Z/N is an element of order two. Fortunately, this
is the only impediment and it is easily corrected by instead working in the group G+ := G/{±1}.
Elements in this group are represented as cosets {x, −x} for x ∈ G and multiplication is defined
as {x, −x} · {y, −y} = {xy, −xy}. Of course when computing in this group it suffices to represent
a coset {x, −x} by a single number, either x or −x, whichever is in the range [0, N/2). The low
order assumption is believed to hold for a group generator GGen that generates such groups.
We note that while Pietrzak [14] suggested using integers N that are a product of strong primes,
our use of the low order assumption suggests that soundness holds for more general N . Recall that a
prime number p is strong if (p−1)/2 is also a prime number. If N = p·q is a product of distinct strong
primes then the group G0 of quadratic residues in (Z/N )∗ (i.e. G0 := {z 2 : z ∈ (Z/N )∗ }) contains no

9
elements of low order other than 1. Hence, the low order assumption holds unconditionally in this
group. Pietrzak proved unconditional soundness of the protocol when used in this group G0 . By
relying on the low order assumption we are able to prove soundness even when N is not a product
of strong primes. We note that checking membership in G0 is difficult and this complicates the
protocol. Checking membership in G+ is easy so that the protocol in Figure 1 can be used as is.
The difficulty with the group (Z/N )∗ is that for best results the group generator GGen must be
trusted to not reveal the factorization of N . One can instead make GGen use public randomness
to choose a sufficiently large N so that factoring N is hard. However the resulting N must be so
large as to be impractical.

The class group of an imaginary quadratic number field. To solve the trusted setup
√
problem one can instead use the class group of the number field Q( p), where p is a negative prime
p ≡ 1 mod 4, as suggested by Wesolowski [16]. This class group has odd order and computing
its order is believed to be difficult when |p| is large. See [5] for a discussion on the choice of
cryptographic parameters for such groups. Concretely, the group generator GGen(λ) outputs a
√
negative prime p from which the class group of Q( p) is completely specified.
The Cohen-Lenstra heuristics [8] suggest that for imaginary quadratic number fields:

• the frequency of fundamental discriminants for which the odd part of the class group is cyclic
is about 97.6%,

• the frequency f (d) of fundamental discriminants for which the order of the class group is
divisible by d is approximately:

f (3) = 44%, f (5) = 24%, f (7) = 16%.

These heuristics suggest that the class group is often cyclic, but often contains elements of small
odd order. The question is how hard is it to find an element of small odd order, if one exists?

An approach to finding low order elements in class groups. The low order assumption in
the class group of an imaginary quadratic extension has not been studied much, and is a fascinating
avenue for future work. For example, can we find an element of order three if one exists?
We mention one possible avenue for attack based on the work of Ellenberg and Venkatesh [10].
√
Let I be an ideal of order 3 in the class group of Q( p). Then I 3 is principle meaning that
√
I 3 = ha + b pi for some a, b ∈ Z. Then the ideal norm N (I) satisfies N (I)3 = N (I 3 ) = a2 + |p|b2 .
Setting z = N (I) we see that the existence of an ideal of order three implies an integral point on
the surface
z 3 = a2 + |p|b2 (4)
where p
|z| ≤ |p|, |a| ≤ |p|3/4 , |b| ≤ |p|1/4 . (5)
The first inequality follows from the fact that we can take I to be a reduced ideal in the class group.
The second and third inequalities follow from the first.
If we could find an integral point (x, y, z) satisfying (5) on the surface (4), where z is not a perfect
√
square, then we will likely break the low order assumption in the class group of Q( p). We want a

10
 p
point (x, y, z) where |z| ≤ |p| is not a perfect square to ensure that z is not the norm of a principal
ideal. Fortunately for this paper, the bounds (5) are out of reach for Coppersmith’s method for
finding low-norm integral points on curves and surfaces [9]. However, perhaps Coppersmith’s
method can be tuned specifically for this family of surfaces? We leave that for future work.

7 Open problems
Post-quantum security. We conclude by pointing out that the two VDFs surveyed here are
insecure against an adversary who has access to a quantum computer – a quantum computer can
easily calculate the order of the group G using Shor’s algorithm and break the VDF. It is a wonderful
open problem to find a simple VDF that is post-quantum secure. Some of the VDFs studied in [3]
are post-quantum secure, but it would be helpful to have a simpler construction. For example,
Buterin [6] describes and implements one of the constructions from [3] using a combination of
MiMC and a STARK.

Acknowledgments
We thank Krzysztof Pietrzak and Benjamin Wesolowski for their helpful comments about this
writeup.

A A parallel algorithm to compute quotients in the exponent

T
We conclude with a brief description of how to compute π = g b2 /`c ∈ G in parallel, as needed to
speed up Wesolowski’s succinct argument. We can accelerate the prover’s time to compute π by a
factor of s using s processors. We do so by storing s group elements as the prover evaluates the
VDF. Taking s = 100 seems reasonable in practice.
So, let b := bT /(s − 1)c. As the prover computes the VDF it stores the following s group
elements as they are encountered along the way:
b 2b ) (s−1)b )
u0 = g, u1 = g (2 ) , u2 = g (2 , ..., us−1 = g (2 .

Next, our algorithm to compute π uses the following subroutine exp, which is essentially the same
as the algorithm from Section 2.1. Here 0 ≤ d < ` is an additional input parameter.
t /`c
exp(h, t, d, `): // output a = hbd2 ∈G
a ← 1 ∈ G, r ← d ∈ {0, . . . , ` − 1}
repeat t times:
q ← b2r/`c ∈ {0, 1}, r ← (2r mod `) ∈ {0, . . . , ` − 1}
a← a2 · hq ∈G
t /`c
output a // this a is equal to hbd2 ∈G
T
Using subroutine exp we can compute π = g b2 /`c ∈ G in time O(T /s) as follows. The algorithm
starts by quickly computing all the remainders needed for the s steps of long division, and then
runs these s steps in parallel.

11
 ib )
input: g, T, `, s as well as ui = g (2


∈ G for i = 0, . . . , s − 1 need s > 1, T > s(s − 2)
T /`c
output: π := g b2 ∈ G computed with s-way parallelism in time O(T /s)

b ← bT /(s − 1)c // batch size

// compute remainders by a quick sequential process

r0 ← (2(T mod b) mod `) ∈ {0, . . . , ` − 1}
for i = 1, . . . , s − 1:
ri ← 2b · ri−1 mod ` ∈ {0, . . . , ` − 1}

// compute π in parallel
(T mod b) /`c
compute π0 ← (us−1 )b2


(1) π0 ← exp us−1 , (T mod b), 1, ` // ∈G
for i = 1, . . . , s − 1:
b /`c
compute πi ← (us−1−i )bri−1 ·2


(2) πi ← exp us−1−i , b, ri−1 , ` // ∈G

output π ← s−1
Q
i=0 πi

The bulk of the work happens on lines (1) and (2), where each call to the function exp requires b
sequential squarings. The point is that all the calls to exp can be processed in parallel. The
algorithm needs enough memory to store only s group elements.

References
[1] M. Bellare and G. Neven. Multi-signatures in the plain public-key model and a general forking
lemma. In Proceedings of the 13th ACM conference on Computer and communications security,
pages 390–399. ACM, 2006.

[2] J. Benet, D. Dalrymple, and N. Greco. Proof of replication. Protocol Labs, 2017. https:
//[Link]/[Link].

[3] D. Boneh, J. Bonneau, B. Bünz, and B. Fisch. Verifiable delay functions. Cryptology ePrint
Archive, Report 2018/601, 2018. [Link]

[4] D. Boneh and V. Shoup. A graduate course in applied cryptography. Cambridge, 2018.

[5] J. Buchmann and S. Hamdy. A survey on iq cryptography. In Public-Key Cryptography and

Computational Number Theory, pages 1–15, 2001.

[6] V. Buterin. STARKs, part 3: Into the weeds, 2018. [Link]

07/21/starks_part_3.html.

[7] B. Cohen. Proofs of space and time. Blockchain Protocol Analysis and Security Engineering,
2017. [Link]

[8] H. Cohen and H. W. Lenstra. Heuristics on class groups of number fields. In Number Theory
Noordwijkerhout 1983, pages 33–62. Springer, 1984.

12
 [9] D. Coppersmith. Small solutions to polynomial equations, and low exponent rsa vulnerabilities.
Journal of Cryptology, 10(4):233–260, 1997.

[10] J. S. Ellenberg and A. Venkatesh. Reflection principles and bounds for class group torsion.
International Mathematics Research Notices, 2007, 2007.

[11] B. Fisch. Poreps: Proofs of space on useful data. Cryptology ePrint Archive, Report 2018/678,
2018. [Link]

[12] A. K. Lenstra and B. Wesolowski. Trustworthy public randomness with sloth, unicorn, and
trx. International Journal of Applied Cryptography, 3(4):330–343, 2017.

[13] S. D. Lerner. Proof of unique blockchain storage, 2014. [Link]

2014/11/03/proof-of-local-blockchain-storage/.

[14] K. Pietrzak. Simple verifiable delay functions. Cryptology ePrint Archive, Report 2018/627,
2018. [Link]

[15] R. Rivest, A. Shamir, and D. Wagner. Time-lock puzzles and timed-release crypto. 1996.

[16] B. Wesolowski. Efficient verifiable delay functions. Cryptology ePrint Archive, Report
2018/623, 2018. [Link]

13