Verifiable Delay Function (VDF)

The defining property of a VDF. Evaluating the function must require a specific number of sequential computational steps, even with unbounded parallel hardware. A polynomial number of processors cannot speed up the computation. This enforces a real-world time delay.

• Mechanism: Typically achieved through repeated squaring in a group of unknown order.
• Contrast: Unlike Proof-of-Work (PoW), which is parallelizable, a VDF's sequential nature guarantees a minimum wall-clock time before an output can be produced.
• Example: Computing y = g^(2^T) mod N requires T sequential squarings.

While evaluation is slow and sequential, the resulting output and its proof must be verified by anyone exponentially faster than the computation itself. Verification should be non-interactive and require only a single round.

• Goal: Verification time is typically logarithmic O(log T) or even constant O(1) relative to the evaluation time T.
• Method: This is often achieved using a succinct proof generated by the prover alongside the output, which the verifier checks using a pairing-based equation.
• Practical Impact: A computation that took 1 hour to run can be verified in milliseconds.

For a given input x and time parameter T, there is exactly one valid output y. A computationally bounded adversary cannot find a different output y' that passes the verification check.

• Critical Distinction: This separates VDFs from Verifiable Random Functions (VRFs), where multiple outputs could be validly generated by a key holder.
• Enforcement: Uniqueness is enforced by the mathematical structure of the function and the verification algorithm, preventing "forking" of the output.
• Use Case: Essential for leader election in consensus protocols where only one valid random beacon value must exist.

The VDF is a pure function. Given identical inputs (x, T), the evaluation algorithm will always produce the identical output y. There is no randomness or non-determinism in the computation itself.

• Property: VDF(x, T) = y is consistent across all evaluators.
• Contrast: This differs from a VRF where the output is determined by a secret key, making it pseudorandom but not publicly computable.
• Significance: Anyone can independently recompute the function and arrive at the same result, enabling public verifiability without a trusted prover.

The delay parameter T must have a tight lower bound on the wall-clock time required for evaluation. An adversary with specialized hardware (e.g., an ASIC) should not gain a significant advantage over a user with commodity hardware.

• Challenge: Designing a function that is inherently sequential on all hardware architectures.
• Approach: Using algebraic structures where the basic operation (e.g., modular squaring) is already highly optimized in silicon, minimizing the gap between commodity and custom hardware.
• Result: The time to compute is predictable and bounded, making the delay reliable for protocol timing assumptions.

The prover can generate the proof of correct evaluation without any back-and-forth communication with the verifier. The proof is a static piece of data that can be broadcast or stored.

• Property: The setup is a one-way process: Prove(x, T) -> (y, π). The verifier then checks Verify(x, T, y, π) -> {true, false}.
• Advantage: Enables asynchronous verification in decentralized networks where verifiers may not be online during computation.
• Implementation: Wesolowski and Pietrzak proofs are both non-interactive, making them suitable for blockchain environments.

A public-key pseudorandom function that produces a unique, unpredictable output along with a cryptographic proof that the output was computed correctly. Unlike VDFs, VRFs generate randomness that is immediately verifiable without requiring sequential delay.

• Used in blockchain leader election and lottery-based consensus
• Provides non-interactive verification of randomness
• Output is deterministic given the same input and private key
• Complements VDFs in protocols requiring both randomness and delay

A cryptographic primitive enabling a computationally weak client to outsource computation to a powerful server while retaining the ability to verify correctness of the result. VDFs are a specialized form where the computation is inherently sequential.

• General-purpose verifiable compute uses SNARKs or STARKs
• VDFs enforce a time-lock that parallelization cannot bypass
• Enables trustless delegation of arbitrary computations
• Critical for scaling blockchain execution layers

A high-frequency VDF developed by Solana that creates a cryptographic record of the passage of time. Each hash output becomes the input for the next step, producing an unforgeable sequential record.

• Generates a verifiable timestamp for each transaction
• Eliminates need for nodes to agree on time externally
• Runs at 400+ kHz on a single core
• Enables Solana's sub-second block times

A cryptographic scheme where a message is encrypted such that it cannot be decrypted until a specified time has elapsed, even by the sender. VDFs provide the delay guarantee that makes time-lock encryption trustless.

• No trusted third party required for time release
• Used in sealed-bid auctions and commit-reveal schemes
• VDF evaluation serves as the mandatory waiting period
• Decryption becomes possible only after VDF output is computed

A consensus mechanism where miners must perform inherently sequential computation that cannot be parallelized. VDFs formalize this concept with the added property of efficient public verification.

• Unlike hash-based PoW, sequential work resists ASIC acceleration
• VDF-based consensus reduces energy waste
• Verification is exponentially faster than computation
• Explored as an alternative to Nakamoto consensus

The most common underlying construction for practical VDFs, based on the computational hardness of repeated modular squaring in an RSA group. The prover computes g^(2^T) mod N sequentially.

• Security relies on the sequentiality assumption in finite groups
• Cannot be parallelized due to chained dependencies
• Verification uses a succinct proof via Wesolowski or Pietrzak protocols
• Requires a trusted setup or class group alternative