Open VDF: VDF Proof Techniques

One of the most important aspects of VDFs is that the delay and randomness they provide is efficiently verifiable. To do this, VDF evaluators generate a small proof that can be quickly verified to prove correctness of the VDF evaluation. This blog post looks at the two main proof generation schemes, namely Wesolowski and Pietrzak, as well as a hybrid system. This study evaluates the complexity, performance, and parallelism in these VDF proof algorithms, and provides performance estimates assuming a ~3ns ASIC-based VDF evaluator and a GPU-based prover. From our evaluation we estimate that a GPU Prover can produce a proof with less than 15% overhead for 1-Wesolowski proofs, and <1% for 3-Wesolowski proofs. However, we find that a series of serial operations in the proof generation limits this to about 25% overhead for 1-Wesolowski.

Proof Types

There are two algorithms that can be used to generate RSA VDF proofs, one from Wesolowski and one from Pietrzak. The Wesolowski proof has higher computational cost to generate but produces smaller proofs with constant and cheap verification time. The Pietrzak proof has lower computational cost but produces larger proofs with variable and longer verification time. Since Wesolowski has improved characteristics for a blockchain setting we’ll start by analyzing it, and then consider whether Pietrzak can or should play a role.

Wesolowski Prover

The Wesolowski VDF is described in depth by Benjamin Wesolowski in his 2018 paper ‘Efficient verifiable delay functions’. For the purpose of this study we will focus on versions of this VDF prover algorithm that are optimized for parallelism as described by Argon Design. To do this we implemented several versions of the algorithms and counted the number of group operations, both total as well as the serial operations that are part of the final portion of the algorithm. The following chart shows operations for the VDF evaluator and several prover approaches:

• VDF Evaluation: — Evaluating a VDF function: g^(2ᵗ) for t = 2²³
• Long Division: — The straightforward approach described by Wesolowski
• Argon Alg1 (or Wesolowski Alg5): — The optimized approach described by Wesolowski and later refined by Argon
• Argon Alg4: — A further optimized approach by Argon

The long division approach is surprisingly expensive, however, as noted by Wesolowski, it’s cost is between t and 2t:

“First, we mention a very simple algorithm to compute π, which simply computes the long division [2ᵗ /ℓ] on the fly, as pointed out by Boneh, Bünz and Fisch, but requires between t and 2t group operations.”

Argon Algorithm #4 Explained

In Argon Algorithm #4 there are two expensive parts, both of which involve operations in the RSA group.

The first is what we’ll call ‘A(b) product generation’, which consists of generating the products of each row of a two dimensional “A” array, which contain references to intermediate values from the VDF evaluation (Ci):

The second component is the series of multiplies to generate the proof (“x”) using the A(b) product results:

For now we’re setting aside the cost of get_block since they are only 256 bit operations, and assume that we can keep it out of the critical path. Note that if you simply call get_block as written in the Wesolowski paper it is quite suboptimal. Significant performance improvements come from refactoring the algorithm to make it iterative.

The overall cost of the algorithm, as stated by Argon, is 𝜏/k+l2ᵏ, where the cost for A(b) products is 𝜏/k and the cost for proof generation is l2ᵏ.

Pietrzak Prover

After analyzing the Wesolowski algorithm requirements, we next took a look at the relative performance of the Pietrzak proof. This second approach to generating VDF proofs is from Pietrzak’s 2018 paper ‘Simple Verifiable Delay Functions’. The high level tradeoffs between the two approaches are shown in the following table:

For the typical blockchain application the tradeoffs generally favor Wesolowski. The proofs must be verified by many validators and therefore low verification cost is paramount.

The following chart shows the relative proof generation and verification costs by counting group operations in the Chia Inkfish implementation for T=2,000,000 for 1-Pietrzak and 1-Wesolowski using Weslowski’s Algorithm #5.

Absolute numbers for the above chart are shown in the following table:

Hybrid Prover

Another option to consider is a hybrid proof approach with a small number of Pietrzak iterations that reduce the total cost of proof generation and enable prover hardware to be shared across more evaluators.

To evaluate this we compared a 2-iteration Wesolowski proof to a 2-iteration ‘hybrid’ proof (one round of Pietrzak followed by one round of Wesolowski). The chart and table are for t=2⁴¹ and delta=8.

Applied Performance Estimates

In this analysis we combine a modified script based on the estimation script from Benjamin Wesolowski along with GPU performance benchmarks to identify more optimal prover settings and estimate the real world performance.

For 1-Wesolowski:

For N-Wesolowski:

At a high level these results look pretty good, and at 13% overhead, one GPU-based prover could support up to 7.7 ASIC evaluators. However, these results assume the algorithm can be fully parallelized. Due to a series of serial operations in the proof generation, we are limited to about 25% overhead for 1-Wesolowski proofs, meaning each GPU can support 4 ASIC evaluators.

Conclusion

After evaluating the various proof techniques, a one or two Wesolowski proof looks like a good approach for use cases where small proofs and fast verification are important. Our study also suggests that GPU-based provers are capable of providing VDF proofs for ASIC-based VDF evaluators while maintaining relatively low overhead. By using a GPU to generate proofs, VDF systems can be deployed quicker and with a lower development cost. These results also suggest that GPU platforms can provide significant performance improvements for highly-parallel cryptographic operations.

Acknowledgements

We’d like to provide a special acknowledgment to the Tezos Foundation for their support of this work.