VDFs Are Impossible in the Random Oracle Model → Research

A close-up view reveals a modern device featuring a translucent blue casing and a prominent brushed metallic surface. The blue component, with its smooth, rounded contours, rests on a lighter, possibly silver-toned base, suggesting a sophisticated piece of technology

A sleek, silver-framed device features a large, faceted blue crystal on one side and an exposed mechanical watch movement on the other, resting on a light grey surface. The crystal sits above a stack of coins, while the watch mechanism is integrated into a dark, recessed panel

Briefing

This foundational paper rigorously demonstrates the impossibility of constructing Verifiable Delay Functions (VDFs) within the Random Oracle Model, specifically for black-box constructions that maintain tight sequentiality. VDFs are critical cryptographic primitives designed to ensure a guaranteed, long sequential computation time while enabling efficient, public verification of the output, finding applications in decentralized randomness generation and blockchain efficiency. The core breakthrough is a definitive negative result, establishing that such VDFs cannot be realized under these widely accepted theoretical assumptions. This finding necessitates a re-evaluation of VDF design principles and their integration into future blockchain architectures, guiding researchers towards alternative construction paradigms or different underlying security models to achieve desired properties.

A central, white toroidal shape intersects a cluster of blue, crystalline structures, surrounded by luminous white spheres encased in transparent, faceted shells. This abstract representation visualizes a sophisticated cryptographic nexus, likely symbolizing the core architecture of a decentralized ledger technology DLT or a distributed autonomous organization DAO

Context

Before this research, Verifiable Delay Functions (VDFs) were conceived as a promising solution to several foundational problems in decentralized systems, including the generation of unbiased, publicly verifiable randomness and enhancing the efficiency of resource-constrained blockchains. The prevailing theoretical challenge centered on establishing robust, provable security for VDFs, often assuming their constructibility from standard cryptographic primitives within models like the Random Oracle Model. The academic community sought constructions that offered tight sequentiality → meaning the computation time was inherently long and resistant to parallelization → while maintaining efficient verifiability, without a definitive understanding of their fundamental limits in idealized cryptographic settings.

A futuristic, deer-like head, constructed from clear blue material with intricate internal components, is partially covered in white, fluffy, snow-like texture. A branched, white antler extends from the head, and a reflective silver sphere floats nearby against a dark background

Analysis

The paper’s core mechanism involves a rigorous impossibility proof within the Random Oracle Model. A Verifiable Delay Function (VDF) is a cryptographic function requiring a long, sequential computation, but whose output is quickly and publicly verifiable. The breakthrough demonstrates that any black-box construction of a VDF from a random oracle, where the evaluation time is tightly bound to the sequentiality parameter, is inherently impossible.

This fundamentally differs from previous approaches that focused on constructing VDFs; instead, this work establishes a theoretical boundary, showing that certain desired properties of VDFs cannot be achieved under these specific, idealized conditions. The proof likely employs advanced oracle-presampling techniques to show that any prover attempting to shortcut the delay in the random oracle model would contradict the model’s properties, or any verifier could not distinguish a valid proof from a false one without incurring the full delay itself.

The image features a detailed close-up of intertwined, tubular structures. One prominent element is translucent deep blue, revealing internal circuit-like patterns and small, embedded metallic rectangular components, while other structures are smooth, reflective silver

Parameters

Core Concept → Verifiable Delay Functions (VDFs)
Cryptographic Model → Random Oracle Model
Key Finding → Impossibility of Black-Box Construction
Authors → Ziyi Guan, Artur Riazanov, Weiqiang Yuan
Publication Venue → Crypto 2025 (to appear)

An intricate, abstract structure composed of numerous interconnected blue and silver electronic components, resembling circuit boards and microchips, forms a dynamic three-dimensional entity against a soft grey background. The complex arrangement of these metallic and vibrant blue elements creates a high-tech, futuristic visual with varying depths of field

Outlook

This research opens new avenues for theoretical inquiry, compelling the cryptographic community to explore alternative models beyond the Random Oracle Model or to devise non-black-box constructions for VDFs. In the next 3-5 years, this could lead to the development of VDFs based on specific number-theoretic assumptions, or to hybrid constructions that leverage different cryptographic primitives. Potential real-world applications could shift towards VDFs with slightly relaxed “tightness” requirements or those designed for specific, constrained environments where the Random Oracle Model’s limitations do not apply. This work will undoubtedly influence the foundational understanding and design of future decentralized systems requiring provable sequential computation, pushing innovation in areas like unbiased randomness beacons and more robust proof-of-stake mechanisms.

The image presents a striking visual of a transparent cubic structure, resembling a quantum processor or qubit, embedded within a complex, crystalline formation of electric blue. This formation is intricately detailed with circuit board pathways, indicative of advanced digital infrastructure

Verdict

This research delivers a decisive theoretical constraint, fundamentally reshaping the foundational understanding of Verifiable Delay Functions and guiding future cryptographic design away from provably impossible constructions.

Signal Acquired from → eprint.iacr.org