Skip to content

Blinded POW Algorithms

Prevent Mining Pool Solution Withholding Attacks by making it impossible for the miner to know whether it has found a solution or a share

Review

Proof Of Work Review

Let us define the proof of work problem as solving: $$ H(B, n) < T $$ where H, B, and T are the proof of work algorithm, the block header, and a target integer respectively, and n is a nonce. H, B, and T are capitalized to indicate that they are constant during a search, while the nonce can be changed. When this relation is true, this attempt is a "solution".

Pool Operation Review

Pools provide B and T to miners (and H is implemented by the mining software) in the form of a "candidate", and miners execute H(B,n) over many n searching for a result less than T.

Pools validate participating miners' work by requesting all results \(H(B,n) < S\) where S is some value > T. When the calculated POW falls between the target value and the share value \(\(T <= H(B,n) < S\)\) this attempt is called a “share”, and is submitted to the pool.

Shares are effectively near misses of the POW problem and provide evidence that the miner is attempting to solve the blockchain’s POW. A pool can change the value of S so that a miner submits shares more or less often.

After the time and S value of some shares are submitted, the expected number of hashes it would take to have produced those shares is calculable within some range of uncertainty. And so the pool can pay the miner a reward for that work.

Pool Solution Withholding

Pool withholding occurs when a miner submits shares, but does not submit solutions. The miner gets paid as if it was a participant in the pool, but it is not helping the pool find blocks.

This strategy is employed to harm competing pools. A pool that pays directly for shares completed may end up owing more money than it makes, which is devastating for a pool operator, and has no negative outcome to the malicious miner. Pool software has therefore been modified to only pay income from solved blocks. But it does this in proportion to shares submitted so that all miner that appear to have worked on the problem receive a portion of the payout.

This distributes the negative consequences of a miner withholding solutions to all miners in proportion to their shares. This causes miner profitability to fall, encouraging them to mine with other pools. The malicious miner does lose some revenue, but a small amount if the miner's hash power is a low percentage of the pool total.

Pool-Withholding-Resistant Proof Of Work Strategies

General Model

We need to ensure that whether a candidate is a solution is blinded (to the miner) but whether the candidate is a share is unblinded.

To accomplish this, the proof of work puzzle is modified to contain two independent puzzles that must both be solved to have a solution. One puzzle is revealed to the miner and solving it constitutes solving a share (the "share puzzle"). The other puzzle is withheld from the miner (the "hidden puzzle"). Solving both puzzles is a block solution.

The difficulty of this hidden puzzle is chosen by the pool for a particular miner, and the difficulty of the share puzzle is adjusted to compensate so the solution difficulty is unchanged. This allows the pool to control the rate at which a miner submits shares.

Blinded Block Headers

This partial solution does not prevent the miner from using side channels to gain the information required to execute an attack. It is included to build to the full solution.

Recall that POW is solving H(B,n) < T, where B is a commitment to a block. In Bitcoin, B is the block header, which contains a few fields, including T. Instead, let B be a cryptographic hash of the block header. By the first property of cryptographic hashes (irreversibility), the miner cannot determine the preimage (the block header contents) from B. The pool must therefore separately provide T since T is now hidden. In fact, the pool simply provides S (the share target) rather than T, and therefore receives both shares and solutions from miners.

Using the cryptographic hash of the block header also has the additional beneficial effect of reducing the length of B and n, which allows them to both fit inside a single round of typical cryptographic hash functions, defeating optimizations like ASIC boost.

This solution hides T from the miner, so, barring any other source of information, the miner must submit all shares to the pool to determine whether they are actually solutions. However, the blockchain is a public data structure so T can be discovered by a miner via some side channel.

An Aside on the Safety of Not Providing Block Candidates to Miners

Note that since the miner cannot see the block header the pool could provide a bogus B to the miner. But this is no worse than the relationship between pools and miners today – a pool can easily provide a miner a block with an invalid transaction since miners do not do full verification (or even receive more than the header). However, the pool has no incentive to cheat the miner, and would have a hard time targeting particular miners since the miner is generally allowed to participate anonymously.

The pool would be effectively be executing a pool withholding attack on itself because any solutions the miner discovers would not be accepted by the blockchain, but the miners shares are valid. Of course, if the pool deliberately gave invalid solutions to a miner, it knows not to pay for that miner's shares. One solution to this (likely largely theoretical) problem is to require the pool to sign the candidates it provides the miner, giving the miner the ability to prove (to others) that the pool provided candidates and did not pay for shares.

Full Proposal

We change the POW rule to fulfill two constraints as follows: $$ H(B,n) < S $$ and $$ H(B,n) \& 2^{C - 1} == D $$ where D is the "solution determinant": a random string of C bits that is specified in the block header. As above, B = H(block header), S is the share target, and n is the nonce.

S is chosen as \(T*(2^C)\) to ensure that the probability of fulfilling both constraints is the same as that of fulfilling the original difficulty problem over T.

Its important to use the same endian convention when calculating both constraints so that the bits that must be zero to match the first constraint do not overlap with bits used in the second constraint.

Note that since the block header is hidden from the miner, the miner is blinded with respect to D during the POW solution search. Even if the miner knows the actual target via a side channel, it cannot know whether it has a solution or a share because it does not know the solution determinant. Only the pools knows the block preimage, and therefore solution determinant, so the miner must submit every share/solution, or none. This defeats the pool withholding attack.

Algorithm Correctness

Since the solution determinant is committed to in the block header, the solution H(B,n) is a function of the determinant. Therefore the pool cannot change the determinant after a share is submitted to turn any share into a solution.

Also note that if the pool chooses to divulge D to the miner, the POW problem is no simpler.

This algorithm requires that T never get so low that it forces the LSB C bits in the solution to be 0. This seems to be to be a safe assumption with 256 bit hash functions. However, there is no requirement and little benefit for there be only 256 bits in the POW algorithm's result. In some blockchains the block identifier and POW use the same algorithm and result (notably Bitcoin). In these cases expanding the result would unnecessarily lengthen the block identifier. However, it makes more sense to separate these concepts. Ideally the block identifier should be as efficiently calculated as possible while meeting the necessary properties of cryptographic hashes. On the other hand, a POW algorithm may be designed to be very complex or memory intensive.

By separating the POW algorithm and the block identifier, the POW solution space could be increased to use cryptographic hashes that produce arbitrarily more ouput bits, without affecting blockchain size.

TODO: prove S is chosen as \(T*(2^C)\) to ensure that the probability of fulfilling both constraints is the same as that of fulfilling the original difficulty problem over T.

Prior Work

In (2), Eyal analyses the pool withholding attack formally. In (1) Rosenfeld describes basic pool operation and payout systems. In section 6.2.3, the paper briefly offers a specific solution to pool withholding that essentially breaks the POW puzzle into hidden and revealed puzzles as described here. While requiring a hard fork, POW puzzle change, block header change, and additional block fields, the proposed solution is perhaps still overly connected to the Bitcoin model, resulting in complexity and inefficiencies. His revealed puzzle's difficulty (e.g. share puzzle) cannot be adjusted, limiting its practical usefulness. And rather than blinding the entire header from the miner, he withholds a secret and commits to the secret in the block header. It is not explicitly stated, but presumably this secret must then be passed to all validating nodes with the header so that block proof of work can be verified. Finally, validating the secret puzzle requires a SHA256 operation, placing a burden on a busy pool.

More recent publications ignore proof of work changes, and instead focus on reward schemes to discourage pool solution withholding (3,4).

References

(1) Meni Rosenfeld. 2011. Analysis of Bitcoin pooled mining reward systems. https://arxiv.org/abs/1112.4980. sha256(f1646a121046a337656d0f7ee6927cece8bdd8adf869602d2d52c29bb54f2b1b)

(2) I. Eyal. 2014. The miner’s dilemma. https://arxiv.org/abs/1411.7099. sha256(d479715d590bd5f09b67a997759fba2904df6ee4991a7cf156e6a5531b9123f6).

(3) Schrijvers, O.; Bonneau, J.; Boneh, D.; and Roughgarden, T. 2017. Incentive compatibility of bitcoin mining pool reward functions. https://timroughgarden.org/papers/bitcoin.pdf. sha256(4eef4e387d6cb09311a9c74eb433040e36a156350945b26db097f921d4aa8edc)

(4) Alkalay-Houlihan, Shah. 2019. The Pure Price of Anarchy of Pool Block Withholding Attacks in Bitcoin Mining. https://www.cs.toronto.edu/~nisarg/papers/bitcoin_poa.pdf. sha256(4332e5b0b742a30e9623ff64c7b7f077b4954e4ffabd0a908f6e1c2c47ad3aad)