Pith. sign in

REVIEW 4 major objections 4 minor 25 references

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

T0 review · 4 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A proof-of-work blockchain can make its consensus computation double as a solver for arbitrary optimization problems.

desk verdict The miniblock variance/fork analysis is neat but assumes a sequential model the protocol doesn't actually implement, and the anti-reuse hinge is explicitly admitted to be breakable. read the letter →

arxiv 1908.01915 v2 pith:RLSCZMPC submitted 2019-08-06 cs.DC

Naoki Shibata This is my paper · ORCID
classification cs.DC
keywords proof-of-searchblockchainconsensusproof-of-workoptimizationproblemsusefulworkminiblocksdistributedcomputingincentivemechanism
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proposes a blockchain consensus protocol, proof-of-search, that keeps proof-of-work's decentralized trust model while putting the consensus computation to use: miners search for good approximate solutions to optimization problems submitted by clients. Instead of hashing arbitrary nonces, a miner hashes a concatenation of a solution candidate and its evaluation value, so a valid block is a probabilistic proof that many solution candidates were actually evaluated. The paper's stated result is that this can be done without sacrificing security, and in fact the probability of a fork and the variance in block time are lower than in proof-of-work when several miniblocks are required per block. If the protocol works, it offers a way to recover the electricity currently wasted by Bitcoin-style mining and turn it into a decentralized optimization service.

What carries the argument

The central object is the evaluator, a deterministic client-supplied program that assigns an evaluation value to a solution candidate; it takes the block's hash as a second argument, with a small injected error so the output depends on that argument, which forces miners to do fresh computation for every hash attempt. The searcher is the client-supplied algorithm that calls the evaluator many times, and each call also hashes the resulting miniblock, so searching and mining are one operation. The miniblock structure, with $N$ miniblocks per block each requiring its own leading-zero hash, is what converts a single lottery into $N$ smaller lotteries and thereby lowers fork probability and block-time variance.

What would settle it

Measure the output-collision rate of a real evaluator by running one solution candidate against many different second arguments; if the rate $u$ is not greater than (evaluation cost + hash cost)/hash cost, or if a miner can produce valid hashes from cached evaluations, then the proof-of-search guarantee collapses and mining reduces to ordinary proof-of-work.

Watch

Extended reading notes

Core claim

The central claim is that proof-of-work can be converted into proof-of-search without giving up PoW's guarantees: a block becomes valid only when a nonce, made of a solution candidate plus its evaluation value, hashes to the required number of leading zero bits. Because the evaluator takes the block hash as a second argument, a fresh evaluation is needed for every hash attempt, so producing a valid miniblock is a probabilistic certificate that a large number of solution candidates were evaluated. The paper's quantitative claim is that with $N$ miniblocks between blocks, a fork requires the same two-node race to be repeated $N$ times, giving fork probability $p_N = (e^{-\lambda d}(e^{-\lambda d}\lambda d))^N$ under its Poisson model, while the variance in block time becomes $1/N$; both are lower than in ordinary PoW. Rewards are split so that the client's charge goes to the best-solution finder while miniblock finders share a constant block reward, which the paper argues aligns incentives.

Load-bearing premise

The protocol only proves useful work if a client-supplied evaluator is hard to reverse-engineer or cheaply replay, so that miners cannot reuse old evaluation results to produce valid hashes; the paper itself flags this as 'a potential flaw in PoS.'

Editorial extensions

If this is right

  • A PoS blockchain can serve as a decentralized batch optimization service: any node can submit a job and any miner can work on it without trusting a coordinator.
  • Because block rewards are split across miniblocks and adjusted by job charge, the expected computation per job remains proportional to the price a client pays.
  • A fork can only win if N consecutive miniblock races are won before the competing chain, which the analysis says makes fork probability lower than PoW for the same network delay.
  • Block times become more regular as N grows, since the variance shrinks to $1/N$ of the one-miniblock variance.
  • If no jobs are submitted, empty jobs are inserted and the system degrades gracefully to ordinary proof-of-work.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A direct test of the paper's load-bearing condition would be to benchmark real evaluators, such as traveling-salesman or protein-scoring functions, for output-collision rates under varied second arguments; the paper supplies no such measurements, so the practical soundness of the condition is open.
  • If a cheap-reuse attack cannot be closed, a practical deployment would likely need to restrict clients to problems whose evaluators are hard to reverse-engineer, which would weaken the claim that any optimization problem can be used.
  • The variance-reduction argument suggests a general consensus-design recipe: split a single lottery into N smaller mandatory lotteries to stabilise block times, a recipe that could be tested in simulation with arbitrary difficulty distributions rather than only the paper's Poisson model.
  • The economics imply that job charges, not block rewards, drive solution quality; an empirical prediction is that jobs with higher charges attract more search effort and yield better solutions, which a client could audit on a live PoS chain.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper proposes 'proof-of-search' (PoS), a proof-of-work-style blockchain consensus protocol that aims to reuse mining computation for approximately solving arbitrary optimization problems. Clients submit jobs consisting of an evaluator and a searcher; miners solve the job while generating miniblocks, and a block is completed when all miniblocks for the current set of jobs are found. The paper claims that, compared with ordinary PoW, the protocol lowers both the probability of a fork (Section IV-B) and the variance of block time (Section IV-C), and that the hash-search process provides a probabilistic proof that miners evaluated many solution candidates. It also discusses incentives, payment, blockchain compaction, and applicable optimization problems.

Significance. The underlying goal of repurposing PoW energy for useful optimization work while preserving the trust model of PoW is worthwhile, and the paper contains a clean, parameter-free derivation of fork probability and block-time variance for a stylized model of N independent exponential miniblock times. Credit is also due for explicitly discussing incentive attacks, solution stealing, and unpaid jobs. However, the central claims are not supported by the protocol as written: the anti-reuse assumption in Section IV-A is not enforced or proved for public evaluators and is acknowledged as a potential flaw in Section IV-F, and the fork and variance analysis in Sections IV-B and IV-C is derived for an idealized Poisson model that differs from the actual job-selection and chain-switching protocol. Because these are the mechanisms behind the 'useful work' and 'better than PoW' claims, the paper does not currently establish its main contribution.

major comments (4)
  1. [IV-A and IV-F] The anti-reuse condition u > (C_eval + C_hash)/C_hash in Section IV-A is derived for a miner who must run the evaluator after guessing a hash, i.e., a miner who cannot predict the evaluator's output for a new second argument. That threat model does not match the protocol: the evaluator is public code registered on the blockchain (Sections III-A and III-C), so a malicious miner can inspect how the 'tiny error' is computed and can update a previously evaluated candidate to a new second argument without performing the full evaluation. Section IV-F explicitly concedes that a party who reverse-engineers the error mechanism can reuse previous evaluations and calls this 'a potential flaw in PoS'; the suggested countermeasure (introduce the error early, e.g., perturb city coordinates in TSP) is heuristic, and no lower bound is given on the cost of updating a cached evaluation to a new second argument. Without such a bound, a miner can generate valid hashes at near-PoW cost while evaluating essentially no new solution candidates, which invalidates the claimed probabilistic proof in Section III-A that consensus formation implies a large number of evaluations. This is the load-bearing security assumption of the whole scheme, not a peripheral implementation concern.
  2. [IV-B, Eq. (1)] Equation (1) asserts p_N = {e^{−λd}(e^{−λd}λd)}^N and concludes that the fork probability decreases exponentially with the number of miniblocks. The formula treats a fork as N independent successive events, but in the protocol of Section III-C a block is complete only when all N miniblocks are added, miners may work on any unfinished miniblock (Algorithm 2, line 16), and miners switch to a longer chain whenever a valid miniblock arrives. The competing chain's miniblocks can be produced by different miners, and the arrival of one miniblock changes the state of the whole mining process; therefore miniblock creation times are not independent sequential Poisson events for a single node. The probability that two nodes end up with different full blocks within a propagation delay d is not the N-th power of the single-miniblock fork probability, so the headline claim that fork probability is lower than in PoW is not established by this derivation.
  3. [IV-C, Eq. (2)] The variance statement in Section IV-C, namely that the block time has variance 1/N, is correct for the Erlang distribution in Eq. (2), which is the sum of N independent exponential random variables of rate N. It is not derived for the protocol as described: accepted miniblock arrivals are not i.i.d. exponentials because miners stop and restart on a new chain after each miniblock (Section III-C), and the block-time distribution is coupled to the fork behavior that Eq. (1) attempts to model. Since the abstract and Section IV-E claim that the variance in block time is lower than that of PoW, this idealized-model gap is load-bearing and should be resolved before the claim can be accepted.
  4. [III-C and III-D / Algorithm 2, line 16] Algorithm 2, line 16 lets each miner 'execute one of unfinished jobs' without specifying how the miner chooses a job or how job choices are made consistent across miners. The zero-bit targets in Section III-C are intended to make expected computation proportional to the charge, but Section III-D adds a separate step-count compensation rule, and the paper does not reconcile the two rules. If a miner can select the job with the highest expected reward per hash, the aggregate miniblock arrival process depends on these choices, so the fork and variance analyses in Sections IV-B and IV-C, which assume identical Poisson rates for all N miniblocks, do not apply to the actual system. A precise job-selection rule and a consistent calibration formula are needed.
minor comments (4)
  1. [Algorithm 4] In Algorithm 4, line 8, h is reassigned to hash(h, id, s, e), so on the next iteration the second argument passed to the evaluator at line 4 is no longer the block hash as described in Section III-A; the pseudocode should either use a separate variable for the block hash or explain that h represents an accumulating chain state.
  2. [IV-F] The denial-of-service discussion in Section IV-F recommends that a malicious node be banned and the payment process restarted, but the paper does not describe how banning or restart is performed in a permissionless blockchain; this deserves either a concrete mechanism or an explicit scope limitation.
  3. [IV-G] In Section IV-G, 'fintech' is a typo and should be 'fintech'.
  4. [II-B] The comparison with proof-of-useful-work [8] criticizes the unclear public demand but does not acknowledge that proofs of useful work provide a cryptographic proof that useful computation was performed, a property that the proposed protocol does not provide; noting this difference would sharpen the positioning of the paper.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper's quantitative claims are derived from explicit Poisson-process assumptions, with no fitted parameters or self-citation chain doing the work.

full rationale

The paper's headline quantitative claims—lower fork probability and lower block-time variance relative to proof-of-work—are derived in Sections IV-B and IV-C from an explicit model in which miniblocks are created as independent Poisson processes. Equation (1) gives the fork probability as p_N = {e^{-λd}(e^{-λd}λd)}^N, and Equation (2) gives the block-time distribution as b(t) = 1 - e^{-Nt} sum_{i=0}^{N-1} (Nt)^i / i!, with variance 1/N. These are mathematical consequences of the stated model and of setting N miniblocks per block; PoW corresponds to N=1. No parameter is fitted to data, no result is imported from the author's prior work, and the 'probabilistic proof that miners evaluated many candidates' is not presented as a separate empirical prediction but as a direct consequence of requiring a valid nonce to contain an evaluated candidate and a hash with a specified number of zero bits. The main weakness identified in the paper—Section IV-F's admission that an evaluator can be reverse-engineered, letting miners reuse prior evaluations—is a correctness and security concern about an unproven anti-reuse assumption, not a circularity: the analysis does not define its conclusion into its premises. There is no self-citation, no fitted-input-called-prediction, and no renaming of a known result as a derivation. The derivation chain is self-contained with respect to the claims it actually proves.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The protocol introduces new structural elements (evaluator, searcher, miniblock, second-argument hashing) but no fitted parameters. The unproven premises are the evaluator anti-reuse condition, the sequential-miniblock model, and the deterministic step-counting VM; each is load-bearing for the paper's headline claims.

assumptions (5)
  • domain assumption Miniblock creation is a Poisson process with per-node rate λ, and miniblock events are independent (Section IV-B).
    The fork probability formula pN = (e^{-λd}(e^{-λd}λd))^N treats each miniblock race as an independent Poisson event; real mining is a Poisson process only approximately.
  • domain assumption The N miniblocks are solved in a fixed sequence, so block time is the sum of N i.i.d. exponential miniblock times (Section IV-C).
    The Erlang CDF in Eq. (2) models the sum of N exponential variables; the protocol description (Algorithm 2, line 16; Section III-C) allows miners to execute any unfinished job, which would make block time the maximum, not the sum.
  • ad hoc to paper The evaluator is deterministic, step-countable, and satisfies the anti-reuse condition u > (eval+hash)/hash (Section IV-A).
    This property is required to prevent miners from reusing evaluations; the paper gives no construction and later states that reverse-engineering the evaluator is a potential flaw (Section IV-F).
  • domain assumption A deterministic interpreter-based virtual machine that counts steps can be implemented (Section III-D).
    The protocol requires platform-independent exact step counting; the paper asserts implementation 'should be straightforward' without providing a design.
  • domain assumption Network delay is a constant d for the fork analysis (Section IV-B).
    Real networks have variable delays; the constant-delay two-node model is an idealization.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Proof-of-Search: Combining Blockchain Consensus Formation with Solving Optimization Problems." pith.science (2026). https://pith.science/paper/RLSCZMPC

@misc{pith2026190801915,
  author       = {Pith},
  title        = {Pith review of: Proof-of-Search: Combining Blockchain Consensus Formation with Solving Optimization Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RLSCZMPC}},
  note         = {Machine review of arXiv:1908.01915}
}
read the original abstract

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.

Figures

Figures reproduced from arXiv: 1908.01915 by the authors.

Figure 1
Figure 1. FIGURE 1: Distributed timestamp server in Bitcoin [1] [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. FIGURE 2: Distributed timestamp server in a minimal PoS scheme [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Miners try to find a valid nonce of any miniblock that [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figures from the paper (3 more)
Figure 3
Figure 3. Figure 3: FIGURE 3: Distributed timestamp server in the proposed method [PITH_FULL_IMAGE:figures/full_fig_p006_3.png]
Figure 4
Figure 4. Figure 4: FIGURE 4: Probability of a fork after a block is added, with [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]
Figure 5
Figure 5. Figure 5: FIGURE 5: Probability that a block is added within a time [PITH_FULL_IMAGE:figures/full_fig_p010_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 24 canonical work pages

  1. [1]

    Bitcoin: A peer-to-peer electronic cash system,

    S. Nakamoto, “Bitcoin: A peer-to-peer electronic cash system,” Dec 2008, accessed: 2015-07-01. [Online]. Available: https://bitcoin.org/bitcoin.pdf

    work page 2008

  2. [2]

    A. Vries. (2018, May) Bitcoin’s growing energy problem. [Online]. Available: https://doi.org/10.1016/j.joule.2018.04.016

    doi:10.1016/j.joule.2018.04.016 2018

  3. [3]

    Pricing via processing or combatting junk mail,

    C. Dwork and M. Naor, “Pricing via processing or combatting junk mail,” in Advances in Cryptology — CRYPTO’ 92. Berlin, Heidelberg: Springer Berlin Heidelberg, 1993, pp. 139–147

    work page 1993

  4. [4]

    Proofs of work and bread pudding proto- cols(extended abstract),

    M. Jakobsson and A. Juels, “Proofs of work and bread pudding proto- cols(extended abstract),” in Secure Information Networks: Communica- tions and Multimedia Security IFIP TC6/TC11 Joint Working Conference on Communications and Multimedia Security (CMS’99) September 20– 21, 1999, Leuven, Belgium. Boston, MA: Springer US, 1999, pp. 258– 272

    work page 1999

  5. [5]

    (2014) Slimcoin a peer-to-peer crypto-currency with proof-of-burn

    P4Titan. (2014) Slimcoin a peer-to-peer crypto-currency with proof-of-burn. [Online]. Available: https://github.com/slimcoin-project/ slimcoin-project.github.io/raw/master/whitepaperSLM.pdf

    work page 2014

  6. [6]

    In Bitcoin’s orbit: Rival virtual currencies vie for acceptance,

    N. Popper, “In Bitcoin’s orbit: Rival virtual currencies vie for acceptance,” Nov 2013. [Online]. Available: https://dealbook.nytimes.com/2013/11/24/ in-bitcoins-orbit-rival-virtual-currencies-vie-for-acceptance/

    work page 2013

  7. [7]

    Proof of activity: Ex- tending bitcoin’s proof of work via proof of stake,

    I. Bentov, C. Lee, A. Mizrahi, and M. Rosenfeld, “Proof of activity: Ex- tending bitcoin’s proof of work via proof of stake,” ACM SIGMETRICS Performance Evaluation Review, vol. 42, no. 3, pp. 34–37, 2014

    work page 2014

  8. [8]

    Proofs of useful work,

    M. Ball, A. Rosen, M. Sabin, and P. N. Vasudevan, “Proofs of useful work,” 2017. [Online]. Available: https://eprint.iacr.org/2017/203

    work page 2017

Show all 25 references
  1. [9]

    Gridcoin: Crypto-currency using berkeley open infrastructure network computing grid as a proof of work,

    R. Halford, “Gridcoin: Crypto-currency using berkeley open infrastructure network computing grid as a proof of work,” May 2014. [Online]. Available: https://bravenewcoin.com/insights/ crypto-currency-using-berkeley-open-infrastructure-network-computing-grid-as-a-proof-of-work

    2014

  2. [10]

    Permacoin: Repurposing bitcoin work for data preservation,

    A. Miller, A. Juels, E. Shi, B. Parno, and J. Katz, “Permacoin: Repurposing bitcoin work for data preservation,” in Security and Privacy (SP), 2014 IEEE Symposium on. IEEE, 2014, pp. 475–490

    2014

  3. [11]

    Primecoin: Cryptocurrency with prime number proof-of- work,

    S. King, “Primecoin: Cryptocurrency with prime number proof-of- work,” p. 6, Jul. 2013. [Online]. Available: http://primecoin.io/bin/ primecoin-paper.pdf

    2013

  4. [12]

    Boinc: A system for public-resource computing and storage,

    D. P. Anderson, “Boinc: A system for public-resource computing and storage,” in Proceedings of the 5th IEEE/ACM International Workshop on Grid Computing, ser. GRID ’04. Washington, DC, USA: IEEE Computer Society, 2004, pp. 4–10

    2004

  5. [13]

    Proofs of space,

    S. Dziembowski, S. Faust, V . Kolmogorov, and K. Pietrzak, “Proofs of space,” in Advances in Cryptology – CRYPTO 2015, R. Gennaro and M. Robshaw, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2015, pp. 585–605

    2015

  6. [14]

    Spacemint: A cryptocurrency based on proofs of space,

    S. Park, A. Kwon, G. Fuchsbauer, P. Gaži, J. Alwen, and K. Pietrzak, “Spacemint: A cryptocurrency based on proofs of space,” in Financial Cryptography and Data Security. Berlin, Heidelberg: Springer Berlin Heidelberg, 2018, pp. 480–499

    2018

  7. [15]

    Proof of luck: An efficient blockchain consensus protocol,

    M. Milutinovic, W. He, H. Wu, and M. Kanwal, “Proof of luck: An efficient blockchain consensus protocol,” in SysTEX ’16 Proceedings of the 1st Workshop on System Software for Trusted Execution. ACM, 2016, pp. 2:1–2:6

    2016

  8. [16]

    (2017) The second coming of blockchain

    Intel Corporation. (2017) The second coming of blockchain. [Online]. Available: https://software.intel.com/en-us/blogs/2017/02/14/ the-second-coming-of-blockchain 12 VOLUME 7, 2019 Naoki Shibata: Proof-of-Search: Combining Blockchain Consensus Formation with Solving Optimizati...

    2017

  9. [17]

    Tendermint: Byzantine fault tolerance in the age of blockchains,

    E. Buchman, “Tendermint: Byzantine fault tolerance in the age of blockchains,” Jun 2016, accessed: 2017-02-06. [Online]. Available: https://allquantor.at/blockchainbib/pdf/buchman2016tendermint.pdf

    2016

  10. [18]

    LeMahieu

    C. LeMahieu. (2008) Nano: A feeless distributed cryptocurrency network. [Online]. Available: https://content.nano.org/whitepaper/Nano_ Whitepaper_en.pdf

    2008

  11. [19]

    Simulation of folding of a small alpha-helical protein in atomistic detail using worldwide-distributed computing,

    B. Zagrovic, C. D. Snow, M. R. Shirts, and V . S. Pande, “Simulation of folding of a small alpha-helical protein in atomistic detail using worldwide-distributed computing,” Journal of Molecular Biology, vol. 323, no. 5, pp. 927–937, 2002

    2002

  12. [20]

    The protein-folding problem, 50 years on,

    K. A. Dill and J. L. MacCallum, “The protein-folding problem, 50 years on,” Science, vol. 338, no. 6110, pp. 1042–1046, 2012

    2012

  13. [21]

    Milkyway@home: Harnessing volunteer computers to constrain dark matter in the milky way,

    H. J. Newberg, M. Newby, T. Desell, M. Magdon-Ismail, B. Szymanski, and C. Varela, “Milkyway@home: Harnessing volunteer computers to constrain dark matter in the milky way,” Proceedings of the International Astronomical Union, vol. 9, no. S298, pp. 98–104, May 2013

    2013

  14. [22]

    Portfolio selection,

    H. Markowitz, “Portfolio selection,” Journal of Finance, vol. 7, no. 1, pp. 77–91, 1952

    1952

  15. [23]

    An extension of the markowitz portfolio selection model to include variable transactions’ costs, short sales, leverage policies and taxes,

    G. A. Pogue, “An extension of the markowitz portfolio selection model to include variable transactions’ costs, short sales, leverage policies and taxes,” The Journal of Finance, vol. 25, no. 5, pp. 1005–1027, 1970

    1970

  16. [24]

    Using genetic algorithm to support portfolio optimization for index fund management,

    K. J. Oh, T. Y . Kim, and S. Min, “Using genetic algorithm to support portfolio optimization for index fund management,” Expert Systems with Applications, vol. 28, no. 2, pp. 371–379, 2005

    2005

  17. [25]

    Goodfellow, Y

    I. Goodfellow, Y . Bengio, and A. Courville, Deep Learning. MIT Press, 2016, http://www.deeplearningbook.org. PLACE PHOTO HERE NAOKI SHIBA T A is an associate professor at Nara Institute of Science and Technology. He received the Ph.D. degree in Computer Science from Osaka Uni...

    2016

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.