Random Number on Blockchain using VDF —1
An Introduction to Verifiable Delay Functions
Author
Suhyeon Lee (Security researcher, Tokamak Network)
Reviewed by Jake Jang and Jamie Judd
Random Number on Blockchain Using VDF Series
1. An Introduction to Verifiable Delay Functions (v)
2. Two Practical VDFs: Wesolowski and Pietrazak’s VDFs
3. Random Number Game: Commit-Reveal-Recover Using VDFs
Introduction
Blockchain, a technology underpinning cryptocurrencies, thrives on algorithms that foster trust and fairness in a decentralized environment. With the criticality of timing and verifiability in blockchain processes, Verifiable Delay Functions (VDFs) have emerged as a pivotal cryptographic tool, ensuring that specific computations are inherently time-bound yet efficiently verifiable.
Why VDFs are important? They ensure that specific processes last a set amount of time, regardless of computational resources. For example, this property can replace the energy-consuming Proof of Work (PoW) systems with the more efficient Proof of Delay (PoD), reducing the environmental impact of blockchain mining. When you compete to be a block proposer with a VDF using sequential computation, you don’t need a huge parallel computing power. Furthermore, you don’t need to make a mining pool.
VDFs delay time until the result is obtained. In other words, VDF can be used when you want to create a value that no one can find out in advance. In this regard, another key application of VDFs in the blockchain is secure random number generation, vital for activities ranging from lotteries to consensus mechanisms.
A Glimpse into Random Number Generation using VDFs
How are the verifiable delay and the random number generation related? Of course, the delay does not directly generate a random number. Rather, the verifiable delay helps to generate a random number securely. We didn’t see how VDFs work but let’s suppose there are VDFs which can force participants delayed calculation outputs.
One way to generate a random number in a distributed system is a commit-reveal game. Participants secretly generate a secret number, submit a random number’s processed value like hash (commit). After all the commits, the participants open their secret numbers (reveal). Participants can check a secret number matches to the revealed value. Finally, participants can generate a random number in a distributed way by hashing all the revealed secret numbers together.
However, what happens if a participant does not reveal the random number? The game does not proceed. Suppose that there is a VDF to open another participant’s secret number. Then we can wait participants to reveal secret numbers and if not, we can reveal the secret numbers using VDFs. As it is a VDF, we can make participants unable to reveal secret numbers before the reveal phase ends.
In this context, this series of articles navigates through the concept of utilizing VDFs for secure random number generation on blockchain. This series aims to explain a commit-reveal-recover scheme to generate a random number securely using VDFs. The technological nuances and contexts of VDFs might be less familiar territories for some. Therefore, let’s begin the exploration of VDF with revisiting its predecessor, the time-lock puzzle.
Hint to VDFs: Time-Lock Puzzles using Hash Chains
Time-lock puzzles, an innovative concept initially proposed in the 1996 paper, “Time-Lock Puzzles and Timed-Release Crypto” by Rivest, Shamir, and Wagner, introduce a compelling conundrum: enforcing a strict, unavoidable computational time delay [1].
hash(x) → hash(hash(x)) → hash(hash(hash(x))) → …
Imagine you are given a hash function, and your task is to compute the repeated hash of an initial input, say for a million iterations, where each step is computationally dependent on its predecessor, thus creating a sequential cascade of calculations. This mathematical puzzle compels a genuine expenditure of time but lacks a quick verification mechanism. To be practical, VDFs require an efficient verification mechanism as well as a time-lock mechanism. Therefore, VDFs essentially need:
- Delay: A sequential function that can’t be computed in parallel
- Verifiability: A verification function that can verify the computed result efficiently
Bridging to VDFs: Enforcing Time and Ensuring Swift Verification
VDFs build on this foundation by providing a computationally intense task that requires a specific time to solve, coupled with a proof that allows efficient verification of the solution’s correctness. To explain, let’s examine a simplistic, RSA-inspired example of a VDF in a cryptographic interaction between a Prover and a Verifier.
SetUp (Verifier):
- Select two large primes p and q, compute n = p × q, and share n with the Prover, keeping p and q concealed.
- Challenge the Prover to compute y = g^(2^t) mod n.
Computation (Prover’s Challenge):
- Calculating y is computationally challenging without knowledge of p and q
- Sequential computation: g² = g×g → g⁴ = g² × g² → g⁸ = g⁴ × g⁴ → … t interation … → y
- This calculation is based on the RSW assumption
Ref. The RSW Assumption
A critical contemplation is the RSW (Rivest, Shamir, Wagner) assumption, propounding that evaluating y = g^(2^t) mod n mandates t sequential squaring operations and cannot be expedited significantly, serving as a keystone in both mechanisms.
Verification (Verifier’s Check):
- Knowing p, q, and therefore ϕ(n), Euler’s totient function ϕ(n) which is (p-1)×(q-1) in this case, the Verifier can authenticate the Prover’s output swiftly, ensuring correctness without repeating the extensive computation.
- Using the Euler’s theorem, g^(2^t) ≡ g^(2^t mod ϕ(n)) mod n
Ref. Euler’s theorem. a^ϕ(n) ≡ 1 mod n
where ϕ(n) is Euler’s totient function, this theorem lays fundamental in number theory and cryptographic applications, permitting efficient modular exponentiation calculations.
What Lies Ahead: Towards Practical VDF Mechanisms
Unfortunately, the simple VDF above is not practical for blockchain. It is because there needs a secret value, which is the Euler’s totient function. Indeed, when it comes to an integer multiplicative group denoted (Z/nZ), the Euler’s totient function outputs the order of the group. The verifier must know the order of the group to verify any VDF submissions. We can think about a core requirements for VDFs to be practical.
- There exists an efficient verification mechanism to verify a VDF submission without knowledge of any secret value
Consequently, anyone can play the role of a verifier. Furthermore, the VDF game can proceed even if the secret value remains unknown to all participants.
The subsequent pieces of this series will draw us deeper into cryptographic realms of VDFs through the advanced mechanisms of VDFs, particularly those articulated by Wesolowski and Pietrzak, and then the commit-reveal-recover scheme for random number generation on blockchain will be introduced.
Acknowledgement
This article was crafted as part of Tokamak Network’s R&D endeavors. We at Tokamak Network are committed to advancing blockchain technologies to the best of our abilities.
Reference
1. R. L. Rivest, A. Shamir, and D. A. Wagner, “Time-lock puzzles and timed-release Crypto,” 1996. [Online]. Available: https://people.csail.mit.edu/rivest/pubs/RSW96.pdf.
