APoW: Auditable Proof-of-Work Against Block Withholding Attacks Sergio Demian Lerner Abstract We introduce Auditable Proof-of-Work (APoW), a novel proof-of-work (PoW) construction inspired by Hashcash-style nonce searching, which enables the auditing of other miners’ work through accountable re-scanning of the nonce space. The proposed scheme allows a miner to probabilistically attest to having searched specified regions of the nonce space in earlier mining rounds, while concurrently earning rewards for performing productive work for a new block or pool share. This capability enables miners belonging to a mining pools to audit another miner’s claimed effort retroactively, thereby allowing the probabilistic detection of block withholding attacks (BWAs) without requiring trusted hardware or trusted third parties. As a consequence, the construction supports the design of decentralized mining pools in which work attribution is verifiable and withholding incentives are substantially reduced. The scheme preserves the fundamental properties of conventional PoW, including public verifiability and difficulty adjustment, while adding an orthogonal auditability layer tailored to pool-based mining. Finally, while a full deployment of APoW in Bitcoin would require a consensus rule change and minor modifications to mining Application-Specific Integrated Circuits (ASICs), the construction remains practically useful even without consensus changes, for instance, as a pool-level auditing mechanism that enables verifiable pay-for-auditing using existing pool reserves. Keywords: Proof-of-Work, Bitcoin, Auditable Proof-of-Work; APoW; Block Withholding Attacks; Mining Pools; Decentralized Mining; Hashcash; Nonce Searching 1 Introduction Mining pools [ 1 , 5 ] are the dominant coordination mechanism in proof-of-work systems such as Bitcoin [ 2 ] , allowing individual miners to reduce variance by aggregating hashpower and sharing rewards proportionally to contributed work. In a typical pool protocol, workers repeatedly attempt proof-of-work puzzles and submit shares—partial solutions that meet a reduced difficulty threshold—to demonstrate ongoing effort. When a full solution is found, the corresponding block is broadcast to the network and the resulting reward is distributed among the participants according to the pool’s payout policy. A Block Withholding Attack [ 5 , 3 ] (BWA) arises when a malicious worker (or coalition of workers) deliberately suppresses valid full-difficulty blocks while continuing to submit low-difficulty shares to the pool. From the pool’s perspective, the attacker appears to contribute honestly: shares are valid, timely and statistically consistent with the expected effort. However, by withholding blocks, the attacker reduces the effective block discovery rate of the pool, thereby harming other participants or enabling strategic advantages in competitive settings. BWAs are particularly difficult to detect because, under standard proof-of-work constructions, the absence of a block is not itself evidence of misbehavior. Block discovery is a low-probability event, and variance alone can explain extended periods without successful blocks even for honest miners. Consequently, distinguishing deliberate withholding from statistical fluctuation requires long observation windows and provides, in the best case, weak confidence guarantees. As a result, most existing pool protocols cannot attribute blame or provide cryptographic evidence of withholding behavior. The problem is exacerbated in decentralized or trust-minimized pool designs, where pool operators lack both identity-based enforcement mechanisms and trusted execution environments. Traditional countermeasures—such as reputation systems, payment delays, or centralized monitoring—either reintroduce trust assumptions or remain vulnerable to Sybil attacks and strategic churn. Fundamentally, BWAs exploit a structural limitation of conventional proof-of-work schemes: while valid solutions are publicly verifiable, unsuccessful search effort leaves no auditable trace. While zero-knowledge proofs could, in principle, certify exhaustive search without revealing individual attempts, constructing such proofs for hash-based PoW entails prohibitive computational and protocol overhead. Pools must therefore infer honesty indirectly from share statistics, an approach that is inherently probabilistic and slow to react. This limitation motivates the exploration of proof-of-work constructions that preserve standard validation properties while enabling miners to later demonstrate, in a verifiable manner, that specific regions of the nonce space were genuinely explored. In this work, we address this gap by introducing a proof-of-work mechanism that supports auditable reuse of prior nonce-space, allowing pools or third parties to probabilistically verify past mining effort while new work is being performed. This added auditability enables the detection of block withholding behavior without requiring trusted hardware, interactive protocols, or changes to the network’s block validation rules, thereby opening the door to decentralized mining pools with stronger resistance to BWAs. 1.1 Mining Pool Payment Schemes and Exposure to Block-Withholding Attacks Mining pools employ a variety of reward distribution schemes to compensate participating miners for contributed hash power. These schemes differ significantly in how mining variance is allocated between miners and pool operators, and consequently in their susceptibility to block-withholding attacks (BWAs), in which a miner submits valid low-difficulty shares while deliberately withholding full-difficulty blocks. Block-withholding incentives. A key observation from prior work is that the profitability of a BWA depends critically on whether a miner’s payout is conditioned on the pool’s actual block discovery events. If rewards are independent of block discovery, a withholding miner can preserve their expected income while reducing the pool’s revenue, thereby creating a strictly profitable deviation. Classification of payment schemes. We classify the most widely deployed mining pool payment schemes according to their resistance to BWAs: • Block-conditioned schemes , such as Pay-Per-Last- N -Shares (PPLNS) and score-based variants, distribute rewards only when the pool successfully mines a block. In these schemes, withholding a valid block reduces the attacker’s own expected revenue, rendering BWAs economically irrational. • Share-conditioned schemes , such as Pay-Per-Share (PPS), compensate miners solely based on submitted shares, regardless of block discovery outcomes. These schemes transfer all variance risk to the pool operator and make BWAs strictly profitable. • Hybrid schemes , such as PPS+, partially condition rewards on block discovery (typically for transaction fees), resulting in intermediate exposure to BWAs. • Full Pay-Per-Share (FPPS) schemes extend PPS to both the block subsidy and transaction fees by paying miners the expected value of each per share, thereby maximizing pool-side variance and BWA exposure. Security comparison. Table 1 summarizes this classification. Scheme Variance Bearer BWA Resistance BWA Profitability PPLNS Miner Strong No Score-based Miner Strong No PPS+ Shared Moderate Partial PPS Pool Weak Yes FPPS Pool Very weak Yes Table 1: Classification of mining pool payment schemes by resistance to block-withholding attacks. Empirical exposure of Bitcoin hashrate. Based on public disclosures by major mining pools, historical hashrate distribution data, and advertised payout options, we estimate that approximately 25%–35% of the current Bitcoin network hashrate participates in pools offering PPS or FPPS-style payouts, and is therefore economically susceptible to block-withholding attacks in the absence of additional detection or auditing mechanisms. This estimate accounts for large pools that either operate exclusively under PPS/FPPS or offer these schemes as a selectable option, and excludes pools that rely solely on PPLNS or score-based methods. While the exact fraction varies over time with market conditions and miner preferences, the prevalence of PPS-style payouts highlights a fundamental tension between payout predictability and incentive compatibility in mining pool design. Implications. The above classification illustrates that widely deployed pool payment mechanisms remain vulnerable to BWAs unless miner compensation is explicitly tied to verifiable block discovery. This motivates the exploration of alternative constructions, such as auditable proof-of-work mechanisms, that can preserve predictable payouts while restoring incentive compatibility without requiring trusted pool operators or trusted hardware. 2 Prior Work on Deterring BWA Block withholding attacks (BWAs) exploit a structural feature of pooled mining: a worker can appear productive by submitting low-difficulty shares while selectively suppressing full-difficulty block solutions, thereby reducing the pool’s block revenue without immediately revealing misbehavior. Since block discovery is a rare event, a pool observing “too few” blocks cannot, in general, distinguish malice from variance using only standard share statistics. 2.1 Rosenfeld’s Oblivious Shares Proposal Rosenfeld’s early analysis of pooled mining identifies block withholding as a practical deviation available to dishonest pool participants and surveys several mitigation ideas [ 5 ] . In §6.2.3, Rosenfeld proposes oblivious shares , a protocol-level mechanism intended to make it possible for a pool to determine whether a submitted share is also a valid block, while preventing the miner from knowing this fact at the time of discovery. Intuitively, the pool supplies work that is constructed so that only the pool can recognize full-block solutions among the shares it receives; thus, a miner cannot selectively withhold blocks because it cannot identify them. Limitations and deployment frictions. While conceptually appealing, oblivious shares introduce several important constraints that are in tension with modern pooled-mining practice: 1. Hard fork / header reinterpretation. To apply an oblivious-shares-style mechanism to Bitcoin, a hard-fork is required: a difficult-to-achieve network-wide coordination procedure. Both full nodes and SPV/light clients would need to upgrade to preserve their security model, since the proof-of-work predicate they implicitly rely on is tied to header semantics. Alternative variants that avoid requiring light-client upgrades have been discussed, but at a cost of significantly reduced security for those clients [ 7 , 6 ] . 2. Share-submission latency versus immediate block broadcast. Under Stratum v2 in certain modes, a worker that finds a full block can broadcast it directly to the P2P network so propagation begins immediately, potentially before the share reaches the pool server. With oblivious shares, by design, the worker cannot recognize a block solution; the share must first be delivered to the pool and transformed into a full block before it can be broadcast, introducing additional latency in the best-case honest setting [ 7 ] . 3. Pool centralization. Rosenfeld’s oblivious-shares approach relies on the pool having secret information that allows it to distinguish block-valid shares from ordinary shares. This requirement naturally concentrates authority at the pool operator, who must generate private templates, control share interpretation, and act as the sole entity capable of recognizing and broadcasting valid blocks. As a result, the protocol structure inherently favors centralized pool architectures. 2.2 Rosenfeld’s “pop quiz” Proposal In addition to oblivious shares, Rosenfeld discusses an alternative deterrence mechanism informally referred to as a “pop quiz” approach [ 5 ] . The idea is to occasionally challenge miners with tasks intended to test whether they are behaving honestly, requesting them to scan a nonce space for which the pool already knows contains a solution. This method has an important limitation: quiz challenges are often distinguishable from ordinary mining work. In practice, a miner receiving a quiz template can detect that it does not correspond to the current tip of the chain (e.g., due to a stale block height or an unexpected parent hash). Once a miner recognizes that a task is a quiz, he may behave honestly, avoiding detection. 2.3 Peer Reviews and Short-Lived Audits Proposal An idea similar to the pop quiz is to temporarily perform ”peer reviewed” mining: the pool requests that two competing miners mine the same nonce range for a short period. We can also use the mechanism as an audit scheme, like ours, by requesting a miner to re-scan the nonce space range scanned by another miner in a previous block. However, the pool cannot dedicate much resources to pop-quizzes or audits without substantial losses, and the probability of catching a cheater is very low. Consequently, while pop quizzes and audits may provide a weak probabilistic deterrent, they usually cannot collect cheating evidence before the pool goes bankrupt. Additionally, audit/review hashing does not contribute to the effective hash rate of the pool, so the miner can rationally choose to ignore the challenge entirely. 3 Description APoW permits miners to operate in two distinct modes. In normal mining mode , a miner searches for a proof-of-work solution for the current block in a manner analogous to Bitcoin. In audit mining mode , a miner simultaneously performs productive mining and audits prior mining effort, an activity we refer to as verification mining or v-mining . A miner engaged in v-mining is called a v-miner , and a block produced as a result of v-mining is termed a verification block (v-block). A miner may enter or exit v-mining for variable durations, depending on pool policy and auditing requirements. We define a mining round i as the mining activity associated with block height i . For a miner A , the search space S_{i}^{A} in round i is defined as the set of nonce intervals explored by A during that round. Each element of S_{i}^{A} is called an auditable work unit and is represented by a tuple (G,n_{s},n_{e}) , where G is a block template header, [n_{s},n_{e}] is a contiguous nonce interval scanned under that template, and all templates G appearing in auditing work units of S_{i}^{A} share the same parent block. For clarity of exposition, we assume a single nonce field of sufficient precision, even though Bitcoin conceptually splits the nonce into an extraNonce (most significant bits) and a nonce (least significant bits). This abstraction does not affect the generality of the construction. When miner A ’s work in round i is audited by another miner B , the auditor does not re-execute the entire search space S_{i}^{A} . Instead, B audits only a randomly selected subset of S_{i}^{A} , yielding a probabilistic verification of A ’s claimed mining effort. In Section 6.5 , we describe how the search space S_{i}^{A} associated with a miner A is communicated to the mining pool and subsequently assigned to an auditor in a centralized pool setting. We further discuss how analogous information can be disseminated in a decentralized mining pool, allowing multiple participants to independently reason about and audit the claimed search space S_{i}^{A} . A v-miner B can v-mine in round j ( 0i) . The v-miner derives the bit strings b_{2} from B_{ID}(j-1) , the block ID on the canonical blockchain at height j-1 . We define b_{2} as b_{2}=\mathsf{pref}_{d}\!\left(H(B_{ID}(j-1))\right) (2) Proof-of-work search. For each nonce test, we build the message M from G and the nonce. The v-miner samples n\leftarrow\{0,1\}^{l_{n}} in the range [n_{s},n_{e}] and computes X:=H(M) as normal, until the work condition X=b_{2}\,\|\,y_{m} (3) is satisfied, with any bit-string y_{m}\in\{0,1\}^{\lambda-{d}} . To provide a finer-grained measurement of difficulty, instead of difficulties that can be only powers of 2, we can compute a maximum distance of the target from the d -bit truncated hash digest to the target value u . While the powers-of-2 difficulty adjustment method was used in pre-release versions of Bitcoin, the launched version of Bitcoin uses the distance from the hash digest to zero. The pattern matching method can be used by the mining hardware only for some leading bits of b_{2} , eliminating the need for a more expensive subtraction operation in the ASIC. Sealing and validation. After finding the PoW, the v-miner builds v-block which consists of the tuple ( i,G_{i},n,j,G_{j},\sigma ) where G_{i} is the template audited at height i , G_{j} is the new block template for height j and \sigma is a signature of the tuple (excluding the signature field), for the public key associated with the auditing of G_{A} . The nonce n is valid if it results in the expected PoW for template G_{A} with the target pattern b_{2} , according to the difficulty for a block at height i . The field G_{i} is valid if it satisfies all the conditions of a block header for height i except for its modified PoW. For G_{i} the \mathsf{poolAddress} must be a valid payment address for the ledger. This is the address used to receive the v-block reward. The field G_{j} is valid if it satisfies all the conditions of a normal block for height j . No PoW is required for this template (the PoW was delegated to G_{i} ). The \mathsf{poolAddress} field of G_{j} is ignored. 3.7 Avoidance of Long Forks In the absence of explicit penalties for equivocation, a miner may attempt to submit multiple competing v-blocks at the same height j , differing for instance in their transaction sets or timestamps. Short-lived forks of depth 1 are not inherently problematic and are common in Nakamoto-style consensus. Several hybrid consensus protocols that combine proof-of-work and proof-of-stake, such as 2-hop [ 8 ] and TwinsCoin [ 9 ] , explicitly tolerate single-block forks by enforcing that the block following a PoS-extended block must be a standard PoW block. This structural constraint prevents the formation of long runs of stake-extended blocks and ensures that forks cannot grow unboundedly without additional PoW investment. We adopt a similar rule: any v-block must be immediately followed by a regular PoW block. As a consequence, not all auditable work units associated with a v-block can necessarily be audited in the immediately following round. However, these units remain eligible for auditing in subsequent rounds. Figure 2 shows a valid blockchain mixing block and v-blocks without consecutive v-blocks. Figure 2: A blockchain mixing blocks and v-blocks auditing previous work units (w.u.), with v-blocks immediately followed by a regular PoW block. More generally, we allow auditing to be performed up to D rounds after the corresponding block is mined. This bounded auditing window preserves chain growth while preventing the accumulation of long forks induced by equivocation at the v-block layer. 3.8 V-Block Attribution We present three scheme variants to attribute a v-block and be able to pay its reward. Paying to the pool. Every block i contains the field \mathsf{poolAddress}_{i} in its block template. This is the address where v-blocks are paid. The address is extracted from the message M in the v-block. The address can be controlled by the pool server, or it can be a smart contract controlled address in the mainchain (if it has this capability) or it can be a sidechain exit address that forwards the funds to a smart contract on a sidechain. The pool server or pool smart contract is responsible for sharing the reward among the workers, in the same manner as a normal block reward. The server can also track who was the auditor of the audited block and pay a special prize to that worker. Alternatively, a field \mathsf{lastBlock}_{i} could be added to the block template. This field would indicate the block ID of the last block created by the same pool that was included in the canonical chain. The protocol could retrieve that block coinbase transaction and distribute the reward to the same addresses and in the same proportion used in the referenced block. This enables Bitcoin decentralized mining pools that pay their workers directly from the coinbase transaction using multiple outputs. Paying an auditor whose identity is derived from proof-of-work. The scheme can embed auditor selection directly into the consensus protocol, allowing the identity of the auditor to be deterministically known and derived from the blockchain itself. To this end, we extend the block template with an additional field \mathsf{auditorsRoot} , defined as the Merkle root of a set of public keys (or ledger addresses) corresponding to all eligible auditors within a mining pool. This field must be built by the mining pool itself and forwarded to all miners. When auditing a share at height i , the identifier of block i already recorded on the blockchain is used as a seed to a cryptographically secure pseudorandom number generator (CSPRNG) that selects a single auditor from the committed set. As a result, immediately after block i is published, the pool can determine which miner is eligible to act as auditor during the mining of block i+1 . If a v-block is subsequently produced, it must include a Merkle inclusion proof linking the selected auditor’s public key to \mathsf{auditorsRoot} , thereby allowing the consensus protocol to verify both the correctness of the auditor selection and the legitimacy of the reward recipient. The v-block can also be sealed with the auditor’s private key, committing to a new block template for height i+1 to be processed with the v-block. Paying to any auditor. The v-miner can include in the transaction T a zero-knowledge proof that he knows M , while revealing all its components except for the nonce. The v-miner can associate the proof with his public address, by proving its knowledge and showing it. Nobody can take attribution of the v-block without finding the nonce themselves. The \mathsf{poolAddress}_{i} field is not required in this case. A generalized formalization of a ZK-PoW is presented in the Appendix A . 3.9 Pool Share Difficulty Management The difficulty of mining a block is 2^{d} (expressed in base-1 difficulty). By requesting the matching of a subset of bits in b instead of all of them, the mining pool can control the difficulty of a share coming from a v-miner. 4 APoW Compared to Prior Work We compare our scheme with the existent solutions to BWA. 4.1 Oblivious Shares vs Our Approach Rosenfeld’s oblivious shares scheme aims to hide from the miner whether a given share is a valid block, thereby preventing selective suppression. In contrast, our construction targets a different axis: it enables auditing of claimed historical search effort by allowing miners to probabilistically attest, while mining current work, to having previously scanned specified regions of nonce space for earlier blocks or shares. This distinction matters operationally. Oblivious shares require the pool to maintain secret information (and typically to control template construction) so that the miner cannot classify solutions at discovery time. Our design instead provides an auditability layer that can be applied retroactively: miners can be challenged to produce evidence consistent with prior scanning while still producing valid shares that will be rewarded by the pool. As a result, our construction supports decentralized pool designs in which miners retain autonomy and no single party must be trusted to correctly identify or disclose block solutions. While our approach avoids several sources of centralization inherent in oblivious-share constructions, it is not without significant deployment friction for existing blockchains. In particular, upgrading Bitcoin to use the proposed proof-of-work function constitutes a consensus-level change and, therefore, requires a hard fork of the Bitcoin consensus protocol. As a consequence, both full nodes and light clients must upgrade to correctly interpret and validate the new proof-of-work predicate. Moreover, because the construction departs from existing SHA-256–based mining by replacing zero bit checks with bit pattern matches, it may necessitate the deployment of new specialized hardware or ASIC designs adapted to the revised workload. These requirements imply a higher coordination and adoption threshold than approaches that operate purely at the mining-pool protocol layer. Consequently, any practical deployment on top of an existing blockchain would need to demonstrate that the benefits of block withholding deterrence and decentralized pool support outweigh the substantial costs associated with network-wide consensus changes and hardware transition. 4.2 “Pop quiz” (and its variants) vs Our Approach Rosenfeld’s pop-quiz proposal and our construction share a common intuition: randomized auditing can be used to deter block withholding even when misbehavior cannot be cryptographically detected. The key difference lies in how the verification cost is handled. In pop-quiz schemes, the hashing spent verifying other miners is not rewarded by the blockchain, limiting their practical effectiveness as a BWA deterrent. In contrast, our approach enables miners to reuse prior nonce-space exploration while mining new blocks or shares. Importantly, this verification occurs concurrently with productive mining, rather than as a separate re-mining step, and therefore does not negate the economic efficiency of pooled mining. 5 Security We identify three potential attacks related to the fairness of mining and v-mining, and we show how our scheme resist such attacks. PoW results caching. A miner could try to store all X ’s computed during the mining of a previous block, and when mining a new block, she could fetch the X ’s from memory, instead of hashing. Using state-of-the-art technology, memory access is at least an order of magnitude slower than computing a hash operation in a pipelined ASIC. Accessing RAM also consumes between one and two orders of magnitude more electricity than computing the hash on-the-fly. Also, memory has to be accessed twice: one for storing and another for loading. Nevertheless, RAM cost would still make this mining method astronomically expensive. An advanced Bitcoin miner performs 200 TH/s and must be run for 600 seconds on average until a new block is found. Assuming 256 bits per hash digest, this implies storing 4 exabytes ( 2^{62} bytes). That amount of RAM would make a v-mining machine cost more than 10 Trillion dollars as of 2025. Memory-CPU trade-off provides little help with regard to RAM costs. Assuming that all hash operations are stored sequentially, each cached hash operation j requires the storage of X_{j} , which is 256-bits in length. It is neither necessary nor optimal to store X_{j} in full. The digests X_{j} could be partially stored and recomputed in full after a positive match with the partial target pattern, to verify the full match. For example, if we store 16-bits per digest, we can retrieve 8 hash results per RAM memory access (assuming a 128-bit wide data bus). This results in an 8X speedup for RAM access and still leaves plenty of time for a CPU or a non-pipelined hashing core to recompute promising partial matches. Since the nonce candidates to check will not be sequential, they need to be transmitted to the hashing component, thus the communication can become the system’s bottleneck. While this optimization could make storing and retrieving results as fast as hashing, the v-mining machine would still cost over 1T dollars. The attacker can also store just 1 bit per hash, packing bits in a 128-bit hint word that can be retrieved in a single RAM access. The attack requires the building of a special ASIC architecture that reads hint words, scans its bits while it increments the nonce counter at double clocking speeds. This small overclocked circuit would stall for 1 cycle when a valid bit (0 or 1) is found in the hint bit sequence, so that the corresponding nonce enters the hashing pipeline, keeping it almost full. Although this design may work, the machine would still cost 39B USD due to its large RAM requirement. BWA while v-mining. A malicious v-miner could withhold solutions while v-mining. Since normally the role of auditor would be rotating among all miners, and the hashrate directed towards auditing would be only a small portion of the total hashrate, the impact of a BWA during auditing may be negligible. Nevertheless, we can also change the scheme to enable v-miners to be audited. Let us assume that the block at height i was audited at height k and that auditing process is audited at height j with ( i