What is a block withholding attack? (and solution)

[organofcorti]

There is a lot of confusion over this, but the attack and solutions were covered a couple of years ago in section 6.2.1 of Meni Rosenfeld's "Analysis of Bitcoin Pooled Mining Reward Systems". It has been discussed recently in other threads, this thread is simply to have the canonical information in one place on the forum.

Since I know many of you won't hit the link, I've copied an abridged except of the relevant sections here. AOBPMRS should be considered a bible for miners; you should at least attempt to understand it. If you don't understand something about bitcoin mining it probably has already been explained in this paper.

Also, it should be noted that the most recent example of this attack was apparently not an attack, rather it was probably a software problem - although this should have already been detected during testing on the testnet, so I'm not sure how "unknown" it could have been.

6.2 Block withholding
The analysis so far rested on the assumption that the atomic action that can be carried out
by participants in a pool is to perform the work needed to find a share, and submit it to the
pool unconditionally. However, with the current protocol, miners can determine whether a share they have found is a valid block or not, and refrain from or delay submitting of blocks.
This can be used for two kinds of attack, sabotage and lie in wait.

6.2.1 Sabotage
The simpler attack is sabotage, where the attacker never submits any blocks. This has no
direct benefit for the attacker, only causing harm to the pool operator or participants. Using a reward system without operator risk like PPLNS, each participant (including the attacker) will lose a portion of his rewards equal to the attacker’s portion of the pool’s hashrate.

.......

6.2.3 Proposed solution – Oblivious shares
One workaround for block withholding attacks is the “pop quiz” – occasionally, the pool will provide miners with work for which a solution is known, and flag participants who do not submit it. However, this leaves much to be desired with both precision and recall. A true solution is to modify the Bitcoin protocol to allow oblivious shares – shares which, when found by miners, cannot be identified as a valid block with submitting to the pool for review.
A possible way to do this will be as follows:
• Every block will have 3 additional field associated with it – SecretSeed, ExtraHash and
SecretHash.
• ExtraHash must be the hash of SecretSeed.
• ExtraHash will be a part of the block header and will be one of the fields used in the
calculation of the block hash.
• SecretHash must be the hash of the concatenation of the block hash and SecretSeed.
• For the block to be valid: Instead of requiring that the block hash is less than 2^256/(2^32D), it is required that the block hash is less than 2^256/2^32 and that SecretHash is less than 2^256/D. The pool operator will choose SecretSeed and keep it secret. He will calculate ExtraHash and provide it to miners along with the other fields that go into the block hash. The miners can calculate the block hash and see if it is less than 2^256/2^32 (which happens with probability 2^−32) and in this case submit it as a share. They do not know if this is a valid block because they don’t know SecretSeed and cannot calculate SecretHash. The operator knows SecretSeed, calculates SecretHash, and if it is less than 2^256/D (with probability p) this is a valid block and it is broadcast to the network.

[DrG]

I assume that the workaround would require a correction to the Bitcoin protocol which would need a hard fork?  Would it be possible to implement without essentially bricking every ASIC?

[-ck]

Your solution assumes that mining software and its attached hardware will work in a deterministic fashion - this is far from the truth. For numerous high level work generation reasons two miners will almost certainly not generate the same work based on what they're submitted by the pool. For one, the coinbase is different on a per-miner basis meaning you'd have to force miners to be working on the same work (based on extranonce1 in the stratum protocol). You couldn't leave them connected like that indefinitely since they'd just be working on the same thing as other miners over and over so you'd need to disconnect them shortly afterwards and reconnect. Secondly, the extranonce2 field is almost never going to be in the same base place by the miner as it's dependent on runtime, number of pools, speed of devices etc etc. Finally, hardware does not work in a deterministic fashion with respect to finding shares within a nonce range. The ASIC may discard work having never tried it, stop short of the full nonce range to reload new work, it may stop as soon as it has found one nonce - missing any after that, and some chips famously only cover 3/4 of the nonce range in a matrix type pattern that is non-linear in coverage.

[eleuthria]

Also, it should be noted that the most recent example of this attack was apparently not an attack, rather it was probably a software problem - although this should have already been detected during testing on the testnet, so I'm not sure how "unknown" it could have been.

The problem was their software discarding shares that matched 2^32-1 difficulty or better.  Anything UNDER that, they worked fine.  So testnet would not have detected anything wrong.

[organofcorti]

I assume that the workaround would require a correction to the Bitcoin protocol which would need a hard fork?  Would it be possible to implement without essentially bricking every ASIC?

No AFAIK, the suggested workaround does not require any fork. However, Meni does state: "However, this leaves much to be desired with both precision and recall. A true solution is to modify the Bitcoin protocol to allow oblivious shares – shares which, when found by miners, cannot be identified as a valid block with submitting to the pool for review."

[organofcorti]

Your solution assumes that mining software and its attached hardware will work in a deterministic fashion - this is far from the truth. For numerous high level work generation reasons two miners will almost certainly not generate the same work based on what they're submitted by the pool. For one, the coinbase is different on a per-miner basis meaning you'd have to force miners to be working on the same work (based on extranonce1 in the stratum protocol). You couldn't leave them connected like that indefinitely since they'd just be working on the same thing as other miners over and over so you'd need to disconnect them shortly afterwards and reconnect. Secondly, the extranonce2 field is almost never going to be in the same base place by the miner as it's dependent on runtime, number of pools, speed of devices etc etc. Finally, hardware does not work in a deterministic fashion with respect to finding shares within a nonce range. The ASIC may discard work having never tried it, stop short of the full nonce range to reload new work, it may stop as soon as it has found one nonce - missing any after that, and some chips famously only cover 3/4 of the nonce range in a matrix type pattern that is non-linear in coverage.

Is this in relation to the 'pop quiz' suggestion, or the suggestion to modify the Bitcoin protocol?

[organofcorti]

Also, it should be noted that the most recent example of this attack was apparently not an attack, rather it was probably a software problem - although this should have already been detected during testing on the testnet, so I'm not sure how "unknown" it could have been.

The problem was their software discarding shares that matched 2^32-1 difficulty or better.  Anything UNDER that, they worked fine.  So testnet would not have detected anything wrong.

Ah, of course, I see your point.

However, it does make me think of something else - they were at 2Phps, weren't they? The network was at ~ 40 Phps? At 5% of the network there's a one in a million chance they would have not have found a block solomining by the time they had been running for  1.68 days. They could have detected the problem with five nines certainty after only 1.4 days.

If they really did have 5% of the network (and I'm not just mis-remembering) I'd be really surprised if they didn't know about it before-hand.

[taipo]

There is no doubt in my mind this was an intentional attack on mining pools.

[TheJuice]

Also, it should be noted that the most recent example of this attack was apparently not an attack, rather it was probably a software problem - although this should have already been detected during testing on the testnet, so I'm not sure how "unknown" it could have been.

The problem was their software discarding shares that matched 2^32-1 difficulty or better.  Anything UNDER that, they worked fine.  So testnet would not have detected anything wrong.

Ah, of course, I see your point.

However, it does make me think of something else - they were at 2Phps, weren't they? The network was at ~ 40 Phps? At 5% of the network there's a one in a million chance they would have not have found a block solomining by the time they had been running for  1.68 days. They could have detected the problem with five nines certainty after only 1.4 days.

If they really did have 5% of the network (and I'm not just mis-remembering) I'd be really surprised if they didn't know about it before-hand.

How does it benefit the attacker if it was intentional? I'm still very confused by this whole ordeal.

[organofcorti]

Also, it should be noted that the most recent example of this attack was apparently not an attack, rather it was probably a software problem - although this should have already been detected during testing on the testnet, so I'm not sure how "unknown" it could have been.

The problem was their software discarding shares that matched 2^32-1 difficulty or better.  Anything UNDER that, they worked fine.  So testnet would not have detected anything wrong.

Ah, of course, I see your point.

However, it does make me think of something else - they were at 2Phps, weren't they? The network was at ~ 40 Phps? At 5% of the network there's a one in a million chance they would have not have found a block solomining by the time they had been running for  1.68 days. They could have detected the problem with five nines certainty after only 1.4 days.

If they really did have 5% of the network (and I'm not just mis-remembering) I'd be really surprised if they didn't know about it before-hand.

How does it benefit the attacker if it was intentional? I'm still very confused by this whole ordeal.

If they had originally planned to solomine then they might have found that they couldn't solve a block solomining. In that case, they could at least mine at a pool and still get btc income - even if they weren't contributing any blocks.

[DrG]

Your solution assumes that mining software and its attached hardware will work in a deterministic fashion - this is far from the truth. For numerous high level work generation reasons two miners will almost certainly not generate the same work based on what they're submitted by the pool. For one, the coinbase is different on a per-miner basis meaning you'd have to force miners to be working on the same work (based on extranonce1 in the stratum protocol). You couldn't leave them connected like that indefinitely since they'd just be working on the same thing as other miners over and over so you'd need to disconnect them shortly afterwards and reconnect. Secondly, the extranonce2 field is almost never going to be in the same base place by the miner as it's dependent on runtime, number of pools, speed of devices etc etc. Finally, hardware does not work in a deterministic fashion with respect to finding shares within a nonce range. The ASIC may discard work having never tried it, stop short of the full nonce range to reload new work, it may stop as soon as it has found one nonce - missing any after that, and some chips famously only cover 3/4 of the nonce range in a matrix type pattern that is non-linear in coverage.

Sadly 1/2 of that went over my head to be honest, but I will read up on it.

Would there be a way to have software implement a query to make sure the miner will submit a winning solve (like a test solve) every X number of shares.  I guess that would require a protocol change since the pool would have to issue the challenge work.

[-ck]

Would there be a way to have software implement a query to make sure the miner will submit a winning solve (like a test solve) every X number of shares. 

Since you basically asked the same question which I gave the long answer to, I'll give you the short version: No

[DrG]

Would there be a way to have software implement a query to make sure the miner will submit a winning solve (like a test solve) every X number of shares. 

Since you basically asked the same question which I gave the long answer to, I'll give you the short version: No

Hey I never said I was intelligent.  I'm a physician damn it, we're not paid to think.  Thank you for the response 

[eleuthria]

Sadly 1/2 of that went over my head to be honest, but I will read up on it.

Would there be a way to have software implement a query to make sure the miner will submit a winning solve (like a test solve) every X number of shares.  I guess that would require a protocol change since the pool would have to issue the challenge work.

ASICs do not always test every nonce from 1 - 2^32.  There's many reasons this may happen such as

1) Many will slice that range into pieces based on the # of chips on the board, giving each one a slice.  If a chip is damaged, that range isn't checked.  Hardware errors.

2) It may be setup to have modules, with each module getting a range, but some units only have 1 or 2 while others have 8.  Instead of splitting the ranges up evenly between available modules, it gives them their static range and ignores the others.

3) It may immediately feed in new work once a solution is found for a nonce range, even though multiple solutions can exist in the full range.



Additionally, modern mining protocols have the miner use a local counter inserted into the coinbase in order to generate work (this is why stratum and GBT are immensely more efficient than getwork, they can make their own work locally).  That counter will be in a different state for every single miner.  If a call were added which forced miners to have that counter in a specific state, you've just clued in a block withholder that the work it received is a test for withholding, so they won't.

[Bitsaurus]

Sadly 1/2 of that went over my head to be honest, but I will read up on it.

Would there be a way to have software implement a query to make sure the miner will submit a winning solve (like a test solve) every X number of shares.  I guess that would require a protocol change since the pool would have to issue the challenge work.

ASICs do not always test every nonce from 1 - 2^32.  There's many reasons this may happen such as

1) Many will slice that range into pieces based on the # of chips on the board, giving each one a slice.  If a chip is damaged, that range isn't checked.  Hardware errors.

2) It may be setup to have modules, with each module getting a range, but some units only have 1 or 2 while others have 8.  Instead of splitting the ranges up evenly between available modules, it gives them their static range and ignores the others.

3) It may immediately feed in new work once a solution is found for a nonce range, even though multiple solutions can exist in the full range.



Additionally, modern mining protocols have the miner use a local counter inserted into the coinbase in order to generate work (this is why stratum and GBT are immensely more efficient than getwork, they can make their own work locally).  That counter will be in a different state for every single miner.  If a call were added which forced miners to have that counter in a specific state, you've just clued in a block withholder that the work it received is a test for withholding, so they won't.

So at this point we are left with no workaround or method of detection for withholding attacks short of statistical outlayers?

[-ck]

Would there be a way to have software implement a query to make sure the miner will submit a winning solve (like a test solve) every X number of shares. 

Since you basically asked the same question which I gave the long answer to, I'll give you the short version: No

Hey I never said I was intelligent.  I'm a physician damn it, we're not paid to think.  Thank you for the response 

I wasn't saying you were stupid, but it's okay if you don't mind taking advice from an anaesthesiologist.

[jonnybravo0311]

Would there be a way to have software implement a query to make sure the miner will submit a winning solve (like a test solve) every X number of shares. 

Since you basically asked the same question which I gave the long answer to, I'll give you the short version: No

Hey I never said I was intelligent.  I'm a physician damn it, we're not paid to think.  Thank you for the response 

I wasn't saying you were stupid, but it's okay if you don't mind taking advice from an anaesthesiologist.

As long as the advice isn't, "Here, take a bit of this before you do your diagnosis."

[philipma1957]

Sadly 1/2 of that went over my head to be honest, but I will read up on it.

Would there be a way to have software implement a query to make sure the miner will submit a winning solve (like a test solve) every X number of shares.  I guess that would require a protocol change since the pool would have to issue the challenge work.

ASICs do not always test every nonce from 1 - 2^32.  There's many reasons this may happen such as

1) Many will slice that range into pieces based on the # of chips on the board, giving each one a slice.  If a chip is damaged, that range isn't checked.  Hardware errors.

2) It may be setup to have modules, with each module getting a range, but some units only have 1 or 2 while others have 8.  Instead of splitting the ranges up evenly between available modules, it gives them their static range and ignores the others.

3) It may immediately feed in new work once a solution is found for a nonce range, even though multiple solutions can exist in the full range.



Additionally, modern mining protocols have the miner use a local counter inserted into the coinbase in order to generate work (this is why stratum and GBT are immensely more efficient than getwork, they can make their own work locally).  That counter will be in a different state for every single miner.  If a call were added which forced miners to have that counter in a specific state, you've just clued in a block withholder that the work it received is a test for withholding, so they won't.

So at this point we are left with no workaround or method of detection for withholding attacks short of statistical outlayers?

   Forced solo mining on all pools   for 1 hour a day . 

We all bear the burden  for that hour and really large  defective miners  could be found out.

 IE a 2ph  mining setup that never makes a block during forced solo mining it would certainly be found easy enough.  Also adds the element of luck for every miner on the pools.

 The cost is nothing for a pool operator for the 1 hour a day. As pools keep track of the block makers any way.

 
   This also make test mining and tweaking a large amount of miners/software such as the 2ph miner less desirable . 
 Since   it may show it is defective during that 1 hour of solo mining.

 So while this is not  a perfect fix it is low cost  to do.  Makes the network far more diverse. 

Frankly where is the down side to it?

[organofcorti]

   Forced solo mining on all pools   for 1 hour a day . 

We all bear the burden  for that hour and really large  defective miners  could be found out.

 IE a 2ph  mining setup that never makes a block during forced solo mining it would certainly be found easy enough.  Also adds the element of luck for every miner on the pools.

 The cost is nothing for a pool operator for the 1 hour a day. As pools keep track of the block makers any way.

 
   This also make test mining and tweaking a large amount of miners/software such as the 2ph miner less desirable . 
 Since   it may show it is defective during that 1 hour of solo mining.

 So while this is not  a perfect fix it is low cost  to do.  Makes the network far more diverse. 

Frankly where is the down side to it?

Why would this fix anything? Going solo won't make block withholding attacks any easier to spot - why did you think they would? Further, all a bad actor would have to do is split his account into many smaller accounts.