Cryptology ePrint Archive: Report 2021/1379

Ofelimos: Combinatorial Optimization via Proof-of-Useful-Work \\ A Provably Secure Blockchain Protocol

Matthias Fitzi and Aggelos Kiayias and Giorgos Panagiotakos and 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.

Category / Keywords: cryptographic protocols / blockchain, proof-of-useful-work, transaction ledger, combinatorial optimization

Date: received 12 Oct 2021, last revised 14 Oct 2021

Contact author: pagio91i at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20211015:082140 (All versions of this report)

Short URL: ia.cr/2021/1379


[ Cryptology ePrint archive ]