Verifiable Delay Functions

Dmitry Khovratovich

​

Ethereum Foundation

Cryptographic Frontier 2021

Distributed Reward Problem

• Parties play a game and don’t trust each other.
• Winner should be selected uniformly at random.
• Winner gets a reward.
• Should be no way to bias the selection.

Example: Ethereum 2.0 validators decide who adds blocks in the next epoch.

Solution at Ethereum 2.0: RanDAO

RanDAO solution:

• Each validator commits a secret string: H(s)
• Everyone reveals its input.
• Hash of the result indicates a winner. H(s1,s2,...,sk)

Problem:

• Withholding a reveal affects the result.
• X malicious players have 2^X options.

Perspective VDF in Ethereum

• Validators submit entropy x1,x2,...xn
• Evaluator E computes a VDF (Proof P, value V= H(x1,x2,...,xn)) for 3 days.
• Everyone can check P and select validator X based on V.
• Blocks for the next epoch (a few hours) are selected by X.

Requirements:

• Tight latency -- no shortcuts
• Minimum hardware for E
• Succinct proofs
• Quantum upgrade
• Delay granularity
• Non-malleability

Existing VDF constructions: RSA

RSA VDF Setup: generate module N=pq so that no one knows p or q.

RSA VDF Run: select input I, make T squarings mod N, output O

RSA VDF Proof: certain intermediate values. Concretely,

• L is random, given to Prover
• Prover provides Z=g^{(2^T)div L}
• Verifier checks if O=Z^Lg^{(2^T)%L}

Needs trusted setup!

Existing VDF construction: Isogenies

• Generate elliptic curve E and select point P.
• Make T transformations of E to another curve, finally E’. Point P becomes P’.
• Prover selects Q’ on E’ and has to revert the same transform (V) to get Q.
• It must hold that e(P’,Q’) = e(P,Q)

Problem:

• The path V requires a lot of storage (GiB/seconds)
• Can be alleviated if V is pseudo-random but only for one run.

IVC-based VDF: Sloth, MinRoot, VeeDo

• Select some iterative transformation F.
• Apply F to input I 2^T times and produce O.
• Prove that I->O.

F is chosen to be SNARK-friendly and hardware-minimal.

IVC-based VDF: Sloth, MinRoot, VeeDo

SnarkPack:

• Split VDF in X parts
• Prove each part when it is ready.
• Aggregate when done.
• Only 1% overhead.

Fastest provers are not post-quantum but can be upgraded

​

VDF and Delay Encryption

Delay Encryption works as follows:

• Protector calls VDF F to derive secret key K=F(x).
• Protector encrypts data D on K: C= E_K(D) along with proof of correctness.
• Protector sends D and x to contract S.
• Someone recomputes K and everyone can decrypt D.

Open Problems

• Post-quantum VDF without trusted setup and low overhead
• Isogeny-based VDF with constant storage
• Simple and secure trusted setup for RSA-based VDF.
• Latency upper and lower bounds for modular multiplications and exponentiations.
• Quantum precomputation attacks on VDF