Geometric method: New cheat-proof mining pool scoring method

[martok]

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?

[Meni Rosenfeld]

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:

Code:

logadd (a,b)
{
  M = max(a,b);
  return M + log ( exp(a-M) + exp(b-M) );
}

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.

[martok]

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

[Meni Rosenfeld]

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

[martok]

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;

[Meni Rosenfeld]

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;

[martok]

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

[Meni Rosenfeld]

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?

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.

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

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.

[martok]

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.

[martok]

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.

[Meni Rosenfeld]

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)

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.

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.

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.

[Meni Rosenfeld]

I have added a correctness proof outline to the OP.

[martok]

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.

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.

[martok]

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.

Sure, that would probably be a more useful measure.

[marcus_of_augustus]

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

update share set score=ln(exp((max-score)*(p2/p1)))?

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?

[Meni Rosenfeld]

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

update share set score=ln(exp((max-score)*(p2/p1)))?

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

Isn't that like doing sin(asin(f(x))) or a cos(acos(X))

It is.

... or is it to round the numerical approximation off or some such?

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.

[Meni Rosenfeld]

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.

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.

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

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.

Sure, that would probably be a more useful measure.

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.

[Craig]

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.

Code:

let f := <initial fixed fee, as portion of total payout>
let c := <initial variable fee, as portion of total payout>
let b := 50 // total block payout

add_share:
let d := most recent difficulty
let p := 1.0 / d

if first round:
let lr := log(1.0 - p + p / c)
let ls := 0
create round:
round.los := log(1 / (exp(lr) - 1))
round.f := f
round.c := c
round.b := b

else with latest round:
let lr := log(1.0 - p + p / round.c)
if first share:
let ls := 0
else with latest share:
let ls := share.lscore + lr

create share:
share.lscore := ls


calculate_payout:
let round := most recent round

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

for share in all shares grouped by worker:
let credit := (1 - round.f) * round.b * sum(exp(share.lscore - max)) / totscore

[Meni Rosenfeld]

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.

[martok]

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

Got it, thanks.

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.

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.