My recent research:
time-based crypto and
verifiable lotteries
Copyright By PowCoder代写 加微信 powcoder
Traditional crypto separates fast and intractable Fast
Intractable
Key search Discrete log Factoring Collision- findng
Encryption Decryption Signing Verification Hashing
Time-based crypto
Time-based cryptography before 2018
● Sequential puzzles [Dwork, Naor 92]
● Time-lock encryption [Rivest, Shamir, Wagner 96]
● Timed commitments [Boneh, Naor 00]
● Proofs of sequential work [Mahmoody, Moran, Vadhan 13]
A dilemma appeared to exist
Public setup
Efficient verif.
Inherently Sequential
Unique output
Sequential puzzles
Time-lock encryption
Timed commitments
Proof of seq. work
Proof of work
The road to VDFS
Motivation: verifiable lotteries
Why have we made so little progress in millenia?
Physical randomness can be (and has been) subverted
Lotteries are important in many applications 1. Fun/excitement
2. Indivisible resources
Negative lotteries are important too
Timeline for a verifiable lottery
1. Algorithm commitment
2. Open audit
3. Choose random seed
Where the action is
for p in players:
p.seed = H(p, R)
sort(players)
5. Independent verification
for p in players: p.seed = H(p, R)
sort(players)
Run algorithm
Idealized abstraction: the randomness beacon 01010001 01101011 10101000 11110000 10010100
● Unpredictable
● Unanimous
● Reliable
● High-bandwidth
● Convincing to the public?
Many applications for randomness beacons
● Lotteries
● Zero-knowledge proofs
● Consensus protocols
Communication-efficient consensus protocols
Random committee selection
Historical example: sortition
Nakamoto consensus uses (expensive) random selection
Expensive, randomized over computation performed
Trilemma: efficient, secure consensus must be randomized Sublinear communication
Nakamoto, proof-of-stake etc.
Round-robin blockchain?
Adaptively secure
Classic BFT
Deterministic
Natural beacons typically aren’t unanimous
sdo.gsfc.nasa.gov
Trusted third-party beacons
random.org
beacon.nist.gov
Physical randomness generation
Physical randomness can fail quietly
US conscription lottery, 1969
Physical randomness can fail quietly
123 852 132
456 963 645 789 897
1. Load in order 2. Rotate axially 3. Draw from top
US conscription lottery, 1969
Physical randomness can fail quietly
Financial data: The numbers game
The numbers game was historically run by mobsters
Sai Wing market data
Problem: market manipulation
Distributed randomness beacon (DRB) via commit-reveal
commit(rA,nA) commit(rB,nB)
commit(rC,nC)
R = combine(rA,rB,rC) R = combine(rA,rB,rC)
= combine(rA,rB,rC) time
The last-revealer problem
commit(rA,nA) commit(rB,nB)
commit(rC,nC)
R = combine(rA,rB,rC)
Recovery from aborts is possible, but at a cost 1. PVSS
● RandHound, RandPiper, Scrape, HydRand, SPURT 2. Threshold crypto
3. Generic MPC
Can recover from f aborted nodes, but N-f nodes can predict
Publicly-verifiable secret sharing (PVSS)
commit(rA), EncB(sAB),EncC(sAC), πA rA
rC = rec(sCA, sCB) R =comb( rA,rB.rC)
rC = rec(sCA, sCB) R =comb( rA,rB.rC)
commit(rB), EncA(sBA),EncC(sBC), πB
commit(rC), EncA(sCA),EncB(sCB), πC
DRAND/League of Entropy
● Simple beacon algorithm: Bi=H[sign(i||Bi-1)]
● Threshold BLS signatures
● Updated every 30 seconds
● Currently 16 nodes
UNICORN [Lenstra, Wesolowski 2015]
Multiparty randomness w/delay functions min time to compute delay()
R = delay(combine(rA,rB,rC)) R = delay(combine(rA,rB,rC))
R = delay(combine(rA,rB,rC))
Delay function prevents last revealer from attacking
? = delay(combine(rA,rB,r?))
Time-based crypto is a game changer
Trust model
Assumptions
Commit-reveal
One honest player
Can punish aborts
Honest majority
Standard crypto
Delay function
One honest player
Time-based crypto
General approach: verifiable delay functions
MalleBaiabsleabrlaensdoumrcseource VDF BeaBceoanconutput
Goal: can’t compute results of bias in time to act
Delay functions harden stock price-based beacons
Attacker observes near-final market data
2. Simulate lottery outcomes for many perturbations
3. Force the 3. Can’t determine
best outcome? best outcome in time
Blockchain-based beacons
prev: H( )
mrkl_root: H( )
nonce: 0x0f0f00f070f07001f1e20…
prev: H( )
mrkl_root: H( )
nonce: 0x7a83
prev: H( )
mrkl_root: H( )
nonce: 0x0f0f00f070f07001f1e20…
≤ 00000000000000001FB893000000000000000000000000000000000000000000 ? Unpredictable
✓ Unanimous
✓ Reliable
? High-bandwidth
Blockchain beacons are now an old idea
Problem: block withholding
I don’t have to publish this I win!
Problem: re-orgs
Problem: re-orgs
Problem: re-orgs
Problem: re-orgs
Hey everybody, mine here!
Problem: re-orgs
Example: chain re-orgs
I don’t know where to attack…
Delay functions also harden blockchain-based beacons
Attacker can’t figure out which branch to promote until it is too late
VDFs in one slide
API Security goals
● Setup(t, λ) → pp
● Eval(pp, x) → y, π
● Verify(pp, x, y, π) → Y/N
V: efficient to verify
D: t-sequential to solve F: unique output
Observe: removing any of V,D,F is easy
● Not verifiable: chained one-way function
F F F F F F…F y
● No delay: Many, e.g. discrete log: Find y s.t. gy = x
● Not a function: proofs-of-sequential-work
F F F F F F…F y
[Dwork, Naor 1992] Classic asymmetric delay: modular square roots
delay(x):√x (mod p)
def delay(x, p):
return modexp(x, (p+1)/4, p)
def verify_delay(x, y, p):
return x == modsquare(y, p)
Generic VDFs from succinct proofs
F F F F F…F Succinct proof system
Verifiable Delay Functions. Boneh, J. Bonneau, Bünz, Fisch. CRYPTO 2018.
Improved VDFs from succinct proofs + square roots
√ √ √ √ √…√
x2 x2 x2 x2 x2 … x2 Succinct proof system
Verifiable Delay Functions. Boneh, J. Bonneau, Bünz, Fisch. CRYPTO 2018.
Modern Algebraic VDF: squaring in group of unknown order delay(x): x2^t (mod N)
def delay(x, t, N):
return modexp(x, 2**t, N)
def verify_delay(x, y, t, N, π):
Exponent proofs in groups of unknown order
[Wesolowski 2018] [Pietrzak 2018]
Exponent proofs in groups of unknown order
Claim: y = x2^t
Challenger choose prime l
Prover computes 2t=ql + r, sends z=xq Challenger checks that y=zlxr
[Wesolowski 2018]
VDF research has exploded
● Continuous VDFs
● Post-quantum VDFs
● Watermarkable VDFs
● Trapdoor VDFs
● Zero-knowledge VDFs
● Re-randomizable VDFs
VDFs already in practical use
Eth 2.0 Beacon Chain
VDFs have re-launched the field of time-based crypto
Computational timestamping
VDFs Proofs in groups of unknown order
Efficient accumulators
Proofs of replication
Timed commitments
Fair exchange
Short-lived proofs
Transparent proof systems
Stateless blockchains
Verifiable registries
Sealed-bid auctions
My work areas in green
better DRBs from VDFs
Narwhal: An efficient distributed randomness beacon with optimal robustness. , , and (work in progress)
The trouble with UNICORN: delay in every case
? = delay(combine(rA,rB,r?))
Can we combine the best of UNICORN + Commit-reveal? Optimistic case:
● As efficient as commit-reveal (no delay function)
Pessimistic case:
● Can recover from N aborts (always same result)
● N-1 parties cannot predict or bias outcome
● One delay function to compute
One-time setup: h = g2^t
Narwhal: optimistic case
c1 = gɑ1 ɑ1 c2 = gɑ2
R = hɑ1hɑ2hɑ3 R = hɑ1hɑ2hɑ3
R = hɑ1hɑ2hɑ3
One-time setup: h = g2^t
Narwhal: pessimistic case
R = (c1c2c3)2^t
= (gɑ1gɑ2gɑ3)2^t = hɑ1hɑ2hɑ3 ✔
One-time setup: h = g2^t
An attack on Narwhal
c3 = Z(c1c2)-1 R = Z2^t
Three (provably secure) variants of Narwhal Narwhal-PC (pre-commitment to ci)
● adds an extra round Narwhal-ZK (prove knowledge of ɑi)
● adds participant overhead
Narwhal-RX (derive a pseudorandom exponent for each ci) ● adds verifier overhead
Narwhal is efficient enough to enable a new type of DRB Scales to millions of participants
● O(n), but with tiny overhead Secure if any participant is honest
● Participatory randomness beacon
Can be implemented in a smart contract Can be proven in a SNARK
Short-lived zero-knowledge proofs and signatures
Short-lived zero-knowledge proofs and signatures. , and 2022. (under submission)
Goal: Proofs that expire, as if written in disappearing ink Physical world:
Signature physically vanishes after time
Digital world:
Soundness vanishes after time
Technical requirements
● Proving true statements is efficient (given a witness)
● Forging proof of any statement possible via a slow computation
○ t-step sequential computation, for desired t
● Verifiers can’t distinguish between the two
○ Result: proof only convincing if verifier believes it was computed quickly
Defining short-lived proofs
Efficiency w.r.t. t
Setup(λ, t) →pp
May be trusted
Prove(x, w, b) →π
Efficiently prove any true statement
O(polylog(t))
Forge(x, b) →π
Forge any statement
Verify(x, b, π)
Efficient verification
O(polylog(t))
Simulate(x, b) →π
Indistinguishable output from Prove/Forge
O(polylog(t))
Extract(x, b, A) →w
Works for any t-sequential prover A
Beacons establish non-interactive proof freshness
Beacon values are unpredictable before a specific time
● Newspaper headlines
● Stock quotes
● Sports scores
● Blockchain blocks
Short-lived proofs with a beacon are convincing for a limited time window
Assumption: no timestamping Forgery delay
Beacon Proof available published
Timestamp?
Application: Deniable DKIM
Application: Deniable DKIM
Application: Verifiable voting
Voting booth
Short-lived proof
Short-lived proof
Generic construction: proof-or-VDF
Input: x, b Witness: w, y, π
Input: x Witness: w Original circuit
Input: b Witness: y, π OR VDF Verifier
● Circuit is short-lived proof of statement P (with beacon b)
● y,π added to secret witness (null for honest prover)
● Reusable: One VDF evaluation allows forging any proof (with b)
Generic SNARKs lead to non-trivial prover overhead
● RSA-2048 Wesolowski proofs with Groth16:
○ ~5M gates
○ ~60 seconds prover overhead
Σ protocols available for many types of proofs Commit(P)
Challenge() [can be H(P)]
Respond(c)
Σ-OR construction with new zero-knowledge VDFs
1. c = H(P, b)
2. πV, c2 = zkVDF.Simulate(b)
3. c1 = c ⊕ c2
4. πP = Prove(P, c1)
2. πP, c1 = Forge(P)
3. c2 = c ⊕ c1
4. y, α = zkVDF.Eval(b)
5. πV = zkVDF.Prove(b, y, α)
● DF property (zero-knowledge). Solution is never revealed
● Classic Σ-OR construction now works
● Extra benefit: reusable forgeability
Trapdoor VDFs lead to efficient short-lived signatures
● Repeated squaring in hidden-order groups is a trapdoor VDF
● Trapdoor is group order (e.g. φ(N)), enables fast evaluation
○ Exponent 2t can be reduced modulo group order
● Normally this is a downside, requiring trusted setup
● For signatures, the trapdoor can be the signing key
3.1 Short-lived signatures from trapdoor VD = VDF.Setup() //trapdoor
2. x = pad (H(m, b))
3. σ = VDF.TrapdoorEval(x, Ksig)
2. x = pad (H(m, b))
3. σ = VDF.Eval(x)
Summary of constructions
Construction
Advantages
Requirements
Generic proof-or-VDF
● Works with any VDF
● Forge any statement with
one VDF eval
● Generic ZK proofs
● Efficient circuit for VDF
verification
Sigma proof-or-VDF
● Works with any Sigma protocol
● Re-randomizable VDFs Or
● Zero-knowledge VDFs
Trap-door VDF signatures
● Very efficient, simple
● Trapdoor VD performance (using Groth16, Wesolowski, RSA-2048)
Proof overhead (bytes)
Prover time overhead
Generic SNARK or
〜60 seconds
Σ-OR with precomp
O(t) precomp.
Σ-OR with rrVDF
(time-space tradeoff)
Σ-OR with zkVDF
Sign with trapdoor VDF
Sign with watermark VDF
Comparison to other deniability notions for proofs
Generic idea: prove statement or knowledge of some secret value
Proof-or-?
Designated verifier proofs
Verifier’s private key
[Jakobbson et al. 96]
PoW solution
[Baldimtsi et al. 16]
Prover-released secret
[Specter et al. 19]
Timekeeper signature
[Specter et al. 19]
Short-lived proofs
VDF solution
[Arun et al. 21]
Future directions in time-based cryptography
0) We’re still figuring out what we can build!
Computational timestamping
VDFs Proofs in groups of unknown order
Efficient accumulators
Proofs of replication
Timed commitments
Fair exchange
Short-lived proofs
Transparent proof systems
Stateless blockchains
Verifiable registries
Sealed-bid auctions
My work in green
VDF engineering challenges
● Parameter setup
● Gap between evaluation & proving time
● Prover parallelism & memory
● Maximum attacker speedup
1) Time-based crypto requires reasoning about new attacks
Crypto community typically worries about attacker abilities to scale, not accelerate
2) Need to ensure honest parties can compute VDFs quickly ● Ongoing research on optimal hardware
● Research on incentives and economics
○ VDFs are typically a public good
○ Innovation: watermarked proofs
Candidate groups of unknown order ● RSA groups (N = pq)
○ Trusted setup (or expensive MPC) ● RSA “UFOs”
○ Large parameters (~30k)
● Class groups of binary quadratic forms
○ small parameters, but no prior deployment
3) How can we convince the public?
Open problems
● Better re-randomization strategies?
● Piggybacking on external VDF computations
● k-reusable forgeability for Sigma-based constructions
● Forgeability for signatures across multiple signers
Exponent proofs in groups of unknown order
x x2^(t/2) x2^t
Claim: (uv)t’ = vw
Challenger chooses: a, b Challenger checks: (uavb)t’ = vawb
[Pietrzak 2018]
Applications of a randomness beacon ● Lotteries
● Zero-knowledge proofs
● Consensus protocols
Randomness and zero-knowledge proofs Queries
Prover Responses Verifier
Beacon-based non-interactive ZK proofs
Proof commitment randomness Query answers
Append-only log
1.2 Generic SNARK construction with k-reusability Precomputation: A = AccumulateSet(b1,b2, … bk)
Input: x, A Witness: w, b, y, π
Input: x Witness: w Original circuit
Input: b Witness: y, π VDF Verifier
Input: A Witness: b AND Set inclusion
Stronger goal: k-reusable forgeability
● Goal: one VDF computation enables forging any proof for time T≤Tb
● Approach: include a set commitment A for k prior beacon values
○ Prove that a VDF has been solved for some b∊A
1.2 Generic SNARK construction with k-reusability Input: x, A Witness: w, b, y, π
Input: x Witness: w Original circuit
Input: b Witness: y, π VDF Verifier
Input: A Witness: b AND Set inclusion
Wesolowski proof construction
Commit: y = x2^t
Challenge: random λ-bit prime l Response: compute 2t=ql + r, send z=xq
● Verify:y=zlxr
zkVDF proof construction
● Commit: choose random v, send a=hvx2^t
● Challenge: random λ-bit prime l ● Response:
○ compute 2t=q1l + r1, v=q2l + r2
○ send z=xq1hq2, r2 ● Verify:a=zlxr1hr2
2.0 Broken construction: Σ-OR construction Σ-VDF
1. c = H(P, b)
2. y, πV = VDF.Simulate(c2)
3. c1 = c ⊕ c2
4. πP = Prove(P, c1)
2. πP, c1 = Simulate(P)
3. c2 = c ⊕ c1
4. y, πV = VDF.Eval(c2)
Problem: VDF proofs reveal y.
A non-time-bounded distinguisher can recompute and detect forgeries
2.1 Σ-OR construction with pre-computed VDF
Proof (precomp)
0.1 Choose random b*
0.2 y, πV = VDF.Eval(b*)
1. c = H(P, b)
2. c2=b⊕b*
3. c1 = c ⊕ c2
4. πP = Prove(P, c1)
2. πP, c1 = Forge(P)
3. c2 = c ⊕ c1
4. y, πV = VDF.Eval(c2 ⊕ b)
Observe: VDF evaluation only needed on a random point
(reuse breaks indistinguishability)
Re-randomizable VDFS
● Repeated squaring VDF solutions can be easily re-randomized:
○ y = b2^t
○ yr = (br)2^t
● Proofs do not easily re-randomize
● Can compute a new proof via a large advice string (also re-randomized)
2.2 Σ-OR construction with re-randomizable VDF
One-time setup
0.1 Choose random bpub
0.2 y, α = VDF.Eval(bpub)
1. c = H(P, b)
2. b*, πV = VDF.randomize(bpub,α) 3. c2=b⊕b*
4. c1 = c ⊕ c2
5. πP = Prove(P, c1)
2. πP, c1 = Forge(P)
3. c2 = c ⊕ c1
4. y, πV = VDF.Eval(c2 ⊕ b)
Setup only needed once globally, is untrusted
3.2 Short-lived signatures from watermarkable VD = VDF.Setup() //trapdoor
2. x = pad (H(m))
3. σ = VDF.TrapdoorEval(x, b, Ksig)
2. x = pad (H(m))
3. σ = VDF.WatermarkEval(x, b)
● Watermarkable VDF construction is straightforward: ○ Fiat-Shamir challenge = H(m,watermark)
Time-space tradeoffs
● Given x, y = x2^t, need an advice string of intermediate points to compute proofs
● Inherent to both Wesolowski and Pietrzak proofs of exponentiation
○ Practical performance much better with Pietrzak proofs
● Needed for three constructions presented:
○ Σ-OR + re-randomizable VDF (prover)
○ Σ-OR + zkVDF (reusable forgery)
○ Trapdoor sign + wmVDF (reusable forgery)
Time-space tradeoffs
Delay parameter
Advice size
Proof size
Prover/Forger time
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com