Ruling Out Computationally Unique VDFs in the Random Oracle Model
Statement: AI-written, not yet formalized. Proof: human draft, not yet independently reviewed, not yet formalized.
A verifiable delay function takes a long, inherently sequential time to evaluate, can be checked quickly, and has a unique accepted output. Can one be built from nothing but an ideal hash function, modelled as a random oracle, with sequential time measured by the number of rounds of adaptive oracle queries an algorithm needs? The answer is no when uniqueness is perfect, meaning no accepting proof for a wrong output exists at all. What remains open is the standard notion, where wrong outputs with accepting proofs may well exist but no efficient adversary can find one. The conjecture is that the impossibility survives this weakening.
View PDF · LaTeX source · Formal statement — not yet formalized
Let \(\lambda\) be the security parameter and \(T = T(\lambda)\) the time bound. A VDF in the parallel random oracle model is \(\Pi = (\mathsf{Setup}, \mathsf{Eval}, \mathsf{Verify})\), where \(\mathsf{Setup}\) makes at most \(s = s(\lambda,T)\) oracle queries, \(\mathsf{Eval}\) at most \(T\), and \(\mathsf{Verify}\) at most \(t = t(\lambda,T)\). It has perfect completeness (\(\gamma = 0\)) if an honestly produced output and proof always verify.
\(\Pi\) is computationally unique if for every adversary running in time \(\mathrm{poly}(\lambda,T)\), given the public parameters, the probability of outputting \((x, y, \pi)\) where \(\pi\) verifies for \(y\) on \(x\) but \(y\) is not the honest output is negligible — the probability taken over \(\mathsf{Setup}\) and the adversary’s coins, but not over the oracle. Perfect uniqueness is the \(\varepsilon = 0\), computationally unbounded case: no such \((x,y,\pi)\) exists at all.
\(\Pi\) is \(\sigma\)-sequential if no pair \((\mathrm{Adv}_0, \mathrm{Adv}_1)\) with total time \(\mathrm{poly}(\lambda,T)\), where \(\mathrm{Adv}_1\) additionally runs in parallel time at most \(\sigma\), computes the honest output with better than negligible probability.
Conjecture. There is a polynomial \(p\) such that: if \(\Pi\) is a VDF in the parallel random oracle model with perfect completeness and \(\Pi\) is computationally unique, then \(\Pi\) is not \(\sigma\)-sequential for \(\sigma = p(\lambda, s, t)\).
Note what the bound does and does not say. The number of rounds \(p(\lambda,s,t)\) depends only on the query counts of \(\mathsf{Setup}\) and \(\mathsf{Verify}\) — never on \(T\) — so the attack it asserts breaks sequentiality by an unbounded margin as \(T\) grows. Since breaking \(\sigma\)-sequentiality also breaks \(\sigma'\)-sequentiality for every \(\sigma' \ge \sigma\), this is the strongest form of the conclusion.
Sources
- Mahmoody, Smith, and Wu. Can Verifiable Delay Functions be Based on Random Oracles?. Cryptology ePrint Archive, Report 2019/663; ICALP 2020.
View PDF — no proof written yet · LaTeX source — no proof written yet · Formal proof — not yet formalized
Resolved. Guan, Riazanov and Yuan, Breaking Verifiable Delay Functions in the Random Oracle Model (ePrint 2024/766, CRYPTO 2025), prove exactly this conjecture — and more. Their Theorem 5.1: any VDF in the ROM with completeness error \(\alpha\) (not just \(\alpha = 0\)) and computational uniqueness admits an adversary breaking \(\sigma\)-sequentiality for \(\sigma = O(q_{\mathsf{Verify}} \cdot q_{\mathsf{Eval}})\) queries in \(O(q_{\mathsf{Verify}})\) rounds — matching this page’s \(s, t, \sigma = p(\lambda, s, t)\) notation term for term (\(q_{\mathsf{Setup}}, q_{\mathsf{Verify}} \leftrightarrow s, t\)), and covering general completeness error, which is strictly more than this page’s perfect-completeness scope asked for.
The perfect-uniqueness case, recalled for contrast. The known 2020 attack simulates the honest evaluation, and after enough simulated executions a majority vote over their outputs recovers the true value — sound only because, under perfect uniqueness, any output that verifies is the honest one.
How the new proof gets around the obstruction this page previously identified. The 2020 argument breaks under computational uniqueness because a wrong-but-accepted output may exist and simply be hard to find, so simulated executions can agree on one and the vote proves nothing. Guan–Riazanov–Yuan’s fix does not sharpen that counting argument; it changes the mechanism. They pair the sequentiality-breaking adversary with a second, explicit adversary that — whenever two of the simulated executions disagree on their (accepting) output for the same input — directly is a uniqueness-breaking witness, since two different accepting outputs for one input is exactly what computational uniqueness forbids. So the proof no longer needs “no wrong output exists” for its vote to be meaningful; a disagreement is now a win condition in its own right rather than something the argument has to rule out. This is the “different mechanism” this page’s Discussion previously said a proof was likely to need.
Adaptive vs. non-adaptive uniqueness — checked, no mismatch. The paper (Remark 3.5) works with a non-adaptive uniqueness notion — the adversary is handed a fixed input \(x\) rather than choosing it — and states plainly that this is deliberate: “since our focus in this paper is on impossibility results, we work with non-adaptive uniqueness, which implies stronger impossibility results compared to their adaptive analogues.” Non-adaptive uniqueness is the easier property for a scheme to have, so ruling out every non-adaptively-unique sequential VDF rules out every adaptively-unique one too (adaptive uniqueness implies non-adaptive uniqueness). This page’s own conjecture, like MSW20’s, uses the standard (adaptive) notion — covered a fortiori.
The tight regime, recalled for contrast. With no uniqueness assumption at all, no VDF is \(\sigma\)-sequential for \(\sigma > T(1 - 1/2(s+t))\), or for \(\sigma = T - T^{\rho}\) — a different, sequentiality-close-to-\(T\) regime that the new result doesn’t need to touch, since it now covers the regime this conjecture was actually about directly.
This was the source paper’s own “main open question remaining” — and per its own abstract, Guan–Riazanov–Yuan’s paper “resolves the open question of whether verifiable delay functions (VDFs) can be constructed in the random oracle model,” closing it as impossible. Computational uniqueness was what the definition of a VDF actually requires, so this closes the question of whether VDFs can be based on ideal hash functions at all in the non-tight regime, not just the strengthened perfect-uniqueness variant the original 2020 result needed to make its proof work.
A companion paper, Abusalah, Azari, Kamath, Tairi and von Consbruch, Impossibility of VDFs in the ROM: The Complete Picture (ePrint 2025/1773), extends the impossibility further, to computationally expensive private-coin setup — closing a gap the first paper left open (which was restricted to public-coin setup). It has been skimmed at the framing level here but not read with the same depth as the primary result; see Open obligations.
The interesting feature, in hindsight, is that the 2020 obstruction really was definitional rather than a counting shortfall: the fix needed a mechanism that certifies disagreement as a uniqueness break in its own right, not a sharper charging argument over how many simulated executions can differ from the real one.