# Proof-of-Search: Combining Blockchain Consensus Formation with Solving Optimization Problems

arXiv: https://arxiv.org/abs/1908.01915 · HTML: https://mlsanity.com/paper/1908.01915/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Aug 2019.

## Built on by (most cited first, 2 of 2)

- [Byzantine-Resilient Learning Beyond Gradients: Distributing Evolutionary Search](https://mlsanity.com/paper/2304.13540/) (2023)
- [SEDULity: A Proof-of-Learning Framework for Distributed and Secure Blockchains with Efficient Useful Work](https://mlsanity.com/paper/2512.13666/) (2025)

## Abstract (arXiv)

To address the large amount of energy wasted by blockchains, we propose a decentralized consensus protocol for blockchains in which the computation can be used to search for good approximate solutions to any optimization problem. Our protocol allows the wasted energy to be used for finding approximate solutions to problems submitted by any nodes~(called clients). Our protocol works in a similar way to proof-of-work, and it makes nodes evaluate a large number of solution candidates to add a new block to the chain. A client provides a search program that implements any search algorithm that finds a good solution by evaluating a large number of solution candidates. The node that finds the best approximate solution is rewarded by the client. Our analysis shows that the probability of a fork and the variance in the block time with our protocol are lower than those in proof-of-work.