![\"\"](\"https:\/\/uplatz.com\/blog\/wp-content\/uploads\/2025\/10\/Verifiable-Delay-Functions-A-Comprehensive-Analysis-of-Cryptographic-Foundations-Applications-and-Deployment-Challenges-1-1024x576.jpg\")
<\/p>\n
career-path—enterprise-architect By uplatz<\/a><\/h3>\n1.1 Formal Definition: The VDF Algorithmic Triad<\/b><\/h3>\n
A VDF scheme is formally defined by a trio of algorithms that govern its lifecycle: Setup, Eval (Evaluate), and Verify. The interplay between these algorithms establishes the security and utility of the function.<\/span>5<\/span><\/p>\n\n- Setup($\\lambda, T$) $\\rightarrow$ ($ek, vk$)<\/b>: This is a probabilistic algorithm that initializes the VDF’s public parameters. It takes as input a security parameter, $\\lambda$, which determines the cryptographic strength of the scheme, and a delay parameter, $T$, which specifies the number of sequential steps required for evaluation.<\/span>5<\/span> The algorithm outputs the public parameters ($pp$), which include an evaluation key ($ek$) and a verification key ($vk$).<\/span>8<\/span> The setup phase is critical as it establishes the underlying mathematical environment, such as a group of unknown order, and defines the rules of operation. A flawed or compromised setup can undermine the entire scheme, potentially leading to predictable outputs or forgeable proofs.<\/span>10<\/span><\/li>\n
- Eval($ek, x$) $\\rightarrow$ ($y, \\pi$)<\/b>: This algorithm performs the core, time-consuming computation. It takes the evaluation key $ek$ and an input value $x$ from a defined domain $X$ and, after a significant delay, produces an output value $y$ in a range $Y$, along with a proof $\\pi$.<\/span>1<\/span> The fundamental design constraint of the Eval algorithm is that it must take at least $T$ sequential, non-parallelizable steps to complete.<\/span>5<\/span><\/li>\n
- Verify($vk, x, y, \\pi$) $\\rightarrow$ {$accept, reject$}<\/b>: This is a fast, deterministic algorithm that allows any party to confirm the correctness of an evaluation. It takes the verification key $vk$, the original input $x$, the purported output $y$, and the proof $\\pi$, and returns either accept or reject.<\/span>1<\/span> For a VDF to be practical, the verification time must be significantly shorter than the evaluation time, with some constructions achieving an exponential gap between the two.<\/span>2<\/span> This efficiency enables even resource-constrained participants, such as light clients, to validate results without re-performing the expensive computation.<\/span>12<\/span><\/li>\n<\/ul>\n
<\/p>\n
1.2 Core Properties: The Pillars of VDF Security<\/b><\/h3>\n
<\/p>\n
To be considered secure and effective, a VDF must satisfy three fundamental cryptographic properties: sequentiality, uniqueness, and efficient verifiability. These properties collectively ensure that the delay is both real and provable.<\/span>1<\/span><\/p>\n\n- Sequentiality (T-Sequentiality)<\/b>: This is the defining characteristic of a VDF. It mandates that the Eval function cannot be computed in fewer than $T$ sequential steps, even if an adversary possesses a vast number of parallel processors.<\/span>5<\/span> The computation is inherently iterative, where the input for step $N$ is derived from the output of step $N-1$, thus rendering parallelization ineffective at reducing the total wall-clock time.<\/span>7<\/span> This property is what fundamentally distinguishes VDFs from traditional Proof-of-Work systems, which are designed to be massively parallelizable.<\/span>7<\/span><\/li>\n
- Uniqueness<\/b>: For any given input $x$, there must be only one unique output $y$ that can be successfully verified.<\/span>5<\/span> This property is formally captured by the <\/span>Soundness<\/b> requirement, which guarantees that the probability of an adversary generating a valid proof $\\pi$ for an incorrect output ($y’ \\neq y$) is negligible.<\/span>1<\/span> This ensures that the VDF’s output is deterministic and cannot be manipulated by a malicious prover.<\/span><\/li>\n
- Efficient Verifiability<\/b>: This property ensures that an honestly generated output and proof can always be validated quickly and successfully. It is formally known as the <\/span>Correctness<\/b> requirement: if $(y, \\pi)$ is the result of an honest computation of Eval(ek, x), then Verify(vk, x, y, \\pi) must always output accept.<\/span>1<\/span> The verification process must be computationally inexpensive, often logarithmic in the delay parameter $T$, making it practical for broad use within a decentralized network.<\/span>5<\/span><\/li>\n<\/ul>\n
<\/p>\n
1.3 Distinguishing VDFs: A Comparative Analysis<\/b><\/h3>\n
<\/p>\n
The unique properties of VDFs become clearer when contrasted with related cryptographic primitives like Proof-of-Work and Time-Lock Puzzles.<\/span><\/p>\n\n- VDFs vs. Proof-of-Work (PoW)<\/b>: While both systems are built on the “hard to compute, easy to verify” paradigm, they differ in two fundamental ways. First is the nature of the work: PoW is a proof of <\/span>parallelizable work<\/span><\/i>, where adding more hardware directly translates to a higher probability of success, fueling a computational arms race.<\/span>7<\/span> VDFs, in contrast, are a proof of <\/span>sequential work<\/span><\/i>, where additional hardware provides no significant speedup.<\/span>7<\/span> Second is the nature of the outcome: PoW is a probabilistic game where miners search for a valid nonce, with success proportional to their hash power. A VDF is a deterministic function that produces a single, unique output for a given input.<\/span>7<\/span> This makes VDFs a tool for proving the passage of time, whereas PoW is a tool for proving the expenditure of energy.<\/span><\/li>\n
- VDFs vs. Time-Lock Puzzles (TLPs)<\/b>: TLPs, such as the original construction by Rivest, Shamir, and Wagner based on RSA, are also slow to solve and serve to encrypt information into the future.<\/span>1<\/span> However, they critically lack an efficient <\/span>public<\/span><\/i> verification mechanism.<\/span>1<\/span> Verifying the solution to a classic TLP typically requires knowledge of a secret trapdoor (e.g., the factorization of the RSA modulus $N$), which is antithetical to the needs of a trustless, decentralized system. VDFs can be viewed as a direct evolution of TLPs, augmenting them with the essential property of public verifiability, thereby transforming them from a two-party tool into a primitive suitable for multi-party, decentralized protocols.<\/span>3<\/span><\/li>\n<\/ul>\n
The introduction of VDFs marks a significant conceptual shift in how scarce resources are modeled in digital systems. PoW established a link between computational work and economic value by making energy the scarce resource that secures the network. The ability to perform parallel computation is a direct proxy for energy expenditure, and the security of a PoW chain is a function of the total energy cost required to rewrite its history.<\/span>7<\/span> VDFs introduce a new, non-energy-based digital resource: verifiably scarce sequential time. By design, an adversary cannot compress a one-hour delay into one minute simply by applying more capital in the form of parallel hardware.<\/span>7<\/span> This allows protocols to be anchored to a verifiable “waiting period” that is roughly consistent for all participants, regardless of their total computational capacity. This paradigm shift enables a new class of “resource-efficient blockchains” and protocols that are not reliant on massive energy consumption, directly addressing a primary criticism of PoW systems.<\/span>2<\/span> The security anchor transitions from a “proof of burnt energy” to a “proof of passed time.”<\/span><\/p>\n <\/p>\n
Section 2: Mathematical Foundations and Core Constructions<\/b><\/h2>\n
<\/p>\n
The theoretical properties of Verifiable Delay Functions are realized through specific mathematical structures designed to be inherently sequential. The search for such structures has led researchers to explore various areas of number theory and algebra, resulting in several distinct families of VDF constructions, each with unique trade-offs regarding security, efficiency, and trust assumptions.<\/span><\/p>\n <\/p>\n
2.1 The Role of Groups of Unknown Order<\/b><\/h3>\n
<\/p>\n
A leading approach for constructing VDFs relies on the conjectured hardness of certain problems within finite abelian groups whose order is unknown to the evaluator.<\/span>8<\/span> The most common operation used is repeated squaring. An evaluator is tasked with computing $y = x^{2^T}$ for some input $x$ and a large delay parameter $T$.<\/span>20<\/span><\/p>\nThe security of this construction hinges on the order of the group, $|G|$, being secret. If an evaluator knew $|G|$, they could use Euler’s totient theorem to drastically shortcut the computation by calculating the exponent modulo $\\phi(|G|)$ (or a related value), i.e., computing $x^{2^T \\pmod{\\phi(|G|)}}$.<\/span>8<\/span> This would instantly break the sequential delay property. Consequently, constructing groups where the order is computationally infeasible to determine without a secret trapdoor is a primary area of VDF research. Two main candidates have emerged for this purpose.<\/span><\/p>\n\n- RSA Groups<\/b>: These are the multiplicative groups of integers modulo $N$, where $N=pq$ is the product of two large, secret prime numbers, $p$ and $q$.<\/span>1<\/span> The order of the group is $\\phi(N) = (p-1)(q-1)$, which is secret as long as the factorization of $N$ is unknown. RSA groups are well-understood and have been studied extensively in cryptography.<\/span>16<\/span> However, their primary drawback in a decentralized context is the requirement of a <\/span>trusted setup<\/b>. The modulus $N$ must be generated in such a way that no single party learns its prime factors, as this knowledge would constitute a master key to bypass the VDF’s delay.<\/span>8<\/span><\/li>\n
- Class Groups<\/b>: An alternative that circumvents the trusted setup requirement is the use of class groups of imaginary quadratic number fields.<\/span>1<\/span> The key advantage of class groups is that they <\/span>do not require a trusted setup<\/b> for their generation.<\/span>8<\/span> To create such a group, one only needs to generate a large, random prime number to serve as the discriminant, a process that can be performed publicly and trustlessly.<\/span>22<\/span> This makes them an ideal candidate for decentralized applications where trust is minimized. However, group operations within class groups are generally more computationally expensive and complex to implement than those in RSA groups.<\/span>16<\/span><\/li>\n<\/ul>\n
<\/p>\n
2.2 A Comparative Study: Pietrzak vs. Wesolowski<\/b><\/h3>\n
<\/p>\n
Building upon the foundation of repeated squaring in groups of unknown order, two seminal VDF constructions were proposed independently by Krzysztof Pietrzak and Benjamin Wesolowski. Both schemes provide a mechanism to make the classic time-lock puzzle publicly verifiable, but they differ significantly in their proof mechanisms, performance characteristics, and underlying security assumptions.<\/span>4<\/span><\/p>\n\n- Wesolowski’s VDF<\/b>: This construction is celebrated for its elegance and efficiency.<\/span><\/li>\n<\/ul>\n
\n- Mechanism<\/b>: The proof is generated using an interactive challenge-response protocol that can be made non-interactive via the Fiat-Shamir heuristic. For a challenge prime $l$, the prover computes a single proof element $\\pi = g^{\\lfloor 2^T\/l \\rfloor}$. A verifier can then check the correctness of the output $y$ by confirming the equation $y = \\pi^l \\cdot g^{2^T \\pmod l}$.<\/span>1<\/span><\/li>\n
- Characteristics<\/b>: The most notable feature is its extremely compact proof, which consists of just a single group element.<\/span>4<\/span> Verification is also highly efficient, requiring only two exponentiations.<\/span>1<\/span> However, this efficiency comes at the cost of relying on a stronger and less-studied security assumption known as the “adaptive root assumption”.<\/span>20<\/span> Furthermore, the non-interactive version requires a hash-to-prime function, which can be complex and costly to implement in constrained environments like on-chain smart contracts.<\/span>24<\/span><\/li>\n<\/ul>\n
\n- Pietrzak’s VDF<\/b>: This construction uses a different approach to proving correctness.<\/span><\/li>\n<\/ul>\n
\n- Mechanism<\/b>: The proof is based on a recursive halving protocol. The prover computes intermediate values of the squaring chain (e.g., $g^{2^{T\/2}}, g^{2^{T\/4}}$, etc.) and includes them in the proof. The verifier then recursively checks the consistency of these intermediate steps.<\/span>20<\/span><\/li>\n
- Characteristics<\/b>: The proof size is larger than Wesolowski’s, growing logarithmically with the delay parameter, i.e., $O(\\log T)$ group elements.<\/span>1<\/span> The verification time is also proportional to $O(\\log T)$. A key advantage is that it relies on more standard and weaker cryptographic assumptions. Despite initial concerns about its practicality for blockchain use due to proof size, recent implementation studies have demonstrated that Pietrzak’s VDF can be verified on the Ethereum Virtual Machine (EVM) with manageable proof sizes (under 8 KB) and acceptable gas costs.<\/span>14<\/span><\/li>\n<\/ul>\n
<\/p>\n
2.3 Emerging Frontiers: Isogenies and SNARKs<\/b><\/h3>\n
<\/p>\n
Beyond groups of unknown order, researchers are exploring other mathematical avenues to construct VDFs, including isogeny-based cryptography and the use of succinct non-interactive arguments of knowledge (SNARKs).<\/span><\/p>\n\n- Isogeny-based VDFs<\/b>:<\/span><\/li>\n<\/ul>\n
\n- Mechanism<\/b>: This approach is based on the problem of computing a long chain, or “walk,” of isogenies (maps between elliptic curves) in a supersingular isogeny graph.<\/span>1<\/span> The sequential nature arises because each step of the walk (computing the next isogeny) depends on the output of the previous step.<\/span><\/li>\n
- Characteristics<\/b>: A significant advantage of this construction is the potential for an empty proof ($\\pi$ is null), as verification can be performed efficiently using the dual isogeny and the Weil pairing.<\/span>1<\/span> However, current isogeny-based VDFs still require a trusted setup.<\/span>1<\/span> They also face practical challenges related to large memory requirements for the VDF parameters, which can run into terabytes for meaningful delay periods, making them expensive to operate.<\/span>26<\/span> Furthermore, their security against quantum computers is an active area of research and debate.<\/span>27<\/span><\/li>\n<\/ul>\n
\n- SNARK-based VDFs<\/b>:<\/span><\/li>\n<\/ul>\n
\n- Mechanism<\/b>: This is a more general approach to constructing VDFs. One can start with a simple, inherently sequential computation that lacks efficient verification, such as an iterated hash function: $y = H(H(…H(x)…))$.<\/span>9<\/span> By itself, this is a “weak VDF” because the only way to verify it is to re-compute the entire chain.<\/span>1<\/span> However, by generating a SNARK or STARK proof of the correct execution of this hash chain, one can create a full-fledged VDF with fast verification.<\/span>9<\/span><\/li>\n
- Characteristics<\/b>: The primary challenge with this method is the high computational cost of generating the SNARK\/STARK proof, which can be extremely slow.<\/span>9<\/span> To address this, major research collaborations involving entities like Protocol Labs, the Ethereum Foundation, and Supranational are working to optimize SNARK-based VDFs. Their strategy involves a hybrid architecture that separates the two main tasks: the low-latency, sequential VDF evaluation is performed on optimized hardware (CPU or ASIC), while the high-throughput, parallelizable proof generation is offloaded to a many-core architecture like a GPU cluster.<\/span>18<\/span><\/li>\n<\/ul>\n
The choice of a VDF construction for any given application is a complex decision involving a careful weighing of these trade-offs. A protocol designer must consider the trust model (is a trusted setup acceptable?), the resource constraints of verifiers (how large can the proof be?), the on-chain costs (what is the verification gas cost?), and the required security assumptions. The following table provides a synthesized comparison to aid in this analysis.<\/span><\/p>\n\n\n\nVDF Construction<\/b><\/td>\n Core Mathematical Problem<\/b><\/td>\n Trusted Setup?<\/b><\/td>\n Proof Size<\/b><\/td>\n Verification Complexity<\/b><\/td>\n Key Security Assumption<\/b><\/td>\n Quantum Resistance<\/b><\/td>\n<\/tr>\n\nWesolowski<\/b><\/td>\n Repeated Squaring in Group of Unknown Order<\/span><\/td>\n Yes (RSA) or No (Class Groups)<\/span><\/td>\n Constant ($O(1)$)<\/span><\/td>\n Constant ($O(1)$)<\/span><\/td>\n Adaptive Root Assumption<\/span><\/td>\n No (if based on RSA\/Class Groups)<\/span><\/td>\n<\/tr>\n\nPietrzak<\/b><\/td>\n Repeated Squaring in Group of Unknown Order<\/span><\/td>\n Yes (RSA) or No (Class Groups)<\/span><\/td>\n Logarithmic ($O(\\log T)$)<\/span><\/td>\n Logarithmic ($O(\\log T)$)<\/span><\/td>\n Repeated Squaring Assumption<\/span><\/td>\n No (if based on RSA\/Class Groups)<\/span><\/td>\n<\/tr>\n\nIsogeny-based<\/b><\/td>\n Computing long isogeny walks<\/span><\/td>\n Yes<\/span><\/td>\n Constant ($O(1)$, often empty)<\/span><\/td>\n Constant ($O(1)$)<\/span><\/td>\n Hardness of isogeny problems<\/span><\/td>\n Potential, but actively debated<\/span><\/td>\n<\/tr>\n\nSNARK-based<\/b><\/td>\n Iterated sequential computation (e.g., hashing)<\/span><\/td>\n No (for hash-based) or Yes (for some SNARKs)<\/span><\/td>\n Constant ($O(1)$)<\/span><\/td>\n Constant ($O(1)$)<\/span><\/td>\n Security of SNARK system + Sequentiality of function<\/span><\/td>\n Yes (if using STARKs)<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n <\/p>\n
Section 3: Application I – Generating Unbiasable Public Randomness<\/b><\/h2>\n
<\/p>\n
One of the most compelling and immediate applications of Verifiable Delay Functions is the creation of secure, decentralized sources of public randomness. In distributed systems like blockchains, obtaining randomness that is unpredictable, unbiasable, and universally verifiable is a notoriously difficult problem, yet it is essential for the fair operation of many protocols, including lotteries, games, and consensus-critical validator selection.<\/span>9<\/span><\/p>\n <\/p>\n
3.1 The Randomness Beacon: Principles and Implementation<\/b><\/h3>\n
<\/p>\n
A “randomness beacon” is a service that periodically publishes a fresh, random value that any participant in a system can access and trust. VDFs provide a powerful mechanism for constructing such beacons in a trustless manner. The core principle is to combine a public source of entropy with a VDF to enforce a time delay between when the entropy is finalized and when the resulting random number is revealed.<\/span>8<\/span><\/p>\nThe process works as follows:<\/span><\/p>\n\n- Entropy Collection<\/b>: The system agrees on a source of public, high-entropy data at a specific point in time. This input, or “seed,” could be the hash of a recent block on a blockchain, a collection of stock market prices at closing, or any other publicly observable and difficult-to-predict value.<\/span>6<\/span><\/li>\n
- VDF Evaluation<\/b>: This seed is fed as the input $x$ into a VDF. An evaluator then computes $(y, \\pi) = \\text{Eval}(ek, x)$ over a predefined delay period $T$.<\/span><\/li>\n
- Randomness Publication<\/b>: Once the computation is complete, the output $y$ is published as the new random value. The accompanying proof $\\pi$ allows anyone in the network to quickly verify that $y$ is the correct and unique output corresponding to the initial seed.<\/span><\/li>\n<\/ol>\n
The enforced delay is the key to security. By the time the VDF computation finishes and the random number $y$ is known, the input seed $x$ is long past, finalized, and can no longer be influenced by any actor trying to manipulate the outcome.<\/span>
- \n
- Setup($\\lambda, T$) $\\rightarrow$ ($ek, vk$)<\/b>: This is a probabilistic algorithm that initializes the VDF’s public parameters. It takes as input a security parameter, $\\lambda$, which determines the cryptographic strength of the scheme, and a delay parameter, $T$, which specifies the number of sequential steps required for evaluation.<\/span>5<\/span> The algorithm outputs the public parameters ($pp$), which include an evaluation key ($ek$) and a verification key ($vk$).<\/span>8<\/span> The setup phase is critical as it establishes the underlying mathematical environment, such as a group of unknown order, and defines the rules of operation. A flawed or compromised setup can undermine the entire scheme, potentially leading to predictable outputs or forgeable proofs.<\/span>10<\/span><\/li>\n
- Eval($ek, x$) $\\rightarrow$ ($y, \\pi$)<\/b>: This algorithm performs the core, time-consuming computation. It takes the evaluation key $ek$ and an input value $x$ from a defined domain $X$ and, after a significant delay, produces an output value $y$ in a range $Y$, along with a proof $\\pi$.<\/span>1<\/span> The fundamental design constraint of the Eval algorithm is that it must take at least $T$ sequential, non-parallelizable steps to complete.<\/span>5<\/span><\/li>\n
- Verify($vk, x, y, \\pi$) $\\rightarrow$ {$accept, reject$}<\/b>: This is a fast, deterministic algorithm that allows any party to confirm the correctness of an evaluation. It takes the verification key $vk$, the original input $x$, the purported output $y$, and the proof $\\pi$, and returns either accept or reject.<\/span>1<\/span> For a VDF to be practical, the verification time must be significantly shorter than the evaluation time, with some constructions achieving an exponential gap between the two.<\/span>2<\/span> This efficiency enables even resource-constrained participants, such as light clients, to validate results without re-performing the expensive computation.<\/span>12<\/span><\/li>\n<\/ul>\n
<\/p>\n
1.2 Core Properties: The Pillars of VDF Security<\/b><\/h3>\n
<\/p>\n
To be considered secure and effective, a VDF must satisfy three fundamental cryptographic properties: sequentiality, uniqueness, and efficient verifiability. These properties collectively ensure that the delay is both real and provable.<\/span>1<\/span><\/p>\n
- \n
- Sequentiality (T-Sequentiality)<\/b>: This is the defining characteristic of a VDF. It mandates that the Eval function cannot be computed in fewer than $T$ sequential steps, even if an adversary possesses a vast number of parallel processors.<\/span>5<\/span> The computation is inherently iterative, where the input for step $N$ is derived from the output of step $N-1$, thus rendering parallelization ineffective at reducing the total wall-clock time.<\/span>7<\/span> This property is what fundamentally distinguishes VDFs from traditional Proof-of-Work systems, which are designed to be massively parallelizable.<\/span>7<\/span><\/li>\n
- Uniqueness<\/b>: For any given input $x$, there must be only one unique output $y$ that can be successfully verified.<\/span>5<\/span> This property is formally captured by the <\/span>Soundness<\/b> requirement, which guarantees that the probability of an adversary generating a valid proof $\\pi$ for an incorrect output ($y’ \\neq y$) is negligible.<\/span>1<\/span> This ensures that the VDF’s output is deterministic and cannot be manipulated by a malicious prover.<\/span><\/li>\n
- Efficient Verifiability<\/b>: This property ensures that an honestly generated output and proof can always be validated quickly and successfully. It is formally known as the <\/span>Correctness<\/b> requirement: if $(y, \\pi)$ is the result of an honest computation of Eval(ek, x), then Verify(vk, x, y, \\pi) must always output accept.<\/span>1<\/span> The verification process must be computationally inexpensive, often logarithmic in the delay parameter $T$, making it practical for broad use within a decentralized network.<\/span>5<\/span><\/li>\n<\/ul>\n
<\/p>\n
1.3 Distinguishing VDFs: A Comparative Analysis<\/b><\/h3>\n
<\/p>\n
The unique properties of VDFs become clearer when contrasted with related cryptographic primitives like Proof-of-Work and Time-Lock Puzzles.<\/span><\/p>\n
- \n
- VDFs vs. Proof-of-Work (PoW)<\/b>: While both systems are built on the “hard to compute, easy to verify” paradigm, they differ in two fundamental ways. First is the nature of the work: PoW is a proof of <\/span>parallelizable work<\/span><\/i>, where adding more hardware directly translates to a higher probability of success, fueling a computational arms race.<\/span>7<\/span> VDFs, in contrast, are a proof of <\/span>sequential work<\/span><\/i>, where additional hardware provides no significant speedup.<\/span>7<\/span> Second is the nature of the outcome: PoW is a probabilistic game where miners search for a valid nonce, with success proportional to their hash power. A VDF is a deterministic function that produces a single, unique output for a given input.<\/span>7<\/span> This makes VDFs a tool for proving the passage of time, whereas PoW is a tool for proving the expenditure of energy.<\/span><\/li>\n
- VDFs vs. Time-Lock Puzzles (TLPs)<\/b>: TLPs, such as the original construction by Rivest, Shamir, and Wagner based on RSA, are also slow to solve and serve to encrypt information into the future.<\/span>1<\/span> However, they critically lack an efficient <\/span>public<\/span><\/i> verification mechanism.<\/span>1<\/span> Verifying the solution to a classic TLP typically requires knowledge of a secret trapdoor (e.g., the factorization of the RSA modulus $N$), which is antithetical to the needs of a trustless, decentralized system. VDFs can be viewed as a direct evolution of TLPs, augmenting them with the essential property of public verifiability, thereby transforming them from a two-party tool into a primitive suitable for multi-party, decentralized protocols.<\/span>3<\/span><\/li>\n<\/ul>\n
The introduction of VDFs marks a significant conceptual shift in how scarce resources are modeled in digital systems. PoW established a link between computational work and economic value by making energy the scarce resource that secures the network. The ability to perform parallel computation is a direct proxy for energy expenditure, and the security of a PoW chain is a function of the total energy cost required to rewrite its history.<\/span>7<\/span> VDFs introduce a new, non-energy-based digital resource: verifiably scarce sequential time. By design, an adversary cannot compress a one-hour delay into one minute simply by applying more capital in the form of parallel hardware.<\/span>7<\/span> This allows protocols to be anchored to a verifiable “waiting period” that is roughly consistent for all participants, regardless of their total computational capacity. This paradigm shift enables a new class of “resource-efficient blockchains” and protocols that are not reliant on massive energy consumption, directly addressing a primary criticism of PoW systems.<\/span>2<\/span> The security anchor transitions from a “proof of burnt energy” to a “proof of passed time.”<\/span><\/p>\n
<\/p>\n
Section 2: Mathematical Foundations and Core Constructions<\/b><\/h2>\n
<\/p>\n
The theoretical properties of Verifiable Delay Functions are realized through specific mathematical structures designed to be inherently sequential. The search for such structures has led researchers to explore various areas of number theory and algebra, resulting in several distinct families of VDF constructions, each with unique trade-offs regarding security, efficiency, and trust assumptions.<\/span><\/p>\n
<\/p>\n
2.1 The Role of Groups of Unknown Order<\/b><\/h3>\n
<\/p>\n
A leading approach for constructing VDFs relies on the conjectured hardness of certain problems within finite abelian groups whose order is unknown to the evaluator.<\/span>8<\/span> The most common operation used is repeated squaring. An evaluator is tasked with computing $y = x^{2^T}$ for some input $x$ and a large delay parameter $T$.<\/span>20<\/span><\/p>\n
The security of this construction hinges on the order of the group, $|G|$, being secret. If an evaluator knew $|G|$, they could use Euler’s totient theorem to drastically shortcut the computation by calculating the exponent modulo $\\phi(|G|)$ (or a related value), i.e., computing $x^{2^T \\pmod{\\phi(|G|)}}$.<\/span>8<\/span> This would instantly break the sequential delay property. Consequently, constructing groups where the order is computationally infeasible to determine without a secret trapdoor is a primary area of VDF research. Two main candidates have emerged for this purpose.<\/span><\/p>\n
- \n
- RSA Groups<\/b>: These are the multiplicative groups of integers modulo $N$, where $N=pq$ is the product of two large, secret prime numbers, $p$ and $q$.<\/span>1<\/span> The order of the group is $\\phi(N) = (p-1)(q-1)$, which is secret as long as the factorization of $N$ is unknown. RSA groups are well-understood and have been studied extensively in cryptography.<\/span>16<\/span> However, their primary drawback in a decentralized context is the requirement of a <\/span>trusted setup<\/b>. The modulus $N$ must be generated in such a way that no single party learns its prime factors, as this knowledge would constitute a master key to bypass the VDF’s delay.<\/span>8<\/span><\/li>\n
- Class Groups<\/b>: An alternative that circumvents the trusted setup requirement is the use of class groups of imaginary quadratic number fields.<\/span>1<\/span> The key advantage of class groups is that they <\/span>do not require a trusted setup<\/b> for their generation.<\/span>8<\/span> To create such a group, one only needs to generate a large, random prime number to serve as the discriminant, a process that can be performed publicly and trustlessly.<\/span>22<\/span> This makes them an ideal candidate for decentralized applications where trust is minimized. However, group operations within class groups are generally more computationally expensive and complex to implement than those in RSA groups.<\/span>16<\/span><\/li>\n<\/ul>\n
<\/p>\n
2.2 A Comparative Study: Pietrzak vs. Wesolowski<\/b><\/h3>\n
<\/p>\n
Building upon the foundation of repeated squaring in groups of unknown order, two seminal VDF constructions were proposed independently by Krzysztof Pietrzak and Benjamin Wesolowski. Both schemes provide a mechanism to make the classic time-lock puzzle publicly verifiable, but they differ significantly in their proof mechanisms, performance characteristics, and underlying security assumptions.<\/span>4<\/span><\/p>\n
- \n
- Wesolowski’s VDF<\/b>: This construction is celebrated for its elegance and efficiency.<\/span><\/li>\n<\/ul>\n
- \n
- Mechanism<\/b>: The proof is generated using an interactive challenge-response protocol that can be made non-interactive via the Fiat-Shamir heuristic. For a challenge prime $l$, the prover computes a single proof element $\\pi = g^{\\lfloor 2^T\/l \\rfloor}$. A verifier can then check the correctness of the output $y$ by confirming the equation $y = \\pi^l \\cdot g^{2^T \\pmod l}$.<\/span>1<\/span><\/li>\n
- Characteristics<\/b>: The most notable feature is its extremely compact proof, which consists of just a single group element.<\/span>4<\/span> Verification is also highly efficient, requiring only two exponentiations.<\/span>1<\/span> However, this efficiency comes at the cost of relying on a stronger and less-studied security assumption known as the “adaptive root assumption”.<\/span>20<\/span> Furthermore, the non-interactive version requires a hash-to-prime function, which can be complex and costly to implement in constrained environments like on-chain smart contracts.<\/span>24<\/span><\/li>\n<\/ul>\n
- \n
- Pietrzak’s VDF<\/b>: This construction uses a different approach to proving correctness.<\/span><\/li>\n<\/ul>\n
- \n
- Mechanism<\/b>: The proof is based on a recursive halving protocol. The prover computes intermediate values of the squaring chain (e.g., $g^{2^{T\/2}}, g^{2^{T\/4}}$, etc.) and includes them in the proof. The verifier then recursively checks the consistency of these intermediate steps.<\/span>20<\/span><\/li>\n
- Characteristics<\/b>: The proof size is larger than Wesolowski’s, growing logarithmically with the delay parameter, i.e., $O(\\log T)$ group elements.<\/span>1<\/span> The verification time is also proportional to $O(\\log T)$. A key advantage is that it relies on more standard and weaker cryptographic assumptions. Despite initial concerns about its practicality for blockchain use due to proof size, recent implementation studies have demonstrated that Pietrzak’s VDF can be verified on the Ethereum Virtual Machine (EVM) with manageable proof sizes (under 8 KB) and acceptable gas costs.<\/span>14<\/span><\/li>\n<\/ul>\n
<\/p>\n
2.3 Emerging Frontiers: Isogenies and SNARKs<\/b><\/h3>\n
<\/p>\n
Beyond groups of unknown order, researchers are exploring other mathematical avenues to construct VDFs, including isogeny-based cryptography and the use of succinct non-interactive arguments of knowledge (SNARKs).<\/span><\/p>\n
- \n
- Isogeny-based VDFs<\/b>:<\/span><\/li>\n<\/ul>\n
- \n
- Mechanism<\/b>: This approach is based on the problem of computing a long chain, or “walk,” of isogenies (maps between elliptic curves) in a supersingular isogeny graph.<\/span>1<\/span> The sequential nature arises because each step of the walk (computing the next isogeny) depends on the output of the previous step.<\/span><\/li>\n
- Characteristics<\/b>: A significant advantage of this construction is the potential for an empty proof ($\\pi$ is null), as verification can be performed efficiently using the dual isogeny and the Weil pairing.<\/span>1<\/span> However, current isogeny-based VDFs still require a trusted setup.<\/span>1<\/span> They also face practical challenges related to large memory requirements for the VDF parameters, which can run into terabytes for meaningful delay periods, making them expensive to operate.<\/span>26<\/span> Furthermore, their security against quantum computers is an active area of research and debate.<\/span>27<\/span><\/li>\n<\/ul>\n
- \n
- SNARK-based VDFs<\/b>:<\/span><\/li>\n<\/ul>\n
- \n
- Mechanism<\/b>: This is a more general approach to constructing VDFs. One can start with a simple, inherently sequential computation that lacks efficient verification, such as an iterated hash function: $y = H(H(…H(x)…))$.<\/span>9<\/span> By itself, this is a “weak VDF” because the only way to verify it is to re-compute the entire chain.<\/span>1<\/span> However, by generating a SNARK or STARK proof of the correct execution of this hash chain, one can create a full-fledged VDF with fast verification.<\/span>9<\/span><\/li>\n
- Characteristics<\/b>: The primary challenge with this method is the high computational cost of generating the SNARK\/STARK proof, which can be extremely slow.<\/span>9<\/span> To address this, major research collaborations involving entities like Protocol Labs, the Ethereum Foundation, and Supranational are working to optimize SNARK-based VDFs. Their strategy involves a hybrid architecture that separates the two main tasks: the low-latency, sequential VDF evaluation is performed on optimized hardware (CPU or ASIC), while the high-throughput, parallelizable proof generation is offloaded to a many-core architecture like a GPU cluster.<\/span>18<\/span><\/li>\n<\/ul>\n
The choice of a VDF construction for any given application is a complex decision involving a careful weighing of these trade-offs. A protocol designer must consider the trust model (is a trusted setup acceptable?), the resource constraints of verifiers (how large can the proof be?), the on-chain costs (what is the verification gas cost?), and the required security assumptions. The following table provides a synthesized comparison to aid in this analysis.<\/span><\/p>\n
\n\n
\n VDF Construction<\/b><\/td>\n Core Mathematical Problem<\/b><\/td>\n Trusted Setup?<\/b><\/td>\n Proof Size<\/b><\/td>\n Verification Complexity<\/b><\/td>\n Key Security Assumption<\/b><\/td>\n Quantum Resistance<\/b><\/td>\n<\/tr>\n \n Wesolowski<\/b><\/td>\n Repeated Squaring in Group of Unknown Order<\/span><\/td>\n Yes (RSA) or No (Class Groups)<\/span><\/td>\n Constant ($O(1)$)<\/span><\/td>\n Constant ($O(1)$)<\/span><\/td>\n Adaptive Root Assumption<\/span><\/td>\n No (if based on RSA\/Class Groups)<\/span><\/td>\n<\/tr>\n \n Pietrzak<\/b><\/td>\n Repeated Squaring in Group of Unknown Order<\/span><\/td>\n Yes (RSA) or No (Class Groups)<\/span><\/td>\n Logarithmic ($O(\\log T)$)<\/span><\/td>\n Logarithmic ($O(\\log T)$)<\/span><\/td>\n Repeated Squaring Assumption<\/span><\/td>\n No (if based on RSA\/Class Groups)<\/span><\/td>\n<\/tr>\n \n Isogeny-based<\/b><\/td>\n Computing long isogeny walks<\/span><\/td>\n Yes<\/span><\/td>\n Constant ($O(1)$, often empty)<\/span><\/td>\n Constant ($O(1)$)<\/span><\/td>\n Hardness of isogeny problems<\/span><\/td>\n Potential, but actively debated<\/span><\/td>\n<\/tr>\n \n SNARK-based<\/b><\/td>\n Iterated sequential computation (e.g., hashing)<\/span><\/td>\n No (for hash-based) or Yes (for some SNARKs)<\/span><\/td>\n Constant ($O(1)$)<\/span><\/td>\n Constant ($O(1)$)<\/span><\/td>\n Security of SNARK system + Sequentiality of function<\/span><\/td>\n Yes (if using STARKs)<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n <\/p>\n
Section 3: Application I – Generating Unbiasable Public Randomness<\/b><\/h2>\n
<\/p>\n
One of the most compelling and immediate applications of Verifiable Delay Functions is the creation of secure, decentralized sources of public randomness. In distributed systems like blockchains, obtaining randomness that is unpredictable, unbiasable, and universally verifiable is a notoriously difficult problem, yet it is essential for the fair operation of many protocols, including lotteries, games, and consensus-critical validator selection.<\/span>9<\/span><\/p>\n
<\/p>\n
3.1 The Randomness Beacon: Principles and Implementation<\/b><\/h3>\n
<\/p>\n
A “randomness beacon” is a service that periodically publishes a fresh, random value that any participant in a system can access and trust. VDFs provide a powerful mechanism for constructing such beacons in a trustless manner. The core principle is to combine a public source of entropy with a VDF to enforce a time delay between when the entropy is finalized and when the resulting random number is revealed.<\/span>8<\/span><\/p>\n
The process works as follows:<\/span><\/p>\n
- \n
- Entropy Collection<\/b>: The system agrees on a source of public, high-entropy data at a specific point in time. This input, or “seed,” could be the hash of a recent block on a blockchain, a collection of stock market prices at closing, or any other publicly observable and difficult-to-predict value.<\/span>6<\/span><\/li>\n
- VDF Evaluation<\/b>: This seed is fed as the input $x$ into a VDF. An evaluator then computes $(y, \\pi) = \\text{Eval}(ek, x)$ over a predefined delay period $T$.<\/span><\/li>\n
- Randomness Publication<\/b>: Once the computation is complete, the output $y$ is published as the new random value. The accompanying proof $\\pi$ allows anyone in the network to quickly verify that $y$ is the correct and unique output corresponding to the initial seed.<\/span><\/li>\n<\/ol>\n
The enforced delay is the key to security. By the time the VDF computation finishes and the random number $y$ is known, the input seed $x$ is long past, finalized, and can no longer be influenced by any actor trying to manipulate the outcome.<\/span>
- VDF Evaluation<\/b>: This seed is fed as the input $x$ into a VDF. An evaluator then computes $(y, \\pi) = \\text{Eval}(ek, x)$ over a predefined delay period $T$.<\/span><\/li>\n
- Characteristics<\/b>: The primary challenge with this method is the high computational cost of generating the SNARK\/STARK proof, which can be extremely slow.<\/span>9<\/span> To address this, major research collaborations involving entities like Protocol Labs, the Ethereum Foundation, and Supranational are working to optimize SNARK-based VDFs. Their strategy involves a hybrid architecture that separates the two main tasks: the low-latency, sequential VDF evaluation is performed on optimized hardware (CPU or ASIC), while the high-throughput, parallelizable proof generation is offloaded to a many-core architecture like a GPU cluster.<\/span>18<\/span><\/li>\n<\/ul>\n
- Mechanism<\/b>: This is a more general approach to constructing VDFs. One can start with a simple, inherently sequential computation that lacks efficient verification, such as an iterated hash function: $y = H(H(…H(x)…))$.<\/span>9<\/span> By itself, this is a “weak VDF” because the only way to verify it is to re-compute the entire chain.<\/span>1<\/span> However, by generating a SNARK or STARK proof of the correct execution of this hash chain, one can create a full-fledged VDF with fast verification.<\/span>9<\/span><\/li>\n
- Characteristics<\/b>: A significant advantage of this construction is the potential for an empty proof ($\\pi$ is null), as verification can be performed efficiently using the dual isogeny and the Weil pairing.<\/span>1<\/span> However, current isogeny-based VDFs still require a trusted setup.<\/span>1<\/span> They also face practical challenges related to large memory requirements for the VDF parameters, which can run into terabytes for meaningful delay periods, making them expensive to operate.<\/span>26<\/span> Furthermore, their security against quantum computers is an active area of research and debate.<\/span>27<\/span><\/li>\n<\/ul>\n
- Mechanism<\/b>: This approach is based on the problem of computing a long chain, or “walk,” of isogenies (maps between elliptic curves) in a supersingular isogeny graph.<\/span>1<\/span> The sequential nature arises because each step of the walk (computing the next isogeny) depends on the output of the previous step.<\/span><\/li>\n
- Characteristics<\/b>: The proof size is larger than Wesolowski’s, growing logarithmically with the delay parameter, i.e., $O(\\log T)$ group elements.<\/span>1<\/span> The verification time is also proportional to $O(\\log T)$. A key advantage is that it relies on more standard and weaker cryptographic assumptions. Despite initial concerns about its practicality for blockchain use due to proof size, recent implementation studies have demonstrated that Pietrzak’s VDF can be verified on the Ethereum Virtual Machine (EVM) with manageable proof sizes (under 8 KB) and acceptable gas costs.<\/span>14<\/span><\/li>\n<\/ul>\n
- Mechanism<\/b>: The proof is based on a recursive halving protocol. The prover computes intermediate values of the squaring chain (e.g., $g^{2^{T\/2}}, g^{2^{T\/4}}$, etc.) and includes them in the proof. The verifier then recursively checks the consistency of these intermediate steps.<\/span>20<\/span><\/li>\n
- Characteristics<\/b>: The most notable feature is its extremely compact proof, which consists of just a single group element.<\/span>4<\/span> Verification is also highly efficient, requiring only two exponentiations.<\/span>1<\/span> However, this efficiency comes at the cost of relying on a stronger and less-studied security assumption known as the “adaptive root assumption”.<\/span>20<\/span> Furthermore, the non-interactive version requires a hash-to-prime function, which can be complex and costly to implement in constrained environments like on-chain smart contracts.<\/span>24<\/span><\/li>\n<\/ul>\n
- Mechanism<\/b>: The proof is generated using an interactive challenge-response protocol that can be made non-interactive via the Fiat-Shamir heuristic. For a challenge prime $l$, the prover computes a single proof element $\\pi = g^{\\lfloor 2^T\/l \\rfloor}$. A verifier can then check the correctness of the output $y$ by confirming the equation $y = \\pi^l \\cdot g^{2^T \\pmod l}$.<\/span>1<\/span><\/li>\n
- Class Groups<\/b>: An alternative that circumvents the trusted setup requirement is the use of class groups of imaginary quadratic number fields.<\/span>1<\/span> The key advantage of class groups is that they <\/span>do not require a trusted setup<\/b> for their generation.<\/span>8<\/span> To create such a group, one only needs to generate a large, random prime number to serve as the discriminant, a process that can be performed publicly and trustlessly.<\/span>22<\/span> This makes them an ideal candidate for decentralized applications where trust is minimized. However, group operations within class groups are generally more computationally expensive and complex to implement than those in RSA groups.<\/span>16<\/span><\/li>\n<\/ul>\n
- VDFs vs. Time-Lock Puzzles (TLPs)<\/b>: TLPs, such as the original construction by Rivest, Shamir, and Wagner based on RSA, are also slow to solve and serve to encrypt information into the future.<\/span>1<\/span> However, they critically lack an efficient <\/span>public<\/span><\/i> verification mechanism.<\/span>1<\/span> Verifying the solution to a classic TLP typically requires knowledge of a secret trapdoor (e.g., the factorization of the RSA modulus $N$), which is antithetical to the needs of a trustless, decentralized system. VDFs can be viewed as a direct evolution of TLPs, augmenting them with the essential property of public verifiability, thereby transforming them from a two-party tool into a primitive suitable for multi-party, decentralized protocols.<\/span>3<\/span><\/li>\n<\/ul>\n
- Uniqueness<\/b>: For any given input $x$, there must be only one unique output $y$ that can be successfully verified.<\/span>5<\/span> This property is formally captured by the <\/span>Soundness<\/b> requirement, which guarantees that the probability of an adversary generating a valid proof $\\pi$ for an incorrect output ($y’ \\neq y$) is negligible.<\/span>1<\/span> This ensures that the VDF’s output is deterministic and cannot be manipulated by a malicious prover.<\/span><\/li>\n
- Eval($ek, x$) $\\rightarrow$ ($y, \\pi$)<\/b>: This algorithm performs the core, time-consuming computation. It takes the evaluation key $ek$ and an input value $x$ from a defined domain $X$ and, after a significant delay, produces an output value $y$ in a range $Y$, along with a proof $\\pi$.<\/span>1<\/span> The fundamental design constraint of the Eval algorithm is that it must take at least $T$ sequential, non-parallelizable steps to complete.<\/span>5<\/span><\/li>\n