Introduction

Suppose you want to run a fair lottery — but you need a random number that nobody could have predicted or manipulated. You could hash the next Bitcoin block, but miners can discard unlucky blocks. You could ask a trusted third party, but then you have to trust them. What you really want is a number that could not have been computed until the deadline, no matter how much compute power anyone had.

That is exactly what a Verifiable Delay Function (VDF) provides. It is a function that:

  • takes a guaranteed minimum sequential time to evaluate — even with a million parallel processors, you cannot go faster;
  • produces a proof alongside the output that lets anyone verify correctness in milliseconds.

The concept was formalized in 2018 by Dan Boneh, Joseph Bonneau, Benedikt Bünz, and Ben Fisch, though the core idea of using sequential computation as a timer goes back to Rivest, Shamir, and Wagner's 1996 time-lock puzzle. VDFs add the crucial element of efficient verifiability, turning a time capsule into a cryptographic primitive.

The key insight: some computations are inherently sequential. No matter how many processors you throw at them, each step depends on the previous one. Repeated squaring modulo a large number is the classic example — to compute x2Tx^{2^{T}} you genuinely must square T times in sequence.

Try It: Run and Verify

This demo simulates the core of a VDF based on repeated squaring: starting from an input x, compute x2T mod Nx^{2^{T}} \bmod N by squaring T times in sequence. Each step depends on the previous — no parallelism can help.

<div class="vdf-wrap">
  <div class="panel">
    <div class="row-group">
      <label>Input x <span class="hint-small">(1–99)</span></label>
      <input id="inp-x" type="number" min="1" max="99" value="7" />
    </div>
    <div class="row-group">
      <label>Delay T <span class="hint-small">(steps)</span></label>
      <input id="inp-t" type="range" min="4" max="20" value="10" />
      <span id="t-val">10</span>
    </div>
    <div class="row-group">
      <label>Modulus N</label>
      <span id="mod-n" class="mono">3233</span>
      <span class="hint-small">(= 61 × 53)</span>
    </div>
    <div class="btns">
      <button id="btn-run" type="button">▶ Compute VDF</button>
      <button id="btn-verify" type="button" disabled>✓ Verify</button>
      <button id="btn-reset" type="button" class="ghost">Reset</button>
    </div>
  </div>

  <div class="chain-wrap">
    <div id="chain" class="chain"></div>
  </div>

  <div class="result-panel" id="result-panel" style="display:none">
    <div class="result-row"><span class="lbl">Output y =</span><span id="out-y" class="mono big"></span></div>
    <div class="result-row"><span class="lbl">Proof π =</span><span id="out-pi" class="mono"></span></div>
    <div class="timing">
      <span>Compute: <b id="t-compute">—</b></span>
      <span>Verify:  <b id="t-verify">—</b></span>
    </div>
    <div id="verdict" class="verdict"></div>
  </div>

  <p class="footnote">
    Demo uses N = 3233 (= 61 × 53) — tiny for pedagogy. Real VDFs use 2048-bit RSA groups where knowing the factorization is impossible without the trapdoor.
  </p>
</div>

*, *::before, *::after { box-sizing: border-box; margin: 0; }
body { font-family: system-ui, sans-serif; color: #1a1a2e; background: #f8f9fc; padding: .6rem; }
.vdf-wrap { display: flex; flex-direction: column; gap: .8rem; }

.panel { background: #fff; border: 1px solid #dde3ec; border-radius: 10px; padding: .9rem 1rem; display: flex; flex-direction: column; gap: .55rem; }
.row-group { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; }
label { font-weight: 600; font-size: .85rem; min-width: 6rem; }
.hint-small { font-size: .75rem; color: #888; font-weight: 400; }
input[type=number] { width: 4rem; padding: .25rem .4rem; border: 1px solid #c5ccd8; border-radius: 6px; font: inherit; }
input[type=range] { width: 120px; accent-color: #2563eb; }
.mono { font-family: ui-monospace, monospace; font-size: .9rem; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .3rem; }
button { font: 600 .82rem system-ui; padding: .4rem .85rem; border-radius: 7px; cursor: pointer; border: 1.5px solid #2563eb; background: #2563eb; color: #fff; transition: opacity .15s; }
button:disabled { opacity: .4; cursor: default; }
button.ghost { background: #fff; color: #2563eb; }

.chain-wrap { overflow-x: auto; padding-bottom: .2rem; }
.chain { display: flex; align-items: center; gap: 0; min-height: 2.6rem; }
.step { display: flex; align-items: center; }
.box { background: #e0e7ff; border: 1.5px solid #6366f1; border-radius: 6px; padding: .25rem .45rem;
       font: 600 .78rem ui-monospace, monospace; color: #3730a3; white-space: nowrap;
       opacity: 0; transform: scale(.7); transition: opacity .25s, transform .25s; }
.box.show { opacity: 1; transform: scale(1); }
.box.current { background: #fef08a; border-color: #ca8a04; color: #713f12; }
.box.done { background: #dcfce7; border-color: #16a34a; color: #14532d; }
.arrow { font-size: .8rem; color: #94a3b8; padding: 0 3px; }

.result-panel { background: #fff; border: 1px solid #dde3ec; border-radius: 10px; padding: .9rem 1rem; display: flex; flex-direction: column; gap: .45rem; }
.result-row { display: flex; align-items: baseline; gap: .5rem; }
.lbl { font-size: .8rem; font-weight: 600; color: #555; min-width: 6rem; }
.big { font-size: 1.2rem; color: #1e40af; }
.timing { display: flex; gap: 1.2rem; font-size: .82rem; color: #555; }
.verdict { font-size: .95rem; font-weight: 700; padding: .3rem .5rem; border-radius: 6px; }
.verdict.ok { background: #dcfce7; color: #14532d; }
.verdict.fail { background: #fee2e2; color: #991b1b; }

.footnote { font-size: .75rem; color: #888; line-height: 1.5; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// VDF demo: repeated squaring mod N (pedagogy — N=3233=61×53, tiny but illustrative).
// Compute: y = x^(2^T) mod N  — T sequential squarings, no parallelism possible.
// Proof: π = x^(2^floor(T/2)) mod N  (the midpoint value, a simplified Pietrzak commit).
// Verify: check π^(2^ceil(T/2)) ≡ y (mod N)  — half the squarings, proves correctness.

const N = 3233; // 61 × 53
let state = null; // { y, pi, T, x }

const $ = id => document.getElementById(id);
const tVal = $('t-val');
$('inp-t').addEventListener('input', e => { tVal.textContent = e.target.value; });

function modpow(base, exp, mod) {
  // Iterative square-and-multiply for BigInt
  let result = 1n;
  base = base % mod;
  while (exp > 0n) {
    if (exp % 2n === 1n) result = result * base % mod;
    exp >>= 1n;
    base = base * base % mod;
  }
  return result;
}

function computeVDF(x, T, N) {
  // Sequential squarings: x, x^2, x^4, ..., x^(2^T)
  const steps = [BigInt(x) % BigInt(N)];
  for (let i = 0; i < T; i++) {
    steps.push(steps[steps.length - 1] ** 2n % BigInt(N));
  }
  const y = steps[T];
  // Simplified proof: midpoint commitment π = x^(2^floor(T/2))
  const pi = steps[Math.floor(T / 2)];
  return { y, pi, steps };
}

function verifyVDF(pi, y, T, N) {
  // Verify: π^(2^ceil(T/2)) mod N should equal y
  const halvings = BigInt(Math.ceil(T / 2));
  const exp = 1n << halvings; // 2^ceil(T/2)
  const check = modpow(pi, exp, BigInt(N));
  return check === y;
}

async function runVDF() {
  const x = parseInt($('inp-x').value) || 7;
  const T = parseInt($('inp-t').value) || 10;

  $('btn-run').disabled = true;
  $('btn-verify').disabled = true;
  $('result-panel').style.display = 'none';
  $('verdict').textContent = '';
  $('verdict').className = 'verdict';

  const chain = $('chain');
  chain.innerHTML = '';

  const t0 = performance.now();
  const { y, pi, steps } = computeVDF(x, T, N);
  const computeMs = (performance.now() - t0).toFixed(3);

  // Animate chain
  for (let i = 0; i <= T; i++) {
    const step = document.createElement('div');
    step.className = 'step';
    const box = document.createElement('div');
    box.className = 'box' + (i === T ? ' done' : i === Math.floor(T/2) ? ' current' : '');
    box.textContent = i === 0 ? `x=${steps[0]}` : `x²^${i}=${steps[i]}`;
    box.title = i === Math.floor(T/2) ? 'π (proof midpoint)' : '';
    step.appendChild(box);
    if (i < T) {
      const arr = document.createElement('span');
      arr.className = 'arrow';
      arr.textContent = '→²';
      step.appendChild(arr);
    }
    chain.appendChild(step);
    // Stagger animation
    await new Promise(r => setTimeout(r, Math.max(30, 300 / T)));
    box.classList.add('show');
  }

  state = { y, pi, T, x };

  $('out-y').textContent = y.toString();
  $('out-pi').textContent = `${pi} (= x^(2^${Math.floor(T/2)}) mod ${N})`;
  $('t-compute').textContent = fmt('%computeMs% ms (%T% squarings)', { computeMs: computeMs, T: T });
  $('t-verify').textContent = '—';
  $('result-panel').style.display = 'flex';
  $('btn-run').disabled = false;
  $('btn-verify').disabled = false;
}

function verifyResult() {
  if (!state) return;
  const t0 = performance.now();
  const ok = verifyVDF(state.pi, state.y, state.T, N);
  const verMs = (performance.now() - t0).toFixed(3);
  $('t-verify').textContent = fmt('%verMs% ms (%ceil% squarings)', { verMs: verMs, ceil: Math.ceil(state.T / 2) });
  const v = $('verdict');
  v.className = 'verdict ' + (ok ? 'ok' : 'fail');
  v.textContent = ok
    ? fmt('✓ Verified! π^(2^%ceil%) ≡ %y% (mod %N%)', { ceil: Math.ceil(state.T/2), y: state.y, N: N })
    : '✗ Verification failed — output is incorrect.';
}

function reset() {
  state = null;
  $('chain').innerHTML = '';
  $('result-panel').style.display = 'none';
  $('verdict').textContent = '';
  $('btn-verify').disabled = true;
}

$('btn-run').addEventListener('click', runVDF);
$('btn-verify').addEventListener('click', verifyResult);
$('btn-reset').addEventListener('click', reset);

// Auto-run on load
runVDF();
Result
Console

Notice the asymmetry. Computing takes T sequential squarings — you can watch each step tick by. Verifying uses a compact proof and checks the answer in a single operation, many times faster. This gap is the whole point: the prover spent real time, but the verifier doesn't have to.

The Real Complexity

What makes a VDF hard to speed up, and easy to verify?

The computation side — sequential squaring: The standard construction computes x2T mod Nx^{2^T} \bmod N where N=p⋅qN = p \cdot q is an RSA modulus whose factorization is secret. To jump ahead in the squaring chain, you would need to know φ(N)=(p−1)(q−1)\varphi(N) = (p-1)(q-1), which lets you reduce the exponent. Without knowing p and q, you are stuck squaring one step at a time. This is the sequential squaring assumption, conjectured to hold since Rivest, Shamir, and Wagner (1996).

The verification side — Pietrzak's proof: Krzysztof Pietrzak (2018) and Wesolowski (2018) independently found ways to prove the result is correct without re-running all T steps. The key idea: the prover commits to an intermediate value at the halfway point, and a recursive argument (or a single modular proof in Wesolowski's scheme) convinces the verifier in O(log⁡T)O(\log T) or O(1)O(1) group operations respectively.

What class does this belong to? VDFs sit in the intersection of cryptography and complexity theory. The hardness is not NP-hardness — it is a sequential hardness assumption. The function is not inherently hard in total work; it is hard because of the dependency chain. This is distinct from the problems in P vs NP and closer in spirit to problems in the class SC (space-efficient sequential computation). The assumption is that no parallel algorithm running in T1−εT^{1-\varepsilon} sequential time (with any amount of space) can compute x2T mod Nx^{2^T} \bmod N.

The status as of 2024: the sequential squaring assumption is widely believed but unproven. It has resisted attack for nearly 30 years. Breaking it would require either factoring N (which breaks RSA) or finding a fundamentally new parallel algorithm for iterated squaring — neither known.

Where It Matters

The ability to prove that real sequential time was spent — and verify it cheaply — unlocks several protocols that were impossible or trusted-party-dependent before:

  • Randomness beacons: Ethereum's proof-of-stake uses a VDF in its design to prevent validators from biasing the random seed for block proposer selection. Because the VDF output isn't known until T seconds after the input is fixed, no validator can grind their way to a favorable result.
  • Leader election: In some consensus protocols, the next block producer is determined by a VDF applied to the previous block hash. Nobody knows the winner in advance, and nobody can become winner faster by buying more hardware.
  • Time-lock puzzles and sealed-bid auctions: A bid can be encrypted with a VDF puzzle — it unlocks automatically after the bidding period, with no trusted party holding the key.
  • Proof-of-elapsed-time: VDFs provide a software alternative to trusted hardware (like Intel SGX) for proving that a node waited the required time before acting.
  • Verifiable randomness for games and lotteries: Any application needing public, unmanipulable randomness — from on-chain games to fair NFT mints — benefits from VDF-based beacons.

The discrete logarithm and factoring problems underpin the security of the RSA groups VDFs commonly use. If those assumptions break — for example via a large-scale quantum computer running Shor's algorithm — VDF constructions would need to migrate to post-quantum groups.

Conclusion

Verifiable Delay Functions solve a subtle problem that turns out to matter enormously: how do you prove that time passed without trusting anyone? The answer is a function whose computation chain cannot be parallelized, paired with a proof that lets anyone check the answer almost instantly.

The gap between sequential hardness and parallel ease is the engine of VDFs. It is not about complexity classes like NP — it is about the irreducible structure of dependency chains. Some computations simply must be done one step at a time, and that constraint, properly packaged, becomes a cryptographic stopwatch.

VDFs are now active ingredients in blockchain consensus protocols, randomness beacons, and sealed-bid auctions. They let decentralized systems enforce time the same way cryptographic hash functions enforce one-wayness: not by trusting an authority, but by making the alternative computationally impossible.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/verifiable-delay-functions/Content licensed under CC BY-NC 4.0.