# VDF open problems **UPDATE** (November 2018): This list is currently OUTDATED! This document should be revamped soon™. --- Verifiable Delay Functions were [formalised](https://eprint.iacr.org/2018/601.pdf) in June 2018 and several constructions appeared in July/July 2018. This new cryptographic building block has applications to blockchains including randomness beacons (Ethereum 2.0), proofs of space (Chia), and proofs of replication (Filecoin). Below we list VDF open problems of which several are likely low-hanging. See the [VDF reading list](https://notes.ethereum.org/52JZtwErThe9KmN6TNd1lg?both) to get up to speed with the literature. Contact [email protected] for clarifications and feedback on the problems below, and to add problems. ### Groups of unknown order ##### RSA group setup 1. What is the smallest (in bits) nothing-up-my-sleeve safe RSA modulus? 2. What is the weakest definition of a safe RSA modulus? * Current best definition: A number which, after factoring out prime factors of size at most 640 bits, is composite and of size at least 2048 bits. 3. What is the best provable lower bound on the density of safe RSA moduli within the natural numbers? * See [Sander's paper](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.28.4015&rep=rep1&type=pdf) 4. Is it possible to build a provable semiprime without a trusted party? * See [Don Reble's post](http://www.graysage.com/djr/isp.txt) * See [David Broadhurst's post](http://physics.open.ac.uk/~dbroadhu/cert/semgpch.gp) 5. Can we build a probabilistic test for RSA moduli safety? ##### Class groups 1. What is the optimal parallel algorithm for squaring elements in a class group of an imaginary quadratic field? * See [A Survey on IQ Cryptography](http://technopalsmeditech.com/library/download/id=859657&type=stream) * See Chia's algorithm competition 2. Is it safe to not refresh the class group discriminant? * Chia and Dan Boneh have thoughts on this ##### Pietrzak/Wesolowski constructions 1. Are the adaptive root and low order assumptions safe? * See [sections 3.1 and 3.2 (pages 5-6)](https://crypto.stanford.edu/~dabo/pubs/papers/VDFsurvey.pdf) 2. Is the adaptive root assumption equivalent to the low order assumption? * See ["Comparison of the assumptions" (page 8)](https://crypto.stanford.edu/~dabo/pubs/papers/VDFsurvey.pdf) 3. Can the Wesolowski prover wall-clock time be improved without significant parallelism? * See [Appendix A (page 11)](https://crypto.stanford.edu/~dabo/pubs/papers/VDFsurvey.pdf) for a parallel algorithm 4. Is it possible to combine proofs or optimise the prover circuit if the same input and the same time parameter is used on two different groups (e.g. two RSA groups with different moduli)? 5. Are there relevant groups of unknown order other than RSA groups and class groups? ### Randomness beacons ##### Difficulty adjustment 1. How should the VDF time parameter (aka the VDF difficulty) be calibrated to real-world time to produce a regular stream of random numbers? 2. How can the difficulty adjustment scheme resist manipulation of block timestamps that artificially increases/decreases the difficulty? 3. How can we mitigate the artificial decreasing of the difficulty through the delayed inclusion of VDF outputs in the blockchain? 4. How can we mitigate a randomness beacon denial-of-service from a fast attacker ramping up the difficulty and then going offline? * See [VDF-based RNG with linear lookahead](https://ethresear.ch/t/vdf-based-rng-with-linear-lookahead/2573) ##### Cryptoeconomics 1. How can the evaluation of VDF outputs be incentivised? * Possible solution: Use two parallel VDFs, the first on the common seed `s`, and the second on `s XOR pk` where `pk` is the public key of the evaluator. Is there a solution which does not have a 2x overhead? 2. How can the evaluation of VDF outputs be made non-outsourceable? * Possible direction: [Proofs of independent execution](https://ethresear.ch/t/proof-of-independent-execution/1988) * Another idea: Execution bits, similar to [custody bits](https://ethresear.ch/t/1-bit-aggregation-friendly-custody-bonds/2236) 4. Are there weak sources of entropy (to feed the VDF) that are censorship resistant? (RANDAO as a weak source of entropy can be censored by skipping all/most blocks in the reveal period.) 5. Are cryptoeconomic VDFs viable in practice? ### Misc ##### Quantum-secure VDFs 1. Are Sloth and MiMC provably quantum-secure? 2. Is combining Sloth (or MiMC) with STARKs a viable scheme in practice? * See Vitalik Buterin's posts [here](https://ethresear.ch/t/hash-based-vdfs-mimc-and-starks/2337) and [here](https://vitalik.ca/general/2018/07/21/starks_part_3.html) * See [Chapter 6 of BBBF18](https://eprint.iacr.org/2018/601.pdf) 3. Can we build a quantum-secure VDF with short proofs? * Dan Boneh is researching this 4. Can hash-based proofs of sequential work be made to have unique outputs? * See ["third open question" (page 18)](https://eprint.iacr.org/2018/183.pdf) * See [Time-Lock Puzzles in the Random Oracle Model](https://www.cs.virginia.edu/~mohammad/files/papers/11%20TimeLock.pdf) 5. Are there quantum-secure groups of unknown order? 6. Are the polynomials of Guralnick and Muller quantum-secure? * See [page 18](https://eprint.iacr.org/2018/601.pdf) 7. Observing that the Pietrzak construction generalised to endomorphisms of Abelian groups, what endomorphisms would be quantum-secure? ##### Permutation polynomials 1. Are there weak VDFs with the same simplicity as Sloth but with better constant speedup? 2. Are the polynomials of Guralnick and Muller safe to use in a VDF? * See [page 18](https://eprint.iacr.org/2018/601.pdf) ##### VDF ASICs 1. How much faster would the ASIC of a no-expense-spared attacker be relative to a commodity ASIC built on a $10m budget? (And same question $10m replaced by $100m.) 2. (Chia) Is it possible to make the attacker advantage be less than 10% compared to a commodity ASIC? 3. How often should the commodity ASIC be refreshed to keep up with advances in process technology? 4. Are there ways to mitigate the trust placed in the ASIC manufacturers when building a commodity ASIC? * Multiple competing manufacturers? 5. Is it possible to manufacture VDF ASICs using exotic semiconductors? (E.g. gallium arsenide, [indium phosphide](https://en.wikipedia.org/wiki/Indium_phosphide), [titanium trisulfide](https://www.ncbi.nlm.nih.gov/pubmed/26129825), or graphene.) 6. Is it possible to build a VDF ASIC that is sometimes much faster at evaluating outputs? * See [AsicBoost](https://www.asicboost.com) for Bitcoin mining ##### Other 1. Are there simple non-expanding decodable VDFs? * See [Chapter 7](https://crypto.stanford.edu/~dabo/pubs/papers/VDFsurvey.pdf) 2. Can the known VDF constructions be aggregated? * Different inputs: If the public parameters (e.g. the RSA modulus) and the time parameters are the same but the input is different, can the proofs be aggregated and/or computed more efficiently? * Different public parameters: If the inputs and the time parameters are the same but the public parameters are different, can the proofs be aggregated and/or computed more efficiently? 2. What are non-obvious applications of VDFs?