Eth3.0

Quantum security

IBM Q

50 qubits

• intro
• Eth1—quantum vulnerability
• Eth2—quantum infancy
• Eth3—quantum security

paradigm shifts

Bitcoin

Eth1

Eth2

Eth3

programmability

scalability

quantum security

2009

2014

2020

2027?

Neven's law vs hype

time

computation

power

Neven's law

double exponential

hype

not scalable

now

🤔

post quantum narrative

> What's your vision for Eth 3.0?

"STARKs, STARKs and lots of STARKs."—Vitalik, Jan 2019

post quantum narrative

• flexibility
• one tool to rule them all

> What's your vision for Eth 3.0?

"STARKs, STARKs and lots of STARKs."—Vitalik, Jan 2019

post quantum narrative

• flexibility
• one tool to rule them all
• lean and resilient crypto
• consolidation of assumptions
• hash functions only
• Lindy effect

> What's your vision for Eth 3.0?

"STARKs, STARKs and lots of STARKs."—Vitalik, Jan 2019

post quantum narrative

• flexibility
• one tool to rule them all
• lean and resilient crypto
• consolidation of assumptions
• hash functions only
• Lindy effect
• performance
• relatively fast prover
• data is cheap™

> What's your vision for Eth 3.0?

"STARKs, STARKs and lots of STARKs."—Vitalik, Jan 2019

Ethereum Foundation grant (July 2018)

~$5 million

"quantum insurance"

Ethereum Foundation grant (July 2018)

STARK-friendly hash function

CPU-optimised prover

open source

~$5 million

"quantum insurance"

third-party

audits

Ethereum Foundation grant (July 2018)

STARK-friendly hash function

CPU-optimised prover

open source

~$5 million

"quantum insurance"

third-party

audits

towards

production readiness

plausibly provably quantum secure

plausibly provably quantum secure

→ slightly larger proofs

plausibly provably quantum secure

→ slightly larger proofs

concrete constant unknown,

expected ~2x

universal SNARK setups

universal SNARK setups

STARK/FRI unique selling point

Eth1—quantum vulnerability

systemic risk

"37% of the [Bitcoin] supply is at risk"

—Pieter Wuille, Mar 2019

systemic risk

"37% of the [Bitcoin] supply is at risk"

—Pieter Wuille, Mar 2019

exposed pubkeys

systemic risk

"37% of the [Bitcoin] supply is at risk"

—Pieter Wuille, Mar 2019

• Eth1 vs Bitcoin
• accounts encourage pubkey reuse vs UTXOs (expecting >37% at risk)
• hard to migrate contracts (e.g. long-running Augur bet)

exposed pubkeys

systemic risk

"37% of the [Bitcoin] supply is at risk"

—Pieter Wuille, Mar 2019

• Eth1 vs Bitcoin
• accounts encourage pubkey reuse vs UTXOs (expecting >37% at risk)
• hard to migrate contracts (e.g. long-running Augur bet)
• governance intervention
• false positives
• possibly controversial

exposed pubkeys

inertia

"Historically, it has taken almost two decades to deploy our modern public key cryptography infrastructure."—NIST website

​

inertia

"Historically, it has taken almost two decades to deploy our modern public key cryptography infrastructure."—NIST website

​

NIST post-quantum competition

​

• 2016—kickoff
• 2017—round 1 (69 candidates)
• 2019—round 2 (26 candidates)
• 2021—round 3
• 2024—draft standard

inertia

"Historically, it has taken almost two decades to deploy our modern public key cryptography infrastructure."—NIST website

​

NIST post-quantum competition

​

• 2016—kickoff
• 2017—round 1 (69 candidates)
• 2019—round 2 (26 candidates)
• 2021—round 3
• 2024—draft standard

​

→ additional friction from blockchain governance

data is cheap™

Nielsen's law—bandwidth grows by 50% per year

data is cheap™

Nielsen's law—bandwidth grows by 50% per year

• data is fungible—a byte is a byte
• data is massively parallelizable
• 200kB proof today ~ 3.5kB proof in 10 years

gas repricing

call data repricing

• EIP2028—67 gas/byte to 16 gas/byte
• prediction—more data repricings

over time

data gets cheaper than computation

Eth2—quantum infancy

backup signatures

• quantum apocalypse backup—one-time migration
• Lamport—simple, available today, low overhead
• backwards compatible—integratable in any existing signature scheme

backup signatures

• quantum apocalypse backup—one-time migration
• Lamport—simple, available today, low overhead
• backwards compatible—integratable in any existing signature scheme

Svalbard Global Seed Vault

backup signatures

Lamport

seed

Lamport

secret key

Lamport

public key

quantum apocalypse contingency

Lamport

seed

Lamport

secret key

Lamport

public key

non-quantum seed

non-quantum

secret key

non-quantum

public key

hash

quantum apocalypse contingency

bit 1

bit 256

Lamport signatures

quantum apocalypse contingency

bit 1

bit 256

Lamport signatures

quantum apocalypse contingency

bit 1

bit 256

Lamport signatures

multi-hashing

multi-hashing

multi-hashing

STARK-friendly hash challenge

HadesMiMC

MARVELlous

GMiMC

family

STARK-friendly hash challenge

HadesMiMC

MARVELlous

GMiMC

Starkad

Poseidon

Vision

Rescue

GMiMC_erf

family

flavour

STARK-friendly hash challenge

HadesMiMC

MARVELlous

GMiMC

Starkad

Poseidon

Vision

Rescue

GMiMC_erf

STARK-friendly fields

• prime fields
• high 2-adicity

​

→ compatible with SNARKs 🎉

family

flavour

longer addresses

length matters

• current output length n = 160 bits
• classical collision resistance—O(n/2) ~ 80 bits
• quantum collision resistance—O(2n/5) ~ 64 bits (technically O(n/3) = 60 bits)
• future cryptanalytic weakenings

2017 result

longer addresses

length matters

• current output length n = 160 bits
• classical collision resistance—O(n/2) ~ 80 bits
• quantum collision resistance—O(2n/5) ~ 64 bits (technically O(n/3) ~ 60 bits)
• future cryptanalytic weakenings

000000000000000000000019b43763eb4519f4fe65eae9be90fe73117b89026d

91 zero bits

avoid 80-bit of security

longer addresses

length matters

• current output length n = 160 bits
• classical collision resistance—O(n/2) ~ 80 bits
• quantum collision resistance—O(2n/5) ~ 64 bits (technically O(n/3) = 60 bits)
• future cryptanalytic weakenings

000000000000000000000019b43763eb4519f4fe65eae9be90fe73117b89026d

91 zero bits

avoid 80-bit of security

new n—256 bits

witness compression for stateless clients

beacon chain

shard

shard

...

execution engine

execution

engine

...

dapp

dapp

...

account

account

...

stateless

witness compression for stateless clients

application data

​

Merkle proofs

10x overhead

uncompressed

witness compression for stateless clients

application data

​

Merkle proofs

10x overhead

STARK

​

application data

10% overhead

uncompressed

compressed

abstraction

not opinionated

• no enshrined ECDSA
• no minimum 21,000 gas

quantum canary

• early detection—calibrated quantum advantage problem
• bounty—e.g. 1m ETH minted by the consensus
• programmatic—trigger for consensus and contracts

Eth3—quantum security

Eth2 pre-quantum cryptography

RANDAO

phase 0

phase 1

aggregate signatures

custody proofs

Eth2 pre-quantum cryptography

RANDAO

phase 0

phase 1

aggregate signatures

custody proofs

secrets involved

• BLS12-381 private key
• MPC-friendliness requirement

Eth2 pre-quantum cryptography

RANDAO

phase 0

phase 1

phase 2

aggregate signatures

custody proofs

VDF

Eth2 pre-quantum cryptography

RANDAO

phase 0

phase 1

phase 2

aggregate signatures

custody proofs

VDF

group of unknown order

• 2048-bit RSA group
• trapdoor

aggregate signatures

aggregation constraints

• batches of 1024 signatures
• 128 batches per block

​

aggregate signatures

aggregation constraints

• batches of 1024 signatures
• 128 batches per block

​

key to 1024 shards

aggregate signatures

aggregation constraints

• batches of 1024 signatures
• 128 batches per block

​

​

idea

• batch 1024 Lamport signatures into a STARK
• aggregate those 128 STARKs into one STARK

preference for hash-based signature schemes

(e.g. Lamport, Winternitz, SPHINCS+)

key to 1024 shards

aggregate signatures

aggregation constraints

• batches of 1024 signatures
• 128 batches per block

​

​

idea

• batch 1024 Lamport signatures into a STARK
• aggregate those 128 STARKs into one STARK

preference for hash-based signature schemes

(e.g. Lamport, Winternitz, SPHINCS+)

key to 1024 shards

open problem—add MPC-friendliness

RANDAO hash onions

seed s

RANDAO hash onions

​

​

​

H¹(s)

seed s

RANDAO hash onions

​

​

​

H¹(s)

seed s

...

...

RANDAO hash onions

​

​

​

H¹(s)

seed s

commitment

c = H¹⁰²⁴(s)

H¹⁰²⁴(s)

​

...

...

RANDAO hash onions

H^-1(c)

​

​

​

H¹(s)

seed s

commitment

c = H¹⁰²⁴(s)

...

...

RANDAO hash onions

H^-1(c)

​

​

​

H¹(s)

seed s

commitment

c = H¹⁰²⁴(s)

H^-2(c)

...

...

...

7 days per layer with 100,000 validators

MPC-friendly hash

custody proofs

data

secret

validator slashed if revealed

custody proofs

data

secret

mix

validator slashed if revealed

custody proofs

data

secret

statement—I know mix consistent with H(data) and H(secret)

mix

validator slashed if secret revealed

not outsourceable

VDFs

STARKs

permutation polynomial

constant gap

"bootstrap"

exponential gap

parallelism

VDFs

pros

​

• quantum secure
• no trusted setup
• cheaper evaluator hardware
• easier to reason about lower bounds

STARKs

permutation polynomial

constant gap

"bootstrap"

exponential gap

parallelism

VDFs

cons

​

• larger proofs
• more expensive prover hardware

pros

​

• quantum secure
• no trusted setup
• cheaper evaluator hardware
• easier to reason about lower bounds

STARKs

permutation polynomial

constant gap

"bootstrap"

exponential gap

parallelism

bonus—minimise fraud proofs

blockchain design heuristics

​

• If cryptography doesn't work, try cryptoeconomics.
• If cryptography does work, avoid cryptoeconomics.

bonus—minimise fraud proofs

blockchain design heuristics

​

• If cryptography doesn't work, try cryptoeconomics.
• If cryptography does work, avoid cryptoeconomics.

data availability

proof of custody

header checks

quantum secure in Eth2

but interactive

thank you :)