What is a Verifiable Delay Function? Rule 30 and STARK proofs

A Verifiable Delay Function, or VDF, is a cryptographic primitive that takes a set amount of sequential time to compute, but whose result anyone can check quickly. Dan Boneh, Joseph Bonneau, Benedikt Bünz, and Ben Fisch defined it that way in 2018 (CRYPTO 2018 / IACR ePrint 2018/601): a VDF requires a specified number of sequential steps to evaluate, yet produces a unique output that can be efficiently and publicly verified.

The important part of that definition is the asymmetry. Evaluation has to take a specified number of sequential steps — work that should not speed up just because you have more machines. Verification should be fast, public, and unique: given the input and parameters, there is one correct output, and anyone can check a proof of it without rerunning the delay.

That combination matters when a system needs time to pass, and needs a proof that it actually passed. The applications Boneh and coauthors listed are still the ones people reach for: public randomness beacons, leader election in consensus protocols, and proofs of replication. On Ethereum research forums, Justin Drake's 2018 note "Minimal VDF randomness beacon" is a standard reference for the randomness-beacon case (https://ethresear.ch/t/minimal-vdf-randomness-beacon/3566). If a block producer can grind on a random value, they can bias the outcome. A VDF makes the delay long enough that the value is revealed only after it is too late to manipulate.

Two early constructions, by Benjamin Wesolowski and by Krzysztof Pietrzak, use repeated squaring in a group of unknown order. Those are the textbook VDFs. They are not the only approach.

STARK-based VDFs already exist in the literature and in earlier deployments. StarkWare's VeeDo is a STARK-based VDF; it was discussed as running on Ethereum mainnet around 2020. On ethresear.ch, the threads "Stark-based VDFs" (https://ethresear.ch/t/stark-based-vdfs/8052) and "Hash-based VDFs, MiMC and STARKs" (https://ethresear.ch/t/hash-based-vdfs-mimc-and-starks/2337) laid out how a transparent, hash-based proof system can attest that a delay function was evaluated correctly, without a trusted setup. That "transparent" property is one reason people look at STARKs for this job: some group-based VDFs need a setup whose trapdoor has to be discarded; a STARK does not. Rule 30 VDF sits in that family of work. It is not the first STARK-based VDF.

The delay function in Rule 30 VDF is Wolfram's Rule 30 cellular automaton, run on a periodic ring. Rule 30 is an elementary cellular automaton Stephen Wolfram introduced in the 1980s. It is simple to write down and, after decades of study, still has no known general shortcut for predicting a future state without stepping through the evolution. Evaluation is sequential: each step depends on the previous state. The hardness claim is a conjecture, not a theorem. It rests on the long-studied idea that Rule 30 is computationally irreducible — that there is no general shortcut to the state after T steps besides running the rule. I do not claim a security reduction to a standard assumption such as factoring, and I do not claim this hardness is proven.

Verification uses STARK proofs (Scalable Transparent Arguments of Knowledge) via the open-source Winterfell library, version 0.13. A STARK lets a verifier check that a trace satisfies the Rule 30 constraints without replaying every step. STARKs are transparent: there is no trusted setup. They rely on hash-function assumptions. People often describe that as a post-quantum property under those hash assumptions. That is a property of the proof system, not a blanket label that "Rule 30 VDF is a post-quantum VDF."

The repository is a working, tested, unaudited research prototype, written in Rust: https://github.com/igor-holt/rule30-vdf

I published a benchmark table in the README from a documented machine: an Intel Xeon KVM guest, 4 vCPU at 2.4 GHz, 15.6 GiB RAM. On that run, median verification was 0.52–0.83 milliseconds across delays of 1,024 to 65,536 trace rows. Proof generation is much more expensive than verification, as you would expect, and the numbers will move on a different machine. The harness is in the repo so others can reproduce the measurement.

I want to be explicit about what this is not. It is not the first STARK-based VDF; VeeDo and the ethresear.ch threads already occupy that ground. It is not an audited product. It is not a zkVM. It is one open construction — Wolfram's Rule 30 cellular automaton for the delay, STARK proofs for verification — that I am hardening, benchmarking, and documenting, including through a public Manifund project: https://manifund.org/projects/rule-30-vdf--harden-benchmark-document

If you want the definition, start with Boneh et al. 2018. If you want prior STARK VDF work, start with VeeDo and those ethresear.ch threads. If you want this particular construction, the code and the measured numbers are in the Rule 30 VDF repo.

Igor Holt is the founder of Kovach Enterprises (founded 2015) and Genesis Conductor (started 2025), an independent, bootstrapped studio in Pasadena, Maryland.

• Rule 30 VDF: https://github.com/igor-holt/rule30-vdf
• ORCID: https://orcid.org/0009-0008-8389-1297
• X: https://x.com/holt_igor
• Website: https://kovachenterprises.com