## CryptoDB

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

Authors: Matthias Fitzi , IOHK Aggelos Kiayias , University of Edinburgh and IOHK Giorgos Panagiotakos , IOHK Alexander Russell , University of Connecticut and IOHK Search ePrint Search Google Slides CRYPTO 2022 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.
##### BibTeX
@inproceedings{crypto-2022-32183,
title={Ofelimos: Combinatorial Optimization via Proof-of-Useful-Work},
publisher={Springer-Verlag},
author={Matthias Fitzi and Aggelos Kiayias and Giorgos Panagiotakos and Alexander Russell},
year=2022
}