Bitcoin Forum
December 05, 2016, 04:50:37 PM *
News: Latest stable version of Bitcoin Core: 0.13.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1] 2 3 4 »  All
  Print  
Author Topic: Optimal pool abuse strategy. Proofs and countermeasures  (Read 28913 times)
Raulo
Full Member
***
Offline Offline

Activity: 238


View Profile
February 04, 2011, 01:49:09 PM
 #1

I have written a description of the optimal pool abuse strategy (for a single pool) with proofs and calculations. Available here:
http://bitcoin.atspace.com/poolcheating.pdf

If the link does work, use a mirror: http://mining.bitcoin.cz/media/download/poolcheating.pdf

I have started this work some time ago and it is not finished (I wanted to derive the optimal strategy for multiple pools but it's not ready yet) but with jgarzik's announcement of a new pool code, there is a chance we have multiple pools very soon and with multiple pools, pool abuse gets more profitable, and because I realized there is a perfect countermeasure, I decided to publish it now .

For those who don't want to bother reading it, the optimal strategy is to join the pool at the start of a new round and stop pooled mining after 43.5% fraction of the current difficulty of shares was contributed and start mining solo. This strategy will bring 28% of extra income compared to only pooled or only individual mining.

In this thread, the author finds no evidence of massive use of this strategy
http://bitcointalk.org/index.php?topic=2941.0
(I didn't read the paper since I find it strange to ask for a payment for something that may or may not contain anything interesting; and I didn't find any hard numbers in the discussion)
However, I was testing it in mid January with 3-4% of the pool hashrate. It is indeed very hard (at this level it is quite well buried in the noise) in the global hashspeed, but it is possible to detect by the pool operator by checking the payout. An abuser, will have significantly larger payouts in the short rounds than in longer ones.

Concerning the countermeasures. Apart of administrative ones (i.e. banning) which will be difficult if one starts to be more clever: randomly changing switching threshold, contributing all the time with a fraction of ones hashspeed, etc, there is of course a connected method which is will be very hard in slush's implementation. It is also possible to calculate the payout based only on the very recent shares but it only reduces the cheating payout, not eliminate it. However, after reading the recent jgarzik's pool discussion
http://bitcointalk.org/index.php?topic=3078.0
and his "bug", where he only counted shares contributed to the latest block, I realized that such counting is a perfect countermeasure. Since finding a block ensures that everybody else who worked on solving this block wasted its effort, there is no incentive to switching from the pool. If one switches from the pool and finds a block, the pool resets its counter and all the cheater's "unearned" shares will be lost. Of on the other hand, one switches from the pool and the pool find the block, it guarantees there is no individual income after the switching. I'd advice slush and other pool operators to implement this counting. It slightly increases the variance of ones income but it's fair, it's simple and eliminates cheating which with multiple pools can become widespread.

Edit; It won't work, see the further discussion.  

1HAoJag4C3XtAmQJAhE9FTAAJWFcrvpdLM
1480956637
Hero Member
*
Offline Offline

Posts: 1480956637

View Profile Personal Message (Offline)

Ignore
1480956637
Reply with quote  #2

1480956637
Report to moderator
1480956637
Hero Member
*
Offline Offline

Posts: 1480956637

View Profile Personal Message (Offline)

Ignore
1480956637
Reply with quote  #2

1480956637
Report to moderator
1480956637
Hero Member
*
Offline Offline

Posts: 1480956637

View Profile Personal Message (Offline)

Ignore
1480956637
Reply with quote  #2

1480956637
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
Ryo
Newbie
*
Offline Offline

Activity: 28


View Profile
February 04, 2011, 02:04:26 PM
 #2

In this thread, the author finds no evidence of massive use of this strategy
http://bitcointalk.org/index.php?topic=2941.0
(I didn't read the paper since I find it strange to ask for a payment for something that may or may not contain anything interesting; and I didn't find any hard numbers in the discussion)

Well, in the discussion, you could have seen confirmation that people who bought the paper didn't feel cheated. The reson I'm asking money first is that I don't believe people would donate, especially people who want to abuse pools. However, it's been some time since anyone downloaded the paper, so here it is, for free:
http://www.bitcoinservice.co.uk/files/111

If anyone wants to donate (and that would incite me to write more about bitcoin), here's an address:
1ESWeHDPSEErzr6tcm3aToVGXKUe8kA9D8
slush
Legendary
*
Offline Offline

Activity: 1358



View Profile WWW
February 04, 2011, 02:49:44 PM
 #3

I'd advice slush and other pool operators to implement this counting. It slightly increases the variance of ones income but it's fair, it's simple and eliminates cheating which with multiple pools can become widespread.

No, it increase the variance a lot, which is against the purpose of pool. Also resetting on new block isn't solution, because bad guy can start mining on every new bitcoin block & stop after 43% of standard time between two bitcoin blocks. Maybe not such effective as cheating against current pool accounting, but this will still works. So I don't plan to change accounting itself.

I know that it is only matter of time, when somebody start to cheat pool with this technique. So I have prepared 'delayed' stats on the pool. With this update, nobody will known how many shares is in current block. This obfuscate real time statistics a lot, but remain completely fair for all miners and cheaters won't have enough data to know when to switch.

Raulo
Full Member
***
Offline Offline

Activity: 238


View Profile
February 04, 2011, 04:13:49 PM
 #4

No, it increase the variance a lot, which is against the purpose of pool.
Not that much and only for low-hash rate miners that have a lot of variance anyway because even now there are short rounds and for CPU-miners, there is not a matter of reducing variance but increasing probability of any payout and your pool will still work in this respect.  The most variance in your pool comes from different level of "pool daily luck" anyway and this scheme will not change it.

Quote
Also resetting on new block isn't solution, because bad guy can start mining on every new bitcoin block & stop after 43% of standard time between two bitcoin blocks. Maybe not such effective as cheating against current pool accounting, but this will still works.

No, it won't. The whole idea of the pool abuse is that you get paid in two places at the same time. With jgarzik's scheme, it's either or. Either you get paid from the pool, or individually. You never get paid twice. If you start mining on every bitcoin block and stop after some time, you either get paid from the pool (pool found a block) or from yourself (you found a block). Finding a block individually guarantees pool shares reset and all you accumulated shares loss. And finding a block by the pool guarantees that you did't find this block by yourself since the switch time. 

Quote
So I don't plan to change accounting itself.

It's your pool and your rules but I'd recommend you reconsider it because your strategy below is much more messy.

Quote
I know that it is only matter of time, when somebody start to cheat pool with this technique. So I have prepared 'delayed' stats on the pool. With this update, nobody will known how many shares is in current block. This obfuscate real time statistics a lot, but remain completely fair for all miners and cheaters won't have enough data to know when to switch.

Actually, the only thing that the cheater needs is the time when the round started so he can join the pool. Since the I(lambda) function is positive, he can switch out anytime provided he joins when the round starts. You will not only need to hide the number of shares but the round starting time and the number of shares one accumulated in the given round (otherwise the cheater can connect one of its miners and see when the counter starts from zero). This way you can effectively turn off all the statistics and publish only "pool mining digest from yesterday". It will also be unfair to anybody who wants to join the pool (and not cheat) because joining midround is unfair. In my opinion, it will impact the usability of the pool much more than the jgarzik's counting method.

And although I'm not sure because I'm not fluent in the bitcoin protocol, I believe a bad guy can test the bitcoin protocol traffic  to learn that it was the pool that found a block (and hence a new round started) by connecting to your 8333 port and getting your "new block found" broadcast before getting this message from other nodes.  Even if you block your port and connect only to some trusted nodes, by listening to other nodes traffic, he may estimate the probability that you found the block and not a guy in, say, Japan which will have a different node propagation signature. He does not need to be right 100% of the time, being right more than not will be enough. Remember, joining and switching off from the pool at complete random intervals is payoff neutral (apart from startup inefficiencies) so it will be enough  to join more frequently at the start of the round than not. And by looking at the delayed statistics he can check if the strategy worked.


1HAoJag4C3XtAmQJAhE9FTAAJWFcrvpdLM
twobitcoins
Full Member
***
Offline Offline

Activity: 144


View Profile
February 04, 2011, 04:25:24 PM
 #5

Slush is right.  The logic behind the proposed countermeasure does not seem correct.

Suppose the pool is reset at the beginning of a block, you join the pool, and everybody in the pool works at a consistent rate.  Then for each hash you compute, the expected payout is the same as if you were working alone, just with lower variance.

Then at some point you leave the pool and start working alone.  The expected payout for each hash you compute is the same as it was before, but additionally you have the chance to get a payout if someone in the pool finds a block.

The fact that a payout cannot come from both the pool and working alone in the same block doesn't mean you can't increase the total expected payout for your work.
Pieter Wuille
Legendary
*
Offline Offline

Activity: 1036


View Profile WWW
February 04, 2011, 04:40:43 PM
 #6

Quote
Also resetting on new block isn't solution, because bad guy can start mining on every new bitcoin block & stop after 43% of standard time between two bitcoin blocks. Maybe not such effective as cheating against current pool accounting, but this will still works.

No, it won't. The whole idea of the pool abuse is that you get paid in two places at the same time. With jgarzik's scheme, it's either or. Either you get paid from the pool, or individually. You never get paid twice. If you start mining on every bitcoin block and stop after some time, you either get paid from the pool (pool found a block) or from yourself (you found a block). Finding a block individually guarantees pool shares reset and all you accumulated shares loss. And finding a block by the pool guarantees that you did't find this block by yourself since the switch time. 


Furthermore, the difference between an acceptable optimization strategy (whether or not it gains you anything at all) and cheating, is IMHO the fact that if everyone used this 43%-strategy on the current system, it would break down (rounds wouldn't ever get finished), while in a only-shares-for-a-block system, the resulting gains would still be perfectly proportional to invested computation power (as share count would be reset after a block is found, even if everybody stopped pool mining, and people would join again).

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
slush
Legendary
*
Offline Offline

Activity: 1358



View Profile WWW
February 04, 2011, 04:47:58 PM
 #7

Actually, the only thing that the cheater needs is the time when the round started so he can join the pool.

Which pool does not provide...


Quote
You will not only need to hide the number of shares but the round starting time and the number of shares one accumulated in the given round (otherwise the cheater can connect one of its miners and see when the counter starts from zero).

Of course, I see no problem with hiding this.

Quote
This way you can effectively turn off all the statistics and publish only "pool mining digest from yesterday".

Not exactly. For now I disabled some numbers completely (expected round reward or worker shares), but I plan to reimplement this from round-oriented to time-oriented stats soon. So you will still see how many shares will miners does and so.

Quote
It will also be unfair to anybody who wants to join the pool (and not cheat) because joining midround is unfair.

It isn't unfair. Everybody have the same probability to hit good or wrong time to join the pool. Also don't forget that 99% users don't care about this when connecting the pool. Until you don't perform cheating, your loss from connecting in the middle of the round are almost zero.

Quote
he may estimate the probability that you found the block

Nonsense. You cannot say who find the block by listening, for example, #bitcoin-monitor.

Ryo
Newbie
*
Offline Offline

Activity: 28


View Profile
February 04, 2011, 05:18:08 PM
 #8

If someone cheat and get more money on on quick blocks, than someone must lose on quick blocks. I am surely will not be the looser (nor will my customers).

You don't lose on quick blocks. You lose on slow blocks. People who "cheat" simply lose less than you on slow blocks.

If you want to check whether people are "cheating", don't look at quick blocks. Chart computing power against time, and if people cheat, you'll notice a drop as blocks grow longer.
Ryo
Newbie
*
Offline Offline

Activity: 28


View Profile
February 04, 2011, 06:01:27 PM
 #9

Not exactly. For now I disabled some numbers completely (expected round reward or worker shares), but I plan to reimplement this from round-oriented to time-oriented stats soon. So you will still see how many shares will miners does and so.

I'm not sure you can remove the stats that allows one to "cheat" and still provide users with proofs that the pool is fair. Did you find a way ?
slush
Legendary
*
Offline Offline

Activity: 1358



View Profile WWW
February 04, 2011, 06:02:10 PM
 #10

If someone cheat and get more money on on quick blocks, than someone must lose on quick blocks. I am surely will not be the looser (nor will my customers).

In quick rounds is much bigger variance. Many people asked me why they have low reward from some short rounds. Basically it is because they was unlucky in those 3 minutes or so. Mining isn't steady at all, even on diff1 and strong machines, of course.

Quote
Slush, I think that simply delaying or removing real-time stats will not help a lot, because most of relevant data can be obtained from the block chain itself.

Which one?

Quote
Do you use new BTC address for every new block?

Afaik this is default bitcoin behaviour.

slush
Legendary
*
Offline Offline

Activity: 1358



View Profile WWW
February 04, 2011, 06:09:14 PM
 #11

I'm not sure you can remove the stats that allows one to "cheat" and still provide users with proofs that the pool is fair. Did you find a way ?

If you critize my trustworthy, then yes, I can cheat users all the time, I don't need to hide stats to do so. Please tell me reasonable way how to cheat now, if you forget some timing attacks as comparing latencies in notifications of new blocks from p2p site or so, which I'm also working on.

I'll put back stats soon, as I make some improvements in pool core.

Ryo
Newbie
*
Offline Offline

Activity: 28


View Profile
February 04, 2011, 06:20:45 PM
 #12

If you critize my trustworthy

I have no opinion about you, good or bad. My interest is what can be done, not what is actually done.

Quote
then yes, I can cheat users all the time, I don't need to hide stats to do so.

As the pool was before, with full statistics, users could check whether their revenue was really ((50/total_shares) * nb_shares). They could also, by talking with each other, evaluate if the pool reported a plausible number of total shares. While there were ways for the pool to cheat, the statistics allowed users to check it didn't cheat too much.

My understanding of the way your pools works now is: miners find shares, they receive bitcoins, but they can't know how much the pools pays each share. As long as you release data on how much a share is worth, "cheating" becomes possible. I was wondering if you had found a way to preserve both openness and fairness.

I believe having the value of contributed shares decrease over time would also fix the cheating problem, ensuring that the expected gain of joining is the same at all times. And you'd still be able to display the statistics like before.
slush
Legendary
*
Offline Offline

Activity: 1358



View Profile WWW
February 04, 2011, 06:45:18 PM
 #13

As the pool was before, with full statistics, users could check whether their revenue was really ((50/total_shares) * nb_shares). They could also, by talking with each other, evaluate if the pool reported a plausible number of total shares. While there were ways for the pool to cheat, the statistics allowed users to check it didn't cheat too much.

Currently, you don't see realtime stats, but you can compare those numbers on found blocks older than 2 hours, so not such big difference. Also, as I said, this is only temporary solution. Once I'll change some internal things, I'll show realtime stats per actual hour, so everybody will see almost the same numbers as before this last update.

Quote
As long as you release data on how much a share is worth, "cheating" becomes possible.

But you can calculate it itself, too. There is no fancy stats now, but I don't hide any needed info. You know how many shares you submitted and how many reward did you get. You also know that one round is worth of 50BTC. There's nothing hidden! You only cannot calculate/use this numbers at realtime.

Quote
I was wondering if you had found a way to preserve both openness and fairness.

Yes, described above.

Quote
I believe having the value of contributed shares decrease over time would also fix the cheating problem, ensuring that the expected gain of joining is the same at all times.

Tell me how, I'll implement this! But this attitude open completely different way of cheating, I spent on this many hours by thinking. And once I'll need to take a financial risk of pool unlucky/cheating, pool mining won't be for free anymore :-).

Fractality
Jr. Member
*
Offline Offline

Activity: 44



View Profile WWW
February 04, 2011, 07:05:59 PM
 #14

I must admit I didn't go through every line of the paper, so I just wanted to double check if I understood the problem correctly, in simple terms.

Is the problem this, as an example: assume there are 10 miners in a pool, and they each calculate 1000 hashes before the winning block is found. Then among those 1000 hashes, each of them has created the same expected amount of shares (let's say they have 2 shares on average). That would be the fair case.

The problem is that usually the shares won't be the last hashes to be found. So miner X might already have generated 2 shares among his first 500 hashes. If he stops exactly then, he'll have the same number of hashes as the other minors, for only half the work (on average). Of course had he continued to do 500 more hashes, he likely would have created more shares, too, so the calculation is not THAT simple.

Or in other words: if you stop right after receiving a share, you will have done less work for your shares than the fair miners, on average.

Not sure if all the maths in the paper adds up, as I said, I didn't check thoroughly. For example it might be incorrect to talk about n hashes, because if the winning block is found before n hashes, there wouldn't even be n attempts at hashing (I assume once a block is found, all calculations reset to the start :-) Correct me if I am wrong, but isn't the expected number of winning hashes after n attempts simply n*p? 1-(1-p)^n is not the probability to find one block after n hashes, it is the probability to find at least one block after n hashes (and, as I said, in a typical scenario there would not be n hashes, as hashing stops after the first block has been found). (I tend to get these probability calculations wrong all the time, though - my apologies in case I am just spouting nonsense).


1K4noMkNgrPztyqtHCYd2CevsZ72FeYUKF
Raulo
Full Member
***
Offline Offline

Activity: 238


View Profile
February 04, 2011, 07:13:45 PM
 #15

slush and twobitcoins,

You are right. The block-shares resetting still allows for cheating. I was blinded by this nullification stuff and didn't notice it will erase some cheating gains but not all.

Slush "blinding" approach is probably best strategy currently (except awarding 50 BTC to the person who found the block which solves the porblem once and for all Smiley ) but I still think by some bitcoin network analysis (due to different network distances between the nodes) one can find at least the continent, where the current block is found. And the strategy would be to join the pool if the last block was found in Europe and leave the pool if not.  This way you will be more likely connected to the pool for fresh rounds and less likely for stale.

Contributed method is very tricky because in fact, all that matters is the winning block and the non-winning shares are all wasted.  

By the way, for those who want to have some practical test of this cheating strategy, instead of special functions, here is the Monte Carlo run which finds the round length (with exp(-x) distribution) and performs swiching to individual mining after some fraction of shares. Here is the awk code.
Code:
#!/usr/bin/awk -f
BEGIN{srand();lambda=0.434
print "pool  independ.  total"
for (i=1;i<=10000000;i++)
{
# calculate current round length..
  r=rand()
  y=-log(r)

  if (y > lambda) # we switched from the pool after lambda
  {
    payolaind+=(y-lambda)  # independent payout based on fractions not connected to the pool
    payola+=lambda/y         # pool payout reduced since we stopped mining after lambda
  }
  else
    payola++             #normal pool payout


  if (i%100000==0) print payola/i,payolaind/i,(payola+payolaind)/i
}
}

1HAoJag4C3XtAmQJAhE9FTAAJWFcrvpdLM
Raulo
Full Member
***
Offline Offline

Activity: 238


View Profile
February 04, 2011, 07:18:53 PM
 #16

Correct me if I am wrong, but isn't the expected number of winning hashes after n attempts simply n*p? 1-(1-p)^n is not the probability to find one block after n hashes, it is the probability to find at least one block after n hashes (and, as I said, in a typical scenario there would not be n hashes, as hashing stops after the first block has been found). (I tend to get these probability calculations wrong all the time, though - my apologies in case I am just spouting nonsense).

Yes, the average is n*p but what we need is the probability of finding indeed at least one block and by reverse not finding any. This is what drives the strategy. If the block is found early, keep mining for the pool. If not, start individual mining and return after the pool finds a block.

1HAoJag4C3XtAmQJAhE9FTAAJWFcrvpdLM
Raulo
Full Member
***
Offline Offline

Activity: 238


View Profile
February 04, 2011, 07:31:28 PM
 #17

I believe having the value of contributed shares decrease over time would also fix the cheating problem, ensuring that the expected gain of joining is the same at all times. And you'd still be able to display the statistics like before.

This will not help since all old shares are in essence worth zero. Only the winning one is worth 50 BTC. I(λ) function is always positive. No matter how low is your payout after switching out of the pool, you still get "unearned" gains.

It may be possible to make cheating impractical but at the expense of making the pool more like individual mining. Because switching between pool and solo mining costs you some hashes (even if you do it as cleverly as possible), if the payout from cheating is low enough, it may be not worth cheating. I did Monte Carlo simulations  that show that counting only last 10% of difficulty of shares in the pool, reduces the extra cheating income to about 5% but the variance in the pool gets larger. But with multiple pools it get more interesting.

1HAoJag4C3XtAmQJAhE9FTAAJWFcrvpdLM
Raulo
Full Member
***
Offline Offline

Activity: 238


View Profile
February 06, 2011, 12:25:28 AM
 #18

Below is a script for calculating cheater's income in a pool that keeps only some number of most recent shares. It makes the switching from the pool much less profitable.

Code:
#!/usr/bin/awk -f
BEGIN{srand();lambda=0.07 # when to stop mining for the pool as a ratio of difficulty.
payratio=0.05 # how many last shares pool counts. Here 5% of difficulty
print "Fractions of income from"
print "Pool     solo     total"
for (i=1;i<=100000000;i++)
{

  r=rand()
  j=-log(r)


  if (j>lambda)
  {
    payolaind+=(j-lambda) # independent payoff
    payola+=(j<=payratio ? lambda :  (lambda-(j-payratio) > 0 ? (lambda-(j-payratio))/payratio : 0 )) # pool payoff counting only last payratio shares
  }
  else
    payola++  #full payoff. Cheater stayed in the pool for the whole round.

  if (i%1000000==0) print payola/i,payolaind/i,(payola+payolaind)/i
}
}


The above code calculates payoff for a pool that keeps 5% of the difficulty number of shares and the cheater exits from the pool after 7% of the difficulty (this value has to be much lower, lower than original 43%). The calculated value is about 2% which should be low enough to discourage this behavior as switching miners has some overhead (and the pool also has some latency overhead compared to solo mining). Keeping 10% difficulty, results in about 4% gain.  

1HAoJag4C3XtAmQJAhE9FTAAJWFcrvpdLM
eMansipater
Sr. Member
****
Offline Offline

Activity: 294



View Profile WWW
February 06, 2011, 08:10:59 AM
 #19

I think you are all missing the point a little.  The concern is not cheating but undetectable cheating.  Every method of cheating the pool proposed thus far, and indeed virtually any statistically significant exploit(by definition), is easily detectable by the pool operator.  Simply detect, warn, and remove.  Case closed.  Although I applaud Slush's efforts to keep abreast of this issue!  I just think his/her valuable time could be better spent elsewhere.

If you found my post helpful, feel free to send a small tip to 1QGukeKbBQbXHtV6LgkQa977LJ3YHXXW8B
Visit the BitCoin Q&A Site to ask questions or share knowledge.
0.009 BTC too confusing?  Use mBTC instead!  Details at www.em-bit.org or visit the project thread to help make Bitcoin prices more human-friendly.
Raulo
Full Member
***
Offline Offline

Activity: 238


View Profile
February 06, 2011, 08:46:48 AM
 #20

I think you are all missing the point a little.  The concern is not cheating but undetectable cheating.  Every method of cheating the pool proposed thus far, and indeed virtually any statistically significant exploit(by definition), is easily detectable by the pool operator. 

With a little effort by the bad guy, slush will have to have an investigative team to find the problem. Switching users, switching IPs, being honest for some time or cheating with only a part of ones hashrate, all it make harder for the pool operator to detect. There is a lot of normal variance and it masks quite a bit. And it will be even harder, if there are many pools. Sure, if you cheat with, say, 25% of the pool hashrate, you are exposing yourself but with up to 5%, not that much.

1HAoJag4C3XtAmQJAhE9FTAAJWFcrvpdLM
Pages: [1] 2 3 4 »  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!