Bitcoin Forum

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 (http://bitcoin.atspace.com/poolcheating.pdf) 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.

Comments and questions are welcome.

Updates:

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).

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 (http://bitcointalk.org/index.php?topic=1976.msg50002#msg50002). 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.

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.

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.

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?

Have any of the pool operators discussed adopting this method?

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

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".

Not that I'm aware of. slush said he would examine it when he has time.

slush's method is not immune to pool-hopping, and if cheaters exist it will have a toll even long-term.

Why?

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 stated very clearly that the expected payout is always the same, and there is never incentive for either shorter rounds or longer rounds.

If this cheaters may predict a future, than yes.

Well, try describe your method in short sentence with all calculations.


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.

Probably I misunderstood here.

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.

Each share has score r^I, where I is the number of shares already submitted, and the operator has score 1/(r-1).

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.

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.
Where is additional profit?
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.

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.

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?".

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.

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

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.

Hmm actually I just overflowed PostGreSQL's numeric format which is the best Postgres can do. Is there any way to make these numbers a bit more reasonably sized?

Yes, there are at least two ways:
1. Periodical rescaling - once in a while (say, 100000 shares) go over all participants and divide their score by s, and reset s to 1. If you are able to do this after every share, you'll also get a more visually pleasant representation of the score. I assume that underflow simply results in 0.
2. Working on a logarithmic scale: Instead of keeping s and the score of each participant, keep their logs. Of course you'll need to adapt all calculations to the new scale, in particular you should use a robust method for addition:

By the way, since it is only capability to work with large numbers that you need and not precision, you can safely use double (or single) precision with these modifications.

Hi,

I don't understand log scale well enough to implement that. Do you just set s to ln(r) as a base then increment s by logadd(s, r)?

However, rescaling did work quite well for getting new scores in but it does have the problem that as pools get faster and faster, rescale will have to occur more and more often.

The payment calculation breaks though. I am using:
s = user score
i = total number of shares submitted by everyone in the round
select (1-f)*b*s*(r-1)/r^i
That gives overflow because i is currently 82000 and r is 1.0108... so that result goes well outside double precision (r^i).

Sorry, I should have clarified that the formula (1-f)*B*S*(r-1)/r^I (which is basically using the summation formula for geometric progressions to evaluate the total score) is valid only for the vanilla method as in the original post. Any changes (adjusting for difficulty changes, rescaling to prevent overflow) require rewriting the formula, and to avoid this complication it's best to not use a formula and just go over the scores of operator and all participants and sum them manually. Then split the (1-f)*B reward between everyone in proportion to their score divided by the total score.

Don't forget that rescaling should be done for the operator's score as well.

I could explain more about logarithmic scale, but if it's not intuitive to you it's best to use periodic rescaling instead. Maybe we'll revisit it when there's a real need (say, the rescaling becomes too resource-demanding).

Hi,

So here is my implementation used on the Continuum pool. Feel free to suggest improvements or things I overlooked. I am particularly interested in how this can be done without periodic rescaling as in moving to a hosted database server, I will have much less CPU power.

So we have round table as:
id int,
(f,c,b) double,
os double ; operator score

share table
id
time
worker
round_id int references round(id)
score double

The score is that assigned for the particular share and not the cumulative score. For that, select sum(score) from share where worker=x and round_id=y

The scoring function is written as a PostgreSQL insert trigger which fires on an insert on share:
CREATE OR REPLACE FUNCTION share_score() RETURNS trigger AS $$
DECLARE
rd round%rowtype;
d double precision;
p double precision;
r double precision;
s double precision;
BEGIN
d := difficulty from difficulty
order by time desc limit 1;
p := 1.0/d;
select * into rd from round
order by id desc limit 1;
if rd is null then
-- First round
insert into round default values;
select * into rd from round
order by id desc limit 1;
r := 1.0-p+p/rd.c;
update round set os=1/(r-1)
where id=rd.id;
s := 1;
else
r := 1.0-p+p/rd.c;
-- Get the last score
s := score*r from share
where round_id = rd.id and score is not null
order by id desc limit 1;
if s is null then
-- first insert in this round
s := 1;
end if;
end if;
NEW.round_id := rd.id;
if NEW.our_result = 'f' then
return NEW;
end if;
-- Check for any needed rescaling
if s > 1e+200 then
update share set score=score/s
where round_id=rd.id;
update round set os=os/s
where id=rd.id;
s := 1;
end if;
NEW.score := s;
RETURN NEW;
END;
$$ LANGUAGE plpgsql;

Then we have worker_payments function which takes round_id and returns a composit of varchar,numeric
CREATE OR REPLACE FUNCTION worker_payments(rnd_id integer)
RETURNS table(
worker text,
cr double precision) AS $$
DECLARE
rd round%rowtype;
totscore double precision;
BEGIN
select * into rd from round where id=rnd_id;
totscore := sum(score)+rd.os from share
where round_id = rd.id;
RETURN QUERY select share.worker,
(1-rd.f)*rd.b*sum(score)/totscore
from share where round_id = rd.id
and score is not null
group by share.worker;
RETURN;
END;
$$ LANGUAGE plpgsql stable;

Ok, I think I know just enough SQL to be able to translate this to logarithmic scale, obviating the need for periodic rescaling. I am assuming log and exp return the natural logarithm and exponentiation. You will of course need to check I didn't mess anything up and test it thoroughly. Note that keeping lr in cache will remove the need to calculate it for each share, and that the summation function in round end is somewhat heavier. Note also that the first function now returns the log of the score. Here is the code, I have also renamed os and score to los and lscore, and bolded the lines I changed.

CREATE OR REPLACE FUNCTION share_score() RETURNS trigger AS $$
DECLARE
rd round%rowtype;
d double precision;
p double precision;
lr double precision;
ls double precision;
BEGIN
d := difficulty from difficulty
order by time desc limit 1;
p := 1.0/d;
select * into rd from round
order by id desc limit 1;
if rd is null then
-- First round
insert into round default values;
select * into rd from round
order by id desc limit 1;
lr := log(1.0-p+p/rd.c);
update round set los=log(1/(exp(lr)-1))
where id=rd.id;
ls := 0;
else
lr := log(1.0-p+p/rd.c);
-- Get the last score
ls := lscore+lr from share
where round_id = rd.id and lscore is not null
order by id desc limit 1;
if ls is null then
-- first insert in this round
ls := 0;
end if;
end if;
NEW.round_id := rd.id;
if NEW.our_result = 'f' then
return NEW;
end if;
-- No need for rescaling!
NEW.lscore := ls;
RETURN NEW;
END;
$$ LANGUAGE plpgsql;

CREATE OR REPLACE FUNCTION worker_payments(rnd_id integer)
RETURNS table(
worker text,
cr double precision) AS $$
DECLARE
rd round%rowtype;
totscore double precision;
max double precision;
BEGIN
select * into rd from round where id=rnd_id;
max := lscore from share
where round_id = rd.id and lscore is not null
order by id desc limit 1;
totscore := sum(exp(lscore-max))+exp(rd.los-max) from share
where round_id = rd.id;
RETURN QUERY select share.worker,
(1-rd.f)*rd.b*sum(exp(lscore-max))/totscore
from share where round_id = rd.id
and lscore is not null
group by share.worker;
RETURN;
END;
$$ LANGUAGE plpgsql stable;

Wow thanks very much. I'll adapt this and see how it works. Does the procedure differ from previous when the difficulty changes or do you just proceed with the new p?

Also, isn't:
totscore := sum(exp(lscore-max))+exp(rd.los-max) from share
likely to overflow any umeric types in PGSQL in the round calculation? I suppose I could just write that function using an arbitrary precision library...

Actually, just moments ago I thought about this again and realized your code doesn't contain the part of updating on difficulty change. Is that on purpose? There is a simple way to implement this, and with a simple tweak it will work for logarithmic scale.

No, that's the magic of the -max part. max can't be much smaller than lscore and los, so the exps won't overflow. They can underflow, but I'm assuming in this case they just return 0 which is ok.


Oh, and I missed two places where score should be replaced with lscore, fixed now.

My difficulty adjustment code is not written as a PLPGSQL function but is done in a cron script written in perl. It looks like:
p1 = 1/od
p2 = 1/nd
update share set score=score*(p2/p1)
update round set os=os*(p2/p1)

Simple stuff. From looking at your log code, would we just do:
update share set score=ln(exp((max-score)*(p2/p1)))?

I don't pretend to understand this stuff yet but that's my wild guess at this point.

Hi,

Another question regarding logging method. Is there a way I can cache totalscore. A balance check is a very common one for users to perform and scanning over share for sum(exp(s-m)) is taking too long. In the exponential method, I was able to keep a totalscore in cache and as a new share came in (totalscore += newscore). It doesn't look that simple with this method since max changes, all of the previous exp(s-max) will also be different.

Ouch, you've done this wrong. In my specification I meant that the scores for existing shares will remain the same, while the variable s that specifies what will be the score for new shares decreases (multiplied by p2/p1). Equivalently, since it's all relative, you could fix s and multiply all scores by p1/p2. But what you've done has two problems:
1. You've multiplied existing scores by p2/p1 instead of p1/p2.
2. Since you don't keep s as a separate variable but rather read it from the shares table, you have scaled both the existing shares and the new shares, so the difficulty fix will actually have no effect whatsoever.
Basically what you want is that the score for the first share submitted after the difficulty change will be multiplied by p2/p1. Then proceed as normal, each share will reference the last one and it will be ok. I don't know what's the DB-friendly way to do that.

Once you show me your solution, I'll adapt it to log scale.

It's quite simple. Note that the value chosen for max is not important, it just needs to be comparable to the highest lscore value and be used consistently.

Keep a value ltotalscore which will represent the logarithm of the total score. Initialize it to los. When a new share is submitted, let ltotalscore += log (1+exp(lscore-ltotalscore)).

Now, if at any point you want to find the balance of a worker, you do

select (1-rd.f)*rd.b*sum(exp(lscore-ltotalscore))
from share where round_id = rd.id
and lscore is not null
and worker = worker_id;

I assume you want to find the balance mid-round? The above will give you what would be the reward if the round ended now. I think it will be more useful to know what is the expected reward. This requires a small tweak, let me know if you are interested in it.

I have added a correctness proof outline to the OP.

Ok, I've refactored the PLPG functions. Now storing r and lastscore in round tbl so difficulty change can just update round set lastscore=lastscore*(p2/p1) and the next insert should do the right thing.

Sure, that would probably be a more useful measure.

Don't want to butt in here guys but how does this bit work?


Isn't that like doing sin(asin(f(x))) or a cos(acos(X)) ... or is it to round the numerical approximation off or some such?

This bit doesn't work (note that martok only asked if it would work). I will soon supply the correct formula.

It is.

It can have a numerical effect, but only for the worse. It can introduce a small error, and if the exp over/under flows you have a problem.

Good. To convert to log scale:
1. Instead of storing r and lastscore, store lr = log(r) and lastlscore = the lscore of the last submitted share.
2. On difficulty change, update round set lastlscore=lastlscore+log(p2/p1).

In fact it's arguably even simpler. For this you don't need to keep ltotalscore. To find the expected payout of a worker for the current round, do

select (1-rd.f)*(1-rd.c)*p*rd.b*sum(exp(lscore-lastlscore))

p should be calculated based on the current difficulty.

To understand the algorithm better, I tried to translate the SQL code from this thread into a more general pseudocode format.  I decided to post it here in case it helps anyone else to understand how the scoring algorithm works.

Note that it does not include the difficulty adjustment calculation as recently discussed.

Note that to help understand how the scoring algorithm works, you would need to post it in linear scale.

Since you wrote it in log scale, it really serves the purpose of helping understand how to implement it in a numerically robust way.

Got it, thanks.

Hmm, unless I am doing something wrong, this is throwing out very small expected values per worker. Much lower than the current balance calculation. < 0.001 BTC.

Is it possible you've used lastscore instead of lastlscore?

If that's not it, can you post the values of

rd.f
rd.c
p
rd.b
lastlscore
sum(exp(lscore-lastlscore))
(1-rd.f)*(1-rd.c)*p*rd.b*sum(exp(lscore-lastlscore))

f = -0.001001...
c = 0.001
lastlscore = 369.6131
sum(exp(lscore-lastlscore)) = 15.0887
(1-f)*(1-c)*p*b*sum
= 0.001

sum(exp(lscore-ltotalscore))
0.0345
(1-f)*b*0.0345
= 1.73

The calculations are correct. 0.001 (actually it's closer to 0.002) is the expectation, while 1.73 is what it would be if it's very lucky and the round ends now (remember, on average 430000 more shares will be introduced before the round ends).
Come to think of it, unless you make c higher (decreasing variance for participants), I don't know if the expectation for already submitted shares is such a useful measure.
Can you tell me the hashrate of this worker and how long it has mined before this evaluation?

That particular worker was my own and it mined at around 330 mhash that round. The round lasted 23 hours, 37 minutes and I would estimate the average of the pool at around 7-8 gh/s. So yes, definitely a short round. I have no long rounds to analyze yet though.

Hi again,

Hopefully I have the payment formulas of your method right. I am wondering what the round duration is before the operator loses money with an expected fee of 0 at c=0.001.
After 4 rounds, I have lost on all even those of relatively short duration. Since I have a miner as well, it doesn't really matter that much. Just wanted to double-check I am scoring correctly.

Here is output on the production pool, note that round 5 is current.
All scores (os, totalscore) are stored in log scale (los = os, ltotalscore = totalscore) I just didn't rename the fields.

select round.id,max(time)-min(time) as duration,
f,c,b,os,totalscore,
cast(f*b as numeric(22,8)) as fixed_fee,
cast((1-f)*b*exp_or_zero(os-totalscore) as numeric(22,8)) as var_fee
from share inner join round on round.id = round_id
group by round.id,f,c,b,os,totalscore
order by round.id;

id|duration|f|c|b|os|totalscore|fixed_fee|var_fee
1|1 day 04:37:44.14842|-0.001001001001001|0.001|50.00050000|5.4987402081296|440.583124446139|-0.05005055|0.00000000
2|2 days 21:09:25.495721|-0.001001001001001|0.001|50.16350000|6.07607688989912|712.769182213441|-0.05021371|0.00000000
3|23:37:05.5112|-0.001001001001001|0.001|50.081|6.07607688989912|375.691503438233|-0.05013113|0.00000000
4|1 day 22:36:46.451189|-0.001001001001001|0.001|50.04050000|6.07607688989912|652.242820446803|-0.05009059|0.00000000
5|2 days 00:42:35.360026|-0.001001001001001|0.001|50|6.07607688989912|833.963234742525|-0.05005005|0.00000000

exp_or_zero function is a wrapper on exp() which returns 0 in case of an underflow. It does so only in the current round which is a bit long.

Looks ok, but it will help if you also post the number of shares on each round.

To profit in a round you need it to have less than 3,000 shares (which happens with probability 1/140). So that's fairly rare, but in those cases you do, you'll make on average about 1/7 of the block reward so it evens out. The variance is still not too bad because even when you lose, you don't lose too much.

Thanks, as long as it looks ok, I am content with the variance.

For completeness though:
select round.id,count(*) from round inner join share on round.id=round_id
where score is not null
group by round.id
order by round.id;
id|count
1|83410
2|275961
3|161084
4|281610
5|412581

I'm finding some inconsistencies between the reported ltotalscore and what it should be based on the number of shares. For rounds 3 and 4 the error is only in the 2nd decimal place so it's tolerable. But for rounds 2 and 5, the total score is as if the round lasted 307990 and 360808 shares, respectively.

Ok, for 5 that may be my posting error. 5 is current round and I posted totalscore earlier in the day and posted share count later.
Here it is in an atomic select
totalscore: 997.23786939
shares: 431965

As for round 2, can the difficulty change account for that? r gets adjusted and subsequent scores also. The above reported r value for round 2 is that at the end of the round, but not so for the duration.

Ok, that's better. There's still an error in the 3rd decimal place which I don't think should happen.


Yeah, that could be it. If you happen to know at which share the difficulty changed I'll be able to verify it (assuming everything worked as specified for that round).

I could really use the help getting this setup on my opensource pool frontend.

It's based on mysql, php and pushpool.

Any help would be greatly appreciated, as well as benefit the community with an opensource solution for their own implementation.

(watching)

I'll sit this one out because I haven't the slightest idea how to set it up (if I had, I probably would have done so myself a long time ago). I hope martok will be willing to compare notes with you.

I'm getting close :D

seems like r^i is huge! even a 53digit double gets rounded eventually.

You'll need to use either periodic rescaling or logarithmic scale, as discussed in this thread.

I'm going for logarithmic, since the other seems hackish.

So, I'm close...... it looks like max is the previous row lscore value, is that right?

Yes. The exact value used for max doesn't matter, as long as it's used consistently and it's about the right size. Its role in the calculation is just to shift the scale to a reasonable location to avoid under/over flowing the exp.

Got it! ;)

I haven't had to wrap my head around this much math in a while.

1 final question.

How do I calculate estimates while using the logarithmic scaling?

(Update, nvm, think I got it)

using (1-rd.f)*(1-rd.c)*p*rd.b*sum(exp(lscore-lastlscore)) to calculate an estimated earning, I'm getting wildly incorrect results.

For example my account says 11.x, when I run the full round calc it's closer to 6.

Additionally, the sum of estimates is >88, when it should be < 50.

I'm looking at a round with ~1mil shares.

I should emphasize that mid-round estimates are fairly meaningless. It is always almost certain that round end will be far enough in the future that all current shares will be worthless. In particular, calculating the expected reward for already existing shares will be close to 0, while calculating the reward if the round ended now will be much higher.

However, the numbers you write might indicate a problem with the calculation. Please post all the values involved, as well as the lscore values of the last few shares - both in general and for the particular worker.

Also, in your thread you say

If you use f=0, c=0.001 then it's not 0.001% fee, it's 0.1% fee. And it's the average - on any round it can be much higher. You can also consider using negative f to make the expected fee 0.

Those not trying to pool-hop will, in expectation, earn exactly as much as those who are, per share submitted.

It's been some time since I've used MySQL but I expect that might give you some trouble implementing this method. Not to say it can't be done but you might have to be careful with it. Unless MySQL has a serializable mode IE select * from round for update blocks other threads trying to score a share, there is a possibility of bad data getting in:
thread1: select * from round; lastscore = 1
thread2 select * from round; lastscore = 1.
thread 1 scores current share at 1+r
thread 2 does the same thing
thread 1: update round set lastscore=lastscore+r
commit
thread2 update round set lastscore=lastscore+r
but thread2's score is wrong because 1's update dwasn't accounted.

MySQL has transactions these days but I wonder how it handles this where shares depend on previous data.

It seems to be behaving now, I think it was just the earlier implementation. It's off, just not quite as badly.



so using
$c = 0.001;
$f = (-$c)/(1-$c);
should result .1%? or should that be closer to 0?
Is there a way to get to 0% without possible losses?


Got it.

With these parameters the expected fee is 0, and for any round and it can be as low as -0.1001% (negative) or as high as 100%.
There's no way to have expected fee of 0% without a risk of losing out on a round. Note that the losses will be very small though.

So I have been trying to figure out the last part of this and from everything I've read in the thread and from some example code I've looked at for both PGSQL and MySQL, I can't quite grasp what's going on here:

let totscore := sum(exp(share.lscore - max)) + exp(round.los - max)

In the pseudo code, PGSQL code and MySQL code, the bolded part would always seem to evaluate to zero?  Is this correct?  If not, it seems that lscore will be an arbitrary number based off the last user to submit a share for that block (presumably the person who found the answer).  So one person can have an lscore of 80, having been there the entire round, and another person can have an lscore of 1, but find the block, thus giving the completely random and arbitrary value of lscore in that scenario.

So, my question is can someone explain which value lscore is and why?  If it's the former, what's the point of having an expression that always evaluates to zero?  If the latter, what's going on with the formula that it can take an essentially random number and use it as a valid value for calculating score?

The formula you quote is used only when the round ends to calculate the payouts.

lscore is the logarithm of the score for a given share.

"share" is a table that contains information about all shares. "max" is the lscore of the last share (note the "order by id desc limit 1;" part). So only for the last share lscore - max will be 0, for earlier shares it will be negative. You sum over all shares.

The later the share was submitted, the higher its lscore, as specified in the algorithm.

Hi Meni,

Thanks for responding.  So just to confirm, MAX is being set to the score of the last share, which is arbitrary in so far as it could be anything depending on when the round ends?

I think I understand what's going on now as far as lscore - max.  Is the share table then intended to contain one row per share each with a score as opposed to one row per user with an aggregate score that is increased for each share submitted?  I think that may be where I went off track and why it wasn't making sense.

Is each share worth a certain amount, regardless of who submitted it or does the value of a share differ depending on who submitted it?  By this, I mean if person A has submitted 500 shares in the past hour and person B has submitted 200 shares in the past hour, person A's 500th share is worth more than person B's 200th share or A's 500th and B's 200th are worth the same if they are submitted at the same time (well, one is worth slightly less than the other depending on which order it was submitted)?

Yes. And it's also arbitrary in the sense that it's just used for numerical stability, you can use another value for it as long as it's used consistently in all parts of the calculation.

Correct, one row per share.

Yes, the value of a share depends only on when it was submitted and not on who submitted it. The total payout of a worker is just the sum of the payouts for all of his shares.

Thank you Meni, I think I understand now.   I will probably have some more questions tomorrow ;)

This is a really interesting score implementation.  I have a few questions.

I have not had a lot of success getting your proof to render for me.  Can you describe how you came up with the decay factor, r?  Isn't it really a growth factor for any reasonable c?

Is it true that for a very low number of shares ( < 1000 ) at the current difficulty, the total fee gets really large ( > 50% ) when c = 0.001?  My implementation seems to show this.  Does this mean that a really lucky block find would mean bad news for pool members, or is my implementation flawed?

Expanding on this, what impact would having the score start at some high arbitrary number (e.g. r^10000) instead of 1 have?  It seems it could enable setting a max value for what fee would be taken, but I'm not sure how doing this would effect the cheat-proofness of the system and expected fee calculations.

For difficulty 2 and difficulty 3 shares is p simply 2/difficulty and 3/difficulty respectively?

It's growth in the score of new shares, but a decay in the value of old shares. It's the unique value that makes the sums come out right. In fact you could choose r first and then find c, the average score fee, in terms of r.

Yes, the fee is large for short rounds. This is because there aren't many participants to receive a reward, otherwise early miners would get a disproportionate reward.

If you do this and keep the score fee as stated, it will be like decreasing the score fee, which means that this is no longer hopping-proof.

Yes.

All in all the method was designed for everything to be 100% accurate in expectation, though this means relatively high variance and some counterintuitive situations.