Wesolowski Proof

A Wesolowski Proof (VDF) is used as a randomness beacon to generate publicly verifiable, unbiasable random numbers. It prevents any participant from predicting or manipulating the output by imposing a mandatory time delay on computation, even with parallel processing.

• Key Property: The output is unpredictable until the slow, sequential computation is complete.
• Example: The drand network uses VDFs to produce verifiable randomness for protocols like Filecoin and Ethereum's beacon chain, securing processes like shard committee assignment.

In Proof-of-Stake (PoS) consensus, VDFs enable secure and fair leader election. They are used to select the next block proposer from a validator set in a way that cannot be accelerated or gamed.

• Mechanism: A VDF is applied to a random seed, creating a delay before the leader is known. This prevents last-revealer attacks where the last validator to reveal their choice can manipulate the outcome.
• Implementation: Chia Network uses VDFs in its Proof-of-Space-and-Time consensus to ensure a minimum time passes between blocks, securing the chain against grinding attacks.

VDFs can augment Proof-of-Work (PoW) by decoupling security from pure energy expenditure. They introduce a mandatory time delay for block production, making certain attacks like selfish mining more difficult.

• Concept: A miner must still solve a PoW puzzle, but the valid solution must also be the input to a slow VDF computation before a block can be published.
• Benefit: This reduces the advantage of miners with access to ASIC boost or other optimizations, as they cannot bypass the fixed-time VDF step, promoting a more level playing field.

Wesolowski Proofs provide a cryptographic timestamping service that is more resource-efficient than Proof-of-Work. They prove that a certain amount of real-world time has passed since an event.

• How it works: A VDF's output serves as a proof that its input (e.g., a document hash) existed before the computation finished.
• Use Case: This enables verifiable delay in decentralized systems for events like governance proposal deadlines, option expiry in DeFi, or proving data existed at a specific prior time without relying on a trusted authority.

The Wesolowski Proof is a specific, efficient construction for a Verifiable Delay Function (VDF). Its core innovation is a succinct, single-round proof that can be verified much faster than it was computed.

• Core Components: It is based on repeated sequential squaring in a group of unknown order (like an RSA group or a class group).
• Advantage: The proof size is constant and verification is fast (logarithmic in the delay time), making it practical for blockchain environments where compact proofs are essential for scalability.

The core security of a VDF relies on the sequentiality assumption: that computing the function requires a specific, non-parallelizable number of sequential steps. This is typically based on the hardness of repeated squaring in a group of unknown order (like an RSA group or a class group). If this assumption is broken—for example, through a novel algorithm that allows parallelization—the proof's security guarantee of elapsed time collapses.

The VDF's soundness depends on the security of the underlying algebraic group. For RSA-based constructions, this requires:

• The RSA assumption to hold (factoring large integers is hard).
• The group order remains unknown to the prover. If the order is discovered, the prover can compute the output without performing the work, breaking the delay.
• Secure, verifiable setup to generate the group parameters without leaking the order.

The Wesolowski Proof is non-interactive and publicly verifiable. Security considerations include:

• Prover Malice: A malicious prover could attempt to provide an incorrect proof. The verification algorithm must be robust against this, efficiently detecting any deviation from the correct computation.
• Verification Speed: Verification must be exponentially faster than the computation itself (typically logarithmic in the time parameter). If verification becomes too costly, the system's practicality is compromised.

The protocol uses a random oracle (modeled by a cryptographic hash function like SHA-256) to generate a random challenge. Security assumptions include:

• The hash function behaves as a true random oracle.
• The generated proof is unique for a given input and time parameter. This prevents a prover from generating multiple proofs and choosing a favorable one (grinding attacks).

Real-world security depends on correct implementation:

• Side-channel attacks: The sequential computation must be constant-time to avoid leaking information through timing or power analysis.
• Parameter selection: The time parameter T and security parameter λ must be chosen to provide sufficient security margins against both classical and quantum attacks.
• Network assumptions: In distributed systems, the security of processes like randomness beacons assumes the VDF computation is not pre-computed before the input is known.

While both prove computational effort, key security differences exist:

• Energy Efficiency: VDFs are designed to be energy-efficient, as the work is not wastefully parallelizable.
• Predictable Timing: VDF delay is deterministic and tunable, unlike PoW's probabilistic finding time.
• Security Foundation: PoW security relies on majority honest hashrate; VDF security relies on cryptographic assumptions and sequential hardness. A broken VDF assumption is a catastrophic failure, whereas PoW security degrades gradually with hashrate loss.

A Verifiable Delay Function (VDF) is a cryptographic primitive that guarantees a computation requires a specific, non-parallelizable amount of elapsed time, yet the result can be verified quickly. The Wesolowski Proof is a specific, efficient proof system that enables this fast verification for VDFs based on repeated squaring in a group of unknown order, such as an RSA group.

• Core Property: Ensures a mandatory time delay, crucial for protocols requiring unbiased randomness or time-based consensus.
• Relation: The Wesolowski Proof is the verification mechanism for a class of VDFs.

Proof of Sequential Work (PoSW) is a protocol that proves a prover has spent a predetermined amount of sequential computational effort. It is built using a Verifiable Delay Function (VDF). The Wesolowski Proof is integral here, as it provides the succinct, efficiently verifiable attestation that the sequential work (the VDF evaluation) was performed correctly, without the verifier redoing the work.

• Application: Used in blockchain consensus and timestamping to prevent grinding attacks.
• Key Role: The Wesolowski Proof makes PoSW practical by enabling lightweight verification.

An RSA group is a multiplicative group of integers modulo (n), where (n) is a product of two large, secret primes. Its unknown order (the totient (\varphi(n))) is central to the security of the VDFs verified by Wesolowski Proofs. The sequential work is typically repeated squaring in this group.

• Security Basis: The prover knows the public modulus (n) but not its factorization, making the computation inherently sequential and hard to shortcut.
• Dependency: The Wesolowski Proof's security relies on the hardness of factoring and the Low Order assumption in such groups.

The Pietrzak VDF is an alternative construction for a verifiable delay function, contemporaneous with the Wesolowski (V)DF. Both use repeated squaring in a group of unknown order but employ different interactive proof systems that are made non-interactive via the Fiat-Shamir heuristic.

• Comparison: While the Wesolowski Proof produces a single, constant-sized proof, the Pietrzak protocol involves a more complex, recursive proof structure.
• Trade-off: Wesolowski Proofs offer simpler verification, while Pietrzak's construction can have smaller proof sizes for very long delay parameters.

The Fiat-Shamir heuristic is a method to convert an interactive public-coin proof system (like the interactive version of the Wesolowski Proof) into a non-interactive one. It replaces the verifier's random challenges with a cryptographic hash of the transcript up to that point.

• Critical Role: This transformation is what allows the Wesolowski Proof to be used in blockchain protocols, as the proof can be published on-chain and verified by anyone without live interaction.
• Standard Practice: Used universally in succinct proofs (zk-SNARKs, etc.) and VDF verification schemes.