Innovative Approaches in Blockchain Optimization
Delve into cutting-edge advancements in blockchain technology focusing on Proof-of-Useful-Work (PoUW) and its implications for solving real-world optimization challenges. Explore the delicate balance between blockchain security and utility, alongside the contributions PoUW makes to solving hard optimization problems efficiently.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Ofelimos: Combinatorial Optimization via Proof-of-Useful-Work Matthias Fitzi Aggelos Kiayias Giorgos Panagiotakos Alexander Russell IACR Crypto 2022
Permissionless Blockchain [N08] Maintain transaction ledger via sequential updates A B: 10 X Y: IOU S T: Public maintenance Sibyl! Resource-based lottery: compete for next update
Bitcoin: Proof-of-Work Blockchain [N08] Proof of Work (PoW) [DN92,JJ99] Solve moderately hard puzzle on given challenge Energy waste Bitcoin: carbon footprint of Greece Alternatives Proof-of-Space[DFKP13,...] (different resource) Proof-of-Stake [BPS16,CM16,KRDO16] (different setup) Proof-of-Useful-Work [here]
Proof-of-Useful-Work (PoUW) Blockchain Repurpose work for computation of real benefit Previous work Compute primes [K12]: not truly useful Resource-efficient mining [ZEEJ+17]: trusted hardware Dist. problem solving [DT20,LDBG+20,...]: no formal analysis Folklore belief: uselessness of PoW is essential for blockchain security
The PoUW Dilemma Blockchain security vs usefulness useful (real-word problems) adversary may have advantage (inject solved problems, ) secure pose useless pseudorandom problem instances
Our Contributions PoUW blockchain solving hard optimization problems useful: real-world client problems (logistics, scheduling, SAT solving) formal security proof (ROM): < adversarial comp. power (weak adversary: < adversarial comp. power (strong adversary: UW for free) no UW speedup) usefulness rate : ~ 1 ~ UW runtime dist. concentrated / weak adversary UW runtime dist. concentrated / strong adversary for bad choices of UW No trusted hardware / third parties
PoW in Bitcoin H(Bctr) < T Mine block: Bctr Bctr H publish Bctr append Bctrto longest chain ctr++ Essential: Fast evaluation (per challenge Bctr) & moderately hard success prob
PoW in Bitcoin ? Mine block: Bctr Bctr H UW publish Bctr append Bctrto longest chain ctr++ Essential: Fast evaluation (per challenge Bctr) & moderately hard success prob Require: Problem instance non-trivial client incentive Decomposable into small uniform steps keep essential property Excellent fit: Stochastic Local Search
Stochastic Local Search (SLS) Computationally hard optimization problem (e.g., TSP) State space S, objective function f(.) Perform random walk in the state space S Goal: find s S to minimize f(s) s = M(s), f(s ) <? f(s) (exploration step M) Highly relevant in practice: Logistics (warehouse location, ) Event scheduling (NFL) SAT Solver
Preparing SLS for PoUW Doubly Parallel Local Search (DPLS) Update(.) Update(.) Update(.) M ( G , z=2 , r1 ) M ( G , z=2 , r2 ) M ( G , z=2 , rk ) Init Update(.) Update(.) pick best Exploration algorithm M Update(.) Update(.)
From PoW to PoUW publish ( Bctr) Bctr H < T ctr++ PoW: hash block against target T
From PoW to PoUW publish ( Bctr, sbest, s ) seed (Bctr , z) H M H s (new state) < T ? ctr++ sbest s Embed exploration step M (useful work) Keep best state sbestfor publication
From PoW to PoUW publish ( Bctr, sbest, s ) seed (Bctr , z) H M H s (new state) < T1 < T ctr++ ? ctr++ sbest s Defend against grinding (variance in M complexity) ExpectedSteps [H(Bctr) < T1 ] worst-case complexity of M less concentrated runtime of M : more compensation by pre-hashing
From PoW to PoUW publish ( Bctr, sbest, s , SNARG ) seed (Bctr , z) H M H SNARG s (new state) < T1 < T ctr++ ? ctr++ sbest s Minimize verification / block validation time Note: 2 SNARGS for many M steps
Analysis: Assumptions Definition: Exploration algo M is (w, ,k)-moderately hard (MH) if: [simplified] Adversary succeeds with probability negl( ) in game: attempt to create m k = poly( ) PoUW queries in time < (1- ) m w (w: worst-case time complexity of M) We assume (w, ,k)-MH ( obtaining non-trivial results for any [0,1] )
Analysis: PoUW Mining is stateful Correlation of mining successes makes PoW mining insecure Add rule: no immediate restart on new longest chain create new block only after transition M SNARG 1-p Miner States tsnarg post- hash 1-p1 w pre-hash block p p1 1
Analysis: Miners Decorrelate Fast Markov-Chain Mixing via Coupling Initialize: (P1,...,Pm)0in pre-hash and (S1,...,Sm)0indep. wrt. stationary distribution Update: Same update for Piand Si (indep. for each i wrt. miner state transitions) pcouple: Hit pre-hash within E = 1 + w + tsnargsteps, p1 1/w pcouple (1 - p1) E 1-p Miner States tsnarg post- hash 1-p1 w pre-hash block p p1 1
Analysis: Miners Decorrelate Fast Markov-Chain Mixing via Coupling Initialize: (P1,...,Pm)0in pre-hash and (S1,...,Sm)0indep. wrt. stationary distribution Update: Same update for Piand Si (indep. for each i wrt. miner state transitions) pcouple: Hit pre-hash within E = 1 + w + tsnargsteps, p1 1/w pcouple (1 - p1) E (1-1/w) ( e-1- O(1/w) ) Stat. dist.: T=L E steps: || (P1,...,Pm)T (S1,...,Sm)T || tv m (1-pcouple)L c w c 1-p Miner States tsnarg post- hash 1-p1 w pre-hash block p p1 1
Analysis: Security Miner states close to independent (adapt existing machinery) Intuition: ( =1) MH: tolerate adversarial computing power ( =0) MH: tolerate adversarial computing power
Analysis: Usefulness Usefulness U: rate at which useful work (M) is performed [simplification] worst-case(M) average-case(M): U add ( =0) MH: (single prehash) U 1
Conclusion Proof-of-Useful-Work Blockchain Protocol solving real-world client optimization problems formal security analysis (ROM) tolerate < t < adversarial computation power moderate hardness ( = 1) ( = 0) usefulness for concentrated exploration algo M 1 ( =1) ( =0) Reduce substantial amount of waste produced by proof-of-work blockchains
Acknowledgements Gorilla icon created by Freepik - Flaticon Sibyls painted by Michelangelo Acropolis provided by Wikipedia
PuoW: Fast State Updates Input Block (IB) seed (Bctr , z) H M H SNARG s (new state) < T1 < T < t ctr++ Ranking Block (RB) ? ctr++ sbest s PoW protected transactions IB IB IB IB Input Endorsers IB IB RB RB RB relevant for consensus
