Topic: pooled mining luck theft attack? (Read 1641 times)

Hi Adam, it was great meeting you in SJ.

I've discussed block withholding attacks in section 6.2 of https://bitcoil.co.il/pool_analysis.pdf. I think there are a few things you've missed here:

1. There are PPS pools, and they will likely be more common in the future. You can withhold blocks from such pools with no consequence to yourself; you gain the advantage of reduced difficulty, and you can harm the pool operator (e.g., if he is a competitor).

2. Withholding completely is not the only thing you can do; you can also delay the reporting and use your additional knowledge for an advantage. This is profitable also against non-PPS pools. I call this "lie in wait".

Eligius originally used the proportional method. I explained that it's broken and suggested that they use a hopping-proof method instead.
Then they switched to MPPS. I explained that it's broken and suggested that they use a hopping-proof method instead.
Then they switched to SMPPS. I explained that it's broken and suggested that they use a hopping-proof method instead.
Then they switched to CPPSRB, and I gave up. It's not as broken as the other methods, but there's no reason to use it over the hopping-proof methods PPS, PPLNS and DGM.

Bitcoin direct mining is cleverly zero-sum if you shake network difficulty (by pulling out for 2 weeks, then piling in 2 weeks and repeating) due to geometric difficulty adjustment.

I think the short intuition for why (pool based) under-contributing difficulty shaking gains an advantage where direct mining can not, is in this case the under-contributor leeches off the pool during his period of under-contributing to make his profit.  With the parameters in my previous post the under-contributor (with his 2 pseudonyms) gains 1/48 and the other pool members lose 1/48.  The gain from network shaking inflation acceleration of 1/24 goes to the other non-pool members.  So a summary under-contributor steals from the pool, and other non-pool miners (or other different pool miners) gain the entire inflation acceleration of 1/24 a unwitting benefactors of the pool shaking.

Note there is an electricity cost to under-contributing, while the reward is reduced; however that does not change the viability of the under-contributing attack.  And there is a net win of 1/48 with the parameters, and the electricity cost is the same as playing fair.

Two other factors which would need to be taken in to account:

1. network difficulty is growing with moore's law inflation (and right now it is growing above moore's law inflation rate as hardware efficiency is getting closer to current moore's limit with ASICs and more users are joining.)  Consequently if the attacker is not increasing his hardware quantity and efficiency at the same rate  as the network, the first 2 weeks loss may outweigh the pool leeching gain.

Factoring in electricity cost, even shaking network difficulty by pulling out can profit because while it is zero-sum, and the hardware amortization is already there, the saves 50% of his electricity cost for the first 2 weeks and his reward is the same.

If multiple people are trying to shake difficulty they may cancel each other out if they do not under-contribute or switch off during the same 2 week period.  Therefore they need to collude or observe and implicitly synchronize their attacks to mutually gain.

Adam

Schadenfreude (doing DoS that costs you but creates costs for others) as you allude probably shouldnt be excluded.  There are people who will do uselessly destructive things because they can even for no gain.

I guess you would call that under-contributing ie getting reward share, but not helping win.  I got exited about network shaking about month ago, and investigated it a bit and concluded it was zero sum (other than schadenfreude).  That was because I was thinking in terms of switching off a big miner, rather than in under-contributing to a pool.  Now that I did that different calculation it seems there is actually a way to win by under-contributing!

Lets consider why would someone do that?  It'll be easier to see if we start with a high powered pool participant (50% of pool).  Say this is a big pool (50% of network).  We have to consider both cases: immediate effect, and after difficulty adjusts.

Immediate: the pool useful power drops to 25%, rest of the network continues at 50%, so block interval increases to 13.3mins average (network reward drops by 25% as it goes uncollected for longer).  The pool claims only 1/3 (25%:50%) of the remaining 3/4 network reward = 1/4.  The under contributor claims half the pool = 1/8 of full speed reward.  Playing fairly would have seen him collect 1/4 of full speed reward.  Under contributor loses.

Difficulty adjusts: difficulty becomes 25% easier, block interval reverts to 10mins, network reward is fully collected.  Under-contributor continues under-contributing, pool still collects 1/3 but of the full reward, under contributor claims half of pool reward = 1/6 of reward.  Attacker continues to lose, just less badly.  Alternatively attacker switches playing fairly & contributing (now difficulty has adjusted), so network power jumps up by 1/3 (25%:75%) so block interval falls to 7.5mins, so network reward increases to by 1/3 to 4/3 of full speed.  Pool claims 1/2 of 4/3 oversped reward = 2/3 of full speed, attacker claims 1/2 of reward = 1/3.  Attacker wins by 1/3-1/4 = 1/12.  However looked at over the 4 week period his average reward was 1/2(1/8+1/3) = 11/48 of a normal full speed reward.  If he played fair the entire time, he makes 1/4 and 11/48 < 1/4.  Attacker loses overall, its in his own interests to play fair.

After that the difficulty adjusts back to normal speed and the cycle starts over.

But continuing, I suppose you could wonder where does the 1/48 loss go.  One thing I notice is 1/2(4/3+3/4) = 25/24 so average network reward increased over the 4 week period by 1/24. 

To see why that is, an analogy if you drive at 75mph for an hour then 133mph for an hour, your average speed is over 108mph (75mph+133mph = 108mph) even though the geometric average is 100mph (0.75*1.33=1).  Difficulty adjusts according to geometric average, but reward is payed out with simple average.

The attacker lost 1/48 relative to playing fair, but other people benefited from that 1/24 reward boost.  If the attacker could gain over half the reward boost for himself he could make a net gain.  Thats a new one to me, lets explore.

If the attacker actually has two pseudonyms A (25% on the pool) & B (another 25% power, direct mining, not on the pool) which seems the most promising direction intuitively.

Psuedonym A we calculated above, it loses 1/48 of its winnings relative to playing fair.

Immediate (for psuedonym B): (copying from above) The pool claims only 1/3 (25%:50%) of the remaining 3/4 network reward = 1/4.  The direct miners collect 1/2 of normal speed (unaffected), so B collects 1/2 of direct miners = 1/4.

Difficulty adjusts (for pseudonym B): (copying from above) Alternatively attacker (A) switches playing fairly & contributing (now difficulty has adjusted), so network power jumps up by 1/3 (25%:75%) so block interval falls to 7.5mins, so network reward increases to by 1/3 to 4/3 of full speed.  Pool claims 1/2 of 4/3 oversped reward = 2/3 of full speed, attacker (A) claims 1/2 of reward = 1/3.  Also B claims half of unpooled reward = 1/4*4/3 = 1/3.

Psueudonym A's lowest loss strategy (other than playing fair) was 11/48; B by playing fair averages 1/2(1/4+1/3)= 7/24.  Combined win for B = 7/24+11/48 =25/48 a net gain of 1/48.

The other players must win the other 1/2 (1/48 average reward) of the 1/24 overall predicted as the attacker only gets half of it.

Wow I did not see that coming.  It seems to actually work to shake the network if you can do it by under-contributing with part of your power!  There will be some net losers as well because the pool participants are leached on by Psuedonym A.  Lets check how bad that is: from above immediate: rest of pool gets 1/8, direct miners unaffected (1/2 splt across 1/4 for B, 1/4 for other direct), difficulty adjusts: pseudonym A lowest loss strategy, pool gets 1/2 of 4/3 = 2/3, the other pool players get 1/3.  Average other pool players get 1/2(1/8+1/3) = 11/48 < 1/4 they lose 1/48.  The other direct miners get 1/2(1/4+1/3)=7/24>1/4 they win 1/24!  Check it adds up: A+B win 1/48, other pool lose 1/48, other direct win 1/24: 1/48-1/48+1/24 = 1/24, which matches total network gain from shaking.

It also seems like the attack scales down, eg with 10% of power split between two pools, or pool and direct, you can do the same thing and gain a small %, though I havent checked with < 50% power examples - any takers?.

Seems like the network is using the wrong type of averaging to adjust difficulty eg simple averaging might solve it.  Drive 75mph then 125mph and your average is 100mph.

Or there is an under-contribution algorithm in the amortizable hashcash paper that is still fairly auditable (only example I know of in the literature of symmetric key blinding:)

See http://hashcash.org/papers/amortizable.pdf page 5, second algorithm on page "Interactive Fair Amortizable Hashcash".  The idea is basically the amount over the share work is measured separately against a secret known to the server, that it will disclose to publicly when it finds the full block.  That is a single hash of extra work for the server.  The server also gains no computational advantage in over-contributing himself relative to the miners from knowledge of the secret.  Knowledge of the secret gives no advantage in over-contributing but allows under-contributing.  Oops!  In amortizable metering & document popularity applications for fair amortizable hashcash that is enough as server under-contribution is not meaningful there.  For under-contribution in bitcoin that means the server itself could perform the network shaking attack (even if the rest of the server skimming issues were fixed).

It might be that other allocations of power to pseudonym A & B might get higher reward.

So I think that brings it back to the wrong averaging algorithm.  Have to explore problem more thoroughly and measure different algorithms immunity to it.

This may also explain the interest in DDoSing big pools - a way to shake the network without the cost of under-contributing.  When there's money at stake most people dont mind if someone else wins more than they do, even if unwitting co-benefactors dont know it, so long as they selfishly win (and some others lose, and the planned inflation curve is accelerated a little).


I thought eligius CPPSRB seemed like a nice way to allocate funds fairly.  Speaking of DDoS to look at CPPSRB I went to eligius.st and it seems to be having problems: nginx bad gateway 502.

Adam

It isn't that harmful.  If the miner gets 99 shares + 1 "win", he doesn't lose much by not submitting. 

It depends on how the payouts work.  If you only get payout for shares in winning blocks, then withholding means you lose your 99 other shares.

P2pool for example pays out to all shares with the last few blocks (3 maybe).  I think the scheme is called "pay for last N shares".

Yes I was thinking since posting the above, it could be more efficient to pay the miners directly,  if there is support for multiple reward addresses per block (or that could be added).   (The pool is going to soon enough pay out anyway which will create the more network traffic).  Additionally by paying out to multiple reward addresses, there does not need to be a transaction fee, which is the basis of the pools policy of non-immediate payout.  Immediate proportional reward is attractive to miners, I know my son was waiting anxiously to get his payout minimum for a few weeks!

I hope it achievable with minor changes.  But its a little more than just putting multiple reward addresses in the block, because you have to protect against a few attacks:

- the amount of share work done must be auditable by the pool participants, so they can know their payout share is fair

- the pool may have a fake miner in his own pool, that is tallied as if it did significant work, but in reality did none, if it is not auditable that the share work was actually done

- ideally this should be done in a network efficient way for the pool

- and even more importantly in a network efficient way for the main network.


I dont think thats possible other than as a self-harming DoS, because the reward goes to the pool's address.  If the miner mines for his own address, the pool will not accept it as a work share proof, so the only possibilities for the miner are to either solo mine, or play fair via the pool, so no attack is possible.

The same would be true of mining against a direct payout list of reward addresses, the pool server would check they are correct, and not count reward if they were not correct.  Or at least the pool has an incentive to do so if there are consequences if a miner can prove any of the accepted mining contributions omitted his past contribution (mainly being he block is invalidated), or include claimed work that didnt happen.


I guess that might work at present if the client is not checking for nor really aware of the pools reward address.  Even if the pool advertises its address, on the pool web site that also can be hacked.  You might even see DNS poisoning, and MITM theft of work.

Probably the trick is to do it partially so the miner doesnt notice how unlucky he is.  Calculating your expected reward proportion is a bit tricky, due work stalls, moving network and actual instantaneous difficulty.  A malicious pool or a MITM could hide a big skim in that. 

Maybe many of these things are happening right now, the profitability didnt seem very good over electricity with a mid-high AMD GPU (especially if you factor in buying the card and machine to put it in).  Hard to say if that is due to large scale skimming via pools, hacked pools and MITMs or the FPGA & ASICs are sucking the profitability out of GPU to that extent already.

btw someone said about slush being DDoSed when the bitcoin price was high - that makes sense because it holds the network hash rate down (bigger % at current difficulty for attacker) and after a while affecting difficulty after averaging takes effect (even bigger % than due for attacker, and all non-DDoSed users); particularly that could work for some miners with no backup pool config and are not monitoring their mining rig very closely.

Adam

Isn't that just the same as putting payments in the block? Just a minor software change.

More important I think is the issue of miners holding back winning solutions from mining pools. Have you put some thought into solving that problem? I can't see how you would even detect that and on top of that a large pool could sneakily redirect clients to other pools, take the funds, and also reduce competition for themselves. Possible to detect that one mind you if clients are really observant, although they aren't...

Do you know where I would look to see the source code to check how the pool server verifies the user before storing (or paying out.)

GBT (GetBlockTemplate https://en.bitcoin.it/wiki/Getblocktemplate) appears to allow (but not require) client challenge randomness:


Do you know if the GBT pool attempts to make the block template challenge unpredictable for the cases where the coinbase/append feature is not offered by the pool or offered but not used by the miner?  (I think the share work issued should be both non-reassignable and unpredictable for defense in depth, if miner chosen extranonce is to remain optional).

There seem to be a number of exploitable avenues for hacking pools, even if they are honest, and even when the GBT user-chosen extranonce is used, and as pools are a concentration of risk with current $500k/day network reward, and near perfect crime status, the attacks are going to be increasingly sophisticated their payout may exceed an exchanges coin float depending on cold-keys etc strategy used by the exchange.

I outlined a scheme to achieve a zero-trust, unskimmable and non-server-hackable pool protocol in this other thread: https://bitcointalksearch.org/topic/m.2035637

Adam

The common (only?) GBT pool server software checks to make sure the work matches the assigned user, and doesn't credit the wrong user. Stratum has a user ID as part of the coinbase, IIRC it's not in the share results, so the work must be submitted as the correct user.

Someone with better knowledge of the pooled mining code could check my potential attack idea.

The way bitcoin tweaks hashcash (I guess bitcoin-hashcash?) the challenges are potentially not random enough any more, because the reward collecting public key is overloaded to serve the function of the hashcash self-chosen challenge.  And up to this point I presume this is considered not an attack because all you do by mining on someone else's address is mine coins for them.

You see artefacts of this in the way that some of the pools protocols share out work, as the reward public key is not self-chosen (being chosen by the pool not the miner), then there becomes non-negligible risk otherwise that pool miners would statistically redo work, or be starved of work. 

The pooled miners seem to be short of search space, because lengths are gone to stretch what work space there is within 32-bits counter, for example increasing the 32-bit time field somewhat (and it cant be increased too far or the network rejects the block), and concerns about flooding the pool with too many small requests.  Obviously the pool needs to send the client updated work string, as it will include new transaction fees, but the mining client should be able to choose its own challenge.

I am not sure to what extent the respective mining protocols are in relative use currently, but DoS pre-mining could actually be a mining security problem in the case of bitcoin pooled mining, depending on some details.  It seems that in some cases a bigger extranonce is used to increase search space, eg as noted here https://en.bitcoin.it/wiki/Transactions    And I saw the Stratum mining proposal http://mining.bitcoin.cz/stratum-mining proposal does use a second variable sized extraNonce2.

But if the challenges hands out that are unencrypted (and sniffed), too small, or predictable an attack could arise based on the attacker pre-mining other pool miners pool shares, and assigning the work to himself (which is a separate question).

Say an attacker has a large amount of mining power, eg enough to slightly exceed a small pool that hands out challenges that are unencrypted, too small, or predictable.  Now as the work done is known to the attacker, he can increase his pooled reward, because the work of the other miners on the pool could be negated if done first by the attacker.  (Whether that would work depends on whether the pool checks if a challenge was submitted by the person it was issued to; as some pools are account-less it seems plausible that this may not always be the case). Presumably a pool wont accept the same pool share solution twice.  Beyond making the other pool miners unexpectedly unlucky this helps the attacker (and other direct miners and pooled miners using different pools) because if he adds say 10% to the network, he simultaneously removes 10% from the network, so over time the difficulty will decrease by 10% from what it would have been had the 10% attacker played fair.

If there are pools that are giving out predictable work, and allowing miners to claim reward for solving other users work shares, the same attack can scale up all the way to the entire proportion of pools that are vulnerable provided the attacker has the CPU power to match.  The attacker could not actually tamper with transactions because the pool is validating them.


Hashcash was designed to defensively avoid this risk by the user including including of a big enough self-chosen challenge to avoid accidental mining collision.  The hashcash paper recommends 128-bits for general use.  The hashcash library implementation use 96-bits for email (16 base64 chars).  In bitcoin it probably should be defensively changed also even if the mining pools do enough checks to avoid the attack above, if nothing else it would be more network efficient for pooled miners to choose their own challenges, and leave the less open to work starvation.  There should be a 128-bit length challenge field (possibly 256-bits even to be defensively conservative given the scale and to balancing other defensive features like double SHA-256 ).  In bitcoin I suppose this could me done by increasing the size of extraNonce to 256-bits and having the miner self-chose a random extraNonce.  (Hashcash defines challenge and counter separately which is slightly preferable  I consider otherwise your challenge security margin is eroded as CPUs get faster the number of possible non-overlapping search spaces is reduced - that is basically what happened to bitcoin in the wiki pages about pooled miners scavenging extra search space by changing time.)

Adam