Post-quantum VDF challenge (draft!) === The VDF Alliance is looking for a team to design and implement a concretely-efficient post-quantum prover system for certain Sloth-like delay statements. Such a prover system would yield a concretely-efficient post-quantum VDF which may be used by L1 projects such as Cosmos, Ethereum, Filecoin, Tezos as well as L2 applications. ### Delay function The delay function is the following Python `delay` function. ```python p = 3*2**124 + 3*2**96 + 2**64 + 1 def cube_root(n): return pow(n, (2*p - 1)//3, p) def round(x): return [cube_root(x[0] + x[1]), (x[1] + 1) % p] def delay(x, difficulty): for _ in range(difficulty): x = round(x) return x ``` *Note*: A different prime `p` may be used if `p > 2**125` and `p % 3 == 2`. ### Delay hardware The delay hardware is a USB stick fitted with an ASIC implementing the delay function where: * **round latency**—every `round` takes 64ns (i.e. sequential modular squarings take ~0.5ns) * **intermediate outputs**—every `2**24`th `round` output is streamed to the host in real time *Note*: The delay hardware is not yet manufactured and may be simulated by precomputing `2**24`th `round` outputs and reading the appropriate output every `2**24 * 64ns` (~1s). ### Delay statements A delay statement is a statement of the form `delay(input, difficulty) == output` where `input` and `output` are pairs of non-negative integers less than `p` and `difficulty` is a non-negative integer. We restrict ourselves to delay statements where: * **delay range**—`2**28 <= difficulty <= 2**42` (~17s to ~3d delay range) * **delay granularity**—`difficulty % 2**24 == 0` (~1s delay granularity) ### Delay proofs A delay proof is a non-interactive argument for a delay statement. We require: * **quantum soundness**—at least 80 bits of provable soundness in the non-programmable quantum random oracle model * **classical soundness**—at least 120 bits of provable soundness in the non-programmable random oracle model * **proof size**—at most 200kB proof size * **verification time**—at most 20ms verification time on a Raspberry Pi 4 Model B (single thread, no overclocking) *Note*: Neither zero knowledge nor knowledge soundness are required. *Note*: SHA256 may be assumed to be an ideal 256-bit hash function and may be used to instantiate a 256-bit random oracle in a Fiat-Shamir transformation. Further, random oracle queries heuristically instantiated by SHA256 calls may be arithmetised in a recursive verifier circuit, e.g. as done in [Halo Infinite](https://eprint.iacr.org/2020/1536.pdf). No other cryptographic assumption or heuristic may be used. ### Prover system A prover system is a prover rig with prover software producing delay proofs for `1 <= u <= 8` always-active delay hardware units. The challenge is to design and implement a prover system where: * **commodity hardware**—the prover rig is built from off-the-shelf commodity hardware and requires little assembly * **low latency**—delay proofs are produced with a latency (relative to the delay function output produced by the delay hardware) of: * at most 10% of the delay time if `difficulty >= 2**36` * at most 20% of the delay time if `difficulty >= 2**32` * at most 40% of the delay time if `difficulty >= 2**28` * **permissive licensing**—the prover software is open-sourced under the Apache 2.0 license