VDF Verification: Verifiable Delay Functions Explained

VDF Verification: Verifiable Delay Functions Explained

A Verifiable Delay Function (VDF) is a cryptographic primitive that requires a specified number of sequential steps to compute, produces a unique deterministic output, and allows efficient verification. Unlike hash functions which are fast to compute, VDFs enforce a minimum computation time (delay), yet anyone can verify the output quickly. VDFs are critical for blockchain applications where randomness, leader election, and transaction ordering must be unpredictable and resistant to manipulation. Notable implementations include the Chia Network's VDF and Ethereum's VDF research.

To understand VDFs properly, it helps to be familiar with verifiable random functions (VRFs), blockchain consensus, and elliptic curve cryptography.

┌─────────────────────────────────────────────────────────────────────────┐
│                      Verifiable Delay Function (VDF)                     │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                          │
│   Properties:                                                            │
│   • Sequential: Computation requires T sequential steps (no parallelism)│
│   • Verifiable: Output verification is fast (O(log T) or constant)      │
│   • Deterministic: Same input always produces same output               │
│   • Uniqueness: Only one valid output for given input                   │
│                                                                          │
│   VDF Evaluation:                       VDF Verification:               │
│   ┌─────────────────────────┐          ┌─────────────────────────────┐  │
│   │ Input x ──→ VDF(x)      │          │ (x, y, π) ──→ Verify       │  │
│   │ Requires T sequential   │          │ Fast (O(log T))             │  │
│   │ steps (e.g., modular     │          │ No need to recompute        │  │
│   │ exponentiation)         │          │ whole VDF                   │  │
│   └─────────────────────────┘          └─────────────────────────────┘  │
│                                                                          │
│   Example: Modular exponentiation (Class group or RSA)                  │
│   VDF(x) = g^(2^T) mod N (sequential squaring)                         │
│   Verification uses proof of exponentiation (PoE)                       │
│                                                                          │
│   Applications:                                                          │
│   • Blockchain randomness (unpredictable, bias-resistant)               │
│   • Leader election (fair, verifiable delay)                            │
│   • Resource-constrained proof of work (PoW alternative)                │
│   • Preventing front-running (ordering delay)                           │
│                                                                          │
└─────────────────────────────────────────────────────────────────────────┘

What Is a Verifiable Delay Function?

A Verifiable Delay Function is a cryptographic function that takes a specified time T to compute (number of sequential steps), produces a unique output, and allows efficient verification. The time parameter T controls the computational delay; no amount of parallelism can compute the function faster than T sequential steps. The function is deterministic, meaning same input always yields same output. The verification process is exponentially faster than recomputation, often taking O(log T) time.

• Sequentiality: Computation cannot be parallelized; each step depends on previous step. This ensures minimum delay even with many processors.
• Verifiability: Anyone can verify output quickly without recomputing whole VDF. Rely on proof of correct execution (e.g., proof of exponentiation).
• Uniqueness: No collisions; each input maps to exactly one output (unlike hash functions where multiple inputs can produce same output).
• Delay Parameter T: Target number of sequential steps; larger T = longer computation time. Trades off security vs performance.

Why VDFs Matter

Blockchains need randomness that is unpredictable and bias-resistant. Traditional methods (commit-reveal, RANDAO) have vulnerabilities. VDFs provide verifiable randomness with guaranteed delay.

• Unpredictable Randomness: VDF output cannot be predicted before computation completes, even by the evaluator. Prevents manipulation of randomness (no last-revealer advantage).
• Leader Election (Proof-of-Stake): Fair election of block proposers. VDF ensures proposer cannot know they will be elected before block time; prevents grinding attacks.
• Front-Running Prevention: Delay transaction ordering information. VDF commits to sequence; malicious validators cannot reorder after seeing content.
• Resource-Bounded Proof of Work (PoW Alternative): VDF requires sequential computation (not parallelizable). More energy-efficient than PoW? Not exactly, but different tradeoffs.
• Verifiable Timed Signatures: Signatures that only become valid after certain time. Useful for escrow, auctions, sealed bids.

Property            Hash (SHA-256)        PoW (Bitcoin)         VDF
─────────────────────────────────────────────────────────────────────────────
Parallelizable      Yes (high)            Yes (very high)       No (sequential)
Verification        Fast                  Fast                  Fast (O(log T))
Uniqueness          No (collisions exist) No (any nonce)        Yes (deterministic)
Time Control        Not possible          Expected (probabilistic) Deterministic
Energy Cost         Low                   Very high             Moderate
Blockchain Use      Commitment, linking   Security              Randomness, leader

VDF Construction: Class Groups (Chia)

Chia Network's VDF uses class groups of imaginary quadratic orders. The evaluation is repeated squaring in the class group. The challenge is repeated squaring (g^(2^T)). Verification uses a proof of exponentiation (PoE) to check correctness without recomputing whole exponentiation.

Setup:
  • Generate class group G of discriminant d (distinct prime)
  • Choose random base element g ∈ G
  • T = number of squaring steps (delay parameter)

Evaluation:
  Compute x = g^(2^T) in G
  This requires T sequential squaring operations
  Each step: current ← current²

Proof Generation (Proof of Exponentiation - PoE):
  Compute y = g^(2^(T/2)) (intermediate)
  Output π = (y, µ) where µ is additional proof data

Verification:
  Check that (y^2)^(2^(T/2)) = x
  Uses class group properties for efficient check
  Time O(log T) vs O(T) for full recompute

Class group advantages:
  • No known trapdoor (no trusted setup)
  • Secure against quantum computers (conjectured)
  • Relatively fast evaluation

RSA VDF (RSA Group)

RSA-based VDF uses repeated squaring modulo N = p·q (RSA modulus). Requires trusted setup (generation of N) with unknown factorization.

Setup (Trusted):
  • Generate RSA modulus N = p·q (p, q secret primes)
  • Choose base g ∈ Z_N^*
  • T = number of squaring steps

Evaluation:
  Compute y = g^(2^T) mod N
  Requires T sequential squaring steps

Pietrzak Proof (interactive):
  • Recursive halving of exponent
  • Prover sends y_i = g^(2^(T/2^i)) at each round
  • Verifier challenges with random µ
  • After log2(T) rounds, final check

Wesolowski Proof (non-interactive):
  • Prover sends y = g^(2^T) and also q = floor(2^T / ℓ)
  • Verifier chooses random prime ℓ
  • Compute r = 2^T mod ℓ
  • Check (g^r * (y^q) ???)

Trusted setup: need RSA modulus N with unknown factorization.
Anyone knowing p, q can cheat (compute faster via φ(N)).

Solutions:
  1. Multi-party computation (MPC) ceremony for N
  2. Use class groups (no trapdoor) - Chia's approach
  3. Use isogeny-based VDF

Risk: If factorization known, evaluator can compute g^(2^T mod φ(N)).
  Without trapdoor, evaluator must do T squarings.

VDF Verification Algorithms

Wesolowski Proof (RSA VDF)

Prover computes y = g^(2^T). Verifier chooses random prime ℓ. Prover computes q = floor(2^T / ℓ) and r = 2^T mod ℓ. Send y, π = g^q. Verifier checks: g^(2^T) should equal (g^r)·(π^ℓ). Verification verifies relation without computing 2^T exponent fully.

Pietrzak Proof (RSA VDF Interactive → Non-interactive via Fiat-Shamir)

Recursive halving: prove log_2(T) rounds. At each round, prover sends intermediate y_i. Verifier sends random challenge µ. Prover computes new base g' = g^µ·y_i (combination). Halve exponent and repeat.

Input: prove that y = g^(2^T)

Round 1:
  Prover sends y₁ = g^(2^(T/2))
  Verifier sends random µ
  Prover computes g₁ = g^µ * y₁
  y₂ = y₁^(2^(T/2))

 New statement: y₂ == g₁^(2^(T/2)) (reduce T/2)

Round 2: Repeat on halved exponent

Complexity:
  • O(log T) rounds for interactive proof
  • O(log T) total work for verifier
  • Non-interactive via Fiat-Shamir transform

VDF Applications in Blockchain

RANDAO + VDF:

1. Validators commit random seeds (RANDAO commit phase).
2. After commit phase, VDF evaluates over committed seeds.
3. VDF delay forces that no one can know final randomness before commit ends.
   (Prevents last-revealer manipulation).

4. Output = VDF(seed_1 ∘ seed_2 ∘ ... ∘ seed_n)
   where VDF takes T sequential steps (e.g., 10 seconds worth).

Properties:
  • Unpredictable: VDF output cannot be computed faster than T steps.
  • Bias-resistant: No participant can influence final output after commit.
  • Verifiable: Anyone can verify VDF output quickly.

VDF Anti-Patterns

• Trusted Setup Compromise (RSA VDF): RSA VDF requires trusted setup (N with unknown factorization). If p or q leaked, evaluator can cheat by using φ(N). Use MPC ceremony or class groups to mitigate.
• Insufficient Delay Parameter T: T too small = VDF computed faster than expected, undermining security. T must be large enough that fastest hardware cannot compute faster than desired delay. Account for hardware improvements over expected lifetime.
• No Proof Aggregation (Poor Verification): Verifier must check VDF proofs individually. Verifying many VDFs may be expensive. Use recursive VDF proofs or aggregation.
• Assuming Parallelization Impossible: Some VDF constructions allow some parallelism (e.g., faster hardware still helps for each squaring). Class groups are not perfectly sequential. Choose VDF with best sequentiality.
• Not Considering Amortization Attacks: Evaluator may compute many VDFs in parallel faster than sequential? Use amortization-resistant construction.

Security:
□ Trusted setup (RSA) or transparent (class group)?
□ T large enough for desired delay (account for Moore's law)
□ Proof of exponentiation (PoE) implemented correctly
□ Check for parallelization speedups (amortization)

Verification:
□ Proof size efficient (O(log T) bytes)
□ Verification time O(log T) operations
□ Non-interactive via Fiat-Shamir

Compatibility:
□ Curve/group selection for target platform (class group or RSA)
□ Language support (Rust, C++ for class groups)
□ Integration with blockchain (EVM, WASM)

VDF Best Practices

• Use Class Groups (Chia) to Avoid Trusted Setup: Class groups have no trapdoor (no trusted setup). Transparent and verifiable: anyone can verify VDF parameters. Not vulnerable to factorization leakage. Class group VDFs are quantum-safe (no known efficient quantum algorithm).
• Use Efficient Proofs (Wesolowski/Pietrzak): Pietrzak proof has O(log T) rounds but requires interaction (Fiat-Shamir for non-interactive). Wesolowski proof is non-interactive but requires verifier to choose random prime ℓ. Both are efficient (verifier O(log T)).
• Choose Appropriate T Based on Target Latency: T = number of squaring steps (target latency). Estimate based on hardware (CPU, GPU, FPGA). Use formula: T = desired_seconds × operations_per_second. Add margin (2-5x) for hardware improvements.
• Parallelize VDF Evaluation Strategically: Computation itself is sequential, but multiple VDFs can be computed in parallel for different inputs. Use pipelining for long chains; GPUs can compute many squarings simultaneously (batch).
• Verify Proofs Before Trusting Output: Always verify VDF output using verification algorithm (not just trusting evaluator). Reject if proof invalid; use on-chain verification where possible.

Parameter           Recommendation
─────────────────────────────────────────────────────────────────────────────
T (delay steps)     Desired delay in seconds * speed (ops/sec)
Example: 10 sec delay, class group VDF (10^6 ops/sec) → T = 10^7
Hardware (CPU):     10^7-10^8 steps (seconds to minutes)
Hardware (FPGA):    10^9 steps (minutes to hours)
Proof Type          Wesolowski (non-interactive) for blockchain
Group               Class groups (transparent) or RSA (trusted)

Leading VDF Implementations

Hardware           Ops/sec         T=10^7 runtime
─────────────────────────────────────────────────────────────────────────────
CPU (1 core)       10^5-10^6       10-100 seconds
CPU (multi-core)   ~10^6 (pipelined) 10 seconds
GPU (CUDA)         10^7-10^8       0.1-1 second
FPGA               10^8-10^9       0.01-0.1 second

Frequently Asked Questions

1. What is the difference between VDF and hash function?
   Hash functions are fast, parallelizable, and non-sequential. VDFs are slow, require sequential steps, and enforce computational delay. Hash functions have collisions (multiple inputs same output). VDFs are deterministic and unique per input.
2. Can ASICs accelerate VDFs?
   Yes, but VDFs are designed to be memory-hard and sequential. Even with ASICs, the fundamental step must be sequential. ASICs speed each operation but cannot parallelize across steps. ASIC resistance is not complete but better than PoW.
3. What is the trusted setup problem for RSA VDF?
   RSA VDF needs RSA modulus N = p·q where p,q are secret primes. If factorization known, evaluator can compute exponentiation faster (using φ(N)). Mitigation: use class group VDF (no trapdoor).
4. Are VDFs quantum-safe?
   Class group VDFs are believed quantum-safe (no known efficient quantum algorithm for class group). RSA VDF is vulnerable to Shor's algorithm (factoring). For long-term security, prefer class group VDFs.
5. How does Chia's Proof of Space and Time use VDF?
   Chia uses VDF to prove that time passed between blocks (time delay). Farmer proves they stored plots over time; VDF ensures sequential delay is enforced. Combines proof of space (storage) with VDF (time).
6. What should I learn next after VDF verification?
   After mastering VDFs, explore verifiable random functions (VRFs), Proof of Space and Time (PoST, Chia), class groups for cryptography, randomness beacon design, and blockchain consensus mechanisms.