Bitcoin Forum
December 03, 2016, 11:49:11 AM
 News: Latest stable version of Bitcoin Core: 0.13.1  [Torrent].
 Home Help Search Donate Login Register
 Pages: [1] 2 3 4  All
 Author Topic: Geometric method: New cheat-proof mining pool scoring method  (Read 22640 times)
Meni Rosenfeld
Donator
Legendary

Offline

Activity: 1890

 March 22, 2011, 08:28:49 PM

I would like to propose a new score-based payout method for mining pools. It was designed to resist pool-hopping, a form of cheating where a miner only participates at the beginning of a round, when his expected payout is too high compared to his efforts and contribution to the pool. This is of course at the expense of honest participants whose payouts will decrease. This cheat was discussed in this paper by Raulo.

I claim, and will later supply a proof as time permits, that this method is 100% immune to this attack. The expected payout per share submitted is always the same no matter when it was submitted. Note that this does not purport to resist any other type of attack.

The greatest disadvantage of this method - which is very mild in my opinion - is that it has the counter-intuitive property that the fee collected per block by the pool operator varies depending on the length of the round. In this sense it is a bit similar to the pay-per-share model (in fact, pay-per-share is a special case). It can be shown, under some very reasonable assumptions, that a variable fee must be introduced to make a scoring scheme cheat-proof without reducing it to solo mining.

I had originally planned to discuss this with slush before posting, but he is working on more important things now so I decided to go ahead.

I will first describe the method and then provide some analysis.

Choose parameters f and c, where f determines the fixed portion of the fee, and c determines the variable fee, or "score fee".
Let p = 1/difficulty be the probability that a share will solve a block.
Let r = 1-p+p/c be a decay factor.
When a participant submits a share, his score for the current round increases by r^i, where i is the number of shares already submitted at the time.
At the end of the round, when a block with reward B is found, each participant receives a payout of (1-f)*B*S*(r-1)/r^I, where S is the score accumulated by the participant in this round and I is the total number of shares submitted by all participants in this round. The rest is kept with the pool operator. For this discussion it is assumed that B is constant.

The intuition behind this payout is: The operator first takes a fixed cut of f from the block reward. He distributes the rest among all participants in proportion to their score, where he assigns himself a score of 1/(r-1) = c/(p-p*c) (which is equivalent to submitting infinitely many shares, in the beginning of the round, at the chosen decay rate).

It can be shown that the expected payout per share submitted is exactly (1-c)*(1-f)*p*B, no matter when the share was submitted. For solo mining this would have been p*B.
The fee collected by the operator varies and is less the longer the round is. The expected fee is (c+f-cf)*B per block.
The variance of a participant's payout, per share, is approximately (p*B)^2 / (2c+p). For solo mining this would have been p*B^2. This is a decrease of roughly (1+2c/p) times.
The variance of the operator's fee, per block, is approximately c*B^2/(2-c).

If the value c+f-cf (or roughly c+f), which is the average fee rate, is kept fixed while c increases and f decreases, the variance for the operator is increased and for participants it is decreased. By choosing c=0.001 and making up the rest of the fee with f, a reasonable variance can be achieved for both. As long as f is positive, the operator will never lose money on a round. If the operator chooses to absorb more variance in behalf of the participants, he can let f be negative and push c further, effectively adding his own money to the block reward, which will lead him to lose from especially long rounds. He can even choose f = (-c)/(1-c) and have an expected fee of 0.

In the limit c=0, only the winning share is rewarded and the participants are effectively mining solo (and paying for it, if f>0). In the limit c=1, with f being correspondingly highly negative, this reduces to pay-per-share (note that the approximate variances given above assume c and f are small and so don't apply for this case). c shouldn't be outside the range (0, 1).

If a participant has only a small part of the pool mining rate, the payouts of his submitted shares will be roughly uncorrelated, and his variance scales linearly with the number of shares (this is a good thing, as it means the standard deviation scales by its square root). As a participant's part approaches 100% of the pool rate, his shares will be adjacent and correlated, reducing to effectively mining solo.

I have not addressed in this description the case that the difficulty changes in the middle of the round, but this is solved with a simple tweak I will describe at a later time.

Correctness proof outline:
Let K be the number of existing shares in the round when you submit a share. The reward you will receive for this share is a random variable which depends on I, the total number of shares at round end, which itself is a random variable at this point. The distribution of I, given that there are already K shares, is
Pr (I = i | I > K) = 0 if i <= K, p(1-p)^{i-K-1} if i > K
The reward for this share, as a proportion of the total reward distributed, in terms of I, is
$\frac{r^K}{\frac{1}{r-1}+\sum_{j=0}^{I-1}r^j}=(r-1)r^{K-I}$
So the expected reward is
$\sum_{i=K+1}^{\infty}p(1-p)^{i-K-1}(r-1)r^{K-i} = \frac{p(r-1)}{1-p} \sum_{i=K+1}^{\infty}((1-p)/r)^{i-K} = \frac{p(r-1)}{p+r-1} = p(1-c)$
Since the total reward distributed is (1-f)B, the expected payout is (1-f)(1-c)pB. This is independent of K, so the expected payout does not change when submitting the share early or late in the round.

As discussed later in the thread, implementing this scoring method requires using a logarithmic scale.

The exact procedure which also deals with difficulty changes is:
1. At the beginning of the round, calculate p = 1/difficulty and r = 1-p+p/c.
2. Assign the operator a score of 1/(r-1).
3. Initialize s=1, this will keep track of the score given for the next share.
4. When a user submits a share: Add s to his score, and let s=s*r.
5. If the difficulty changes to a new value so that 1/difficulty is now p2: Let s=s*p2/p and r=1-p2+p2/c (which is the same formula for r, now with the new p). Continue with step 4 for each submitted share henceforth.
6. When round ends, sum up all scores and divide the reward proportionally (this sum can be evaluated quickly using the formula for a geometric progression, keeping in mind that each difficulty change creates a new progression, but it's simpler to do a brute-force sum).

1EofoZNBhWQ3kxfKnvWkhtMns4AivZArhr   |   Who am I?   |   bitcoin-otc WoT
Bitcoil - Exchange bitcoins for ILS (thread)   |   Israel Bitcoin community homepage (thread)
Analysis of Bitcoin Pooled Mining Reward Systems (thread, summary)  |   PureMining - Infinite-term, deterministic mining bond
1480765751
Hero Member

Offline

Posts: 1480765751

Ignore
 1480765751

1480765751
 Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1480765751
Hero Member

Offline

Posts: 1480765751

Ignore
 1480765751

1480765751
 Report to moderator
1480765751
Hero Member

Offline

Posts: 1480765751

Ignore
 1480765751

1480765751
 Report to moderator
hippich
Hero Member

Offline

Activity: 546

 March 22, 2011, 08:44:26 PM

Not sure which method Slush's pool uses, but there if you submit few shares and then leave pool, your profit will be almost 0 by the end of the round. So it looks very similar to solution to the problem you describe here.

Meni Rosenfeld
Donator
Legendary

Offline

Activity: 1890

 March 22, 2011, 08:50:35 PM

Not sure which method Slush's pool uses, but there if you submit few shares and then leave pool, your profit will be almost 0 by the end of the round. So it looks very similar to solution to the problem you describe here.
Of course I know all about (well, something about) the method slush uses, which is described here. He uses a share score that decays exponentially with the age of a share in units of time, with a decay factor for which he gave no motivation. It is best seen as a crude approximation to the method I present here. slush's method is cheat-resilient, but mine is cheat-proof.

1EofoZNBhWQ3kxfKnvWkhtMns4AivZArhr   |   Who am I?   |   bitcoin-otc WoT
Bitcoil - Exchange bitcoins for ILS (thread)   |   Israel Bitcoin community homepage (thread)
Analysis of Bitcoin Pooled Mining Reward Systems (thread, summary)  |   PureMining - Infinite-term, deterministic mining bond
bobR
Member

Offline

Activity: 112

 March 22, 2011, 09:01:55 PM

Slush's method is ....take a chance  ... when will you get lucky
Lately is's crap... submit you shares we'll take them    guess what u got   squat
slush decays too rapidly
the last couple days are ...
but he clames it all averages out
Well I'm NOT seeing that
I'm seeing less pay out per day..pay out per share
niooron
Full Member

Offline

Activity: 190

 March 22, 2011, 09:28:02 PM

Slush's method is ....take a chance  ... when will you get lucky
Lately is's crap... submit you shares we'll take them    guess what u got   squat
slush decays too rapidly
the last couple days are ...
but he clames it all averages out
Well I'm NOT seeing that
I'm seeing less pay out per day..pay out per share

I have a Radeon HD 4670, that only gets 35 Mhash/s. I get much better payment than a paypershare pool as long as a block is found in less than 2 hours.

14dxwuQwkQiLbZjJFfciZ26xSGdRU5mKEp
xenon481
Sr. Member

Offline

Activity: 406

 March 31, 2011, 09:34:48 PM

I really like this method and don't want it to get lost.

The easiest way to describe it (although not exactly precise) is that the pool operator takes X% of fee from every round but that % goes down the longer (more shares submitted) that the round goes.

This is beautiful from a marketing perspective because it can be spun as the pool giving a rebate of it's fees for longer rounds.

Tips Appreciated: 171TQ2wJg7bxj2q68VNibU75YZB22b7ZDr
martok
Full Member

Offline

Activity: 140

 April 18, 2011, 09:55:26 PM

I have not addressed in this description the case that the difficulty changes in the middle of the round, but this is solved with a simple tweak I will describe at a later time.

It isn't obvious to me how you handle this case. Would you recalculate the previous scores with the new difficulty value and just rescore the round?
marcus_of_augustus
Legendary

Offline

Activity: 2086

 April 18, 2011, 10:06:09 PM

Have any of the pool operators discussed adopting this method?

dbitcoin
Hero Member

Offline

Activity: 742

BTCDig - mining pool

 April 19, 2011, 04:32:54 PM

I really like this method and don't want it to get lost.

The easiest way to describe it (although not exactly precise) is that the pool operator takes X% of fee from every round but that % goes down the longer (more shares submitted) that the round goes.

This is beautiful from a marketing perspective because it can be spun as the pool giving a rebate of it's fees for longer rounds.

How about motivation for exit from pool and got a longer rounds? Result - zero/low fee for operator

BTCDig - mining pool (Stratum, VarDiff, DGM, SSL, JSON API)
dbitcoin
Hero Member

Offline

Activity: 742

BTCDig - mining pool

 April 19, 2011, 04:40:21 PM

Have any of the pool operators discussed adopting this method?

Current exponential score method enough for eliminate pool-hooping cheaters problem.
Without any noticeable side effects in long term mining period.
The described method more complicated for end user and have a problem with difficulty change during round.
And this method has potential incentive for "longer rounds".

BTCDig - mining pool (Stratum, VarDiff, DGM, SSL, JSON API)
Meni Rosenfeld
Donator
Legendary

Offline

Activity: 1890

 April 19, 2011, 05:15:55 PM

Have any of the pool operators discussed adopting this method?
Not that I'm aware of. slush said he would examine it when he has time.

Current exponential score method enough for eliminate pool-hooping cheaters problem.
Without any noticeable side effects in long term mining period.
slush's method is not immune to pool-hopping, and if cheaters exist it will have a toll even long-term.

The described method more complicated for end user
Why?

and have a problem with difficulty change during round.
I stated very clearly that it does not have a problem with difficulty change. This only requires a rescaling of the scores which is very simple (just multiply all current scores by p2/p1).

But there's a more fundamental problem with your statement. My method comes with a guarantee of 100% fairness, so maintaining this guarantee under all contingencies may require special attention. slush's method doesn't come with any guarantee so it's easy to ignore such contingencies. In particular, slush's method also stands to gain by rescaling at difficulty jumps, which he doesn't currently do.

And this method has potential incentive for "longer rounds".
I stated very clearly that the expected payout is always the same, and there is never incentive for either shorter rounds or longer rounds.

1EofoZNBhWQ3kxfKnvWkhtMns4AivZArhr   |   Who am I?   |   bitcoin-otc WoT
Bitcoil - Exchange bitcoins for ILS (thread)   |   Israel Bitcoin community homepage (thread)
Analysis of Bitcoin Pooled Mining Reward Systems (thread, summary)  |   PureMining - Infinite-term, deterministic mining bond
dbitcoin
Hero Member

Offline

Activity: 742

BTCDig - mining pool

 April 19, 2011, 07:36:33 PM

Quote
slush's method is not immune to pool-hopping, and if cheaters exist it will have a toll even long-term.
If this cheaters may predict a future, than yes.

Quote
The described method more complicated for end user
Why?
Well, try describe your method in short sentence with all calculations.

Quote
I stated very clearly that it does not have a problem with difficulty change. This only requires a rescaling of the scores which is very simple (just multiply all current scores by p2/p1).

But there's a more fundamental problem with your statement. My method comes with a guarantee of 100% fairness, so maintaining this guarantee under all contingencies may require special attention. slush's method doesn't come with any guarantee so it's easy to ignore such contingencies. In particular, slush's method also stands to gain by rescaling at difficulty jumps, which he doesn't currently do.

I don't see 100% guaranties here if this method need special attention.
Exponential score method guaranties what all honest miners got the same money as on proportional payout
and cheaters do not get any additional profit from jumping (only losses).
Only long term period matter (weeks, month), 1-2 day do not matter at all.

Quote
I stated very clearly that the expected payout is always the same, and there is never incentive for either shorter rounds or longer rounds.
Probably I misunderstood here.

BTCDig - mining pool (Stratum, VarDiff, DGM, SSL, JSON API)
Meni Rosenfeld
Donator
Legendary

Offline

Activity: 1890

 April 20, 2011, 03:12:31 AM

Quote
I stated very clearly that it does not have a problem with difficulty change. This only requires a rescaling of the scores which is very simple (just multiply all current scores by p2/p1).
But there's a more fundamental problem with your statement. My method comes with a guarantee of 100% fairness, so maintaining this guarantee under all contingencies may require special attention. slush's method doesn't come with any guarantee so it's easy to ignore such contingencies. In particular, slush's method also stands to gain by rescaling at difficulty jumps, which he doesn't currently do.
I don't see 100% guaranties here if this method need special attention.
Exponential score method guaranties what all honest miners got the same money as on proportional payout
and cheaters do not get any additional profit from jumping (only losses).
Only long term period matter (weeks, month), 1-2 day do not matter at all.
I do not enjoy repeating myself.
slush's method does not guarantee that cheaters do not get additional profit. By participating only very early in the round, they can increase their profit and of course the profit of honest miners will decrease. The problem is of course not as severe as in proportional but still.
This increase/decrease is in expectation, and thus will maintain itself over long periods of time.
slush's method also needs to rescale at difficulty jumps (which is so simple I can't believe we're arguing this) but this is ignored because it doesn't have any guarantees to begin with.
Rescaling is just a part of the very careful design of my method, just like the value of the score fee was specifically chosen to make the payout distribution time-invariant.
My method is also exponential, so a better way to refer to slush's method might be "fixed-fee time-exponential score method". The main differences of my method is that the exponential depends on shares rather than time, and that a score fee is introduced to make it 100% cheat-proof.
The "special attention" I talked about was in the design, not in the operation. Of course I paid attention to every detail to make it work flawlessly. The pool operator just needs to plug in the formulae, fire and forget.

Well, try describe your method in short sentence with all calculations.
Each share has score r^I, where I is the number of shares already submitted, and the operator has score 1/(r-1).

1EofoZNBhWQ3kxfKnvWkhtMns4AivZArhr   |   Who am I?   |   bitcoin-otc WoT
Bitcoil - Exchange bitcoins for ILS (thread)   |   Israel Bitcoin community homepage (thread)
Analysis of Bitcoin Pooled Mining Reward Systems (thread, summary)  |   PureMining - Infinite-term, deterministic mining bond
dbitcoin
Hero Member

Offline

Activity: 742

BTCDig - mining pool

 April 20, 2011, 03:34:00 AM

I do not enjoy repeating myself.
slush's method does not guarantee that cheaters do not get additional profit. By participating only very early in the round, they can increase their profit and of course the profit of honest miners will decrease.

What you mean here: 'only very early in the round' ?
Round may ends in 3 seconds or continue up to 3 hours (with slush's pool hashrate).
When cheater should exit from round?

BTCDig - mining pool (Stratum, VarDiff, DGM, SSL, JSON API)
Meni Rosenfeld
Donator
Legendary

Offline

Activity: 1890

 April 20, 2011, 03:48:27 AM

I do not enjoy repeating myself.
slush's method does not guarantee that cheaters do not get additional profit. By participating only very early in the round, they can increase their profit and of course the profit of honest miners will decrease.
What you mean here: 'only very early in the round' ?
Round may ends in 3 seconds or continue up to 3 hours (with slush's pool hashrate).
When cheater should exit from round?
Probably after 30 minutes or so.
Another problem with time-exponential is that it is much harder to analyze than score-exponential. It can be analyzed if we assume the pool's hash rate is constant.
If we make this assumption, and we know the pool's hashrate and slush's decay factor, I'll be able to calculate when is the best time to hop and what can be gained by it. But I don't think calculating the exact numbers is as important as simply knowing that hopping is profitable.
Also, for time-exponential, the decay factor should be proportional to the pool's hashrate. I did not see you or slush mentioning you do that, and if you don't, the decay will become weaker when your hashrate increases.
Time-exponential is also vulnerable to attacks based on fluctuations in the hashrate.

1EofoZNBhWQ3kxfKnvWkhtMns4AivZArhr   |   Who am I?   |   bitcoin-otc WoT
Bitcoil - Exchange bitcoins for ILS (thread)   |   Israel Bitcoin community homepage (thread)
Analysis of Bitcoin Pooled Mining Reward Systems (thread, summary)  |   PureMining - Infinite-term, deterministic mining bond
dbitcoin
Hero Member

Offline

Activity: 742

BTCDig - mining pool

 April 20, 2011, 04:23:56 AM

When cheater should exit from round?
Probably after 30 minutes or so.
Another problem with time-exponential is that it is much harder to analyze than score-exponential. It can be analyzed if we assume the pool's hash rate is constant.
If we make this assumption, and we know the pool's hashrate and slush's decay factor, I'll be able to calculate when is the best time to hop and what can be gained by it. But I don't think calculating the exact numbers is as important as simply knowing that hopping is profitable.
Also, for time-exponential, the decay factor should be proportional to the pool's hashrate. I did not see you or slush mentioning you do that, and if you don't, the decay will become weaker when your hashrate increases.
Time-exponential is also vulnerable to attacks based on fluctuations in the hashrate.

Probably if method much harder to analyze - it's better for protection?
Ok, after 30 min cheater exit from pool and in the next 30 min (or faster), submitted shares lost their value.
As I say one "lucky" round or even 2 days doesn't matter. Only long term average value.

And of course decay adjusted to lover value, when pool hashrate grow.

BTCDig - mining pool (Stratum, VarDiff, DGM, SSL, JSON API)
Meni Rosenfeld
Donator
Legendary

Offline

Activity: 1890

 April 20, 2011, 04:55:53 AM

Probably if method much harder to analyze - it's better for protection?
Not as good as a method which was analyzed and proven to be secure (I did not post the proof yet due to insufficient interest). Also, someone who wants to cheat for profit will be motivated to analyze it anyway.

Ok, after 30 min cheater exit from pool and in the next 30 min (or faster), submitted shares lost their value.
If the round lasts a long time after the cheater left and the shares lost all their value, he'll gain nothing either way.
But if the round ends shortly after or before cheater decides to hop, then his profit will be much higher if the round is fresh, because there will be less people with shares to split the reward with.
Let's say shares are devalued completely after 30 minutes. Then it doesn't matter if the age of the round is 30 minutes, or 60, or 100 or more, because in all those cases there are 30 minutes worth of shares. But if the age is 0 minutes, or 10 or 20, or anything less than 30, there will be less than 30 minutes worth of outstanding shares, thus profit will be greater.
Taking this into account, expected payout will be greater when participating early. Expectation = long term average value.
My method takes care of this by always having "30 minutes worth of shares", so to speak, where the operator has them if they do not yet belong to participants.
Of course I'm just handwaving here, but this can be rigorously analyzed.
The correct question to ask is always, "If I submit a share now, what is my expected payout from it?".

1EofoZNBhWQ3kxfKnvWkhtMns4AivZArhr   |   Who am I?   |   bitcoin-otc WoT
Bitcoil - Exchange bitcoins for ILS (thread)   |   Israel Bitcoin community homepage (thread)
Analysis of Bitcoin Pooled Mining Reward Systems (thread, summary)  |   PureMining - Infinite-term, deterministic mining bond
Meni Rosenfeld
Donator
Legendary

Offline

Activity: 1890

 April 21, 2011, 06:43:34 PM

I have not addressed in this description the case that the difficulty changes in the middle of the round, but this is solved with a simple tweak I will describe at a later time.

It isn't obvious to me how you handle this case. Would you recalculate the previous scores with the new difficulty value and just rescore the round?
Sorry for the late reply, I didn't notice your post. Here is the exact procedure which also deals with difficulty changes:

1. At the beginning of the round, calculate p = 1/difficulty and r = 1-p+p/c.
2. Assign the operator a score of 1/(r-1).
3. Initialize s=1, this will keep track of the score given for the next share.
4. When a user submits a share: Add s to his score, and let s=s*r.
5. If the difficulty changes to a new value so that 1/difficulty is now p2: Let s=s*p2/p and r=1-p2+p2/c (which is the same formula for r, now with the new p). Continue with step 4 for each submitted share henceforth.
6. When round ends, sum up all scores and divide the reward proportionally (this sum can be evaluated quickly using the formula for a geometric progression, keeping in mind that each difficulty change creates a new progression, but it's simpler to do a brute-force sum).

This way, whenever a participant submits a share, he always sees behind him a score of 1/(r-1) times this share's score, with r based on the current difficulty.

Edit: Fixed an error in the formula. Again.

1EofoZNBhWQ3kxfKnvWkhtMns4AivZArhr   |   Who am I?   |   bitcoin-otc WoT
Bitcoil - Exchange bitcoins for ILS (thread)   |   Israel Bitcoin community homepage (thread)
Analysis of Bitcoin Pooled Mining Reward Systems (thread, summary)  |   PureMining - Infinite-term, deterministic mining bond
martok
Full Member

Offline

Activity: 140

 April 22, 2011, 12:41:26 AM

5. If the difficulty changes to a new value so that 1/difficulty is now p2: Let r2=1-p2+p2/c and s=s*(p2 r)/(p r2) (which is the same formula for r, now with the new p). Continue with step 4 with r=r2 for each submitted share henceforth.
6. When round ends, sum up all scores and divide the reward proportionally (this sum can be evaluated quickly using the formula for a geometric progression, keeping in mind that each difficulty change creates a new progression, but it's simpler to do a brute-force sum).

This way, whenever a participant submits a share, he always sees behind him a score of 1/(r-1) times this share's score, with r based on the current difficulty.

Thanks for this explanation. I have a working PostgreSQL implementation now and the data is looking good.
martok
Full Member

Offline

Activity: 140

 April 23, 2011, 10:16:23 PM

Well, one thing I've learned about this algorithm today. double precision is not enough and one has to use an arbitrary precision type to handle s as it gets very big indeed for long rounds.
 Pages: [1] 2 3 4  All
 « previous topic next topic »