Summary
The paper looks at how to prove that a certain amount of time was genuinely spent computing something in a way that others can verify quickly. While Verifiable Delay Functions (VDFs) can show a delay took place, just having a proof isn't enough because someone could prepare it in advance. The authors introduce Fresh-Challenge VDF Attestations, which tie the proof to a new unpredictable challenge and records of when the messages were sent and received. This method helps ensure that no one could have created the proof after seeing the challenge, as long as certain technical assumptions hold. They also provide a tested implementation showing that checking these proofs is much faster than creating them.
What this means in practice
- •For blockchain developers: Add verified delay attestations to blockchain transactions to provide publicly checkable proofs of computational latency tied to fresh challenges.
- •For distributed systems engineers: Use fresh-challenge VDF attestations to verify timing guarantees for sequential operations in distributed protocols under known adversary bounds.
Abstract
Can a finite verifier obtain public, model-relative evidence about response latency for sequential computation? Verifiable delay functions (VDFs) make this possible in principle: evaluation requires T sequential steps, whereas verification is efficient in the security parameter and polylogarithmic in the numerical value of T for standard constructions. Thus a delay can be astronomically large to evaluate yet succinctly represented and feasibly checked. A VDF proof for a chosen message alone is insufficient because it may be precomputed. We specify and analyze Fresh-Challenge VDF Attestations (FCLA), a protocol composition that binds a VDF to an unpredictable public challenge, a message, and independently auditable release and receipt records. Under explicit assumptions about VDF sequentiality, the challenge source, witness logs, and a calibrated upper bound on an adversary's sequential evaluation rate, an accepted FCLA transcript is inconsistent with post-challenge generation by an adversary in that bounded model. The result neither identifies a named claimant nor excludes relaying, outsourcing, or a faster unmodeled machine. A benchmark of the public reference implementation confirms the expected empirical separation between evaluation and verification on one documented machine. Our contribution is a protocol/design analysis and benchmarked reference implementation layer, not a new VDF construction or cryptographic primitive.