Topic: Geometric method: New cheat-proof mining pool scoring method - page 3. (Read 24426 times)

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.

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.

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.

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.

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

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;

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;

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,

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

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.

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?

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.

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

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.

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

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.

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.

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?

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

Why?