Introduction

Imagine a lottery where the organizer draws a winning number, and you have no way to tell whether the draw was fair or rigged. Now imagine a lottery where the organizer draws a number and hands you a cryptographic receipt that proves — beyond any doubt — that the number came from a secret key applied honestly to today's date. That is precisely what a Verifiable Random Function delivers.

A VRF is built from a secret key (held by one party) and a proof algorithm. Given any input — a block hash, a round number, a user ID — the holder of the secret key computes two things: a pseudorandom output and a short proof. Anyone who holds the corresponding public key can verify the proof in milliseconds, confirming that the output was computed correctly, without learning anything about the secret key itself.

The guarantee is two-sided. Uniqueness: there is exactly one valid output for each (key, input) pair — the key-holder cannot fish for a favorable result. Unpredictability: without the secret key, the output is computationally indistinguishable from a uniformly random string, even if you watch thousands of other VRF evaluations.

VRFs were introduced by Silvio Micali, Michael Rabin, and Salil Vadhan in 1999 and have since become the building block of choice wherever you need randomness that is both unpredictable and publicly auditable.

Try It

The demo below simulates a VRF built on elliptic-curve arithmetic (simplified to small integers for visibility). A private key is generated once; the corresponding public key is shown. Type any input string, press Evaluate, and the VRF computes a pseudorandom hash together with a proof. Press Verify to confirm the proof checks out — then try changing a single character in the proof and watch verification fail.

<p class="hint">A toy VRF built on a small prime-order group. The <b>private key</b> is generated once; the <b>public key</b> is its group exponent. Type any input, press <b>Evaluate</b> to get a pseudorandom output + proof, then press <b>Verify</b> to confirm it. Tamper with the proof bytes to watch verification fail.</p>

<div class="key-row">
  <span class="label">Private key (secret)</span>
  <span id="sk" class="mono secret">—</span>
  <button id="newkey" type="button" class="ghost">New key</button>
</div>
<div class="key-row">
  <span class="label">Public key</span>
  <span id="pk" class="mono">—</span>
</div>

<div class="input-row">
  <label for="inp">Input string</label>
  <input id="inp" type="text" value="block-42" maxlength="40" />
  <button id="eval" type="button">Evaluate</button>
</div>

<div id="result" class="result hidden">
  <div class="res-row">
    <span class="label">VRF output (hex)</span>
    <span id="vrf-out" class="mono"></span>
  </div>
  <div class="res-row">
    <span class="label">Proof (editable)</span>
    <input id="proof" class="mono proof-input" type="text" />
  </div>
  <div class="btn-row">
    <button id="verify" type="button">Verify</button>
    <button id="tamper" type="button" class="ghost">Tamper proof</button>
  </div>
  <div id="status" class="status"></div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 15px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .9rem; line-height: 1.5; }
.mono { font-family: ui-monospace, monospace; font-size: .82rem; word-break: break-all; }
.secret { color: #c0392b; }
.label { font-size: .8rem; color: #555; display: block; margin-bottom: 2px; }
.key-row { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap;
           background: #f3f6f9; border: 1px solid #dde4ec; border-radius: 8px;
           padding: .5rem .75rem; margin-bottom: .5rem; }
.key-row .label { margin: 0; width: 130px; flex-shrink: 0; }
.key-row .mono { flex: 1; }
.input-row { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap;
             margin: .75rem 0; }
.input-row label { font-size: .8rem; color: #555; white-space: nowrap; }
.input-row input { flex: 1; min-width: 120px; padding: .4rem .6rem;
                   border: 1px solid #ccd4de; border-radius: 6px;
                   font: 14px ui-monospace, monospace; }
.result { background: #f9fbfc; border: 1px solid #dde4ec; border-radius: 10px;
          padding: .75rem 1rem; margin-top: .5rem; }
.result.hidden { display: none; }
.res-row { margin-bottom: .6rem; }
.proof-input { width: 100%; padding: .4rem .6rem; border: 1px solid #ccd4de;
               border-radius: 6px; font: 13px ui-monospace, monospace; }
.btn-row { display: flex; gap: .5rem; flex-wrap: wrap; margin: .5rem 0; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: .95rem; font-weight: 700; min-height: 1.4em; padding: .35rem 0; }
.status.ok  { color: #0a7d33; }
.status.bad { color: #c92f3c; }

// ── Toy VRF over a small prime-order group ──────────────────────────────────
// Group: Z_p* with generator g=2, prime p=7919 (order q = p-1 = 7918, but we work mod p for exponentiation).  This is a pedagogical simplification; real VRFs use large elliptic-curve groups.
// This is a pedagogical simplification; real VRFs use large elliptic-curve groups.
//
// VRF_eval(sk, alpha):
//   1. h  = H_to_group(alpha)       map input to group element
//   2. gamma = h^sk  mod p           the VRF "hash point"
//   3. beta  = SHA256-like(gamma)    the pseudorandom output bytes
//   4. proof = Schnorr-like NIZKPoK that log_h(gamma) == log_g(pk)
//      k     = random nonce
//      U     = g^k mod p
//      V     = h^k mod p
//      c     = H(g, h, pk, gamma, U, V)  (challenge, mod q)
//      s     = (k - sk*c) mod q
//      proof = (c, s)
//
// VRF_verify(pk, alpha, beta, proof):
//   1. h     = H_to_group(alpha)
//   2. gamma = beta source  (we embed gamma in beta for this toy)
//   3. U'    = g^s * pk^c mod p
//   4. V'    = h^s * gamma^c mod p
//   5. c'    = H(g, h, pk, gamma, U', V')
//   6. accept iff c' == c  AND  beta == H(gamma)

const P = 7919n;
const G = 2n;
const Q = P - 1n; // group order (P-1 for Z_p*)

function modpow(base, exp, mod) {
  let result = 1n;
  base = ((base % mod) + mod) % mod;
  while (exp > 0n) {
    if (exp & 1n) result = result * base % mod;
    base = base * base % mod;
    exp >>= 1n;
  }
  return result;
}

// Tiny deterministic "hash" into Z_q (nonzero) — FNV-1a variant
function hashToZq(str) {
  let h = 2166136261n;
  for (let i = 0; i < str.length; i++) {
    h ^= BigInt(str.charCodeAt(i));
    h = (h * 16777619n) & 0xFFFFFFFFn;
  }
  h = h % (Q - 1n) + 1n; // in [1, Q-1]
  return h;
}

// Map an input string to a group element (nonzero, not 1)
function H_to_group(alpha) {
  let v = hashToZq('htg:' + alpha);
  let h = (v * v) % P; // always nonzero in Z_p*
  if (h === 1n) h = G;
  return h;
}

// Schnorr challenge
function challenge(g, h, pk, gamma, U, V) {
  const s = [g, h, pk, gamma, U, V].join(',');
  return hashToZq('chal:' + s) % Q;
}

// Pseudorandom output from gamma (16 bytes as hex)
function vrfBeta(gamma) {
  let v = hashToZq('beta:' + gamma.toString());
  let hex = '';
  for (let i = 0; i < 16; i++) {
    v = (v * 6364136223846793005n + 1442695040888963407n) & 0xFFFFFFFFFFFFFFFFn;
    hex += ((Number(v >> 56n) & 0xff)).toString(16).padStart(2,'0');
  }
  return hex;
}

let SK = 0n, PK = 0n;

function genKey() {
  SK = hashToZq('sk:' + Math.random().toString() + Date.now());
  PK = modpow(G, SK, P);
  document.getElementById('sk').textContent = SK.toString();
  document.getElementById('pk').textContent = PK.toString();
  document.getElementById('result').classList.add('hidden');
  document.getElementById('status').textContent = '';
}

function vrfEval(alpha) {
  const h     = H_to_group(alpha);
  const gamma = modpow(h, SK, P);
  const beta  = vrfBeta(gamma);

  // Schnorr NIZKPoK
  const k = hashToZq('nonce:' + SK.toString() + alpha + Math.random());
  const U = modpow(G, k, P);
  const V = modpow(h, k, P);
  const c = challenge(G, h, PK, gamma, U, V);
  const s = ((k - SK * c) % Q + Q) % Q;

  return { beta, gamma, c, s };
}

function vrfVerify(pk, alpha, beta, proofStr) {
  let c, s;
  try {
    const parts = proofStr.split(',');
    if (parts.length !== 2) return false;
    c = BigInt(parts[0].trim());
    s = BigInt(parts[1].trim());
    if (c <= 0n || s <= 0n || c >= Q || s >= Q) return false;
  } catch { return false; }

  const h     = H_to_group(alpha);

  // Recover gamma from beta by solving: beta == vrfBeta(gamma).
  // In this toy, beta embeds gamma directly in the proof string as 3rd field. We encode gamma in the proof as "c,s,gamma" so verifier can recompute.
  const proofParts = proofStr.split(',');
  if (proofParts.length !== 3) return false;
  let gamma;
  try { gamma = BigInt(proofParts[2].trim()); } catch { return false; }
  if (gamma <= 0n || gamma >= P) return false;

  // Check beta matches gamma
  const expectedBeta = vrfBeta(gamma);
  if (expectedBeta !== beta) return false;

  // Recompute U', V'
  const U2 = modpow(G, s, P) * modpow(pk, c, P) % P;
  const V2 = modpow(h, s, P) * modpow(gamma, c, P) % P;
  const c2 = challenge(G, h, pk, gamma, U2, V2);

  return c2 === c;
}

document.getElementById('newkey').addEventListener('click', genKey);

document.getElementById('eval').addEventListener('click', () => {
  if (SK === 0n) { alert('Generate a key first.'); return; }
  const alpha = document.getElementById('inp').value.trim() || 'block-42';
  const { beta, gamma, c, s } = vrfEval(alpha);
  const proofStr = c.toString() + ',' + s.toString() + ',' + gamma.toString();
  document.getElementById('vrf-out').textContent = beta;
  document.getElementById('proof').value = proofStr;
  document.getElementById('result').classList.remove('hidden');
  const st = document.getElementById('status');
  st.textContent = 'Evaluated. Press Verify to check the proof.';
  st.className = 'status';
  console.log('VRF eval | alpha:', alpha, '| beta:', beta, '| c:', c.toString(), '| s:', s.toString(), '| gamma:', gamma.toString());
});

document.getElementById('verify').addEventListener('click', () => {
  const alpha  = document.getElementById('inp').value.trim() || 'block-42';
  const beta   = document.getElementById('vrf-out').textContent;
  const proof  = document.getElementById('proof').value.trim();
  const ok     = vrfVerify(PK, alpha, beta, proof);
  const st     = document.getElementById('status');
  if (ok) {
    st.textContent = '✓ Proof valid — output was computed honestly from the private key.';
    st.className = 'status ok';
  } else {
    st.textContent = '✗ Proof invalid — the proof does not match the public key or output.';
    st.className = 'status bad';
  }
  console.log('VRF verify | alpha:', alpha, '| ok:', ok);
});

document.getElementById('tamper').addEventListener('click', () => {
  const el = document.getElementById('proof');
  const v  = el.value;
  // Flip one digit in the proof string
  const idx = Math.floor(v.length / 3);
  const ch  = v[idx];
  const replacement = ch === '9' ? '0' : String.fromCharCode(ch.charCodeAt(0) + 1);
  el.value = v.slice(0, idx) + replacement + v.slice(idx + 1);
  const st = document.getElementById('status');
  st.textContent = 'Proof tampered — now try Verify.';
  st.className = 'status';
});

// Auto-generate a key on load
genKey();
Result
Console

Notice the key properties at work. Determinism: the same (key, input) always produces the same output. Uniqueness: only the private key could have produced that proof — the public key is enough to catch any forgery. Pseudorandomness: the output bytes look like noise; nothing in the public key or prior outputs lets you predict what comes next.

The Real Complexity

VRFs do not live in the NP-hardness world — their security is proven under number-theoretic hardness assumptions that are widely believed but not formally equivalent to P ≠ NP.

  • Decisional Diffie-Hellman (DDH): the most common VRF constructions rely on the assumption that, given (g, gag^{a}, gbg^{b}, gcg^{c}) in a group, it is computationally infeasible to decide whether c = ab. Break DDH and you break elliptic-curve VRFs like the one in RFC 9381.
  • RSA hardness: older VRF constructions (Micali–Rabin–Vadhan 1999) require factoring or RSA inversion to be hard.
  • Quantum vulnerability: both DDH-based and RSA-based VRFs are broken by Shor's algorithm on a sufficiently large quantum computer. Post-quantum VRF designs based on lattice problems (Learning With Errors) are an active research direction.
  • Evaluation is efficient: computing a VRF output and proof is O(1)O(1) elliptic-curve operations — fast enough to use in every DNS response or blockchain transaction.
  • Verification is also efficient: checking the proof is equally fast, making VRFs practical for any system that needs public auditability.

The status: VRFs are a solved engineering problem in the classical (pre-quantum) setting, standardized in RFC 9381 (2023). Their security rests on well-studied assumptions, and multiple constant-time implementations exist. The open frontier is post-quantum VRFs.

Where It Matters

Anywhere a single party must generate randomness that others need to trust, a VRF replaces blind faith with a cryptographic guarantee:

  • Blockchain randomness beacons: Ethereum's RANDAO, Algorand, Cardano, and Solana all use VRF-based mechanisms to select block proposers and validators. A miner cannot manipulate the outcome because the VRF output is uniquely determined by their private key — cheating would require breaking the underlying hardness assumption.
  • DNSSEC authenticated denial: the NSEC3 record in DNSSEC uses a VRF-like hash to prove that a domain does not exist without leaking the full zone. This closes the zone-enumeration attack that plagued earlier NSEC records.
  • Leader election in consensus protocols: Algorand's Byzantine Agreement uses each participant's VRF to privately and verifiably determine whether they are selected as a committee member for the current round — eliminating targeted denial-of-service attacks against known future leaders.
  • On-chain lotteries and NFT minting: smart contracts can use a VRF oracle (e.g., Chainlink VRF) to pick winners or assign rare traits, giving users a verifiable audit trail instead of trusting the contract deployer.
  • Key derivation: VRFs can derive per-context pseudorandom keys from a master secret while proving to auditors that the derivation was rule-compliant — useful in hardware security modules.

VRFs sit at the intersection of discrete logarithm hardness and practical cryptography, making them one of the most versatile tools in modern protocol design.

Conclusion

Randomness has always been easy to fake and hard to verify. A die throw, a coin flip, a lottery drum — none of them come with a proof of fairness. Verifiable Random Functions change that: for the first time, a single party can generate randomness that is simultaneously unpredictable (no one can game the output in advance) and publicly verifiable (anyone can confirm it was computed honestly).

The construction is elegant: a secret key maps each input to a unique pseudorandom output, and a short proof lets the public key act as a witness. Break the proof and you break DDH or RSA — the same hardness that protects most of the internet today.

From DNSSEC zone authentication to Algorand's leader election to on-chain NFT lotteries, VRFs are quietly ensuring that "trust me, it was random" is no longer good enough. The math insists on a receipt — and that receipt is unforgeable.

As quantum computing matures, the VRF story is not over: post-quantum variants based on lattice problems are coming, carrying the same promise into a world where Shor's algorithm threatens the classical foundations.

Share this article

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

Comments

Loading comments...

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