Random Number on Blockchain using VDF — 3
Random Number Game: Commit-Reveal-Recover Using VDFs
Author
Suhyeon Lee (Security researcher, Tokamak Network)
Reviewed by
Random Number on Blockchain Using VDF Series
1. An Introduction to Verifiable Delay Functions
2. Two Practical VDFs: Wesolowski and Pietrazak’s VDFs
3. Random Number Game: Commit-Reveal-Recover Using VDFs (v)
Introduction
In this article, we’ll dive into the Commit-Reveal-Recover, a methodology to safely generate random numbers in the blockchain. If you’ve followed our series, I recommend you to read our previous articles. The first article introduced the foundational concepts of Verifiable Delay Functions (VDFs), and the second shed light on the intricate workings of practical VDFs. We will base this discussion on the understanding of VDF concepts from our previous articles.
Recap: Commit-Reveal
We started the first article by introducing a random number generation using the Commit-Reveal scheme which is also used in Ethereum Randao. At its core, the Commit-Reveal mechanism involves participants generating secret values and subsequently publishing its processed value using a one-way function like hash). After a specific deadline, they reveal the original secret inputs so that we can simply construct a random value using the fixed inputs.
In this process, there’s a simple and critical security issue. If the random number is to be constructed through this, or even if it is unknown, the action of combining random numbers does not serve their interests, the participants may simply not disclose the secret value.
To deter such behavior, some blockchain implementations mandate a deposit. If participants refrain from revealing, they incur a penalty. Yet, even with this safeguard, there exists a ‘non-reveal’ strategy (often termed a “suicidal attack”), which may prevent random number generation in that session. This limitation paved the way for the Commit-Reveal-Recover scheme, a robust extension.
To understand Commit-Reveal-Recover, our focus now shifts to Bicorn-RX [1], a cutting-edge Commit-Reveal-Recover algorithm utilizing VDFs, known for its blockchain applicability.
Commit-Reveal-Recover Example: Bicorn-RX
Bicorn-RX is claimed the most practical among the three algorithms introduced in the Bicorn paper, while not ideal in terms of gas costs for blockchain operations. It has less user interaction and computational simplicity. The algorithm’s intricacies and associated security proofs are covered in-depth in the original paper [1].
Here’s a simplified explanation with the above figure:
Setup
Create a group and its generator. Then, register a value ‘h’ derived from the exponentiation operation g^(2^T), aimed at a desired delay, T. This ‘h’ plays a pivotal role in recovering the eventual random number. For reference, the Bicorn paper employs the QR+ group to satisfy the low-order assumption.
Commit
Participants generate secret numbers (a), perform an exponentiation operation (g^a), and submit the resultant value (c) by a specified Deadline, T1.
Reveal
By Deadline T2, participants reveal their original secret numbers (a). In the optimistic case, if all adhere to the reveal, a collective random number (Ω) is derived using simple exponentiation, fortified with a value b* to thwart reverse computations by potential adversaries.
Recovery (Pessimistic case)
If a participant abstains from the reveal by Deadline T2, the algorithm, through a 2^T exponentiation operation, can still ascertain the random number (Ω). The proof-of-exponentiation for the recovery value is submitted and should be verified on blockchain.
In summary, Bicorn-RX requires participants to submit two times for the optimistic random number generation. Even if no participants reveal their secret numbers, one honest participant can recover the collective random number after the sequential computation. Also, as this is using VDF, this sequential computation takes time but not lots of computation power.
Open Problems
Through our three-article series, we’ve explored why Commit-Reveal-Recover is one of the significant techniques for randomness generation in the blockchain, what is the role of VDF in this context, and examined a viable algorithm for actual blockchain use. Lastly, we aim to conclude by introducing related open problems:
- Optimization: Current Commit-reveal-recover schemes utilizing VDFs require at least one or two deadlines. This setup introduces a delay, impeding the immediate generation of random numbers. It’s vital to stress that in real-world scenarios, such delays can significantly impact the responsiveness of the blockchain services.
- Reward and Punishment: Beyond the simple “Commit-Reveal” system where only non-revealing participants face a reduction in their deposit, the “Commit-reveal-recover” mechanism introduces added complexities. It’s not just about penalizing non-revealing users; it’s also about adequately rewarding those who participate in the recovery process. Determining fair and incentive-compatible reward structures for these participants is a pivotal challenge.
- Time Delay Adjustment: The time delay of VDFs is not same for the all participants (CPU). As CPU capabilities enhance over time, the value of T might need adjustments to ensure that the VDF remains effective. This constant evolution highlights the need for a more stable benchmark. Recognizing this, there are efforts underway to develop ASIC chips specifically tailored for VDFs, aiming to establish a consistent standard across the board.
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] K. Choi, et al. “Bicorn: An optimistically efficient distributed randomness beacon.” Cryptology ePrint Archive (2023).
