Class Group VDF

A Class Group VDF is a function that requires a specified number of sequential squarings within a class group of an imaginary quadratic field. This structure ensures the computation cannot be parallelized, creating a verifiable time delay. The output includes a proof that can be verified much faster than it was generated, providing a trustless proof of elapsed time.

The Chia blockchain uses a Class Group VDF as the "Time" in its Proof of Space and Time (PoST) consensus. Farmers with provable storage (Proof of Space) become eligible to win blocks. A VDF then imposes a mandatory delay between these eligibility proofs, ensuring block times are consistent and preventing grinding attacks, making the chain more secure and decentralized than pure Proof of Work.

Class Group VDFs are a core component of unbiasable randomness beacons. In protocols like Randstorm, a VDF is applied to a high-entropy seed (e.g., from a commit-reveal scheme or BLS threshold signature). The mandatory delay prevents the last participant from manipulating the final output, as they cannot compute the VDF result faster than anyone else. This produces publicly verifiable, unpredictable randomness for smart contracts and lotteries.

Class Group VDFs are contrasted with RSA-based VDFs (e.g., Wesolowski, Pietrzak). Key differentiators include:

• Quantum Resistance: Relies on the hardness of computing class numbers, believed to be post-quantum secure.
• Succinct Proofs: Generates very small, constant-sized proofs.
• No Trusted Setup: Unlike RSA groups which require a trusted prime generation, class groups are setup-free. The trade-off is that computation can be slower than optimally configured RSA VDFs.

Efficient implementation requires optimized algorithms for composition and reduction of binary quadratic forms within the class group. Key challenges include:

• Minimizing the overhead of the reduction step after each squaring.
• Ensuring the discriminant is chosen to guarantee a large, cyclic class group.
• Hardware acceleration for the sequential squaring operation, which is a core bottleneck. Projects like Chia invest heavily in optimized VDF client software.

The security of a Class Group VDF rests on two main computational assumptions:

1. Sequentiality: That the repeated squaring operation cannot be meaningfully parallelized.
2. Soundness: That the class group order (the class number) is unknown and difficult to compute. Knowing the group order would allow for shortcutting the delay. The trust model is minimal, requiring only that the initial discriminant parameters are correctly generated to form a suitable group.

A critical assumption is the correct generation of the public parameters, specifically the discriminant. This process must:

• Generate a fundamental discriminant of sufficient size.
• Ensure the discriminant's class number is not trivially small.
• Securely discard the factorization of the discriminant during setup. If the setup is compromised (e.g., the factorization is leaked), an adversary could compute the VDF output instantly, breaking the delay property. This necessitates a trusted setup ceremony or novel setup-free constructions.

Security requires a clear separation between two properties:

• Sequentiality (Hardness): The evaluation of the VDF must take a prescribed number of sequential steps. The class group assumption guarantees that no algorithm, even with many parallel processors, can compute the output significantly faster.
• Verifiability (Easiness): The proof that the output is correct must be efficiently and quickly verifiable by anyone. This is typically achieved via a Wesolowski or Pietrzak proof, which relies on different cryptographic assumptions (like the Adaptive Root Assumption).

A key security goal is unpredictable, unbiasable randomness. The VDF design must prevent:

• Parallel Speedup: The iterative squaring operation in the class group should have no shortcut, forcing a strict sequential chain of operations.
• Precomputation Attacks: An adversary should not be able to precompute future outputs before the input (e.g., a block hash) is known. The security model assumes the input is unpredictable until the VDF evaluation begins.

Practical security depends on a correct and robust implementation. Key risks include:

• Algorithmic Errors: Incorrect group operation logic can break sequentiality or verifiability.
• Side-Channel Attacks: Timing or power analysis on the sequential squaring loop could leak internal state.
• DoS via Verification: While verification is fast, it is not free; systems must guard against spam with invalid proofs.

Class group VDFs make different trade-offs than the more common RSA-based VDFs:

• Post-Quantum Security: Based on problems (class group structure) believed to be hard for quantum computers, unlike RSA factorization.
• Setup Requirement: Requires a trusted setup to generate the discriminant, whereas RSA VDFs can use a publicly verifiable modulus (like the RSA UFO).
• Group Size: Class group elements have more compact representations than RSA groups for equivalent security levels, improving efficiency.

RSA groups are the multiplicative group of integers modulo a product of two large primes (n = p*q). They were the first candidate structure proposed for constructing VDFs, as repeated squaring in this group is inherently sequential. However, their security relies on the factoring assumption, and they require a trusted setup to generate the modulus n, which is a significant drawback for decentralized applications compared to class groups.

A time-lock puzzle is a cryptographic problem designed to be solvable only after a specific amount of sequential computation has been performed. VDFs are a special, publicly verifiable type of time-lock puzzle. While time-lock puzzles can be constructed for private messages (e.g., "encrypt this so it can only be decrypted in 10 years"), VDFs produce a public output that anyone can efficiently verify was computed correctly after the time delay.

The sequentiality assumption is the computational hardness assumption that underpins VDFs and time-lock puzzles. It posits that for a specific function (like repeated squaring in a class group), there is no algorithm that can compute the output significantly faster than a sequential computation, even with massive parallelism. This is distinct from assumptions about reversing a function (one-wayness) and is crucial for proving that the imposed delay is robust.

A randomness beacon is a service that produces publicly verifiable, unpredictable, and unbiasable random values at regular intervals. VDFs are a core component in constructing decentralized beacons (e.g., Drand). They are used to add a mandatory time delay between the commitment and revelation of random values, preventing last-revealer bias and ensuring the output cannot be predicted or manipulated before it is published.

Proof of Sequential Work (PoSW) is a protocol where a prover demonstrates they have performed a specific amount of sequential computation. A VDF naturally generates such a proof. PoSW is used in blockchain consensus mechanisms like Chia's Proof of Space and Time, where it acts as the "Time" component, ensuring blocks are produced at consistent intervals regardless of the total network space committed, preventing grinding attacks.