1 of 40

Verifiable lotteries

​

​

Joseph Bonneau

Courant Institute

New York University

2 of 40

What modern cryptographers do

Replace

trust assumptions

with

computational assumptions

3 of 40

Physical randomness generation is old

4 of 40

Physical randomness generation is widespread

5 of 40

Lotteries have been subverted many times

Lucky Numbers, 2000

6 of 40

Lotteries have been subverted many times

7 of 40

Physical randomness can be faked

8 of 40

Physical randomness can fail quietly

US conscription lottery, 1969

9 of 40

Physical randomness can fail quietly

10 of 40

Physical randomness can fail quietly

US conscription lottery, 1969

1

2

3

4

5

6

7

8

9

  1. Load in order

7

4

1

8

5

2

9

6

3

2. Rotate axially

1

3

2

6

4

5

8

9

7

3. Draw from top

11 of 40

Physical randomness can fail quietly

12 of 40

Timeline for a verifiable lottery

  1. Algorithm commitment

​

  • Public audit period

​

  • Choose random seed

​

  • Run algorithm

​

  • Public verification

13 of 40

Timeline for a verifiable lottery

  • Algorithm commitment

​

  • Public audit period

​

  • Choose random seed

​

  • Run algorithm

​

  • Public verification

for p in players:

p.seed = H(p, R)

​

sort(players)

14 of 40

Timeline for a verifiable lottery

  • Algorithm commitment

​

  • Public audit period

​

  • Choose random seed

​

  • Run algorithm

​

  • Public verification

for p in players:

p.seed = H(p, R)

​

sort(players)

15 of 40

Timeline for a verifiable lottery

  • Algorithm commitment

​

  • Public audit period

​

  • Choose random seed

​

  • Run algorithm

​

  • Public verification

for p in players:

p.seed = H(p, R)

​

sort(players)

16 of 40

Pseudorandom number generation

a276e6f4c488387e1b0b1f88dc402cd8

PRNG

574fb8dc165c47e2434753a8f7e8dd2d9543296eb3512e7b642832a8f54f7392f63f9afeb3c6f7e714c2ac785aed8a207d7f8e4ad62eec1a90fa070e1fffa9935162bbff82e9fdc6df899d4ca7dce0908025638808ae526f6099044609c09e5846154cc58d10cca845bf4807f6578941b99024e1fd07a7f2babd70daad3dbe51

(128-bit seed)

(infinite output)

17 of 40

Timeline for a verifiable lottery

  • Algorithm commitment

​

  • Public audit period

​

  • Choose random seed

​

  • Run algorithm

​

  • Public verification

​

for p in players:

p.seed = H(p, R)

​

sort(players)

for p in players:

p.seed = H(p, R)

sort(players)

+

18 of 40

Timeline for a verifiable lottery

  • Algorithm commitment

​

  • Public audit period

​

  • Choose random seed

​

  • Run algorithm

​

  • Public verification

for p in players:

p.seed = H(p, R)

​

sort(players)

for p in players:

p.seed = H(p, R)

sort(players)

+

19 of 40

The randomness beacon

01010001 01101011 10101000 11110000 10010100

20 of 40

The randomness beacon

01010001 01101011 10101000 11110000 10010100

  • Unpredictable
  • Unanimous
  • Reliable
  • High-bandwidth

21 of 40

The randomness beacon

01010001 01101011 10101000 11110000 10010100

  • Unpredictable
  • Unanimous
  • Reliable
  • High-bandwidth

​

​

  • Convincing to the public?

22 of 40

Third-party beacons require trust

random.org

beacon.nist.gov

23 of 40

Natural beacons typically aren’t unanimous

sdo.gsfc.nasa.gov

24 of 40

Historical inspiration: The numbers game

25 of 40

Historical inspiration: The numbers game

Joseph

Moriarity

Sai Wing

Mock

Giosue

Galluci

Teddy

Roe

26 of 40

Modern idea: Financial data as a beacon

Problem: market manipulation

27 of 40

Manipulating a financial beacon

AAPL

$178.02

AMZN

$1571.68

GOOG

$1134.42

  1. Observe near-final value

2. Simulate lottery outcomes for many perturbations

AAPL

$178.01

AMZN

$1571.67

GOOG

$1134.41

AAPL

$178.03

AMZN

$1571.69

GOOG

$1134.43

...

3. Force the best outcome

28 of 40

Similar manipulation for blockchain beacons

29 of 40

New approach: verifiable delay functions

Natural randomness

VDF

Beacon output

Goal: by the time the output can be computed, it’s too late to attack

30 of 40

What is a Verifiable Delay Function?

  • Verifiable: easy to verify the result

​

  • Delay: slow to compute, with any computer

​

  • Function: unique result

​

31 of 40

Preventing manipulation with a VDF

AAPL

$178.02

AMZN

$1571.68

GOOG

$1134.42

  • Observe near-final value

2. Simulate lottery outcomes for many perturbations

AAPL

$178.01

AMZN

$1571.67

GOOG

$1134.41

AAPL

$178.03

AMZN

$1571.69

GOOG

$1134.43

...

3. Market closes before attacker can evaluate options

32 of 40

Delay with slow verification: iterated hashing

H

H

H

H

H

H

H

x

y

...

def delay(x, t):

for i in range(t):

x := SHA256(x)

return x

delay(x): Ht(x)

33 of 40

A proto-VDF: square roots

[Dwork, Naor 1992]

def delay(x, p):

return x(p+1)/4 (mod p)

delay(x): √x (mod p)

​

def verify_delay(x, y, p):

return x == y2 (mod p)

34 of 40

Modern VDF: squaring in group of unknown order

delay(x): x2 (mod N)

​

def verify_delay(x, y, t, N, π):

...

t

​

def delay(x, t, N):

for i in range(t):

x := x2 (mod N)

return x

35 of 40

New computation model

Cryptography community typically

worries about scaling, not speed

36 of 40

Many uses in decentralized protocols

  • Multiparty randomness protocols

​

  • Leader election in proof-of-stake

​

  • Proofs of useful space/replication

​

37 of 40

Many smart contracts need randomness

38 of 40

Many types of real-world “lottery”

39 of 40

Convincing the public is difficult

40 of 40

Be skeptical of authorities!