Block Withholding Defense

[mcelrath]

A Block Withholding Attack (BWA) is an attack whereby one pool mines on another pool in order to decrease its profitability. If they ever win a block, they withhold this block and do not send it to the pool. Since the attacker gets paid for shares, the marginal cost of this attack is low.

This is nearly impossible to detect, but we can expect to be attacked this way.

If miners are allocated a range of nonces [A,B], and come back for another range of nonces [C,D] claiming to not have found a share, we know a range of nonces which should not contain a bitcoin block. We can then allocate a different miner to re-mine this range of nonces. This is probably the only way to detect this attack.

We could also analyze the "luck" of individual miners, and choose to re-mine the nonces of miners with only the lowest luck. If done quickly enough before a new block comes, this could even result in additional profit for the pool.

Furthermore upon detection of a nonce range containing a withheld block, we can invalidate all shares by that miner, increasing the profits of honest miners, and increasing the cost to the attacker.

A defense (of the attack) is a Sybil Defense with with many different miner identities. This way even if one Sybil identity is discovered, a fewer number of shares are invalidated. Since we can't prevent miners from joining with a new identity or connect with multiple identities, we can't programmatically prevent this.

Now obviously this is a "waste" of hashrate and we'd need to decide how much hashrate (w%) to devote to this defense. If the luck of the pool is high, we probably shouldn't re-mine nonce ranges at all. An analysis to determine w could include:

1. Given the luck of the pool, we can estimate how much BWA hashrate could be in the pool. Above some threshold, start re-mining nonce ranges.
2. Analyze subsets of (small) miners with low luck and treat them as a single miner, for the purpose of identifying the attacker and re-mining shares. (See Sybil Defense)
3. Determine the detection probability given w%.
4. Determine how long an attackers identity must be stable (see Sybil Defense) for this to be worth it.
5. Does it make any sense to assign low-luck miners to re-mine nonce ranges?
6. Can we defend against the Sybil Defense by limiting the number of miners that can join the pool? Perhaps require miners to declare in epoch E that they will continue to mine in the following epoch using the same identity, and only allow a fraction N% of new miners to join in the upcoming epoch. This would lock most miners into keeping the same identity across epochs, increasing detection probability, while allowing only N% new miners (and potential Sybils) per epoch.
7. Can we come up with a formula for w=f(N,luck)?

We can also gamify this somewhat by making this configurable. We could offer a bounty for proving blocks to be withheld, and let individual miners configure how much hashrate they want to devote to that. This is especially easy to pay for if the miner manages to mine a valid block and get it in the blockchain. That's a block the pool wouldn't have had anyway, and we can give that miner a larger potion of the reward from that block.

See also Share Withholding Attacks.