Welcome to the resource topic for 2025/2091
Title:
Efficient and Proof-of-Useful-Work Friendly Local-Search for Distributed Consensus
Authors: Matthias Fitzi, Aggelos Kiayias, Laurent Michel, Giorgos Panagiotakos, Alexander Russell
Abstract:Blockchain protocols based on the popular Proof-of-Work'' mechanism yield public transaction ledgers maintained by a group of distributed participants who solve computationally hard puzzles to earn the right to add a block. The success and widespread adoption of this mechanism has led to staggering energy consumption devoted to solving such (otherwise) useless’’ puzzles. While the environmental impacts of the framework have
been widely criticized, this has been the dominant distributed ledger
paradigm for years.
The Ofelimos ``Proof-of-Useful-Work’’ protocol (Fitzi et al.,
CRYPTO 2022) addressed this by establishing that useful
combinatorial problems could replace the conventional hashing puzzles,
yielding a provably secure blockchain that meaningfully utilizes the
computational work that underlies the protocol.
The usefulness to wastefulness ratio of Ofelimos hinges on the properties of its underlying generic distributed local-search algorithm—Doubly Parallel Local Search (DPLS). We observe that this search procedure is particularly wasteful when exploring steep regions of the solution
space.
To address this issue, we introduce Frequently Rerandomized Local
Search (FRLS), a new generic distributed local search algorithm that
we show to be consistent with the Ofelimos architecture. While this
algorithm retains ledger security, we show that it also provides compelling
performance on benchmark problems arising in practice: Concretely, state-of-art
local-search algorithms for cumulative scheduling and warehouse
location can be directly adapted to FRLS and we experimentally
demonstrate the efficiency of the resulting algorithms.
ePrint: https://eprint.iacr.org/2025/2091
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 .