Ilmu Komputer & AI editorial
Open AccessOA2026
Fresh-Challenge VDF Attestations for Model-Relative Response Latency
A protocol composition for public, model-relative evidence of sequential computation delay
Ansar Yesmukhanov; Aruzhan Tlessova· 2026· DOI 10.48550/arXiv.2609.12727
The core problem
Can a finite verifier obtain public, model-relative evidence about response latency for sequential computation? The authors, Ansar Yesmukhanov and Aruzhan Tlessova, frame this question around verifiable delay functions (VDFs), which in principle enable such evidence: evaluation requires sequential steps, while verification is efficient in the security parameter and polylogarithmic in the numerical value of for standard constructions. Thus a delay can be astronomically large to evaluate yet succinctly represented and feasibly checked. However, a VDF proof for a chosen message alone is insufficient because it may be precomputed. To address this, the paper specifies and analyzes 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. The contribution is positioned as a protocol/design analysis and benchmarked reference implementation layer, not a new VDF construction or cryptographic primitive. The work sits at the intersection of cryptography, cybersecurity, and network architecture, offering a mechanism for model-relative latency attestation.
Innovation
The benchmark of the public reference implementation confirms the expected empirical separation between evaluation and verification on one documented machine. While specific numerical results are not provided in the abstract, the authors report that the separation aligns with theoretical expectations: evaluation requires sequential steps, whereas verification is efficient in the security parameter and polylogarithmic in . This empirical validation supports the practical feasibility of the FCLA protocol. The security analysis yields a formal result: under the stated assumptions, an accepted FCLA transcript is inconsistent with post-challenge generation by an adversary bounded by a calibrated sequential evaluation rate. The result is model-relative, meaning it holds within the bounded model but does not exclude relaying, outsourcing, or a faster unmodeled machine. The authors also note that the protocol does not identify a named claimant, highlighting the limits of the attestation.
Can a finite verifier obtain public, model-relative evidence about response latency for sequential computation? The authors, Ansar Yesmukhanov and Aruzhan Tlessova, frame this question around verifiable delay functions (VDFs), which in principle enable such evidence: evaluation requires sequential steps, while verification is efficient in the security parameter and polylogarithmic in the numerical value of for standard constructions. Thus a delay can be astronomically large to evaluate yet succinctly represented and feasibly checked. However, a VDF proof for a chosen message alone is insufficient because it may be precomputed. To address this, the paper specifies and analyzes 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. The contribution is positioned as a protocol/design analysis and benchmarked reference implementation layer, not a new VDF construction or cryptographic primitive. The work sits at the intersection of cryptography, cybersecurity, and network architecture, offering a mechanism for model-relative latency attestation.
The FCLA protocol composes several components: a VDF, an unpredictable public challenge source, a message, and independently auditable release and receipt records. The security analysis proceeds under explicit assumptions: VDF sequentiality, the unpredictability of the challenge source, the integrity of witness logs, and a calibrated upper bound on an adversary's sequential evaluation rate. Under these assumptions, an accepted FCLA transcript is inconsistent with post-challenge generation by an adversary in that bounded model. The authors emphasize that the result neither identifies a named claimant nor excludes relaying, outsourcing, or a faster unmodeled machine. A benchmark of the public reference implementation is conducted on one documented machine to confirm the expected empirical separation between evaluation and verification. The protocol flow can be represented as follows:
Why it matters
The FCLA protocol addresses a critical gap in VDF-based attestations: the need to prevent precomputation by binding to a fresh, unpredictable challenge. By incorporating auditable release and receipt records, the protocol enables independent verification of the timing and integrity of the computation. However, the security guarantees are conditional on explicit assumptions, including a calibrated upper bound on the adversary's sequential evaluation rate. This model-relative nature means that the attestation is only as strong as the assumed bounds. The authors acknowledge that the protocol does not exclude relaying or outsourcing, nor does it identify a named claimant, which may limit its applicability in scenarios requiring strong identity binding. The benchmark on a single machine provides initial evidence of the evaluation-verification separation, but broader deployment would require validation across diverse hardware. The contribution is a protocol/design analysis and benchmarked reference implementation layer, not a new VDF construction or cryptographic primitive. Future work could explore stronger assumptions, multi-party challenges, and integration with identity systems. The taxonomy candidates include Architecture, Cybersecurity, Network, and Cryptography, reflecting the interdisciplinary nature of the work.
Who should read this
CS practitioners and researchers
Opening member content…