  Metaheuristic search strategies have proven their effectiveness against
man-made solutions in various contexts. They are generally effective in local
search area exploitation, and their overall performance is largely impacted by
the balance between exploration and exploitation.
  Recent developments in parallel local search explore methods to take
advantage of the efficient local exploitation of searches and reach impressive
results. This however restricts the scaling potential to nodes within a
private, trusted computer cluster.
  In this research we propose a novel blockchain protocol that allows parallel
local search to scale to untrusted and anonymous computational nodes. The
protocol introduces publicly verifiable performance evaluation of the local
optima reported by each node, creating a competitive environment between the
local searches. That is strengthened with economical stimuli for producing good
solutions, that provide coordination between the nodes, as every node tries to
explore different sections of the search space to beat their competition.
