Briefing
This research resolves a major open problem by formally proving that Verifiable Delay Functions (VDFs) cannot exist in the Random Oracle Model (ROM), the common idealization for hash functions. The breakthrough is a non-existence proof demonstrating that any black-box construction of a VDF from standard primitives, such as one-way functions, can be trivially broken by a fast adversary in the ROM. This finding fundamentally re-architects the security basis for all decentralized systems relying on VDFs for provably fair randomness generation and transaction ordering, compelling them to move away from generic hash function assumptions toward complex, structured number-theoretic assumptions.
Context
Before this work, Verifiable Delay Functions were a critical theoretical tool, designed to enforce a minimum sequential computation time, which is essential for mitigating frontrunning and generating unbiasable public randomness in Proof-of-Stake consensus. The prevailing challenge was to establish their security under the weakest possible, most generic assumptions, specifically the Random Oracle Model, to ensure the primitive’s robustness regardless of the underlying cryptographic functions. The question of whether a black-box VDF construction could be proven secure in this model remained a foundational, unsolved problem in cryptographic theory.
Analysis
The paper’s core mechanism is a proof of impossibility, leveraging advanced oracle-presampling techniques. The logic dictates that a fast-computing adversary, which can query the Random Oracle (idealized hash function) a large number of times, can effectively simulate the VDF’s output much faster than the designated sequential delay time. The adversary’s speed is a function of its query complexity to the oracle, not the sequential computation steps. By showing the adversary can “pre-sample” the oracle’s outputs and use this information to construct a valid proof for a delayed computation in minimal time, the sequentiality property of the VDF is fundamentally violated under the ROM assumption.
Parameters
- Security Model Invalidated → Random Oracle Model (ROM) – The idealized hash function model where the VDF non-existence is proven.
- Primitives Ruled Out → One-Way Functions, One-Way Permutations – Standard cryptographic building blocks from which VDFs cannot be black-box constructed in the ROM.
Outlook
This negative result immediately shifts the research focus for VDFs toward constructions based on structured number-theoretic problems, such as the hardness of finding square roots in hidden order groups, which do not rely on the ROM. In the next three to five years, this will lead to a bifurcation → either protocols will adopt these more complex, non-ROM-based VDFs, or they will abandon VDFs entirely for randomness and fair ordering, driving new research into alternative MEV mitigation and decentralized randomness mechanisms that rely on different, provably secure cryptographic primitives.
Verdict
This non-existence proof is a foundational theoretical correction, forcing a critical re-evaluation of the security assumptions underpinning all Verifiable Delay Function implementations in decentralized systems.
