Verifiable Delay Functions

A brief and gentle introduction

Introduction

Verifiable Delay Functions (VDFs henceforth) are a cryptographic primitive that allows a prover to show a verifier that a certain amount of time running a function was spent, and do it in a way that the verifier can check the result quickly.

These functions aim to provide a minimum amount of time delay on players either knowing some piece of information or participating in the protocol in some way. VDFs do this by requiring significant computation to calculate but relatively little computation to verify, and here many people may become nostalgic and think something like “this reminds me a lot of Proof of Work” and somehow they are right: VDFs and PoW share the philosophy of “hard to compute” vs. “easy to verify”, but the main difference is that PoW is a representative for proof of parallelizable work, whereas VDFs are an example of proof of sequential work.

Among the applications of VDFs we highlight:

• Securely running a lottery on a blockchain, where one uses the output of the VDF of a given block-hash to pick the winner. This could prevent miners from attempting to manipulate hashes to win the lottery.
• Adding a delay to a Proof of Stake consensus algorithm could prevent malicious miners from predicting the randomness to their benefit and becoming able to affect when they would be chosen to mine a block.
• Implementing a “proof of elapsed time” consensus protocol that doesn’t depend on trusted hardware.

We observe two facts here: the first one is that the first two applications of VDFs suggest that it is easy for attackers to see how different inputs affect the result of a pseudo-random number generator, and this idea was the main motivation for the introduction of VDFs made by Boneh, Bonneau, Bünz and Fisch. The second fact is that it is not a coincidence that the three applications are Blockchain-related.

First examples

Following the first appearance of verifiable delay functions in Boneh et al. the area experienced very intense research due to its potential applications to blockchain technology. Since then, the following techniques have been explored:

Chaining hash functions

This is the first example of a verifiable delay function and relies on chaining a hash function

Chaining hash functions take t steps even in the case of using parallel computations, but the solution lacks efficient verification as the only way to verify the result is to recompute the composition of functions. This solution appeared as a naïve VDF in Boneh’s paper, and for this reason, was called a weak VDF.

Modular square roots

The underlying idea is: given a prime number p such that p = 3 mod 4, a (canonical) square root a = sqrt(s) mod p can be computed using the formula a = s^((p+1)/4), which requires about O(log^2(p)) binary operations. On the other hand, verifying correctness only requires checking that a^2 = s, costing O(log(p)) binary operations.

Time-lock puzzles

Warning! As we will see, this construction cannot be classified as a VDF since there is not an efficient way to perform public verification without giving away the factorization of N.

Time-lock puzzles were introduced to provide encryption that can only be decrypted after a given time t. They use a classical RSA modulus N=p · q for primes p and q; the encryption key is then a = s^(2^t) mod N for some starting value s. A party knowing the value of the Euler function φ(N) can compute the value of a quickly as they can perform a reduction of the exponent e = 2^t mod φ(N). But for everyone else, the value of a is obtained by computing t sequential squaring operations.

Definitions and properties

The first three examples share some characteristics that are key for VDFs. We get a bit more technical and define a VDF as the trio of algorithms below:

• Setup takes a security parameter s and a puzzle difficulty parameter t and outputs a pair of public parameters pp = (ek, vk), where ek stands for evaluation key and vk stands for verification key. In some situations the algorithm may require a source of secret randomness, therefore it may require a trusted setup. This detail will be important when talking about hidden order groups and isogeny-based VDFs.
• Eval takes an element x in the input space X and the evaluation key to output an element y in the output space Y together with a possibly empty proof 𝜋. Essentially, Eval evaluates the VDF on input x and it is meant to be infeasible in less than t.
• Verify is a deterministic algorithm that outputs either True or False on an input of the form {vk, x, y, 𝜋}. If y is the correct output for Eval(ek, x) it will return True, or False otherwise. The algorithm may require a source of auxiliary information. This algorithm is meant to be significantly faster than Eval.

The requirements that a VDF must meet are the following:

• Correctness: here one requires that the output of honest evaluation always outputs True in the verify algorithm.
• Soundness: this property says that the probability of getting True from the verify algorithm, given a malicious output from Eval, is negligible.
• Sequentiality: honest parties can compute (y, 𝜋) = Eval(ek, x) in t sequential steps whereas no adversary using a parallel machine cannot distinguish from random in significantly fewer steps.

The above are the musts of any contender VDF, additionally one can find:

• Decodability: if there is an algorithm Dec such that it satisfies the equality Dec(Eval(ek, x)) = x. This kind of VDF appears in protocols of Proof of Replication.
• Incremental: a VDF is incremental when a single set of public parameters support different puzzle parameters. Here the number of steps to compute y is specified in 𝜋 instead of being fixed in Setup. Incremental VDFs have reduced proof sizes and may be interesting in Blockchain.

Three more constructions

Wesolowski’s VDF

In 2018, Wesolowski presented a VDF based on groups of unknown order. His work leverages the time lock puzzle above, introducing a way to publicly verify the output a = s^(2^t). Wesolowski defines an interactive protocol where, after seeing the output a, the verifier sends to the prover a random prime l < B, where B is some small bound. The prover replies with the computation of the value b = s^⌊(2^t)/l⌋; the verifier then checks the equality a = (b^l)·(s^r), where r = 2^t mod l. Since the verifier only uses public randomness, this protocol can be made non-interactive using the Fiat–Shamir heuristic. Wesolowski’s proposal requires only one group element for the proof and only two group exponentiations for the verification.

Pietrzak’s VDF

Pietrzak introduced another protocol to verify Rivest-Shamir-Wagner time-lock puzzles, based on an interactive recursive protocol, where the prover outputs a proof consisting of O(log(t)) group elements, and the verifier needs about O(log(t)) time to do the verification. The main advantage of this construction is that the prover only needs about O(sqrt(t)) group multiplications to build.

Univariate permutation polynomials

Boneh, Bonneau, Bünz and Fisch explored in their seminal paper an approach based on permutation polynomials over finite fields Fp. Their proposal is a weaker form of VDF, where a certain amount of parallelism is needed to give an advantage to the evaluator. The point of this approach is that, given a permutation polynomial of degree t, inverting such a polynomial implies computing polynomial GCDs. This operation takes O(log(p)) multiplications of dense polynomials (i.e. those polynomials which most of their coefficients are not 0) of degree O(t), and it is conjectured that it cannot be done in less than t steps on at most O(t^2) processors.

Hidden order groups

Groups of hidden order are getting attention from the research community due to their applications in time-lock puzzles, accumulators or verifiable delay functions to name a few. As one can imagine, a hidden order group is a group, from the mathematical point of view, such that it is infeasible to compute its order unless some private information about the group is revealed. The two main proposals are:

• RSA groups, which are the multiplicative group of ℤ/Nℤ for N = p · q the product of two primes. RSA groups have an important defect: they require a trusted setup when generating N or that there exists the security that nobody knows the factorization of N.
• Class groups, which are quotients of the form P(K) / I(K) where P(K) denotes the set of principal ideals of a number field K and I(K) denotes the set of fractional ideals of K. Besides the astringent definition, the key fact that one needs to have in mind is that class groups do not require a trusted setup for their generation, and this fact makes them suitable in cryptography (remember that in some settings, the Setup algorithm of a VDF might require trusted setups for their construction).

Research on class groups focused especially on a particular kind of groups, known as quadratic imaginary groups, and the required parameters to make them resistant against the Hafner-McCurley algorithm for the computation of orders of quadratic imaginary groups. Recent research by Dobson, Galbraith and Smith showed that Sutherland’s algorithm opens the door to strong attacks that force searching parameters much larger than proposed currently, making quadratic imaginary groups not that practical for cryptography.

There is another kind of class group that could replace quadratic imaginary groups since they are more efficient to compute at the same security level: we talk about Jacobians of hyperelliptic curves of genus 3. We will define a hyperelliptic curve later, for the moment it is sufficient to know that hyperelliptic curves of genus 2 or 3 provide algorithms with the same security levels when compared to elliptic curves, but using primes much smaller. And why using Jacobians? Because, in contrast to elliptic curves, the set of points of hyperelliptic curves does not form a group and, to overcome the problem, one considers the class group of 0-divisors of the hyperelliptic curves, which is the Jacobian.

Elliptic curves in VDFs

Elliptic curves play an interesting role in VDFs as they open the door to two different instantiations of VDFs: we can either work with Jacobians of genus 3 curves, as seen in the previous section or with isogenies, as we will see. We will need a few introductory concepts which imply a bit of mathematical background, for a reference see Silverman’s The Arithmetic of Elliptic Curves.

An elliptic curve over a field K is the graph of an equation of the form, below:

We will use the standard notation when talking about the set of points of an elliptic curve and will define it as the set

Here O denotes the point of infinity, which is a technical requirement needed for the good definition of the addition of points.

For the hyperelliptic case, we define them as the graph of equations of the form

where f and h are polynomials such that deg(f) = 2g + 1; deg(h) ≤ g for an integer g ≥ 1 which is called the genus of the curve. We assume that f is monic and that there are no x, y in K such that 2y + h(x) = 0 = f’(x) - yh’(x). Observe that when g = 1 one gets an elliptic curve in generalized Weierstrass form.

The set of points of an elliptic curve can be added and, when considered together with the addition, conform a group, meaning that addition is associative, commutative, every point has an opposite and there is a neutral element, which is O. A point P of an elliptic curve E has order m when adding itself m times equals O. The subgroup of points of E with order m is denoted E[m].

Let us assume now that we are in a field of characteristic p. An elliptic curve E is supersingular if E[p^r] = 0 for r a positive integer.

Finally, given two elliptic curves E1, E2, an isogeny between them is a morphism ρ : E1 → E2 such that ρ(O) = O. An example of isogeny is the multiplication-by-m map [m] : E → E that takes P to [m](P) = P + … + P where we add m terms. In our setting, it is required to know about the existence of a particular isogeny for every given isogeny ρ*. This special isogeny is called the dual isogeny of ρ.

The composition of isogenies between (supersingular) elliptic curves gives rise to a graph with interesting applications. In such a graph the nodes represent isomorphism classes of (supersingular) elliptic curves; the edges, as one may imagine, are isogenies between these curves. Below follows a classic graph of isogenies:

https://www.microsoft.com/en-us/research/blog/cryptography-quantum-computing-intersect

Isogenies represent a relatively new field in cryptography that has managed to become well-established thanks to their efficiency, the small sizes of the keys involved in the algorithms relying on them, and the potential quantum resistance of these algorithms. Isogenies started to gain visibility after the works of Charles, Goren and Lauter, who presented a collision-resistant hash function based on deterministic walks in isogeny graphs of supersingular elliptic curves like the one above.

Quantum resistance of (some) isogeny-based constructions, such as hash functions and VDFs, rely on the complexity of the computation of specific isogenies. The problem of the computation of isogenies requires, roughly speaking, to find a particular isogeny between two supersingular elliptic curves over a finite field F(p^2) of order p^2 for a prime p.

VDFs are another technique that uses the idea of forcing a user to take a walk through an isogeny graph. In their work on isogeny-based VDFs, De Feo, Mason, Petit and Sanso define a function that makes the evaluator take a random walk of length depending on the difficulty parameter t, and where the verifier makes use of pairings for fast verification. The main idea of their proposal is:

Setup:

• Choose a prime number p and a difficulty parameter t.
• Choose a supersingular elliptic curve E.
• Take a random non-backtracking walk of length t in the form of a composition isogeny ρ : E → E’.
• Compute the dual isogeny ρ*.
• Choose a point P and compute ρ(P).
• Output {ρ*, E, E’, P, ρ(P)}.

Evaluation:

• Get a random point Q in E.
• Compute ρ*(Q).

Verification:

• Use the Weil pairing to verify eP(P, ρ*(Q))=eP(ρ(P), Q).

This construction has some interesting advantages: the proof of the VDF is empty, and this translates into saving computation time, which makes it potentially suitable for Blockchain applications. Further, it is a kind of bogoff (buy one and get one for free): the construction allows creating a VDF and also a verifiable random function, which is a cryptographic function that processes inputs and produces verifiable pseudorandom outputs.

On the other hand, there are several drawbacks (it is the price for elegance): it requires a trusted setup (although some information points out that Dan Boneh is about to solve this problem), furthermore the setup time has the same magnitude of the difficulty parameter t.

There is also an “almost-a-drawback”: since the VDF makes use of pairings, it is not quantum-resistant; nevertheless, an attacker with a quantum computer would not be able to break sequentiality, meaning that she would require breaking each instance separately. The authors of the VDF call this property quantum annoyance.