TL;DR
This paper introduces Verifiable Delay Functions (VDFs), a new cryptographic primitive that requires a specific amount of sequential time to compute but can be verified very quickly. VDFs are crucial for building more robust decentralized systems, like secure randomness beacons and leader election mechanisms, by preventing adversaries from manipulating outcomes through speedups.
What Problem Does This Paper Address?
Imagine a lottery system that relies on a random number generated from a public source, like stock prices. A sophisticated attacker, like a high-frequency trader, could subtly manipulate these prices in the final moments before the random number is determined, biasing the lottery in their favor. To prevent this, we need a way to ensure that generating the random number takes a significant, fixed amount of time, making it impossible for an attacker to influence the outcome after the fact. This is where Verifiable Delay Functions (VDFs) come in. They act like a cryptographic "time lock" for computation: it takes a guaranteed amount of time to compute the result, but anyone can quickly check that the computation was indeed performed correctly.
Methods
The paper formalizes the concept of a VDF, defining it as a triple of algorithms: Setup, Eval, and Verify.
Setup: Generates public parameters.Eval: Takes an input and computes a unique output along with a short proof, requiring a specific sequential timet.Verify: Efficiently checks the output and proof, taking only polylogarithmic time.
The authors propose several candidate constructions for VDFs, including:
- A theoretical VDF based on Incrementally Verifiable Computation (IVC), which uses SNARKs (Succinct Non-Interactive Arguments of Knowledge).
- A construction based on injective polynomials over algebraic sets, which are hard to invert.
- A practical efficiency boost for IVC-based VDFs using time-asymmetric encodings.
- A VDF secure against bounded pre-computation attacks using exponentiation in groups of unknown order.
They also introduce the notion of "weak VDFs" which allow for more parallelism in the evaluation phase.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- The Need for "Slow" Computation: VDFs are essential for applications where a guaranteed, non-manipulable delay is critical, such as in preventing front-running or ensuring fair randomness.
- The "Exponential Gap": The core innovation is achieving an "exponential gap" between the time it takes to compute a VDF and the time it takes to verify it. This gap is what makes VDFs practical for real-world use.
- Formalizing Security: The paper rigorously defines the security properties of VDFs, particularly "σ-sequentiality," which ensures that an adversary cannot compute the VDF output in significantly less time than
t, even with parallel processors. - Building Blocks: The authors leverage existing cryptographic tools like SNARKs and IVC, but adapt and combine them in novel ways to construct VDFs.
- Weak VDFs: Recognizing that some applications might tolerate more parallelism in evaluation, the concept of "weak VDFs" is introduced, offering a trade-off.
Key Results
- Formal Definitions: The paper provides the first formal definitions for Verifiable Delay Functions, including their security properties like correctness, soundness, and sequentiality.
- Novel Constructions: The authors present the first candidate constructions for VDFs that achieve an exponential gap between evaluation and verification time.
- Theoretical VDF: A theoretical VDF is constructed using IVC and SNARKs, achieving σ(t) = (1 − ε)t − O(1) sequentiality.
- Weak VDF: A weak VDF is proposed based on injective rational maps, offering a delay parameter of t² and inversion time of t-o(t) with O(t²) processors.
- Practical Improvements: Techniques are presented to significantly boost the efficiency of VDF constructions, offering up to a 7,000-fold improvement in SNARK efficiency compared to naive hash chains.
Limitations and Future Work
- Theoretical Optimality: The paper acknowledges that a theoretically optimal VDF (simple, inherently sequential, low parallelism for computation, fast verification, and post-quantum secure) is still an open research question.
- Trusted Setup: Some constructions may require a trusted setup, which is a common limitation in cryptographic primitives.
- Parameter Sensitivity: The performance and security of some constructions are highly dependent on specific parameters (e.g., the value of
ain VDFvc). - Future Directions: The authors suggest exploring new problems not traditionally used in cryptography for VDF construction, aiming for better efficiency and post-quantum security. They also pose an interesting research question about constructing a "Random Delay Oracle" from a σ-sequential VDF and a random oracle.
Summary updated