Ofelimos: Combinatorial optimization via proof-of-useful-work

Matthias Fitzi; Aggelos Kiayias; Giorgos Panagiotakos; Alexander Russell

doi:10.1007/978-3-031-15979-4_12

Ofelimos: Combinatorial optimization via proof-of-useful-work

Matthias Fitzi, Aggelos Kiayias, Giorgos Panagiotakos^*, Alexander Russell

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 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 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. DPLS can be used to implement variants of popular local search algorithms such as WalkSAT that are used for real world combinatorial optimization tasks. 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.

Original language	English
Title of host publication	Advances in Cryptology – CRYPTO 2022
Editors	Yevgeniy Dodis, Thomas Shrimpton
Publisher	Springer
Pages	339-369
Number of pages	31
Volume	13508
ISBN (Print)	9783031159787
DOIs	https://doi.org/10.1007/978-3-031-15979-4_12
Publication status	Published - 13 Oct 2022
Event	42nd Annual International Cryptology Conference - Santa Barbara, United States Duration: 15 Aug 2022 → 18 Aug 2022

Publication series

Name	Lecture Notes in Computer Science
Volume	13508
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	42nd Annual International Cryptology Conference
Abbreviated title	CRYPTO 2022
Country/Territory	United States
City	Santa Barbara
Period	15/08/22 → 18/08/22

Keywords / Materials (for Non-textual outputs)

Blockchain
consensus
proof-of-useful-work
stochastic local search

Access to Document

10.1007/978-3-031-15979-4_12

FitziEtalCRYPTO2022OfelimosCombinatorialOptimizationSubmitted manuscript, 1.07 MBLicence: Creative Commons: Attribution (CC-BY)

https://ia.cr/2021/1379Licence: Creative Commons: Attribution (CC-BY)

Cite this

@inproceedings{5496199cb6c4446592aa61413160c2df,

title = "Ofelimos: Combinatorial optimization via proof-of-useful-work",

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{\textquoteright}s longest-chain protocol with a 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 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. DPLS can be used to implement variants of popular local search algorithms such as WalkSAT that are used for real world combinatorial optimization tasks. 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.",

keywords = "Blockchain, consensus, proof-of-useful-work, stochastic local search",

author = "Matthias Fitzi and Aggelos Kiayias and Giorgos Panagiotakos and Alexander Russell",

note = "Publisher Copyright: {\textcopyright} 2022, International Association for Cryptologic Research.; 42nd Annual International Cryptology Conference, CRYPTO 2022 ; Conference date: 15-08-2022 Through 18-08-2022",

year = "2022",

month = oct,

day = "13",

doi = "10.1007/978-3-031-15979-4\_12",

language = "English",

isbn = "9783031159787",

volume = "13508",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "339--369",

editor = "Yevgeniy Dodis and Thomas Shrimpton",

booktitle = "Advances in Cryptology – CRYPTO 2022",

address = "United Kingdom",

}

Fitzi, M, Kiayias, A, Panagiotakos, G & Russell, A 2022, Ofelimos: Combinatorial optimization via proof-of-useful-work. in Y Dodis & T Shrimpton (eds), Advances in Cryptology – CRYPTO 2022. vol. 13508, Lecture Notes in Computer Science, vol. 13508, Springer, pp. 339-369, 42nd Annual International Cryptology Conference, Santa Barbara, California, United States, 15/08/22. https://doi.org/10.1007/978-3-031-15979-4_12

Ofelimos: Combinatorial optimization via proof-of-useful-work. / Fitzi, Matthias; Kiayias, Aggelos; Panagiotakos, Giorgos et al.
Advances in Cryptology – CRYPTO 2022. ed. / Yevgeniy Dodis; Thomas Shrimpton. Vol. 13508 Springer, 2022. p. 339-369 (Lecture Notes in Computer Science; Vol. 13508).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Ofelimos

T2 - 42nd Annual International Cryptology Conference

AU - Fitzi, Matthias

AU - Kiayias, Aggelos

AU - Panagiotakos, Giorgos

AU - Russell, Alexander

PY - 2022/10/13

Y1 - 2022/10/13

N2 - 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 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 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. DPLS can be used to implement variants of popular local search algorithms such as WalkSAT that are used for real world combinatorial optimization tasks. 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.

AB - 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 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 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. DPLS can be used to implement variants of popular local search algorithms such as WalkSAT that are used for real world combinatorial optimization tasks. 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.

KW - Blockchain

KW - consensus

KW - proof-of-useful-work

KW - stochastic local search

UR - https://www.scopus.com/pages/publications/85141680590

U2 - 10.1007/978-3-031-15979-4_12

DO - 10.1007/978-3-031-15979-4_12

M3 - Conference contribution

AN - SCOPUS:85141680590

SN - 9783031159787

VL - 13508

T3 - Lecture Notes in Computer Science

SP - 339

EP - 369

BT - Advances in Cryptology – CRYPTO 2022

A2 - Dodis, Yevgeniy

A2 - Shrimpton, Thomas

PB - Springer

Y2 - 15 August 2022 through 18 August 2022

ER -