VDF

This project entails the implementation of a Verifiable Delay Function (VDF). Its main function is to generate a new VDF by providing specific public parameters and the corresponding proof upon completion of the computation. There are two alternative proofs to be considered as mentioned in the project proposal: the Group Exponentiation Proof [Pietrzak’18] and the Proof [Wesolowski’18]. Since the two methods are similar, the project only implements the Wesolowski’18 version. Besides the RSA group, the class group is also considered a good choice to be implemented this time.

Implementation

1. The VDF function: given a specific public parameter, calculate the output and generate a corresponding proof.

   1. RSA Group

      RSA groups are groups of the form (Z/NZ)*, the generation of which is similar to the RSA encryption method. The obvious problem is that N should be generated by the trusted party to avoid the leakage of p and q [1].

   2. Class Group

      Class groups can be generated without a trusted setup. This project implements a binary quadratic form according to Chia Network [2]. The class group has the same initial element for the squaring (a=1, b=1) with a size of 1024 discriminant.

2. VDF proof: Wesolowski’18.

Details

The repo has 5 files: main.py, ClassGroup.py, RSAGroup.py, VDF.py, and PrimeUtils.

1. main.py

Unit Tests for VDF with RSA group and Class group by test_rsa_group() and test_class_group() functions respectively.

2. ClassGroup[2]

The class group has a more complicated structure compared to the RSA group. Similar to integer multiplication in the RSA group, the class group use compose () method instead to compose two from f1, and f2 into f3. Therefore, square(f1) is actually composed of f1 with f1. The difference is that compose() needs to use the Linear congruence algorithm and the extended Euclidean algorithm to achieve the functionality.

3. RSAGroup

Provide $Power(base, T, N)$ methods to calculate $ \text{base}^T%N.$

4. VDF

The main functions of VDF, include eval(), prove(), and verify().

5. PrimeUtils

Offer utility functions of generating prime using the Miller-Rabin prime test.