Verifiable Delay Function (VDF)

The function must be evaluated in a strictly sequential manner. No parallelization advantage is possible, even with an unbounded number of processors. This is the defining characteristic that enforces a real-world time delay. The computation is a single long chain of steps where the output of step n is the input to step n+1, preventing a faster machine from finishing in less wall-clock time than a slower one. This property is often achieved through repeated squaring in a group of unknown order.

While evaluation is slow, verification of the output must be exponentially faster than the computation itself. A verifier should be able to confirm the correctness of the result in logarithmic time, typically O(log(T)), where T is the number of sequential steps. This asymmetry is what makes a VDF practical; anyone can quickly check the proof without redoing the work. This is commonly achieved through a succinct proof generated alongside the output.

For a given input and delay parameter, a VDF produces exactly one valid output. This determinism is critical for applications like randomness beacons. If multiple valid outputs were possible, a malicious evaluator could choose the one most favorable to them. The uniqueness property is enforced by the mathematical structure of the function and is verified by the accompanying proof, ensuring no ambiguity exists in the final result.

The delay parameter T specifies the exact number of sequential computational steps required. The function's runtime is predictable and non-negotiable. Given a specific hardware setup, the wall-clock time to evaluate the VDF can be estimated with high precision. This contrasts with proof-of-work, where finding a solution is a probabilistic lottery. A VDF guarantees that a specific amount of time has elapsed since the computation began.

VDFs generate publicly verifiable randomness that no single party can manipulate. The sequential computation ensures the output cannot be precomputed or biased, even by a powerful adversary.

• How it works: Multiple participants submit entropy, which feeds into a VDF. The delay prevents any participant from knowing the final output before committing their contribution.
• Example: The League of Entropy's drand network uses a VDF-inspired approach to produce randomness for Filecoin and other protocols.
• Key benefit: Eliminates the 'last actor' advantage in randomness generation, where the final participant could bias the result.

VDFs enforce a mandatory time delay between transaction submission and execution, neutralizing MEV (Maximal Extractable Value) attacks where validators reorder transactions for profit.

• Mechanism: Transactions are committed to a block, but their ordering is determined by a VDF output that only becomes available after a fixed delay. No one can predict the ordering in advance.
• Real-world impact: Protocols like UniswapX explore VDF-based ordering to create fair batch auctions where arbitrageurs compete on price rather than gas fees.
• Result: Reduces the $1B+ annual MEV extraction problem by making transaction ordering unpredictable and tamper-proof.

VDFs enable encryption that decrypts only after a specific time has elapsed, without requiring a trusted third party to hold the key. The decryption key is the VDF output itself.

• Use case: Sealed-bid auctions where all bids are encrypted and revealed simultaneously after the auction closes.
• Use case: Delayed disclosure of sensitive corporate information, ensuring it becomes public at a predetermined future moment.
• Technical note: Unlike timelock puzzles based on repeated squaring, VDF-based time-lock encryption produces a publicly verifiable proof that the correct delay was performed.

Solana's Proof of History (PoH) is the most prominent production deployment of a VDF, creating a cryptographic clock that orders events without requiring nodes to communicate about time.

• How it works: A high-frequency VDF runs continuously, producing a sequence of hashes that prove real time has passed between events. Validators use this shared clock to agree on transaction ordering.
• Performance: Enables sub-second block times by removing the need for validators to coordinate timestamps through consensus messages.
• Trade-off: Requires specialized hardware (high-core-count CPUs) to run the VDF at speed, introducing some centralization risk in the sequencer role.

In leader-election protocols, VDFs prevent 'grinding' attacks where a validator repeatedly tries different inputs to manipulate their chance of being selected as the next block proposer.

• Problem without VDFs: A validator could compute many potential leader-election outcomes in parallel and choose the most favorable one.
• VDF solution: The election seed is fed through a VDF, forcing a sequential delay. By the time the output is known, the window for manipulation has passed.
• Adoption: Protocols like Chia use VDFs to ensure fair leader election in their Proof-of-Space-and-Time consensus.

VDFs provide a cryptographic alternative to trusted timestamping authorities (TSAs), proving that a document existed before a certain time without relying on a centralized service.

• Process: A document hash is combined with a VDF output from a public randomness beacon. The resulting proof demonstrates the document existed before the VDF computation began.
• Advantage over TSAs: No single entity controls the timestamp. The proof is mathematically verifiable by anyone, anywhere, without trusting an authority's clock.
• Integration: Can be combined with transparency logs like Certificate Transparency to create fully decentralized, auditable timestamping infrastructure.

A cryptographic primitive that allows a party to commit to a chosen value while keeping it hidden, with the ability to reveal it later. The scheme ensures binding (cannot change the value) and hiding (value remains secret until revealed).

• Pedersen Commitments: Perfectly hiding, computationally binding
• Hash-based Commitments: Computationally hiding, perfectly binding
• Used in VDF-based randomness beacons to commit to future outputs

A trusted third party that issues a timestamp token cryptographically binding a document's hash to a specific point in time. VDFs offer a trustless alternative to centralized TSAs by providing a mathematical proof that a specific duration elapsed during computation.

• Traditional TSA relies on a single trusted entity
• VDF-based timestamping removes the need for trust
• Enables decentralized ordering of events in distributed systems

A method allowing a prover to convince a verifier that a statement is true without revealing any information beyond the statement's validity. VDFs complement ZKPs by providing a time-based proof of work that cannot be parallelized.

• zk-SNARKs: Succinct, requires trusted setup
• zk-STARKs: Transparent, post-quantum secure
• VDFs + ZKPs enable private, time-locked transactions

A cryptographic proof, typically generated using a Merkle tree, that verifies a specific data element belongs to a larger committed dataset without revealing the entire dataset. VDF outputs can be included in Merkle trees to create verifiable delay proofs for decentralized applications.

• Enables efficient light client verification
• Combines with VDFs for auditable randomness
• Critical for blockchain state verification at scale

A signature scheme supporting efficient aggregation and batch verification, allowing multiple signatures from different parties to be combined into a single compact signature. VDFs often use BLS signatures for threshold randomness generation.

• Enables signature aggregation across validators
• Pairs with VDFs in randomness beacons like drand
• Produces deterministic, publicly verifiable outputs

A technique for converting an interactive proof into a non-interactive one by replacing the verifier's random challenges with a cryptographic hash function output. This heuristic is fundamental to making VDF proofs publicly verifiable without requiring back-and-forth communication.

• Transforms interactive protocols into standalone proofs
• Underpins the non-interactive nature of VDF verification
• Essential for public randomness generation schemes