Defeating the block withholding attack
8 messages, 3 to 5 Jun 2012. Started by Luke Dashjr.
Luke Dashjr (4), Mike Koss (2), Watson Ladd, Peter Vessenes
Analysis, comments, constructive criticism, etc welcome for the following:
==Background== At present, an attacker can harm a pool by intentionally NOT submitting shares that are also valid blocks. All pools are vulnerable to this attack, whether centralized or decentralized and regardless of reward system used. The attack's effectiveness is proportional to ratio of the attacker's hashrate to the rest of the pool.
There are obvious solutions that can be used to defeat this attack on centralized pools. For example, including a secret in the coinbase transaction that is accepted by the network as a partial preimage proof-of-work. All these solutions require changes to Bitcoin's proof-of-work acceptance terms, and since centralized pools can be harmful to the network's security, these rule changes are not likely to gain enough acceptance among the greater Bitcoin community.
==Proposed Solution== Please comment on the viability of this new proof-of-work algorithm, which I think should be viable for even decentralized pools:
Blocks are accepted at a lower difficulty N (choosable by the pool; eg, the share difficulty) iff they are submitted with a candidate for the next block and SHA256(SHA256(NewBlockHash + NextBlockCandidateHash)) meets difficulty M. The relationship between M and N must be comparable to the normal network difficulty; details on the specifics of this can be figured out later, ideally by someone more qualified than me. M and N must be chosen prior to searching for the block: it should be safe to steal some always-zero bytes from the prevblock header for this.
This algorithm should guarantee that every share has an equal chance of being a valid block at the time it is found, and that which ones are actually blocks cannot be known until the subsequent block is found. Thus, attackers have no way to identify which shares to withhold even while they have full knowledge of the shares/blocks themselves.
==Backward Compatibility== Obviously, this change creates a hard-fork in the blockchain. I propose that if it solves the block withholding risk, the gain is sufficient that the community may approve a hard-fork to take place 1-2 years from consensus.
Since mining continues to use a double-SHA256 on a fixed 80 byte header, existing miners, FPGAs, etc should work unmodified. Poolservers will need to adapt significantly.
On Sat, Jun 2, 2012 at 7:52 PM, Luke-Jr <luke@dashjr•org> wrote:
Quoted text (8 lines)
> Analysis, comments, constructive criticism, etc welcome for the following: > > ==Background== > At present, an attacker can harm a pool by intentionally NOT submitting shares > that are also valid blocks. All pools are vulnerable to this attack, whether > centralized or decentralized and regardless of reward system used. The > attack's effectiveness is proportional to ratio of the attacker's hashrate to > the rest of the pool.
This attack has an obvious signature: getting outworked on the same block as the pool was trying to verify, and always by the same person.
Quoted text (21 lines)
> > There are obvious solutions that can be used to defeat this attack on > centralized pools. For example, including a secret in the coinbase transaction > that is accepted by the network as a partial preimage proof-of-work. All these > solutions require changes to Bitcoin's proof-of-work acceptance terms, and > since centralized pools can be harmful to the network's security, these rule > changes are not likely to gain enough acceptance among the greater Bitcoin > community. > > ==Proposed Solution== > Please comment on the viability of this new proof-of-work algorithm, which I > think should be viable for even decentralized pools: > > Blocks are accepted at a lower difficulty N (choosable by the pool; eg, the > share difficulty) iff they are submitted with a candidate for the next block > and SHA256(SHA256(NewBlockHash + NextBlockCandidateHash)) meets difficulty M. > The relationship between M and N must be comparable to the normal network > difficulty; details on the specifics of this can be figured out later, ideally > by someone more qualified than me. M and N must be chosen prior to searching > for the block: it should be safe to steal some always-zero bytes from the > prevblock header for this.
So the goal is to prevent the attacker double-dipping by submitting cycles to the pool, which if he found a correct answer he could submit himself. I don't see how this does that: if he finds a valid block he finds a valid block. Only if the operator has a secret is this prevented.
Quoted text (6 lines)
> > This algorithm should guarantee that every share has an equal chance of being > a valid block at the time it is found, and that which ones are actually blocks > cannot be known until the subsequent block is found. Thus, attackers have no > way to identify which shares to withhold even while they have full knowledge > of the shares/blocks themselves.
This further delays the finalization of a transaction. That's not a good thing.
Quoted text (20 lines)
> > ==Backward Compatibility== > Obviously, this change creates a hard-fork in the blockchain. I propose that > if it solves the block withholding risk, the gain is sufficient that the > community may approve a hard-fork to take place 1-2 years from consensus. > > Since mining continues to use a double-SHA256 on a fixed 80 byte header, > existing miners, FPGAs, etc should work unmodified. Poolservers will need to > adapt significantly. > > ------------------------------------------------------------------------------ > Live Security Virtual Conference > Exclusive live event will cover all the ways today's security and > threat landscape has changed and how IT managers can respond. Discussions > will include endpoint security, mobile security and the latest in malware > threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge•net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development
On Sat, Jun 2, 2012 at 8:52 PM, Luke-Jr <luke@dashjr•org> wrote:
Quoted text (13 lines)
> Analysis, comments, constructive criticism, etc welcome for the following: > > ==Background== > At present, an attacker can harm a pool by intentionally NOT submitting > shares > that are also valid blocks. All pools are vulnerable to this attack, > whether > centralized or decentralized and regardless of reward system used. The > attack's effectiveness is proportional to ratio of the attacker's hashrate > to > the rest of the pool. > >
I'm unclear on the economics of this attack; we spent a bit of time talking about it a few months ago at CoinLab and decided not to worry about it for right now.
Does it have asymmetric payoff for an attacker, that is, over time does it pay them more to spend their hashes attacking than just mining?
My gut is that it pays less well than mining, meaning I think this is likely a small problem in the aggregate, and certainly not something we should try and fork the blockchain for until there's real pain.
Consider, for instance, whether it pays better than just mining bitcoins and spending those on 'bonuses' for getting users to switch from a pool you hate.
Watson, I don't believe the attack signature you mention is a factor here, since the pool controls the merkle, only that pool will benefit from block submission. The nonce / coinbase combo is worthless otherwise, and so this attack is just in brief "get lucky, but don't submit."
So, can anyone enlighten me as to some actual estimates of badness for this attack?
Peter
On Monday, June 04, 2012 1:43:42 AM Peter Vessenes wrote:
Quoted text (2 lines)
> Does it have asymmetric payoff for an attacker, that is, over time does it > pay them more to spend their hashes attacking than just mining?
That depends on the pool's reward scheme. Some complicated forms are capable of getting "bonus" earnings out of the pool. Under all systems, the attacker at least gains the "hurt the pool" benefit. Given the frequency of DDoS attacks on pools, it is clear there are people who will even pay for attacks that provide no other benefit than harming pools. Under all systems, the attacker doesn't lose out in any significant way.
Quoted text (3 lines)
> My gut is that it pays less well than mining, meaning I think this is > likely a small problem in the aggregate, and certainly not something we > should try and fork the blockchain for until there's real pain.
If we wait until there's real pain, it will be a painful fork. If we plan it 1-2 years out, people have time to upgrade on their own before it breaks.
Quoted text (3 lines)
> Consider, for instance, whether it pays better than just mining bitcoins > and spending those on 'bonuses' for getting users to switch from a pool you > hate.
With this attack, attackers can hurt the pool's "luck factor" *and* spend the bitcoins they earn to bribe users away.
As I understand the attack, the attacker gets compensated for the shares they earn, but the pool will be denied any valid blocks found. The attacker DOES NOT have access to the Bitcoins earned in the unreported block (only the mining pool has access to the Coinbase address and transactions in the block).
So it's a zero-net-cost attack for the attacker (but no chance of making a profit) to hurt the pool operator. The only way to detect such an attack now is to look for "unlucky" miners; at the current difficulty, you can't detect this cheat until many millions of shares have been earned w/o a qualifying block. Since an attacker can also create many fake identities, they can avoid detection indefinitely by abandoning each account after a million earned shares.
I don't understand your proposal for fixing this. You would have to come up with a scheme where:
- The miner can detect a qualifying hash to earn a share. - Not be able to tell if the hash is for a valid block.
The way I would do this is to have a secret part (not shared with the miners) of a block that is part of the merkle hash, which is also used in a secondary hash. Difficulty is then divide into two parts: the first, solved by the miner (earning a "share" - e.g., 1 in 4 Billion hashes). And a second, solved by the pool (1 in Difficulty shares). A valid block would have to exhibit a valid Share Hash AND a valid Pool Hash in order to be accepted.
This would be a very major change to the Block structure. Given that attackers do not have direct monetary gain from this attack, I'm not sure we can justify it at this point.
On Sun, Jun 3, 2012 at 7:04 PM, Luke-Jr <luke@dashjr•org> wrote:
Quoted text (44 lines)
> On Monday, June 04, 2012 1:43:42 AM Peter Vessenes wrote: > > Does it have asymmetric payoff for an attacker, that is, over time does > it > > pay them more to spend their hashes attacking than just mining? > > That depends on the pool's reward scheme. Some complicated forms are > capable > of getting "bonus" earnings out of the pool. Under all systems, the > attacker > at least gains the "hurt the pool" benefit. Given the frequency of DDoS > attacks on pools, it is clear there are people who will even pay for > attacks > that provide no other benefit than harming pools. Under all systems, the > attacker doesn't lose out in any significant way. > > > My gut is that it pays less well than mining, meaning I think this is > > likely a small problem in the aggregate, and certainly not something we > > should try and fork the blockchain for until there's real pain. > > If we wait until there's real pain, it will be a painful fork. If we plan > it > 1-2 years out, people have time to upgrade on their own before it breaks. > > > Consider, for instance, whether it pays better than just mining bitcoins > > and spending those on 'bonuses' for getting users to switch from a pool > you > > hate. > > With this attack, attackers can hurt the pool's "luck factor" *and* spend > the > bitcoins they earn to bribe users away. > > > ------------------------------------------------------------------------------ > Live Security Virtual Conference > Exclusive live event will cover all the ways today's security and > threat landscape has changed and how IT managers can respond. Discussions > will include endpoint security, mobile security and the latest in malware > threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge•net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development >
On Monday, June 04, 2012 8:49:48 PM Mike Koss wrote:
Quoted text (5 lines)
> As I understand the attack, the attacker gets compensated for the shares > they earn, but the pool will be denied any valid blocks found. The > attacker DOES NOT have access to the Bitcoins earned in the unreported > block (only the mining pool has access to the Coinbase address and > transactions in the block).
With decentralized pools, the attacker does have access to the block, and can potentially submit it to the Bitcoin network directly bypassing the pool if it benefits them to do so.
Quoted text (2 lines)
> So it's a zero-net-cost attack for the attacker (but no chance of making a > profit) to hurt the pool operator.
Because of the above, there is a possibility an attacker can make a profit.
Quoted text (5 lines)
> The only way to detect such an attack now is to look for "unlucky" miners; > at the current difficulty, you can't detect this cheat until many millions > of shares have been earned w/o a qualifying block. Since an attacker can > also create many fake identities, they can avoid detection indefinitely by > abandoning each account after a million earned shares.
There are other modes of detection, but nobody has bothered to implement them since attackers can easily do a simple workaround in an arms race.
Quoted text (5 lines)
> I don't understand your proposal for fixing this. You would have to come > up with a scheme where: > > - The miner can detect a qualifying hash to earn a share. > - Not be able to tell if the hash is for a valid block.
With my proposal, miners can find shares, but won't know if it's a valid block until the subsequent block is also found (that subsequent block might not end up being a real block in the big picture).
Quoted text (7 lines)
> The way I would do this is to have a secret part (not shared with the > miners) of a block that is part of the merkle hash, which is also used in a > secondary hash. Difficulty is then divide into two parts: the first, > solved by the miner (earning a "share" - e.g., 1 in 4 Billion hashes). And > a second, solved by the pool (1 in Difficulty shares). A valid block would > have to exhibit a valid Share Hash AND a valid Pool Hash in order to be > accepted.
This only works for centralized pools, which are contrary to the health of the Bitcoin network. Decentralized pools cannot have a secret.
I don't understand how your proposal will work for decentralized pools - can you explain it more concretely?
What would the new block header look like?
What is required for a share to to be earned?
What is required for a block to be valid (added to Block Chain)?
I don't think I understand what you mean by NextBlockCandidate. Perhaps a concrete example using difficulty 1.7 million would be instructive.
On Mon, Jun 4, 2012 at 2:05 PM, Luke-Jr <luke@dashjr•org> wrote:
Quoted text (59 lines)
> On Monday, June 04, 2012 8:49:48 PM Mike Koss wrote: > > As I understand the attack, the attacker gets compensated for the shares > > they earn, but the pool will be denied any valid blocks found. The > > attacker DOES NOT have access to the Bitcoins earned in the unreported > > block (only the mining pool has access to the Coinbase address and > > transactions in the block). > > With decentralized pools, the attacker does have access to the block, and > can > potentially submit it to the Bitcoin network directly bypassing the pool > if it > benefits them to do so. > > > So it's a zero-net-cost attack for the attacker (but no chance of making > a > > profit) to hurt the pool operator. > > Because of the above, there is a possibility an attacker can make a profit. > > > The only way to detect such an attack now is to look for "unlucky" > miners; > > at the current difficulty, you can't detect this cheat until many > millions > > of shares have been earned w/o a qualifying block. Since an attacker can > > also create many fake identities, they can avoid detection indefinitely > by > > abandoning each account after a million earned shares. > > There are other modes of detection, but nobody has bothered to implement > them > since attackers can easily do a simple workaround in an arms race. > > > I don't understand your proposal for fixing this. You would have to come > > up with a scheme where: > > > > - The miner can detect a qualifying hash to earn a share. > > - Not be able to tell if the hash is for a valid block. > > With my proposal, miners can find shares, but won't know if it's a valid > block > until the subsequent block is also found (that subsequent block might not > end > up being a real block in the big picture). > > > The way I would do this is to have a secret part (not shared with the > > miners) of a block that is part of the merkle hash, which is also used > in a > > secondary hash. Difficulty is then divide into two parts: the first, > > solved by the miner (earning a "share" - e.g., 1 in 4 Billion hashes). > And > > a second, solved by the pool (1 in Difficulty shares). A valid block > would > > have to exhibit a valid Share Hash AND a valid Pool Hash in order to be > > accepted. > > This only works for centralized pools, which are contrary to the health of > the > Bitcoin network. Decentralized pools cannot have a secret. >
On Tuesday, June 05, 2012 12:00:25 AM Mike Koss wrote:
Quoted text (4 lines)
> I don't understand how your proposal will work for decentralized pools - > can you explain it more concretely? > > What would the new block header look like?
For example (just a draft; in reality, merged mining would probably be
integrated in a hardfork)
4 bytes: Block version number = 2
31 bytes: Hash of the block 2 back, except for the minimum last 8 bits of zero
1 byte : Share difficulty (measured in "zero" bits)
4 bytes: Timestamp
4 bytes: "Bits" (current target in compact format)
4 bytes: Nonce
Quoted text (1 line)
> What is required for a share to to be earned?
The final <share difficulty> bits (minimum 32) of the block header are zero.
Quoted text (1 line)
> What is required for a block to be valid (added to Block Chain)?
The hash of this block header, concatenated with a valid share candidate for the next block header, must hash to a value less than the current target offset against the share difficulty (this algorithm may need adjustment).
Quoted text (2 lines)
> I don't think I understand what you mean by NextBlockCandidate. Perhaps a > concrete example using difficulty 1.7 million would be instructive.
The first share becomes a block only after a second share is found that combined hashes to meet the real difficulty. That second share becomes a block when a third is found. Etc.