{"id":"707d83dd-bde6-41bf-8481-bfc2995c0b44","arxiv_id":"2504.14328","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"ScaloWork replaces hash-based mining with minimum dominating set problems on isomorphic graph instances and uses distributed pool mining to scale and prevent solution stealing.","lead":"This paper proposes ScaloWork, a proof-of-work system in which miners earn block rewards by finding small dominating sets in large graphs instead of hashing. It is worth reading because it tries to turn the energy spent on cryptocurrency mining into useful computation and claims to fix security and fairness flaws in earlier useful-proof-of-work designs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Security against solution stealing rests on an unproven practical hardness of graph isomorphism for the paper's own scale-free instances; standard canonical-labeling tools may break Theorems 4–5.","rationale":"Agree with the reader's weakest_assumption. The central claim is conditional on practical isomorphism hardness; if that fails, the scheme reduces to a competition in which the first pool to broadcast any valid dominating set can be cloned by every other pool, so the 'useful work' is not actually required and the protocol is not 'as secure as hash-based PoW'. The other concerns (k attainable by greedy, apples-to-apples comparison) are real and reinforce rejection, but the isomorphism point is the load-bearing one because it attacks the security guarantee rather than the performance/liveness parametrization. Note also that the protocol's own design makes the adversary's task easier than the Theorem 4 model: instances are public before block generation, enabling precomputation; and Section 5 uses synthetic scale-free graphs, the very class for which degree-sequence anchors make canonical labeling likely easy. The internal concession in Theorem 5 about distinct-degree hubs strengthens this. Because the paper provides no experimental GI-hardness data for its generated instances, the security claim is unsubstantiated on the exact benchmark class used to claim outperformance. I would not change the reader's REJECT; the result should be revised with an empirical GI-hardness evaluation or an alternative solution-stealing defense before resubmission.","tokens_in":20416,"tokens_out":4206,"duration_ms":42122,"concrete_test":"Take the exact Barabási-Albert graph-generation parameters used in Section 5 (e.g., n = 100,000 with average degree 50; or the instances in the public GitHub repo), create two random relabelings, and run nauty's labelg (or Traces/bliss) on the pair on hardware comparable to the paper's Threadripper setup. If canonical labelings or an explicit isomorphism are returned in seconds to minutes—far below a 10-minute TG_max—Theorem 4 is empirically refuted for the paper's own benchmark class; repeat on 100 random relabelings to check consistency. Also record the time to compute an isomorphism mapping from one relabeling to the other directly, since that is exactly what a solution-stealing pool needs.","verdict_should_be":"UNCHANGED","load_bearing_attack":"ScaloWork's headline security property ('as secure as hash-based PoW') and its defense against solution stealing reduce to Theorems 4 and 5: two mining pools get different public isomorphic instances, and another pool cannot find the isomorphism within TG_max. The proof only counts n! mappings and invokes Babai/Helfgott quasi-polynomial worst-case bounds; it never addresses practical canonical-labeling algorithms (nauty/Traces/bliss) or average-case hardness for the Barabási-Albert scale-free instances used in Section 5. The paper's own Theorem 5 concedes that if the b high-degree vertices have distinct degrees, 'the mapping is straightforward'; scale-free graphs have exactly that skewed degree structure, so this admission undermines the claimed hardness. Moreover, all z isomorphic instances are dumped into the public problem pool before the mining phase, so an adversary can canonicalize all instances and compute pairwise isomorphisms before TG_max begins; when an honest pool broadcasts a dominating set, translating it to the adversary's instance is immediate if canonical forms match. The n!-search argument in Theorem 4 is therefore not the right model, and the claim that solution stealing is prevented with negligible probability is not supported for the paper's own instance class.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"ScaloWork is a proof-of-useful-work framework that proposes to replace Bitcoin's hash-based PoW with computation of minimum dominating sets (MDS) on large graph instances. Each mining pool receives a distinct isomorphic instance of the same graph, computes a dominating set via a distributed greedy algorithm, and the best solution within a time limit determined by a lookup table wins the block. The paper claims that the scheme is as secure as hash-based PoW, provides solution extractability, eliminates free-riders, and outperforms the Chrisimos protocol in scalability and efficiency. The paper presents a security analysis and experiments on synthetic Barabási-Albert and Erdős-Rényi graphs.","tokens_in":20696,"tokens_out":11387,"duration_ms":96211,"significance":"The proposed direction is timely: reusing PoW computation for useful optimization problems is an active research area, and giving each pool a unique isomorphic instance is a reasonable approach to deterring solution stealing. The paper also contributes a comparative experimental study against Chrisimos and a prototype implementation. However, the central claims are not substantiated by the current analysis. The liveness of the protocol depends on unproved assumptions about the greedy algorithm's solution quality and the sufficiency of the block-time estimate, while the security argument relies on a graph-isomorphism hardness assumption that the paper's own Theorem 5 undermines for scale-free instances. These are load-bearing gaps, not presentation issues.","major_comments":[{"comment":"Algorithm 1 only accepts a dominating set of size at most k = n(1+ln(1+δ))/(1+δ). Theorem 2 guarantees only a ln Δ approximation for Algorithm 3, and no proof is given that the greedy algorithm can find a set of size ≤ k for the benchmark graphs. If no such set is found within T_G^max, the pool aborts, so the protocol can stall even when all pools are honest. The paper needs either a proof that Algorithm 3 meets the Alon-Spencer bound on the relevant instances or a different acceptance criterion.","section":"Section 3.2 (Algorithm 1) and Theorem 2"},{"comment":"Lemma 1 is circular: T_G^max is set to lτ with l>1 using times from the authors' own greedy implementation, and for new instances scaled by |E''||V''| / (|E'||V'|). The proof concludes the time is sufficient because the lookup table was made with the greedy heuristic, but a multiple of a measured time is not a proof that the same heuristic will complete on a new instance within that limit. This directly affects liveness and should be replaced by a formal or empirically validated hardness model.","section":"Section 3.3, Lemma 1"},{"comment":"The security against solution stealing rests on the assumption that no pool can compute an isomorphism between two public isomorphic instances within T_G^max. The proof only counts n! mappings and cites worst-case quasi-polynomial algorithms, ignoring practical canonical-labeling tools. Theorem 5 explicitly concedes that if the high-degree vertices have distinct degrees, 'the mapping is straightforward'; Barabási-Albert scale-free graphs have exactly this property. Since all isomorphic instances are public before mining, an adversary can precompute canonical forms and translate another pool's dominating set immediately. The negligible-probability claim is not supported for the paper's own instance class.","section":"Section 4.1, Theorems 4 and 5"},{"comment":"The statement that two pools will never receive the same graph instance is over-strong. The instance index is computed as H(h⟨MR,τ'⟩||hBprev) mod z; for z instances, two distinct preimages produce the same index with probability about 1/z, which is not negligible for the pool counts discussed in the paper. The protocol must handle index collisions explicitly.","section":"Section 4.1, Theorem 3"},{"comment":"The claim that ScaloWork eliminates free-riders is not backed by a concrete mechanism. The paper says that from the lack of information on a free rider's assigned vertices it will be 'easy to point out' and penalize free-riders, but no protocol or analysis describes how the pool manager verifies individual contributions, distributes rewards, or detects and punishes a miner who withholds span updates. This is a central contribution and needs a complete specification.","section":"Section 3.2, free-rider resistant pool mining"}],"minor_comments":[{"comment":"The bilinear pairing is described as 'degerate'; the intended term is 'non-degenerate'.","section":"Section 2.3"},{"comment":"The caption says Chrisimos stops at node count 100000 due to the 15-minute cutoff, while the text reports 197 minutes at 500000 nodes; these statements are inconsistent.","section":"Section 5, Figure 1 and text"},{"comment":"The notation for committee public keys is inconsistent: Algorithm 2 uses 'pk mt' after earlier defining a committee of size |cm|.","section":"Section 2.5 and Algorithm 2"},{"comment":"Section 3.1 assumes a partially synchronous communication model, but Section 4.2 says safety and liveness are proved in the synchronous model; the mismatch should be addressed.","section":"Section 4.2"},{"comment":"The claim that the greedy heuristic takes O(|V|) time should be clarified; Algorithm 3 is a distributed algorithm with O(n) rounds, and the relationship between rounds and wall-clock time is not immediate.","section":"Lemma 3"},{"comment":"The ScaloWork storage total is given as 2K|E| edges, but each isomorphic instance has |E| edges; the arithmetic should be checked.","section":"Section 5, storage overhead"},{"comment":"The statement that n=100 gives more than 2^600 possibilities appears to overestimate; log2(100!) is about 525, so the bound should be corrected.","section":"Theorem 4"}],"recommendation":"reject","confidential_remarks":"The manuscript addresses a significant problem and includes a working prototype, but the core security and liveness arguments are not currently supportable. The graph-isomorphism hardness assumption is particularly troublesome because the authors themselves note the straightforward mapping when hub degrees are distinct, which is the generic case for scale-free graphs. I do not see a way to repair this within the scope of a normal revision, as the protocol's security design depends on that assumption. The writing also contains numerous typos and inconsistent notations, which suggests the manuscript needs substantial further work before it can be reconsidered."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this paper is worth reading if you care about useful proof-of-work, but the main security claim is not supported. The genuinely new pieces are per-pool isomorphic instances to prevent solution stealing, a distributed greedy pool-mining protocol, and free-rider resistance. Those are real contributions relative to Chrisimos, and the authors correctly identify real weaknesses in that earlier protocol: probabilistic graph extension kills extractability and adds storage and verification overhead.\n\nWhat the paper does well: giving each pool a different isomorphic copy of the same graph is a clean way to equalize hardness and preserve extractability. The distributed greedy scheme is a plausible way to partition work, and free-riding becomes detectable because each miner's partial result must contribute to a global dominating set; a wrong or missing share breaks the solution. The code is on GitHub and the storage-overhead comparison with Chrisimos is simple and sound.\n\nNow the soft spots, in proportion. The load-bearing security proof—that a pool cannot map another pool's solution to its own isomorphic instance within the block interval—does not hold up for the paper's own instance class. Theorem 4 argues from the n! search space and Babai's worst-case quasipolynomial bound, but the adversary does not need worst-case general graph isomorphism. All z isomorphic instances sit in the public problem pool before mining starts, so a pool can canonicalize every instance offline with nauty/Traces/bliss; on Barabási-Albert scale-free graphs, those tools often finish quickly. Theorem 5 actually concedes that if the high-degree vertices have distinct degrees—which scale-free graphs typically do—the mapping is straightforward. That concession undermines the negligible-probability claim.\n\nThere is a second issue that is independent of graph isomorphism. Algorithm 1 accepts a dominating set only if its size is at most the Alon-Spencer bound k, but the distributed greedy algorithm is only proved to be a ln Δ approximation for MDS. No argument shows it can reach k. If greedy cannot hit that bound, the block interval liveness argument is vacuous. Lemma 1 is also not a proof: it sets TG_max = l·τ with l > 1 by construction, so it asserts sufficiency rather than demonstrating it. The experimental comparison is not apples-to-apples either: Chrisimos runs solo on the extended graph while ScaloWork uses 48 threads, so “outperforms in all aspects” conflates parallelism with protocol improvement.\n\nWho this is for: researchers working on useful PoW or blockchain consensus will find the protocol design instructive and the attack surface worth probing. The paper deserves a serious referee because the ideas are real and the code ships, but the current security analysis is not close to proving the headline claim. My recommendation: send it to peer review, expect major revision, and if the scale-free isomorphism hardness cannot be fixed with an instance-class-specific argument, the secure-PoW claim should be withdrawn.","headline":"ScaloWork is a genuine engineering extension of Chrisimos with a clean per-pool isomorphism idea, but its headline security claim rests on an unproven practical hardness of graph isomorphism for scale-free instances and the accepted solution bound may not be attainable by the prescribed greedy algorithm.","tokens_in":21160,"tokens_out":2372,"would_cite":false,"duration_ms":24905,"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":"ScaloWork replaces hash-based Bitcoin mining with minimum dominating set puzzles and proves the scheme as secure as hash-based proof-of-work.","keywords":["Bitcoin","Proof-of-Work","Proof-of-Useful-Work","Minimum Dominating Set","Graph Isomorphism","Distributed Pool Mining","Free-rider Problem","NP-Complete Problem"],"falsifier":"Take pairs of isomorphic scale-free graphs with the vertex counts and average degrees used in the experiments (100 thousand to 5 million vertices, average degrees 50–100), reveal the dominating set of one member, and run a modern graph-isomorphism or canonical-labeling solver to recover the mapping and translate the dominating set to the other member; record the wall-clock time against the corresponding TG_max. If the translation time is routinely below TG_max, the paper's claim that stealing is negligible is empirically refuted.","tokens_in":20196,"feed_emoji":"⛏️","tokens_out":8893,"duration_ms":73945,"temperature":0.7,"pith_summary":"ScaloWork is a proof-of-useful-work framework that replaces the hash puzzle in a Bitcoin-style blockchain with the task of finding a small dominating set—the smallest set of vertices that covers every node of a graph—on real-world network instances. It claims that this mining work is genuinely useful, because utility companies can read the dominating set directly from the mined block, and that the protocol is 'as secure as hash-based PoW'. To protect miners from solution stealing, each pool receives a different isomorphic copy of the same graph, so all pools face equal-hardness instances while an attacker cannot cheaply translate another pool's solution. The framework also supports distributed pool mining through a distributed greedy algorithm, which makes large graphs tractable and lets pool managers detect free-riders who submit useless shares. If the claims hold, blockchain mining energy would produce usable solutions to minimum dominating set problems instead of wasting power on hashes.","feed_headline":"ScaloWork makes mining solve minimum dominating sets","feed_subtitle":"A dominating-set proof-of-work claims hash-grade security, direct solution extraction, and fairer pools.","key_machinery":"The load-bearing mechanism is the combination of isomorphic problem instances with a distributed greedy dominating-set algorithm. A minimum dominating set is the smallest subset of vertices such that every vertex is either in the subset or adjacent to one of its members. The utility company submits z isomorphic copies (same graph with relabeled vertices) of its instance, and a pool's block header selects which copy it mines deterministically; the paper argues from the n! relabeling space and the best-known quasi-polynomial isomorphism algorithm that no pool can recover the mapping within the block interval TG_max, so one pool cannot steal another's solution. Miners in a pool run a greedy heuristic that repeatedly adds the highest-span vertex (the node covering the most uncovered vertices within distance two), giving a ln Δ-approximation and making each miner's contribution independently checkable. The framework surrounds this with committee-signed graph instances, a lookup table that sets TG_max from graph size and degree, and a chain-selection rule that prefers the chain with more accumulated work, where work is graph size times the ratio of the bound to the submitted dominating set size.","core_discovery":"The paper's central claim is that a useful proof-of-work based on the minimum dominating set (MDS) problem, with isomorphic per-pool instances and a distributed greedy pool-mining protocol, is as secure as hash-based PoW while solving several problems that block earlier MDS-based systems. Each mining pool is assigned an isomorphic copy of a graph supplied by a utility company; the pool that returns the smallest valid dominating set within a block interval wins the block and the reward. Because the instances are isomorphic, every pool faces the same hardness, and because the utility company holds the mapping, the returned dominating set is directly extractable as a solution for the original graph—the paper's answer to Chrisimos's extractability problem. The paper further claims that the distributed greedy algorithm removes free-riders, since every miner's contribution is a verifiable part of the solution, and that experiments show ScaloWork scales to graphs of millions of nodes with block generation times far below Chrisimos. Theorems 4 and 5 assert that recovering the isomorphism between two instances, or translating another pool's dominating set from one instance to another, has negligible probability within the block interval.","pith_inferences":["The security proof rests on the hardness of graph isomorphism for the specific scale-free instances; since off-the-shelf isomorphism and canonical-labeling tools are fast on structured graphs, the negligible-probability claim should be tested empirically on the paper's generated graphs rather than taken from the n! bound alone.","The performance claim is measured in a single-machine, 48-thread simulation of pool members; a real deployment must add network latency, message loss, and Byzantine miners, so the reported 'outperforms Chrisimos in all aspects' should be read as a laboratory result until a multi-pool testbed is run.","The same framework could carry other NP-complete problems with polynomial-time verification, such as clique or graph coloring, as the paper mentions; the key requirement is a supply of instances for which isomorphism recovery stays hard and solutions remain practically useful.","The chain-selection rule's work metric weights solution quality against graph size; one unexplored consequence is that pools may be incentivized to mine larger graphs or manipulate graph parameters if the reward formula does not align hardness with payment, a game-theoretic question the paper leaves open."],"forward_implications":["If ScaloWork is as secure as hash-based PoW, the same Nakamoto-style consensus frame can run on useful computation: honest majority, fork resolution by accumulated work, and block confirmations are preserved.","Mining pools can be rewarded by solution quality and verifiable participation, so a miner cannot claim a share with fake work; free-rider detection becomes a property of the consensus protocol.","Utility companies can obtain minimum dominating set solutions for their network instances directly from the public blockchain, giving real-world applications such as sensor coverage, rumor containment, and transmission monitoring a subsidized computation service.","The block interval time can be tuned through the lookup table, allowing the difficulty of the mining puzzle to be adjusted by graph size and average degree rather than by a hash target.","Because each pool mines a distinct instance, the per-block workload remains equal across pools even when many pools compete, avoiding the topology advantages that Chrisimos's probabilistic extension creates."],"supporting_citations":[{"why":"Chrisimos, the prior MDS-based PoUW that ScaloWork replaces; supplies the lookup-table idea and the baseline for performance claims.","marker":"[27]"},{"why":"The quasi-polynomial graph-isomorphism algorithm invoked to argue that finding the mapping between isomorphic instances takes too long inside the block interval.","marker":"[32]"},{"why":"The improved exponent for quasi-polynomial isomorphism, used in the same infeasibility argument for Theorems 4 and 5.","marker":"[33]"},{"why":"The probabilistic bound for the size of a dominating set, used as the acceptance threshold that miners must beat.","marker":"[36]"},{"why":"BLS aggregate signatures, used to let the auditing committee jointly endorse graph instances and to construct the time-locked reward transaction.","marker":"[37]"},{"why":"The rotating-share committee election approach, used to assemble an auditing committee with an honest majority.","marker":"[46]"},{"why":"The difficulty-estimation framework for combinatorial optimization instances, used by the committee to reject too-easy graphs.","marker":"[47]"},{"why":"The cited source for the distributed greedy heuristic that underlies pool mining and free-rider detection.","marker":"[48]"}],"fun_headline_variants":["ScaloWork: PoW that solves minimum dominating sets","Dominating-set mining is secure and pool-friendly","Useful PoW with extractable solutions, no free-riders","Chrisimos but faster, more scalable, and fairer"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The defense against solution stealing assumes that no mining pool can recover the relabeling between two publicly available isomorphic graph instances within the block interval time; if practical graph-isomorphism or canonical-labeling tools solve these instances faster than that, the security argument fails.","fun_headline_variants_meta":{"raw":{"variants":["ScaloWork: PoW that solves minimum dominating sets","Dominating-set mining is secure and pool-friendly","Useful PoW with extractable solutions, no free-riders","Chrisimos but faster, more scalable, and fairer"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000934,"raw_usage":{"total_tokens":4055,"prompt_tokens":1064,"completion_tokens":2991,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":680,"completion_tokens_details":{"reasoning_tokens":2923}},"tokens_in":680,"tokens_out":2991,"duration_ms":20113,"temperature":1.0,"reasoning_tokens":2923,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:51:48.917889+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take pairs of isomorphic scale-free graphs with the vertex counts and average degrees used in the experiments (100 thousand to 5 million vertices, average degrees 50–100), reveal the dominating set of one member, and run a modern graph-isomorphism or canonical-labeling solver to recover the mapping and translate the dominating set to the other member; record the wall-clock time against the corresponding TG_max. If the translation time is routinely below TG_max, the paper's claim that stealing is negligible is empirically refuted.","supporting_citations":[{"cited_title":"Minimum connected dominating set based rsu allocation for smartcloud vehicles in vanet,","cited_arxiv_id":null,"evidence_quote":"Chrisimos, the prior MDS-based PoUW that ScaloWork replaces; supplies the lookup-table idea and the baseline for performance claims."},{"cited_title":"The graph isomorphism problem,","cited_arxiv_id":null,"evidence_quote":"The quasi-polynomial graph-isomorphism algorithm invoked to argue that finding the mapping between isomorphic instances takes too long inside the block interval."},{"cited_title":"Graph isomorphism in quasipolynomial time,","cited_arxiv_id":null,"evidence_quote":"The improved exponent for quasi-polynomial isomorphism, used in the same infeasibility argument for Theorems 4 and 5."},{"cited_title":"Computers and intractability,","cited_arxiv_id":null,"evidence_quote":"The probabilistic bound for the size of a dominating set, used as the acceptance threshold that miners must beat."},{"cited_title":"The miner’s dilemma,","cited_arxiv_id":null,"evidence_quote":"The rotating-share committee election approach, used to assemble an auditing committee with an honest majority."},{"cited_title":"Enhancing bitcoin security and perfor- mance with strong consistency via collective signing,","cited_arxiv_id":null,"evidence_quote":"The difficulty-estimation framework for combinatorial optimization instances, used by the committee to reject too-easy graphs."},{"cited_title":"Controlling the difficulty of combinatorial optimization problems for fair proof-of-useful-work-based blockchain consensus protocol,","cited_arxiv_id":null,"evidence_quote":"The cited source for the distributed greedy heuristic that underlies pool mining and free-rider detection."}],"review_version":1}