NutMiC’19, June, 2019

Verifiable Delay Functions:
How to Slow Things Down (Verifiably)
Dan Boneh
Stanford University

What is a VDF?
(verifiable delay function)
Intuition: a function X ⟶ Y that(1) takes time T to evaluate, even with polynomial parallelism,(2) the output can be verified efficiently• Setup(λ, T) ⟶ public parameters pp• Eval(pp, x) ⟶ output y,proof π• Verify(pp, x, y, π) ⟶ { yes, no }(parallel time T)(time poly(λ, log T) )

Security Properties (simplified)[B-Bonneau-Bünz-Fisch’18]• Setup(λ, T) ⟶ public parameters pp• Eval(pp, x) ⟶ output y,proof π• Verify(pp, x, y, π) ⟶ { yes, no }“Uniqueness”:(parallel time T)(time poly(λ, log T) )if Verify(pp, x, y, π) = Verify(pp, x, y’, π’) = yesthen y = y’“ε-Sequentiality”: for all parallel algs. A, time(A) < (1-ε)⋅time(Eval),
for random x∈X, A cannot distinguish Eval(pp, x) from a random y∈YApplication: lotteries
Problem: generating verifiable randomness in the real world?

Standard solutions
are unsatisfactory

Broken method: distributed generation
Alice

Bob

ClaireZoerarbrcrz

Public Bulletin Board (blockchain)
output rand = ra ⊕ rb ⊕ ⋯ ⊕ rz

∈ {0,1}256

Problem: Zoe controls value of rand !!

∈ {0,1}256

Solution: slow things down with a VDF [LW’15]
AliceBob

ClaireZoe

rarbrcrz

Public Bulletin Board (blockchain)hash(ra , rb , ⋯ , rz ) ∈ {0,1}256
VDF

output (rand, π)Solution: slow things down with a VDF• Submissions: start at 12:00pm, end at 12:10pm• VDF delay: about one hour (≫ 10 minutes)
Sequentiality: ensures Zoe cannot bias output
Uniqueness: ensures no ambiguity about output
Public Bulletin Board (blockchain)hash(ra , rb , ⋯ , rz ) ∈ {0,1}256

VDF(rand, π)Being implemented and deployed …

Construction 1: from hash functions
Hash function H: {0,1}256 ⟶ {0,1}256(e.g. SHA256)• pp = (public parameters for a SNARK)
H(T)(x) = H(H(H(H(H( … (H(H(x))) … )))))
T times(sequential work)• Eval(pp, x): output y = H(T)(x) , proof π = (SNARK)• Verify(pp, x, y, π): accept if SNARK proof is valid

Construction 1: from hash functions
Problem: computing SNARK proof π takes longer thancomputing y = H(T)(x)⇒ adversary can compute y long before Eval(pp, x) finishes

Simple solution using log2(T)-way parallelism[B-Bonneau-Bünz-Fisch’18]

Construction 2: exponentiation
Why?

G: finite abelian group• Assumption 1: the order of G cannot be efficiently computed
pp = (G,H: X ⟶ G)

• Eval(pp, x): outputy = H(x)<latexit sha1_base64="mYjLOkFntbLtDLpEzmMgZpXDosk=">AAACBnicbVDLSsNAFJ34rPUVdSnCYBHaTUm60Y1QdGGXFfqCNi2TyaQdOpnEmYkYQldu/BU3LhRx6ze482+ctllo64ELh3Pu5d573IhRqSzr21hZXVvf2Mxt5bd3dvf2zYPDlgxjgUkThywUHRdJwignTUUVI51IEBS4jLTd8fXUb98TIWnIGyqJiBOgIac+xUhpaWCeJPAS1ooPpX5arPQbpQmEvbsYebBHObwZmAWrbM0Al4mdkQLIUB+YXz0vxHFAuMIMSdm1rUg5KRKKYkYm+V4sSYTwGA1JV1OOAiKddPbGBJ5pxYN+KHRxBWfq74kUBVImgas7A6RGctGbiv953Vj5F05KeRQrwvF8kR8zqEI4zQR6VBCsWKIJwoLqWyEeIYGw0snldQj24svLpFUp21bZvrUK1assjhw4BqegCGxwDqqgBuqgCTB4BM/gFbwZT8aL8W58zFtXjGzmCPyB8fkDJ46WXA==</latexit>
sha1_base64="a6pE2PQQd1/gMxQhgh6Hjwt+k/8=">AAACBnicbVC7SgNBFL0bXzG+Vi1FGBKEBCHsptFGCFqYMkJekI1hdjLRIbOz68ysGJZUNn6GrY2FIrZ+g51/4+RRqPHAhcM593LvPX7EmdKO82WlFhaXllfSq5m19Y3NLXt7p6HCWBJaJyEPZcvHinImaF0zzWkrkhQHPqdNf3A29pu3VCoWipoeRrQT4CvB+oxgbaSuvT9EJ6iSvytcJvnSZa0wQsi7iXEPeUyg866dc4rOBGieuDOSK2e9w0cAqHbtT68XkjigQhOOlWq7TqQ7CZaaEU5HGS9WNMJkgK9o21CBA6o6yeSNETowSg/1Q2lKaDRRf04kOFBqGPimM8D6Wv31xuJ/XjvW/eNOwkQUayrIdFE/5kiHaJwJ6jFJieZDQzCRzNyKyDWWmGiTXMaE4P59eZ40SkXXKboXJo1TmCINe5CFPLhwBGWoQBXqQOAenuAFXq0H69l6s96nrSlrNrMLv2B9fAM6DZfl</latexit>
sha1_base64="07BIbQP7jDhUcHVWGZykj4T6EG4=">AAACBnicbVDLSsNAFJ34rPUVdSnC0CK0CCXpRjdC0YVdVugLmrRMptN26GQSZyZiCF258QP8CTcuFHHrN7jr3zh9LLT1wIXDOfdy7z1eyKhUljU2VlbX1jc2U1vp7Z3dvX3z4LAug0hgUsMBC0TTQ5IwyklNUcVIMxQE+R4jDW94PfEb90RIGvCqikPi+qjPaY9ipLTUMU9ieAnLuYd8O8kV29X8CELnLkJd6FAObzpm1ipYU8BlYs9JtpRxzp7HpbjSMb+dboAjn3CFGZKyZVuhchMkFMWMjNJOJEmI8BD1SUtTjnwi3WT6xgieaqULe4HQxRWcqr8nEuRLGfue7vSRGshFbyL+57Ui1btwE8rDSBGOZ4t6EYMqgJNMYJcKghWLNUFYUH0rxAMkEFY6ubQOwV58eZnUiwXbKti3Oo0rMEMKHIMMyAEbnIMSKIMKqAEMHsELeAPvxpPxanwYn7PWFWM+cwT+wPj6AUN3mWs=</latexit>

T squarings, e.g. T = 109

(2T )

2G

need proof π = (proof of correct exponentiation)[Pietrzak’18, Wesolowski’18]

Proof of correct exponentiation (T=power of 2)
Method 1: [Pietrzak’18]
Prover𝑢= 𝑔/𝑔, ℎ ∈ 𝐺 , claim: ℎ = 𝑔(. )impliesVerifier(.//3 )need to check://3 )(.
𝑔=𝑢random 𝑟 ∈ {1, … , 29.:}//3 )(.
𝑢=ℎverify both at once!
Set 𝑔9= 𝑔< 𝑢 ,ℎ9= 𝑢< ℎ.

Recursively prove(.//3 )
ℎ9 = 𝑔9

Proof of correct exponentiation [P’18]
Prover (𝑔, ℎ)(.//3 )
claim: ℎ9 = 𝑔9

𝑢= 𝑔(.//3 )

𝑟(.//= )𝑢9 = 𝑔9𝑟9.
claim: ℎ?@A B = 𝑔?@AB⋮ (log 𝑇 rounds)

Proof π = (𝑢, 𝑢9, … , 𝑢?@A B )Verifier (𝑔, ℎ)
𝑔9 = 𝑔< 𝑢 , ℎ9 = 𝑢< ℎ𝑔. = 𝑔<> 𝑢 , ℎ. = 𝑢<> ℎcompute: ℎ?@A B , 𝑔?@A B.
accept if ℎ?@A B = 𝑔?@AB

Proof of correct exponentiation [P’18]
As a non-interactive proof:• Proof π = 𝑢, 𝑢9, … , 𝑢?@A B

via the Fiat-Shamir heuristic𝑟H = hash(𝑔, ℎ, 𝑢, 𝑟, … , 𝑢HI9, 𝑟HI9, 𝑢H ),Computing the proof π:𝑖 = 1, … , log 𝑇

fast, only O( 𝑇) steps/• By storing 𝑇 values while computing 𝑔(. )Soundness/)(.
suppose ℎ ≠ 𝑔,Theorem [BBF’18] (informal):but prover P convinces verifier (with non-negligible probability 𝜖).
Then there is an algorithm, whose run time is twice that of P,
that outputs (with prob. 𝜖2)(𝒘, 𝒅) where 𝟏 ≠ 𝒘 ∈ 𝑮 and d < 2128 such that 𝒘𝒅 = 𝟏
assumption 2
so: hard to find 1 ≠ 𝑤 ∈ 𝐺 of known order ⇒ protocol is secureAssumption 2 is necessary for security
Suppose some (𝑤, 𝑑) is known where 1 ≠ 𝑤 ∈ 𝐺 and 𝑤 T = 1.
⇒ Prover can cheat with probability 1/𝑑How?

set//Now, verifier falsely accepts wheneverwhy?

//3 )ℎ = 𝒘 ⋅ 𝑔(. ) ≠ 𝑔(. ) ,𝑢 = 𝒘 ⋅ 𝑔(.

𝑟 + 1 ≡ 2B/. (𝑚𝑜𝑑 𝑑)(.//3 )
in this case: ℎ9 = 𝑔9=//3=<(𝑔< ℎ)(. )𝑢 ℎholds with prob. 1/d

More generally … nothing special about squaring
𝐺: finite abelian group.

𝜙: 𝐺 → 𝐺 an endomorphism𝒈, 𝒉 ∈ 𝑮 ,Prover (𝑔, ℎ)claim: 𝒉 = 𝝓 𝐓 (𝐠)𝑢 = 𝜙 a/. (g)𝑟claim: ℎ9 = 𝜙 B/. (g9)⋮Verifier (𝑔, ℎ)
𝑔9 = 𝑔< 𝑢 , ℎ9 = 𝑢< ℎProof π = (𝑢, 𝑢9, … , 𝑢?@A B )Proof of correct exponentiation: method 2
Method 2: [Wesolowski’18]
Proverlet q = ⌊ 2B /ℓ ⌋ℓ ← 𝑃𝑟𝑖𝑚𝑒𝑠(29.:)
𝑢 = 𝑔g

Proof π = (𝑢)/𝑔, ℎ ∈ 𝐺 , claim: ℎ = 𝑔(. )Verifiercompute 𝑟 = 2B 𝑚𝑜𝑑 ℓ
accept if: 𝑢ℓ ⋅ 𝑔< = ℎsingle element!

Soundness
Need assumption 2: hard to find 1 ≠ 𝑤 ∈ 𝐺 of known order… but is not sufficient

Security relies on a stronger assumption
called the adaptive root assumption.

Candidate abelian groups
Goal: group G with no elements ≠1 of known order• n ∈ ℤ, unknown factorization.

𝐺l = ℤ/𝑛 ∗ /{±1}Con: trusted setup to generate n• 𝑝 ≡ 3 (𝑚𝑜𝑑 4) prime.

(or a large random n)

𝐺s = class group of ℚ −𝑝 .

Con: no setup, but complex operation (slow verify)
Pro: can switch group every few minutes ⇒ smaller params

Candidate abelian groups
Goal: group G with Noteno elements≠1 of knownorder
DJB parallelism
for exponentiationin 𝐺l• n ∈ ℤ, unknown factorization.

𝐺l = ℤ/𝑛 ∗ /{±1}Con: trusted setup to generate n• 𝑝 ≡ 3 (𝑚𝑜𝑑 4) prime.

(or a large random n)

𝐺s = class group of ℚ −𝑝 .

Con: no setup, but complex operation (slow verify)
Pro: can switch group every few minutes ⇒ smaller params

Assumption 2 in class groups?
hard to find 1 ≠ 𝑤 ∈ 𝐺s of known small order
Cohen-Lenstra:frequency d divides |𝐺s | :d=3: 44%,d = 5: 24%,

d = 7: 16%

Open: When 3 divides |𝐺s |,can we efficiently find an element of order 3 in 𝐺s ?

The Chia class group challenge
Recent class number record: 512-bit discriminant• Beullens, Kleinjung, Vercauteren 2019:
The Chia challenge: computing larger class numbers• Are there interesting discriminants to include in challenge?

https://github.com/Chia-Network/vdf-competition

VDF construction 3: isogenies[De Feo, Masson, Petit, Sanso’ 19]
Degree-2 supersingular isogeny classes over 𝔽s :(p ≡ 7 𝑚𝑜𝑑 8)(curves and isogenies defined over 𝔽s )

𝑗~𝑗9
𝑗|𝑗.

𝑗}

∈ 𝔽s

∈ 𝔽s

VDF construction 3: isogenies[De Feo, Masson, Petit, Sanso’ 19]
Degree-2 supersingular isogeny classes over 𝔽s :(p ≡ 7 𝑚𝑜𝑑 8)

𝐸/𝔽sT steps𝐸′/𝔽s

𝜙: 𝐸 → 𝐸 • ,‚ 𝐸• → 𝐸 ,𝜙:deg 𝜙 = 2B

Tools|𝐸(𝔽† )| = |𝐸′(𝔽† )| = 𝑝 + 1.

𝐸𝜙𝜙‚𝐸’Let ℓ | 𝑝 + 1 be a large prime factor of 𝑝 + 1
Fact: For all 𝑃 ∈ 𝐸 ℓ ∩ 𝐸 𝔽†

and 𝑃′ ∈ 𝐸′ ℓ ∩ 𝐸′ 𝔽†‰𝒆^ ℓ(𝑷, 𝝓(𝑷′))= 𝒆^ ℓ’ (𝝓 𝑷 , 𝑷′)
non-degenerate pairing on E

non-degenerate pairing on E’

The VDF(over 𝔽† )Setup: (1) choose 𝑃 ∈ 𝐸 ℓ ∩ 𝐸(𝔽† ),[De Feo, Masson, Petit, Sanso’ 19]

compute 𝑃• = 𝜙 𝑃(2) 𝐻: 𝑋 → 𝐸 • ℓ ∩ 𝐸′(𝔽† )𝑝𝑝 = (𝐸, 𝐸’, 𝐻, 𝜙, 𝑃, 𝑃’)

No proof π !!

Eval(pp, x) = 𝜙‚ 𝐻 𝑥(T steps)

Verify(pp, x, y):𝒆^ ℓ(𝑷, 𝒚) = 𝒆^ ℓ’ (𝑷’, 𝑯(𝒙))accept ifand 𝑦 ∈ 𝐸 ℓ ∩ 𝐸 𝔽† .

Does Eval take T steps?
Can an attacker find a low degree isogeny 𝜓: 𝐸 • → 𝐸 ??
Answer: yes, if EndF̄p (E) is known[Kohel, Lauter, Petit, Tignol, 2014]<latexit sha1_base64="f5kFBAjcfJkHP4q8GlQBnkGpYJI=">AAACF3icbVDLSsNAFJ3UV62vqks3g0Wom5KIoMuiVFxWsA9oSphMp+3QySTM3Agh5C/c+CtuXCjiVnf+jdM2C209MMPhnHu59x4/ElyDbX9bhZXVtfWN4mZpa3tnd6+8f9DWYawoa9FQhKrrE80El6wFHATrRoqRwBes40+up37ngSnNQ3kPScT6ARlJPuSUgJG8cq0hB17qaqp4BPkPiWDY9YlK3YDA2PfTmyzzoqzaOPXKFbtmz4CXiZOTCsrR9Mpf7iCkccAkUEG07jl2BP2UKOBUsKzkxppFhE7IiPUMlSRgup/O7srwiVEGeBgq8yTgmfq7IyWB1kngm8rponrRm4r/eb0Yhpf9lMsoBibpfNAwFhhCPA0JD7hiFERiCDGZmF0xHRNFKJgoSyYEZ/HkZdI+qzl2zbk7r9Sv8jiK6Agdoypy0AWqo1vURC1E0SN6Rq/ozXqyXqx362NeWrDynkP0B9bnD3iGoLI=</latexit>

Solution: use a trusted setup to generate asupersingular 𝐸/𝔽† s.t. EndF̄p (E) is unknown<latexit sha1_base64="f5kFBAjcfJkHP4q8GlQBnkGpYJI=">AAACF3icbVDLSsNAFJ3UV62vqks3g0Wom5KIoMuiVFxWsA9oSphMp+3QySTM3Agh5C/c+CtuXCjiVnf+jdM2C209MMPhnHu59x4/ElyDbX9bhZXVtfWN4mZpa3tnd6+8f9DWYawoa9FQhKrrE80El6wFHATrRoqRwBes40+up37ngSnNQ3kPScT6ARlJPuSUgJG8cq0hB17qaqp4BPkPiWDY9YlK3YDA2PfTmyzzoqzaOPXKFbtmz4CXiZOTCsrR9Mpf7iCkccAkUEG07jl2BP2UKOBUsKzkxppFhE7IiPUMlSRgup/O7srwiVEGeBgq8yTgmfq7IyWB1kngm8rponrRm4r/eb0Yhpf9lMsoBibpfNAwFhhCPA0JD7hiFERiCDGZmF0xHRNFKJgoSyYEZ/HkZdI+qzl2zbk7r9Sv8jiK6Agdoypy0AWqo1vURC1E0SN6Rq/ozXqyXqx362NeWrDynkP0B9bnD3iGoLI=</latexit>

Summary and open problems
VDFs are an important new primitive• Several elegant constructions, but looking for more.
Problem 1: is there a simple fully post-quantum VDF?
Problem 2: other groups of unknown order?
• goal: no trusted setup and fast group operation
To learn more: see survey at https://eprint.iacr.org/2018/712

THE END