Welcome to the resource topic for 2021/1379
Title:
Ofelimos: Combinatorial Optimization via Proof-of-Useful-Work \ A Provably Secure Blockchain Protocol
Authors: Matthias Fitzi, Aggelos Kiayias, Giorgos Panagiotakos, Alexander Russell
Abstract:Minimizing the energy cost and carbon footprint of the Bitcoin blockchain and related protocols is one of the most widely identified open questions in the cryptocurrency space. Substituting the proof-of-work (PoW) primitive in Nakamoto’s longest chain protocol with a {\em proof of useful work} (PoUW) has been long theorized as an ideal solution in many respects but, to this day, the concept still lacks a convincingly secure realization. In this work we put forth Ofelimos, a novel PoUW-based block-chain protocol whose consensus mechanism simultaneously realizes a decentralized optimization-problem solver. Our protocol is built around a novel local search algorithm, which we call Doubly Parallel Local Search (DPLS), that is especially crafted to suit implementation as the PoUW component of our blockchain protocol. We provide a thorough security analysis of our protocol and additionally present metrics that reflect the usefulness of the system. As an illustrative example we show how DPLS can implement a variant of WalkSAT and experimentally demonstrate its competitiveness with respect to a vanilla WalkSAT implementation. In this way, our work paves the way for safely using blockchain systems as generic optimization engines for a variety of hard optimization problems for which a publicly verifiable solution is desired.
ePrint: https://eprint.iacr.org/2021/1379
Talk: https://www.youtube.com/watch?v=aQTQQi8-Vq0
Slides: https://iacr.org/submit/files/slides/2022/crypto/crypto2022/423/slides.pptx
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .