International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Ofelimos: Combinatorial Optimization via Proof-of-Useful-Work

Matthias Fitzi , IOHK
Aggelos Kiayias , University of Edinburgh and IOHK
Giorgos Panagiotakos , IOHK
Alexander Russell , University of Connecticut and IOHK
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2022
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 {\em Ofelimos}, a novel PoUW-based blockchain 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.
Video from CRYPTO 2022
  title={Ofelimos: Combinatorial Optimization via Proof-of-Useful-Work},
  author={Matthias Fitzi and Aggelos Kiayias and Giorgos Panagiotakos and Alexander Russell},