The permutation polynomials have been considered:
- Sloth: Only provides a constant gap between evaluation time and verification time. For it to be practical to build a Sloth VDF ASIC the multiplier needs to be of reasonable size (say, at most 4096 bits, yielding a ~2048 gap). This 2048 gap only applies if the evaluator and verifier run on the same hardware, making CPU verifiers useless in practice (unless you use intermediate values, but then bandwidth becomes an issue). This means you now need VDF ASICs for verifiers as well. You could have a cryptoeconomic scheme (e.g. see here) but a cryptographic scheme is clearly preferable (less trust, less complexity).
- MiMC: Basically the same as Sloth but worse: smaller gap for equivalently sized multipliers, and more complex intermediate non-arithmetic operations.
- Guralnick and Muller: I was told by various experts (Dan Boneh, Benedikt Bünz) that these polynomials are too risky because no one has seriously tried to break them. A promising approach, though.
- Sloth++ with SNARKs: Based on the research on ASIC multipliers my guess is that the basic step in Sloth++ (e.g. 256-bit modular squaring) can be done in ~1 nanosecond. So the SNARK prover stands no chance to keep up unless it is itself implemented as an ASIC. It’s unclear building a SNARK ASIC that is fast enough is practical.
- Sloth++ with STARKs: This is currently our best candidate for a quantum-secure VDF. The situation is similar to the above except 1) STARKs are quantum-secure, 2) STARKs provers are faster, 3) recursive STARKs are harder 4) STARKs are not as mature.
Is there a permutation polynomial you think should be (re)considered?
The EVM has no bearing on VDFs (other than the randomness opcode yielding hashes of VDF outputs). The VDF logic is implemented at the consensus layer.