Random Number on Blockchain using VDF — 2

Wesolowski and Pietrzak’s VDFs

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
2. Two Practical VDFs: Wesolowski and Pietrazak’s VDFs (v)
3. Random Number Game: Commit-Reveal-Recover Using VDFs

Introduction

In our previous article, we introduced the concept of Verifiable Delay Functions (VDFs). These functions are designed to guarantee that a particular computation takes a certain amount of time but can be verified quickly once completed. Such properties make VDFs crucial for secure random number generation on blockchains.

However, a limitation was pointed out: the simplified VDF scheme needs a verifier to have access to a secret value for Proof-of-Exponentiation (PoE), a constraint not always practical in transparent, decentralized systems.

This is where the advances by Wesolowski [1] and Pietrazak [2]’s VDFs come into play. They developed VDFs that can be validated by anyone, even without knowledge of the secret value. In this article, we focus on how their VDFs handle Proof-of-Exponentiation efficiently.

For those who might need to brush up on the foundational concepts of VDFs, our introductory article provides a comprehensive overview. For a deep and rigorous understanding into the mathematical intricacies and limitations of these VDFs, Wesolowski and Pietrazak’s original papers [1, 2], as well as Dan Boneh’s Analysis on them [3], are recommended reads.

Photo by National Cancer Institute on Unsplash

One key insight shared across both VDF models is the emphasis on presenting a challenge to the Prover, underscoring the robustness of the verification process without the knowledge of secret values. To construct non-interactive VDFs, we can skip the challenge communication using Fiat-Shamir heuristic. But this is not under the coverage of this article. With this context set, let’s step into the mechanics of Wesolowski and Pietrazak’s VDFs.

Wesolowski’s Approach: A Prime Number Challenge

The below figure presents how Wesolowski’s VDF works. The key step is the challenge using a prime number l. The verifier samples a prime number to challenge the prover. The prover uses this prime number as a divider to construct a proper proof. Then, with this proof, the verifier can efficiently verify the VDF proof.

The Wesolowski’s VDF in Detail:

Value check:

• Right at the start, the verifier checks the submitted VDF outputs. It ensures that both g and ℎ are genuine members of the group G.
• If not, the verifier is straightforward — it outputs reject and stops the protocol.

Random Prime Challenge:

• The verifier takes a random prime, denoted as l
• This prime is then sent over to the prover

Prover’s Response:

• Upon receiving the prime, it calculates q and r such that the equation 2^T =ql+r holds.
• The prover then computes π, given by g^q, and sends it to the verifier.

Final Verification:

• The verifier calculates r using the equation r = 2^T mod l.
• If π is an element of G and the equation h=π^l × g^r holds within G, the verifier outputs accept. Else, it’s a reject.

In summary, Wesolowski’s VDF can verify a submitted VDF evaluation using a prime challenge. This scheme offers a simpler and shorter proof compared to Pietrzak’s VDF, which will be explained next. However, it does not guarantee the implementation of Wesolowski’s VDF is more efficient on the blockchain. Firstly, if we implement this protocol, it may require a hash-to-prime function that searches for a prime on blockchain. Secondly, the performance test of a research shows Wesolowski’s VDF is not beneficial relatively.

Pietrzak’s Approach: Halving Protocol

The below figure presents how a part of Pietrzak’s VDF works. And this is called a halving protocol. With the halving protocol, the prover and the verifier can reduce the exponent of the problem they want to confirm. Specifically, they obtain a Proof-of-Exponentiation problem scaled down by half, and they repeat this process until the exponent T reaches 1. As a result, a verifier can verify that the all the Proof-of-Exponentiation process is correct by performing a single square operation.

The Pietrzak’s VDF in Detail:

Pietrzak proposes a layered approach to the VDF problem. The protocol operates as follows when given a tuple (G, g, h, T):

# Halving protocol for T > 1

Prover’s Computation:

• The prover calculates v = g(2^(T/2)) and sends this value v to the verifier

Verifier’s Initial Check:

• The verifier sends the prover a random challenge r

Next Input Calculation and Repeat:

• Both entities compute g1​ = g^r v and ℎ1​ = v^r h within G.
• Subsequently, the prover and verifier recursively engage in an interactive proof for (G, g1​ ,h1​ ,T/2) to ensure that ℎ1​ equals g1(2^(T/2))​ within group G.

# Halving procotol for T =1

Finally, if T equals 1, the verifier directly checks if ℎ is equivalent to g² within group G.

• The verifier then outputs accept if the equation holds true or reject otherwise and terminates the protocol.

In summary, Pietrzak’s mechanism uses a recursive approach to verify the proof-of-exponentiation by the halving protocol. Finally, the number of repeatations is log₂T and the length of proof is log₂T. Compared to the Wesolowski’s approach where the length of the proof is 1, it takes a longer time and has a longer proof. However, considering the experimental results of implementations to be described later and the fact that a mechanism that requires significant operations such as a hash-to-prime function is not needed, it can be considered practical in the blockchain.

Performance Comparison

The aforementioned mechanism does not directly show which VDF is more efficient or practical. Of course, there are pros and cons. One important aspect to consider for us is performance. According to the implementation result of Attias et al., “Implementation Study of Two Verifiable Delay Functions,” Tokenomics 2020, we can compare the two VDFs in the below table:

In the table, t is the time parameter for VDFs, λ is the security parameter, and s is the number of cores. For generation of a VDF proof, some operations can be handled in parallel. When λ = 2048 implicates RSA 2048, the VDFs provide enough security environment. Therefore, I compared the two VDFs with it. In summary, the Pietrzak’s VDF is more advantageous for proof generation and verification. However, we should consider that the Pietrazak’s long proof length can burden your network.

Concluding Remarks on Assumptions and Open Problems

Before we finish, I would like to emphasize that the VDF mechanism relies on several mathematical and cryptographic assumptions. Two main premises stand out. The first is the RSW (Rivest, Shamir, Wagner) assumption, which posits that exponentiation operations occur serially. The second involves the Fiat-Shamir heuristic; when we structure a non-interactive VDF using it, we rely on the random oracle model.

Additionally, we’ve scarcely discussed group G where these operations take place, but challenges persist there too. Who initially determines the specifics of group G? Such a decision-maker might access the secret value “order” of group G that facilitates efficient operations. A pivotal technique is devising a way to create a group G without the knowledge of its order. This problem is very mathematically complicated, but if you’re interested, I recommend that you look at the provided references below.

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] B. Wesolowski. “Efficient verifiable delay functions.” Advances in Cryptology–EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19–23, 2019, Proceedings, Part III 38. Springer International Publishing, 2019.
[2] K. Pietrzak. “Simple verifiable delay functions.” 10th innovations in theoretical computer science conference (itcs 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
[3] D. Boneh, B. Bünz, and B. Fisch. “A survey of two verifiable delay functions.” Cryptology ePrint Archive (2018).
[4] Attias et al., “Implementation Study of Two Verifiable Delay Functions,” Tokenomics 2020