Optimal pool abuse strategy. Proofs and countermeasures

[slush]

I think you are all missing the point a little.  The concern is not cheating but undetectable cheating. 

Bad guy can mask his behaviour pretty easily, so with anonymous registrations it is still a problem. And I'm also trying to keep the system to be fully automatic, with clear rules. I don't like to disconnecting users because I 'think' the worker is 'maybe' cheating.

[1715542096]

1715542096

[1715542096]

1715542096

[Cryptoman]

Slush, I miss the number of shares counters.  It was a good way for me to tell how my machines were doing relative to one another.  Is it possible to at least show a percentage or bar graph comparing each of a user's miners for the current block and maybe overall mining history?  It does not need to be compared to the pool as a whole.

[comboy]

Hiding number of my shares seems weird. I can see them in my miner. Why hide information that came from me in the first place?

[slush]

Hiding number of my shares seems weird. I can see them in my miner. Why hide information that came from me in the first place?

You see your shares, but you don't know to which block it fits. But shares on profile page were cleared when block was found. That's the difference.

[comboy]

Hiding number of my shares seems weird. I can see them in my miner. Why hide information that came from me in the first place?

You see your shares, but you don't know to which block it fits. But shares on profile page were cleared when block was found. That's the difference.

edit: sorry for not reading thread carefully, but as davidonpda mentioned, any kind of stats would be nice. Your site is very handy for monitoring miners performance.

[slush]

For those that like to see, say estimated performance, what if you included: Number of shares in the last 2 hours?

If you read yesterday's posts here and in pool thread carefully, I mentioned this many times.

But things changed, looks like there will be all stats back soon.

[eMansipater]

I think you are all missing the point a little.  The concern is not cheating but undetectable cheating. 

Bad guy can mask his behaviour pretty easily

Really?  My guess is that any of these strategies would differ drastically from the typical miner.  Your statistics may show differently, but I'm guessing most people who bother to use a mining pool leave their clients running pretty steadily in at least large chunks (if not 24/7), rather than connecting and disconnecting all the time.  All of the cheating strategies require disconnecting early, a behaviour that can be distributed but not masked by using multiple anonymous accounts--at any meaningful degree of exploitation, a significant proportion of those clients have to be in at the beginning of each round, with that same client disconnecting consistently before the end.  The only portion of the attack that can be masked through multiple accounts is the obtaining of statistics on the beginning of each round, which is not behaviourally necessary to identify the cheating signature.  Detection code consists of the following:

1.  Record connected/disconnected periods using getwork requests, not submitted shares (presumably already done based on your leaderboard's online/offline capability)
2.  Implement minimum send threshold of .5 bitcoins, or similar amount of value as the bitcoin exchange rate and network hashrate both grow.
3.  On send/payout of any account, calculate the average in and out times across blocks worked on by each worker, compared to the overall average.
4.  If times are notably shifted towards the cheating strategy once, send the following email:

Dear user, the server has detected that your worker account "X" is frequently connecting and disconnecting at odd times.  Perhaps there is a problem with your client software or internet connection?  Since it exists to reduce the variance of the mining process for a large group of people, pooled mining works best when your client is connected for longer periods at a time, or consistently during regular periods of the day and week.  If you are unable to connect your client consistently, perhaps pooled mining is not for you.  Should the problem persist, the next payout from that worker may be held by the server until you have an opportunity to resolve it.  Thank you for your cooperation!

If it happens again, do what you said but be willing to give someone one more chance if they can come up with a reasonable explanation for their mining client's bizarre behaviour.

...and then, because the only way to get around this method of cheat detection is to use accounts once and then burn them at an incredible rate....
5.  Implement captcha on account and worker registration.

Problem solved!

Keep in mind that for any of these attacks to work the cheater has to *consistently* be in at the beginning of each round (and I mean the very beginning, because even a short delay or randomisation will significantly impact the profits through loss of short blocks) and avoid the really long ones at all costs (because going all the way to the end with any kind of consistency, again, wipes out that edge very fast).  And I fail to see how this behaviour can be masked across any combination of accounts, because no legitimate user is going to randomly be connected at the precise beginning of every single round and then never stay connected to the end of a long block.

For any given detection code in step 4 above you can calculate both the chance of accidentally catching someone who's not trying to cheat and the maximum margin of cheating possible--you'll see what I mean pretty quickly.  As an example, if you're up for it Raulo or Ryo, try calculating these for detection code that flags workers whose average time logging in a worker for the first time (as opposed to just continuing from the end of a previous block) is < 5 minutes after a round begins, and average time out for good on a round is < 25 minutes later in it.  You'll notice that the cheating edge is blown away by trying to beat the detection filter, yet the probability of a user randomly obtaining these stats by accident is redonkulous.  Am I drastically missing a strategy here?

Sincerely,
eMansipater

[ByteCoin]

Good catch to spot this pool exploit! I completely missed this in spite of thinking about pooled mining quite a lot.

If you have any doubts about the reality of this exploit then consider the following thought experiment:
Suppose there are ten miners hashing at equal rates. After they each submit one work-unit to the pool, if a block is then found they each get 1/10th of the total profit. If one of the miners leaves and is replaced by a new miner at that stage and each miner then submits another work-unit then, if a block is then found the new miner gets 1/20th of the profit having done the same amount of work as the miner whose place he took. It's only fair if the share of the profit is proportional to the work done.

One solution to the problem is to make the payout for the block proportional to the time since the last block. The mining pool would have to have a slush fund to cover the cases where the block generation rate falls below the long-term average.

ByteCoin

[knoop]

Sorry, I'm failing to understand the nature of the "unearned income", discussed in the paper. The critical section appears to be the first two paragraphs of section 2 "Pool cheating". In particular, the sentence:

"However, if you stop mining before the block is found, there is an extra “unearned” income."

I can't seem to find an explanation of what this "unearned income" is. The only possibility I can think of is that it becomes more difficult to find hashes which have not been found before, as work progresses on a block, thereby making the earlier shares easier to find. If this is not the case, then I cannot see where the share based system would introduce unfairness.

Also, the paragraph starts with the sentence:

"Therefore, switching between pools in connected mode and between such pools and individual mining does not change your payoff."

This statement seems to directly contradict the hypothesis that cheating is in fact possible...

I expect all the conclusions made in the paper and the adjustments made on its basis are sound, but the paper does seem to lack at least one critical point, so some elaboration would be appreciated.

[Raulo]

"However, if you stop mining before the block is found, there is an extra “unearned” income."

I can't seem to find an explanation of what this "unearned income" is. The only possibility I can think of is that it becomes more difficult to find hashes which have not been found before, as work progresses on a block, thereby making the earlier shares easier to find. If this is not the case, then I cannot see where the share based system would introduce unfairness.

When you submit a share, there is 1/difficulty chance it is a winning hash. But all the non-winning shares do not help finding the winning hash. So if you stop contributing, all your previous effort has zero value to the pool and pool should pay you zero for them. If it pays something, it is "unearned" income.

"Therefore, switching between pools in connected mode and between such pools and individual mining does not change your payoff."

This statement seems to directly contradict the hypothesis that cheating is in fact possible...

"Connected" mode is defined in previous paragraphs of the paper. A truly connected mode is not practical because it means miners are sending all the hashes (not just shares) to server. In connected mode, if you do not sending hashes this very moment, you get zero payment if the block is found because it couldn't have been you that found the block. A connected mode can be approximated by taking into account only shares contributed during, say, last minute or like in current slush's pool, by wighting recent shares much more than the older ones. In such mode cheating is mathematically possible, but the benefit is so small that it is note worth the effort and switching costs (it always costs some hashes to redirect ones mining effort).

Slush's old pool (before anti-cheating measures) was in "contributed" mode. All your past shares counted. It was prone to cheating described in this paper.

[Ricochet]

This was also an issue back when doublec ran his pool using puddinpop's server and client programs (before slush started his) which used a slightly different mining method but the end result was similar.  It was originally in "connected" mode and then changed to "contributed" due to user feedback, but there was much debate between the two.  Because it took days for the group to find a block, this was a large problem since it would actively dictate the behavior of potential users and whether they'd join the pool or not.  My first post on the forums in fact was my thoughts on the matter, in which I suggested something similar to what slush is currently doing with the time-weighting.  

[Meni Rosenfeld]

It looks like the paper is unavailable from http://bitcoin.atspace.com/poolcheating.pdf . Where can I get it now?

[Raulo]

It looks like the paper is unavailable from http://bitcoin.atspace.com/poolcheating.pdf . Where can I get it now?

The web hosting I use, started to become pretty unreliable recently. I need to find something different. But if you PM me your email, I can email the paper to you.

[slush]

http://mining.bitcoin.cz/media/download/poolcheating.pdf

[Meni Rosenfeld]

It looks like the paper is unavailable from http://bitcoin.atspace.com/poolcheating.pdf . Where can I get it now?

The web hosting I use, started to become pretty unreliable recently. I need to find something different. But if you PM me your email, I can email the paper to you.

Thanks! This was obviated by slush's gracious hosting.

http://mining.bitcoin.cz/media/download/poolcheating.pdf

Thanks! Saved to disk this time.

[luv2drnkbr]

I'm not math-savvy enough to get the whole thing, but I am a gambler and I understand expectation, and the basic premise is false:

If one stops mining for a pool that has not found a share, one still gets a payment [...] even though now you contribute nothing to the pool chance of success. This enables cheating.

It doesn't matter if you contributed to the pool and a hash wasn't found.  It still took your previous work as well as the work of everybody else to find the hash.  You DID contribute to finding that solution.  And you are getting paid for the amount of work that you did.  If you then go and continue working on your own, that doesn't matter.

If I am playing in a re-buy poker tournament on a team's bankroll (a team I'm a part of), and if my win would get chopped with the team, but then I bust out, and the team doesn't want to re-buy me back into it, I can still go into my pocket and buy myself in on my own money.

If somebody on the team wins the tournament, I still get part of it because I AM part of that team, and if I cash on my own money with my re-buy, I get all of it because the team didn't pay for that.

That's not unfair to anybody.  I was working for the team, and if the team wins money, I should get paid for my role in the team effort.  If I then go off and put the effort in by myself and win, then I should get all of it.  There's no conflict there.

The basic premise of your paper is false.  The EV is the same for the miner--it's merely a function of his total effort put in, pool or no pool.

What you are describing is simply a "gambling system" that doesn't change the house edge.  You've stumbled upon the Martingale system for blackjack and now think you have an edge.

You don't.  Nothing has changed.  The premise is false.

I will demonstrate what I'm saying must be true:  If everybody in the pool mines for a bit then goes solo, the pool has done some work but now will never find a solution.  However, one of the solo miners will (assuming no outside people in this example).  The chance of any individual miner finding a winner is exactly the same as it was when he was part of a pool, it's just that when he was in a pool, he would have had to give most of his winnings away, but in return he got part of the winnings if somebody else won.  By mining solo, he has merely given himself a bigger potential payout but at a cost of it being less likely.  But his average monetary gain over the course of his lifetime will be the same, whether or not it's paid in small increments or in random 50 btc spurts.  Thus, if the two are equal, it cannot be true that switching to one or the other at some magical point in time will somehow yield a higher profit.

100% of $5 is mathematically equivalent to 10% of $50.  The only difference is variance.

The premise is false!

[Meni Rosenfeld]

luv2drnkbr, I agree with you. Raulo's formulation of "not having contributed if you leave the pool" is incorrect. I have never raised my dissent because the analysis of pool hopping does not depend on it as a premise. It is still a way to benefit on the expense of others in proportional pools, which is unsustainable if done by everyone.

The correct way to view this is to ignore the past, look at the present and see how it affects the future. If I submit a share now, what is the expected benefit to the pool? What is my expected payout? Are they the same? In my scoring method, the contribution and reward are always equal (up to fees). In a proportional pool, the reward is higher than the contribution in young rounds, and lower in old rounds.

On a proportional pool, suppose the current round already has shares twice the difficulty. If you submit a share, what is your expected contribution? You have a probability p=1/difficulty to find a valid block with reward B, so it's pB. What is your expected payout for this share? No matter what happens, you will get less than (pB/2) reward, so the expectation is less than pB/2. So you're better off mining solo which has pB expectation per share.

What if the round is very fresh, say, no shares at all? Your contribution to the pool is still pB. But now you have a probability of p to get the whole reward B to yourself, this contingency alone adds pB to the expectation; probability p(1-p) of getting half the block - since 1-p is quite small, this already puts you at almost 1.5pB; and with probability p(1-p)^2 you get a third, and so on. So your expected payout is roughly log(1/p)pB, which at current difficulty is 13pB. So shares submitted early on will give you a very large expected payout, much more than your fair share for your contribution to the pool.

[luv2drnkbr]

luv2drnkbr, I agree with you. Raulo's formulation of "not having contributed if you leave the pool" is incorrect. I have never raised my dissent because the analysis of pool hopping does not depend on it as a premise. It is still a way to benefit on the expense of others in proportional pools, which is unsustainable if done by everyone.

The correct way to view this is to ignore the past, look at the present and see how it affects the future. If I submit a share now, what is the expected benefit to the pool? What is my expected payout? Are they the same? In my scoring method, the contribution and reward are always equal (up to fees). In a proportional pool, the reward is higher than the contribution in young rounds, and lower in old rounds.

On a proportional pool, suppose the current round already has shares twice the difficulty. If you submit a share, what is your expected contribution? You have a probability p=1/difficulty to find a valid block with reward B, so it's pB. What is your expected payout for this share? No matter what happens, you will get less than (pB/2) reward, so the expectation is less than pB/2. So you're better off mining solo which has pB expectation per share.

What if the round is very fresh, say, no shares at all? Your contribution to the pool is still pB. But now you have a probability of p to get the whole reward B to yourself, this contingency alone adds pB to the expectation; probability p(1-p) of getting half the block - since 1-p is quite small, this already puts you at almost 1.5pB; and with probability p(1-p)^2 you get a third, and so on. So your expected payout is roughly log(1/p)pB, which at current difficulty is 13pB. So shares submitted early on will give you a very large expected payout, much more than your fair share for your contribution to the pool.

I did not understand that proportional pools existed.  Thank you for that explanation Holy-Fire.

[PoulGrym]

This to me just sounds messy. Why not just keep it simple and stay with PPS?? Then no weird stuff..  is there anyway to cheat with the Pay Per Share System? Not that I can think of anything. Skipping a share? Then you get a big pool of stales.. no way to get around that one..

Just keep it simple.. Just wasting time and energy. IMHO

[Raulo]

This to me just sounds messy. Why not just keep it simple and stay with PPS?? Then no weird stuff..  is there anyway to cheat with the Pay Per Share System? Not that I can think of anything. Skipping a share? Then you get a big pool of stales.. no way to get around that one..

Pay per share (PPS) is very dangerous for pool operators, especially the small ones. In PPS, the pool operators have to pay for bad lack streaks with their own pockets. It can make them go bankrupt because 10-20% bad luck streaks are not uncommon. Moreover, there can be malicious users who do not submit winning shares. With difficulty over 400,000, the loss for the user is negligible, for pool operator it is huge.