{"id":"9df05bec-cf34-40bb-be8c-ec70f6753d94","arxiv_id":"1908.01915","paper_version":2,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"Proof-of-search is a blockchain protocol that turns mining into a search for good approximate solutions to client-submitted optimization problems while claiming to improve on proof-of-work's fork probability and block-time variance.","lead":"This paper proposes a blockchain consensus protocol, proof-of-search, that lets mining computation solve user-submitted optimization problems. It claims lower fork probability and block-time variance than proof-of-work, but the analysis and security rest on assumptions the paper itself questions.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Anti-reuse is the hinge, and it fails because evaluator code is public: Section IV-F's admitted reverse-engineering risk lets miners reuse prior evaluations, decoupling hashing from useful search.","rationale":"The reader's weakest assumption correctly identifies the evaluator anti-reuse condition as the load-bearing point, and I agree with that diagnosis. The paper's own Section IV-F admits a route to reuse, and the admission is more severe than a mere remote risk because the evaluator code is published on the blockchain: 'reverse-engineering' is not an exotic extraction of a secret but a static analysis of the exact program miners are given. Without a formal guarantee that deriving a new evaluation from an old one is as expensive as the original evaluation, the consensus mechanism can be reduced to ordinary proof-of-work with a cheap evaluator, so the computation is not demonstrated to be useful search. The other concerns noted in the reader's verdict, such as the gap between the Poisson miniblock model and Algorithm 2's 'execute one of unfinished jobs' behavior, are real and secondary: they attack the quantitative fork/variance claims, but even if those statistics were repaired, the protocol would still fail its core purpose if useful work can be bypassed. The paper's suggested mitigation of injecting error early in evaluation is a plausible research direction, but no construction, security model, or complexity assumption is supplied, and no implementation or formal verification is provided. The verdict should remain REJECT as written: the central claim is not supported, although the underlying idea is worth refining.","tokens_in":16471,"tokens_out":12270,"duration_ms":161210,"concrete_test":"Implement the paper's own suggested hardening for a TSP evaluator (Section IV-F): inject error by slightly changing city coordinates. For a fixed tour and a moderate instance, measure (1) full evaluation cost C_eval, (2) the cost of computing the evaluation for a new second argument from a previously evaluated tour plus the known coordinate perturbation, and (3) the collision rate u across many second arguments. Then check whether a miner using cached evaluations can generate valid nonces faster than honest PoS mining despite u > (C_eval+C_hash)/C_hash, or whether u falls below that bound. If either condition holds, the anti-reuse guarantee fails for the paper's own example and the proof-of-search claim is unsupported for the suggested construction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that consensus computation constitutes useful search requires that each block-hash attempt force a fresh evaluator execution. Section IV-A tries to guarantee this with the condition u > (C_eval + C_hash)/C_hash, where u is the mean number of distinct second arguments before an evaluator returns the same output for a fixed candidate. This condition is not established for the protocol as described, because the evaluator is a public program: a job includes the evaluator and is registered on the blockchain, so every miner can inspect exactly how the 'tiny error' depends on the second argument. Section IV-F concedes that if the error mechanism is reverse-engineered, prior evaluations can be reused to produce outputs for new second arguments cheaply, calling this 'a potential flaw in PoS' and proposing only a heuristic mitigation (introduce error early, e.g., perturb TSP city coordinates). No complexity assumption or proof is given that updating a cached evaluation to a new second argument is as hard as the original evaluation. Absent such a property, a miner can generate hashes at near-PoW speed without performing the expensive search, and the claimed probabilistic proof that miners evaluated many solution candidates collapses. The Section IV-A condition only bounds collision frequency for miners who cannot compute the error function; it does not address an adversary who already knows the public algorithm. This is load-bearing because it is the entire basis for the paper's claim that wasted energy is repurposed into useful optimization work.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":16672,"tokens_out":8307,"duration_ms":91698,"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":[{"comment":"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.","section":"IV-A and IV-F"},{"comment":"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.","section":"IV-B, Eq. (1)"},{"comment":"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.","section":"IV-C, Eq. (2)"},{"comment":"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.","section":"III-C and III-D / Algorithm 2, line 16"}],"minor_comments":[{"comment":"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.","section":"Algorithm 4"},{"comment":"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.","section":"IV-F"},{"comment":"In Section IV-G, 'fintech' is a typo and should be 'fintech'.","section":"IV-G"},{"comment":"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.","section":"II-B"}],"recommendation":"reject","confidential_remarks":"The author's own Section IV-F concedes that the central anti-reuse assumption may fail; in my reading, this gap is not fixable by a small revision because it would require either hiding evaluators (breaking public verifiability) or introducing a new, formally analyzed computational hardness assumption. Given the current draft, I recommend rejection, although the underlying idea could be revisited with a different construction."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper has a good idea buried in it, but the two headline claims are not supported as stated.\n\nWhat's actually new: the client-supplied evaluator/searcher framework, and the use of miniblocks to keep block time constant while running multiple jobs. The paper is clearly written, the incentive design (charge paid by client, reward for miniblock) is thoughtful, and it honestly flags its own biggest weakness in IV-F.\n\nThe soft spots are load-bearing. First, the fork and variance analysis (IV-B, IV-C) treats the N miniblocks as arriving sequentially: block time is the sum of N exponential variables, each with rate N. That gives variance 1/N and a nice fork reduction. But Algorithm 2 line 16 has each miner working on 'one of unfinished jobs' — meaning the network's hash power is split across jobs, and the time until all N are done is closer to the maximum of N exponentials, not the sum. The paper doesn't reconcile this. The variance claim overstates the improvement.\n\nSecond, the entire 'proof of search' rests on the condition in IV-A that an evaluator rarely returns the same output for the same candidate with a different second argument. That condition only defends against a naive miner who hopes the evaluation doesn't change; it does nothing against a miner who reads the public evaluator source and reverse-engineers the error function. Section IV-F admits this, calls it a potential flaw, and offers a heuristic. That is a genuine hole in the main claim that consensus forces useful work. It might be fixable with a stronger obfuscation assumption or a different construction, but it is not fixed here.\n\nThird, the assertion that 'all properties of PoW are preserved' is stated with no argument. Maybe true, maybe not, but in a security-sensitive protocol you need more than a one-line claim.\n\nWho is this for: people working on useful proof-of-work and blockchain consensus design. It is a conceptual paper with no implementation, so the value is in the ideas and the honest discussion of what can go wrong.\n\nI would send it to peer review, but I would push the authors to either change the protocol to match the sequential model or redo the analysis for the parallel case, and to either prove an anti-reuse property under a concrete assumption or substantially pull back the 'probabilistic proof of useful work' claim.","headline":"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.","tokens_in":17246,"tokens_out":2935,"would_cite":true,"duration_ms":30980,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A proof-of-work blockchain can make its consensus computation double as a solver for arbitrary optimization problems.","keywords":["proof-of-search","blockchain consensus","proof-of-work","optimization problems","useful work","miniblocks","distributed computing","incentive mechanism"],"falsifier":"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.","tokens_in":16190,"feed_emoji":"🔍","tokens_out":9642,"duration_ms":86271,"temperature":0.7,"pith_summary":"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.","feed_headline":"Proof-of-search turns blockchain mining into useful computation","feed_subtitle":"Mining effort goes to client-submitted optimization jobs, with lower fork risk and steadier block times than proof-of-work.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the proof-of-work blockchain and longest-chain majority rule that proof-of-search builds on and compares against.","marker":"[1]"},{"why":"Introduces the original proof-of-work idea for deterring spam, which the paper adapts into proof-of-search.","marker":"[3]"},{"why":"Generalizes proofs of work and bread-pudding protocols, the lineage the paper claims for useful-work consensus.","marker":"[4]"},{"why":"Gives proof-of-useful-work, the closest prior approach that the paper's design extends to arbitrary optimization problems.","marker":"[8]"},{"why":"Presents a useful-work cryptocurrency whose dependence on an external platform the paper's design is meant to avoid.","marker":"[9]"},{"why":"Shows a useful-work consensus for prime chains; the paper compares its limited public demand with general optimization jobs.","marker":"[11]"}],"fun_headline_variants":["Proof-of-search: mining becomes useful computation","Blockchain proof-of-search turns waste into solutions","Proof-of-search lowers fork probability, stabilizes blocks","Mining useful: proof-of-search reward for best solution"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.'","fun_headline_variants_meta":{"raw":{"variants":["Proof-of-search: mining becomes useful computation","Blockchain proof-of-search turns waste into solutions","Proof-of-search lowers fork probability, stabilizes blocks","Mining useful: proof-of-search reward for best solution"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000156,"raw_usage":{"total_tokens":1191,"prompt_tokens":890,"completion_tokens":301,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":506,"completion_tokens_details":{"reasoning_tokens":240}},"tokens_in":506,"tokens_out":301,"duration_ms":4256,"temperature":1.0,"reasoning_tokens":240,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:00:47.498116+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Bitcoin: A peer-to-peer electronic cash system,","cited_arxiv_id":null,"evidence_quote":"Defines the proof-of-work blockchain and longest-chain majority rule that proof-of-search builds on and compares against."},{"cited_title":"Pricing via processing or combatting junk mail,","cited_arxiv_id":null,"evidence_quote":"Introduces the original proof-of-work idea for deterring spam, which the paper adapts into proof-of-search."},{"cited_title":"Proofs of work and bread pudding proto- cols(extended abstract),","cited_arxiv_id":null,"evidence_quote":"Generalizes proofs of work and bread-pudding protocols, the lineage the paper claims for useful-work consensus."},{"cited_title":"Proofs of useful work,","cited_arxiv_id":null,"evidence_quote":"Gives proof-of-useful-work, the closest prior approach that the paper's design extends to arbitrary optimization problems."},{"cited_title":"Gridcoin: Crypto-currency using berkeley open infrastructure network computing grid as a proof of work,","cited_arxiv_id":null,"evidence_quote":"Presents a useful-work cryptocurrency whose dependence on an external platform the paper's design is meant to avoid."},{"cited_title":"Primecoin: Cryptocurrency with prime number proof-of- work,","cited_arxiv_id":null,"evidence_quote":"Shows a useful-work consensus for prime chains; the paper compares its limited public demand with general optimization jobs."}],"review_version":1}