Public randomness, blockchains,

and delay functions

​

​

Joseph Bonneau

​

Chinese University of Hong Kong

Jan 26 2017

End goal: accountable algorithms

Verify that an authority is behaving faithfully

​

Procedural fairness: “the rules are followed”

​

Key milestone: verifiable random algorithms

US Diversity Visa (green card) lottery

“During DV season, I double my business. Everybody participates. Even I do.”

--Ethiopian WebCafe owner Tsehay Wondim, as told to the Wall Street Journal

2012 US Diversity Visa lottery bug

When participants submit their records, the computer program assigns a sequential number to each record based on the participant’s region. Subsequently, the selection process uses the sequential numbers to randomly rank-order the participants’ records. CST management decided in November 2010 not to use the commercial off-the-shelf statistics analysis program that it had used successfully for random rank-ordering in numerous previous years. Instead, CST management asked one of its contractors to develop a program. This new computer program had a coding error that produced a nonrandom rankordering and thus failed to meet INA requirements. The program not only selected 98 percent of the applicants from the first two dates of the allowed submission dates, it also selected multiple individuals from the same families.

--OIG investigation report on 2012 DV lottery

Public displays of randomness

Pros: cheap, simple to understand

Cons: difficult to verify (sleight of hand)

high-latency

1980 “Triple Six Fix”, PA state lottery

Balls “6” and “4” weighted with lead

1985 NBA draft lottery

1985: Knicks win rights to Patrick Ewing

2015 Serbian lottery

Five numbers shown

Only 3 balls drawn!

Cryptographic beacons

01010001 01101011 10101000 11110000 10010100

Many Applications: lotteries, auditing, zero-knowledge proofs, cut-and-choose, ...

service to regularly publish random data

Security goals

01010001 01101011 10101000 11110000 10010100

• Guaranteed min-entropy
• Unpredictability before t₀
• Public consensus by time t₁ > t₀
• Manipulation-resistant
• DoS-resistant

Engineering goals

01010001 01101011 10101000 11110000 10010100

• High-bandwidth
• Frequent publication (low latency)
• Rapid consensus (minimize t₁ - t₀)
• Low-cost
• Public confidence

NIST beacon

Pros: high-bandwidth, frequent

quantum-mechanical randomness

Cons: completely centralized

Security goals

01010001 01101011 10101000 11110000 10010100

• Guaranteed min-entropy
• Unpredictablity before t₀
• Public consensus by time t₁ > t₀
• Manipulation-resistant
• DoS-resistant

No trusted parties

Multiparty randomness: commit-reveal

Alice

Bob

Carol

commit(r_A,n_A)

time

commit(r_B,n_B)

commit(r_C,n_C)

t₀

t₁

r_A,n_A

r_B,n_B

r_C,n_C

R = r_A⊕r_B⊕r_C

R = r_A⊕r_B⊕r_C

R = r_A⊕r_B⊕r_C

Multiparty randomness: commit-reveal

Improvements:

• Forfeit bond if r_i not revealed

​

• Share each r_i with PVSS, assume hon. majority

​

[Andrychowicz et al. 2014]

[Syta et al. 2016]

Security goals

01010001 01101011 10101000 11110000 10010100

• Guaranteed min-entropy
• Unpredictablity before t₀
• Public consensus by time t₁ > t₀
• Manipulation-resistant
• DoS-resistant

distributed?

Natural phenomena

Sun spots

Cosmic background radiation

Weather

Pros: cheap, random, manipulation-resistant

Cons: low-bandwidth, no consensus

Stock prices

Pros: good randomness [6-9 bits/stock]

Cons: high-latency, possible insider attacks

[Clark, Hengartner 2010]

Stock prices can be manipulated...

Bitcoin to the rescue!

• decentralized
• continuously publishing
• PoW solutions inherently unpredictable

Recall: Bitcoin block chain format

H( ) H( )

H( ) H( )

H( ) H( )

transaction

transaction

transaction

transaction

Hash chain of blocks

Hash tree (Merkle tree) of transactions in each block

Recall: Bitcoin block criteria

mrkl_root: H( )

prev: H( )

mrkl_root: H( )

hash: 0x0000

nonce: 0x7a83

prev: H( )

hash:

hash: 0x3485...

hash: 0x6a1f...

nonce: 0x0000...

nonce: 0x0001...

hash: 0xc9c8...

nonce: 0x0002...

hash: 0x300c...

nonce: 0xffff...

hash:

nonce: 0x0000...

hash: 0xd0c7...

nonce: 0x0001...

hash: 0x0224...

hash: 0x0000...

nonce: 0xf77e...

mrkl_root: H( )

prev: H( )

hash:

hash: 0x3485...

hash: 0x6a1f...

nonce: 0x0000...

nonce: 0x0001...

hash: 0xc9c8...

nonce: 0x0002...

hash: 0x300c...

nonce: 0xffff...

hash:

nonce: 0x0000...

hash: 0xd0c7...

nonce: 0x0001...

hash: 0x0224...

hash: 0x0000...

nonce: 0xf77e...

≤ 00000000000000001FB893000000000000000000000000000000000000000000

69+ leading zeroes required...

Hash

Turning the block chain into a beacon

mrkl_root: H( )

prev: H( )

mrkl_root: H( )

hash: 0x0000

nonce: 0x7a83

prev: H( )

hash:

hash: 0x3485...

hash: 0x6a1f...

nonce: 0x0000...

nonce: 0x0001...

hash: 0xc9c8...

nonce: 0x0002...

hash: 0x300c...

nonce: 0xffff...

hash:

nonce: 0x0000...

hash: 0xd0c7...

nonce: 0x0001...

hash: 0x0224...

hash: 0x0000...

nonce: 0xf77e...

mrkl_root: H( )

prev: H( )

hash:

hash: 0x3485...

hash: 0x6a1f...

nonce: 0x0000...

nonce: 0x0001...

hash: 0xc9c8...

nonce: 0x0002...

hash: 0x300c...

nonce: 0xffff...

hash:

nonce: 0x0000...

hash: 0xd0c7...

nonce: 0x0001...

hash: 0x0224...

hash: 0x0000...

nonce: 0xf77e...

Extract

Extract

Extract

01010001 10101000 10010100

70+ bits

Computational min-entropy bound

If you could predict the next nonce with a greater than 2^-d probability, you’d have a mining shortcut

Therefore, each valid block has

d bits of computational min-entropy

Currently, d > 70

Assuming miners follow the default protocol

At least one lottery startup

Beacon useful in smart contracts

• Publicly-verified programs on the blockchain
• Currently no random behavior possible
• all miners must evaluate equally
• de facto solution: hash last block
• Many other smart contract applications
• Randomized micropayments
• Non-interactive cut-and-choose

​

Is it secure?

​

No! miners can withhold blocks

Assume rational attacker

Can we bound the cost of manipulation?

Attack model based on bribery

12.5 BTC opportunity cost to suppress a block

​

​

​

​

​

• Covers attacker who is a miner
• Covers attacker who is a mining pool

Manipulation via Bernoulli trial

To force a beacon outcome with probability p:

​

• Discard c(p) = 1/p - 1 blocks

​

• Measure in units of “block rewards”
• ≥ 12.5 BTC
• Currently ≈ US$11,000 (HKD$88,000)

Can we extend to multiple rounds?

mrkl_root: H( )

prev: H( )

mrkl_root: H( )

hash: 0x0000

nonce: 0x7a83

prev: H( )

hash:

hash: 0x3485...

hash: 0x6a1f...

nonce: 0x0000...

nonce: 0x0001...

hash: 0xc9c8...

nonce: 0x0002...

hash: 0x300c...

nonce: 0xffff...

hash:

nonce: 0x0000...

hash: 0xd0c7...

nonce: 0x0001...

hash: 0x0224...

hash: 0x0000...

nonce: 0xf77e...

mrkl_root: H( )

prev: H( )

hash:

hash: 0x3485...

hash: 0x6a1f...

nonce: 0x0000...

nonce: 0x0001...

hash: 0xc9c8...

nonce: 0x0002...

hash: 0x300c...

nonce: 0xffff...

hash:

nonce: 0x0000...

hash: 0xd0c7...

nonce: 0x0001...

hash: 0x0224...

hash: 0x0000...

nonce: 0xf77e...

Extract

01010001

Last block is privileged!

Extension via collective coin-flipping

[Ben-Or, Linial 1990]

output

Each block must have

Ω(lg n / n) influence

Problem: blockchains can fork

Block A

Block B

?

Collisions blow up security model

​

• Opportunity cost is ε in the event of a collision

​

• Even worse: can try to recoup after withholding

​

• Bitcoin network provides no guarantees

Solution: use a proof-of-delay

mrkl_root: H( )

prev: H( )

mrkl_root: H( )

hash: 0x0000

nonce: 0x7a83

prev: H( )

hash:

hash: 0x3485...

hash: 0x6a1f...

nonce: 0x0000...

nonce: 0x0001...

hash: 0xc9c8...

nonce: 0x0002...

hash: 0x300c...

nonce: 0xffff...

hash:

nonce: 0x0000...

hash: 0xd0c7...

nonce: 0x0001...

hash: 0x0224...

hash: 0x0000...

nonce: 0xf77e...

mrkl_root: H( )

prev: H( )

hash:

hash: 0x3485...

hash: 0x6a1f...

nonce: 0x0000...

nonce: 0x0001...

hash: 0xc9c8...

nonce: 0x0002...

hash: 0x300c...

nonce: 0xffff...

hash:

nonce: 0x0000...

hash: 0xd0c7...

nonce: 0x0001...

hash: 0x0224...

hash: 0x0000...

nonce: 0xf77e...

Extract

Extract

Extract

01010001 10101000 10010100

Delay

Delay

Delay

delay period

Delay functions

F: {0,1}^* × Z → {0,1}^k

x t y

input time output

Delay functions: required properties

​

• entropy-preserving
• inherently sequential
• requires Θ(t) steps
• deterministic
• no private setup
• succinct, easily verifiable proof

Many uses!

Verifiable in an Ethereum contract

Multiparty randomness: Unicorn

Alice

Bob

Carol

time

t₀

t₁

r_C

R = F(r_A⊕r_B⊕r_C)

R = F(r_A⊕r_B⊕r_C)

​

R = F(r_A⊕r_B⊕r_C)

r_A

r_B

[Lenstra, Wesolowski 2015]

delay time

delay time

t_close

t_open

delay time

Combining multiple public beacons

time

delay time

Proof-of-stake consensus

committee 1

committee 2

committee 3

• Random committee i chosen collectively by committee i-k
• Collective coin-flipping
• PVSS

​

• Better solution: apply proof-of-delay

Delay functions: required properties

​

• entropy-preserving
• inherently sequential
• requires Θ(t) steps
• deterministic
• no private setup
• succinct, easily verifiable proof

Easy if we remove any one!

Best known approach

[Dwork, Naor 1992]

​

• Modular square root

F(x): find y s.t. y²=x (mod p)

​

computation: x^(p+1)/4 (mod p)

proof: y

verification: y² (mod p)

​

lg p squarings

lg p bits

1 squaring

Hardening via iteration

F

π

F

π

F

π

F

x

y

proof

Invariant:

computation/verification ratio is constant

...

[Lenstra, Wesolowski 2015]

Sample parameters: p = 2048 bits, t = 2¹⁷

​

computation: ~10 minutes

verification: ~1 second

proof size: 2048 bits

​

Refereed model

F

π

F

π

F

π

F

x

y

...

[Canetti,Riva, Rothblum, 2011]

x₁

x₂

Merkle commitment

proof

Challenge protocol:

• Challenger claims y’ is correct
• Prover, challenger reveal x_i‘s, binary search to find divergence point
• Find divergence point x_i, x_i+1, x’_i+1
• Verify correct value of F(x_i)

​

Cost: lg t rounds, lg² t hashes, 1 invocation of F

Refereed model in Ethereum

x

x_n

[ongoing work]

x₁

Ethereum costs:

​

POST: ~80000 gas (US $0.02)

CHALLENGE: ~720,000 gas (US $0.12)

DEFEND: ~280,000 gas (US $0.05)

Prover:

Challenger:

2²⁰○F

x₂

2²⁰○F

x_i-1

x_i

2²⁰○F

...

...

Challenger: x_i is wrong

Prover: yeah? Prove it!

x_i-1

x’_i

y₁

2¹⁶○F

y₂

2¹⁶○F

y_i-1

y_i

2¹⁶○F

...

...

Prover:

y_i-1

y’_i

z₁

2¹²○F

z₂

2¹²○F

z_i-1

z_i

2¹²○F

...

...

Direct recomputation

Generic approach: verifiable comp.

F

π

F

π

F

π

F

x

y

Problem:

circuit is very deep → massive proving time

...

Computationally-sound proof system

Generic approach: SNARGs

F

π

F

π

F

π

F

x

y

Problem:

circuit is very wide

...

witness

Succinct non-interactive argument system

Generic approach: SNARGs

F

π

F

π

F

π

F

x

y

Depth/width tradeoff:

Send sqrt(t) intermediate values

...

witness

Succinct non-interactive argument system

From black-box obfuscation

private signature_key k

​

function step(x, i, n, σ):

if (i == 0 || verify(x‖i-1‖n, σ):

for (j = 0; j < n; j++); //nop

return sign(x‖i‖n, k)

​

Given obfs(P), Define F(x) = sign(x‖t‖n, k)

Proofs-of-delay: required properties

​

• entropy-preserving
• inherently sequential
• requires Θ(t) steps
• deterministic
• no private setup
• succinct, easily verifiable proof
• incrementally updateable

Construction from recursive SNARKs

x

SNARK

SNARK

x

++

x+1

SNARK

x+1

++

x+2

SNARK

x+t-1

++

x+t

...

Language L:

successors(x)

x

​

y if y-1 ∈ L

Application: timestamping

committee 1

committee 2

committee 3

long-range fork

committee 2’

committee 3’

Prove which chain is longer using proof-of-delay

​

Takeaways

• Practical today:
• Blockchain beacon w/coin-flipping
• Blockchain beacon w/bond & challenge

​

Both rely on an economic security model

​

Takeaways

• Unknown approaches today
• verifiable computation
• obfuscation

​

Proofs-of-delay are a target for both

Takeaways

• Open algorithmic problem:
• Better tradeoffs than modular square roots

​

​

computation: x^(p+1)/4 (mod p)

proof: y

verification: y² (mod p)

​

lg p squarings

lg p bits

1 squaring

Takeaways

• We lack tools for precise lower-bounds

​

Takeaways

• any independent beacon is a security upgrade

​

Thanks!

• jbonneau@cs.stanford.edu
• Co-authors
• Steven Goldfeder
• Jeremy Clark

No succinct proof?

​

• Iterated hash [Back 1997]

F(x): H^t(x)

​

[Morris, Thompson 1979]

Not inherently sequential?

​

• Partial pre-images (hashcash) [Back 1997]

F(x): find y s.t. H(x,y) < t

​

• Discrete log

F(x): find y s.t. g^y = x (mod p)

​

​

Use private setup?

​

• Time-lock encryption/commitment

F(x): compute y^{2^(2^d)} (mod N)

​

[Rivest, Shamir, Wagner 1996]

[Boneh, Naor 2000]

[Karame, Capkun 2010]

Not deterministic?

Publicly-verifiable proof of sequential work

[Mahmoody, Moran, Vadhan 2013]

​

x₀

x₁

x₂

x₃

x₄

x₅

x₆

x₇

x₈

x₉

x_t

x

y

...

Merkle commitment

NIZK (Fiat-Shamir)

depth-robust graph

Bandwidth

• ≈69 bits min-entropy every 10 minutes
• much higher for some alt-coins

Latency required

• Bitcoin not synchronized securely to real time
• Must choose a block number

time

parameters agreed

“not before” time

expected time

expected latency

Latency follows a Gamma distribution

Minimum 2 hours

Several papers use Bitcoin as a beacon

• Mixcoin
• RationalZero (ZeroCoin)

Constructing a lottery is difficult today

Andrychowicz, Dziembowski, Malinowski & Mazurek. “Secure Multiparty Computations on Bitcoin” IEEE Security & Privacy 2014

​

Lotteries are easy with OP_BEACON

// Beacon parameters:

0x41e053d8 // nonce

1 // number of blocks to wait

OP_BEACON // Push random integer on the stack

0 // Threshold to determine the winner

OP_LESSTHANOREQUAL

OP_IF // Check for Alice's signature, if Alice won

OP_DUP

OP_HASH160

<alicePubKeyHash>

OP_EQUALVERIFY

OP_CHECKSIG

OP_ELSE // Check for Bob's signature, if Bob won

OP_DUP

OP_HASH160

<bobPubKeyHash>

OP_EQUALVERIFY

OP_CHECKSIG

OP_ENDIF

Many applications for beacon opcode

• Lotteries
• Random mixing fees
• Non-interactive cut-and-choose

​

Worst-case scenario: Dolev-Yao

​

• Attacker is the network
• Such an attacker could kill any block

Partial network control

​

• Assume the attacker can choose between near-simultaneous blocks
• controls access to a fraction β of the network

Limits on network attacks

• Such an attacker could extract 25β in rent
• assuming no collusion by miners
• Opportunity cost is as high as bribing*
• other block is already known

​

• Chance to attack is very rare

Practical concerns

• Exchange rate volatility

​

Practical concerns

• Transition to fee-based mining

​

Courtesy:

Brian Warner

2012 US Diversity Visa lottery

• Registration: Oct-Nov 2010
• Winners announced May 1, 2011
• Results rescinded May 13, 2011
• New results announced July 15, 2011

Stock prices

[Clark, Hengartner 2010]

• Min-entropy estimate: 6-9 bits/stock/day
• Already used in a real municipal election!

Not deterministic?

Subset sum problem

[Tritilanunt, Boyd, Foo, Nieto 2007]

​

Candidate: linear programming

F(x):

• compute vectors c, b & matrix A from H(x)
• find vector z s.t. c^Tz is maximal, Az ≤ b
• y = H(z)

1969 Vietnam conscription lottery

Late-year birthday bias

Publicly-verifiable proof of seq. work

Publicly-verifiable proof of sequential work

[Mahmoody, Moran, Vadhan 2013]

​

x₀

x₁

x₂

x₃

x₄

x₅

x₆

x₇

x₈

x₉

x_t

x

y

...

Merkle commitment

NIZK (Fiat-Shamir)

depth-robust graph

US Diversity Visa (green card) Lottery

Annual lottery for US permanent resident cards

• 55,000 winners
• Roughly 5 M entrants
• Complicated, but public allocation