Meni Rosenfeld
Donator
Legendary
Offline
Activity: 2044
Merit: 1000


August 28, 2011, 12:04:16 PM 

PPLNS, or "Pay per last N shares", is a reward system that has been known for a while, but I don't think there's a definitive thread discussing it, including how to implement it in a way that is hoppingproof even considering difficulty changes. The basic method is this: Whenever a block is found, payment is given to shares in a window, starting with the last share submitted and going backwards up to some number N of shares. Shares older than the window are not paid. This is essentially a 01 cutoff decay function. There is no concept of rounds  shares can be paid even if they were found before the previous block. This means that a given share can be paid more than once  however, the payouts are chosen so that the expected reward is equal to solo expected reward. Because the payment for a share depends only on blocks found in the future and not on shares and blocks found in the past, there is no way to hop based on the current status of the pool. However, if implemented incorrectly, it is possible to hop based on imminent difficulty changes. The most naive implementation is to have a fixed N and simply pay the last N shares equally. However, this makes it more profitable to mine before difficulty decreases, and less profitable before difficulty increases  the number of blocks that are expected to be found in your window depends on the future difficulty, while the payout you can receive elsewhere depends on the current difficulty. It doesn't help if N is chosen to be a given multiple of the difficulty at the time a block is found. If the difficulty is about to increase, it is more profitable to mine a short while before. For example, if N is set equal to the difficulty D, a share submitted D shares before the increase will be paid the full expectation in the Dwindow, and then when difficulty increased it will once again go inside the window and have more expected reward. And, like the previous case, shares submitted just before the difficulty change will be rewarded similarly to shares submitted after it. Another incorrect implementation is to pay all shares in a window given in units of time (sometimes called PPLNM or PPLNH). In addition to the problems above, it has a problem common to all reward systems that use time as a factor, which is that it is more profitable to mine when the current hashrate is higher than the average. The correct method is as follows.1. Choose a parameter X, which represents multiples of D to include in the window when difficulty is static. X=2 is a good choice. 2. When a share is submitted, assign to it a score of 1/D, where D is the difficulty at the time the share is submitted. 3. When a block is found, pay (sB)/X for the last share (the one before the winning share), where s is the share's score and B is the block reward. Continue backwards, paying each share based on its score, until you reach a share which brings the total score of the shares counted above X. Pay that share the amount (sB)/(tX) * min (r,t), where r is the score required to bring the total to exactly X and t is the score of the winning share. Don't pay any older shares. 4. If the pool has just started, and a block is found before there are shares totaling a score of X, there will be leftover rewards and it should be decided what to do with them. It doesn't matter much, but I recommend that the operator keeps them (in a macroscopic view, if the pool ever changes, this is compensation for the funds needed to cash participants out). Other options include donating to charity, or distributing among the miners. The expected payout for a share with score s, so that the total score of it and all younger shares is Y, is sB * Max (0, 1Y/X). It follows that the expected payout per share when it is submitted is always B/D. The variance in the payout per share is (pB)^2/X. The average number of shares it takes to receive payment, in multiples of the difficulty, is X/2. Thus X can be chosen to have the desired tradeoff between variance and maturity time, with the invariant being that their product is (1/2)*(pB)^2. Note that for a miner who constitutes a significant portion of the pool, the shares are correlated  if the portion is q, the total steadystate variance can't be lower than q times solo variance. If the parameter X ever needs to be changed (for example, to harness increases in the pool's size to decrease variance without changing maturity in units of time), the scores of all recent shares should be changed so that their new expected remaining payout will be equal to the old one, starting from the youngest share and moving backwards. If X is increased, scores should be decreased. This creates a situation similar to the start of the pool where there could be leftover rewards. If X is decreased, scores should be increased. For some of the older shares, it will be impossible to increase the score to maintain the expected value. In this case they should be "cashed out", with the operator paying from his own funds their expected reward. A variant of this is, instead of using a 01 cutoff, use an exponential decay function. This is equivalent to the double geometric method with o=1. If shares decay by a factor of e every (XD/2) shares, the variance is (pB)^2/X and the maturity time is X/2, just like with 01. The advantage is that the due payment of a miner can be encoded with a single number, his score  there's no need to keep or handle a history of shares. The disadvantages are that it takes longer to receive the reward in full, and that the implementation requires either a logarithmic scale or periodic rescaling. Another variant is to use a linear decay function. This achieves a better variancematurity tradeoff invariant, (4/9)*(pB)^2. However, it is probably harder to implement and understand. A substantially different variant is to pay for every share at most once. If, when going backwards in the list of shares, we encounter some that were already paid, we skip them and move on to older shares. X needs to be less than 1 to make sure that eventually we will have enough unpaid shares to draw on. I'm not sure what's the correct way to handle difficulty changes with this variant. Edit: Fixed an error in the description of the block payment.





Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.



Sukrim
Legendary
Offline
Activity: 2408
Merit: 1002


August 29, 2011, 11:20:08 AM 

Something that I'd be interested in and where I'd really love to know if it's possible:
Can you let your users choose N (in multiples of D) individually?
Let's say I have a miner that wants to have payouts as fast as possible and be able to cash out and leave the pool quickly at any time  so he chooses N = 0.5*D Another one really loved the idea of prop that every share gets paid at least something and wants to be paid something at every (or nearly every) share, so he chooses N=10*D
Is it possible to pay these users their fair share without enabling them to hop the pool by creating a few workers witrh different Ns and choosing the optimal(?) one?
If there is a scoring system for this (and I suspect there is), users then could "tune" the pool payouts + variance to their individual needs. If you first had N=1 and then set it to N=10, of course you'd only apply this to shares submitted afterwards, not to past shares...

https://www.coinlend.org < automated lending at various exchanges. No fees(!). Mail me at Bitmessage: BMBbiHiVv5qh858ULsyRDtpRrG9WjXN3xf



Meni Rosenfeld
Donator
Legendary
Offline
Activity: 2044
Merit: 1000


August 29, 2011, 12:05:29 PM 

Something that I'd be interested in and where I'd really love to know if it's possible:
Can you let your users choose N (in multiples of D) individually?
Let's say I have a miner that wants to have payouts as fast as possible and be able to cash out and leave the pool quickly at any time  so he chooses N = 0.5*D Another one really loved the idea of prop that every share gets paid at least something and wants to be paid something at every (or nearly every) share, so he chooses N=10*D
Is it possible to pay these users their fair share without enabling them to hop the pool by creating a few workers witrh different Ns and choosing the optimal(?) one?
If there is a scoring system for this (and I suspect there is), users then could "tune" the pool payouts + variance to their individual needs. If you first had N=1 and then set it to N=10, of course you'd only apply this to shares submitted afterwards, not to past shares...
Yes, this is possible. It creates some variance for the operator, but if the pool's composition doesn't change much it's fairly small. Basically, when you go backwards in the list of shares, you pay each share (sB/X) if the total score so far is less than X, where X is the value specific for this share. For participants it doesn't matter at all that others use a different X, because their own payments are exactly like in uniform PPLNS. For the operator it can matter, because there's no guarantee that the total paid is equal to the block reward, but longterm it will average out and I don't think the variance will be much of a problem. This is consistent with some ideas I have for moving away from traditional reward systems and using a more general "futures market" for pool shares. Instead of distributing block rewards, the operator keeps block rewards but allows miners to trade shares for "bets" on blocks found in the future. This way there's no fundamental need for different miners to take the same bets. If the bets conform to one of the known reward systems, the system will reduce to them, and if the bets are offered in a way that the total obligation per block is equal to the block reward, you have 0 operator variance. And these contracts could be traded on an exchange, so investors who are not riskaverse and not mining themselves, can trade instant money for a contract that will have a higher eventual expected return. This will also allow miners to get cheap PPS. But I'm getting ahead of myself... In the more immediate future, you can have a system where a miner can configure in the pool's website what reward system and parameters he wants to use, and get a quote for the fee the operator demands to compensate for the induced variance.




asher2
Newbie
Offline
Activity: 39
Merit: 0


August 30, 2011, 04:33:23 AM 

Allowing users to change the N value themselves is a terrible idea for pool operators. Anyone implementing this please let me know though




c_k
Donator
Full Member
Offline
Activity: 242
Merit: 100


August 30, 2011, 05:10:39 AM 

However, if implemented incorrectly, it is possible to hop based on imminent difficulty changes. I wonder what the real world implications of this are  roughly: A 10 GH/s user that has an expected reward of 10 BTC can get an extra 0.2 BTC based on the difficulty decreasing 2% ?




Meni Rosenfeld
Donator
Legendary
Offline
Activity: 2044
Merit: 1000


August 30, 2011, 07:20:18 AM 

Allowing users to change the N value themselves is a terrible idea for pool operators. Anyone implementing this please let me know though It won't be too bad if some limitations are imposed, e.g. X must be between 0.1 and 10, and can be changed only once per day. I want to say "and only after the account has already submitted some number of shares", but that may be too inconvenient for honest newcomers. However, if implemented incorrectly, it is possible to hop based on imminent difficulty changes. I wonder what the real world implications of this are  roughly: A 10 GH/s user that has an expected reward of 10 BTC can get an extra 0.2 BTC based on the difficulty decreasing 2% ? Basically yes. If N is a fixed number of shares, D1 is the current difficulty, D2 is the future difficulty, p1=1/D1 and p2=1/D2, then the expectation for a share submitted just before the difficulty change is p2B where the fair reward is p1B, an increase by a factor of D1/D2. For a share submitted N shares before the difficulty change, the fair reward p1B is obtained. For the inbetween period it increases linearly from p1B to p2B, so the total extra that could be obtained (with enough hashrate) is (p2p1)NB/2 per difficulty change. Of course, to exploit it will require a reasonably accurate estimate of the time of difficulty adjustment, which is easier to do if the hashrate of the pool (including hoppers) is small.




iopq


August 31, 2011, 12:29:54 AM 

you need to have a score system for PPLNS where each share is paid based on the current difficulty so when the difficulty changes the score for the new shares changes per share
so that way the rewards are consistent and that means the round where the cutoff changes will have a weird amount of shares actually paid, in fact a single share could be partially paid to fairly reward the corrent N for the old difficulty and for the new difficulty




Meni Rosenfeld
Donator
Legendary
Offline
Activity: 2044
Merit: 1000


August 31, 2011, 06:09:40 AM 

you need to have a score system for PPLNS where each share is paid based on the current difficulty so when the difficulty changes the score for the new shares changes per share
so that way the rewards are consistent and that means the round where the cutoff changes will have a weird amount of shares actually paid, in fact a single share could be partially paid to fairly reward the corrent N for the old difficulty and for the new difficulty
That's what I said in the OP. Are you simply agreeing with it?




iopq


September 01, 2011, 07:31:35 AM 

you need to have a score system for PPLNS where each share is paid based on the current difficulty so when the difficulty changes the score for the new shares changes per share
so that way the rewards are consistent and that means the round where the cutoff changes will have a weird amount of shares actually paid, in fact a single share could be partially paid to fairly reward the corrent N for the old difficulty and for the new difficulty
That's what I said in the OP. Are you simply agreeing with it? this is the tl;dr version of your OP




sirky


September 01, 2011, 10:48:14 AM 

Something that I'd be interested in and where I'd really love to know if it's possible:
Can you let your users choose N (in multiples of D) individually?
Let's say I have a miner that wants to have payouts as fast as possible and be able to cash out and leave the pool quickly at any time  so he chooses N = 0.5*D Another one really loved the idea of prop that every share gets paid at least something and wants to be paid something at every (or nearly every) share, so he chooses N=10*D
Is it possible to pay these users their fair share without enabling them to hop the pool by creating a few workers witrh different Ns and choosing the optimal(?) one?
If there is a scoring system for this (and I suspect there is), users then could "tune" the pool payouts + variance to their individual needs. If you first had N=1 and then set it to N=10, of course you'd only apply this to shares submitted afterwards, not to past shares...
Yes, this is possible. It creates some variance for the operator, but if the pool's composition doesn't change much it's fairly small. Basically, when you go backwards in the list of shares, you pay each share (sB/X) if the total score so far is less than X, where X is the value specific for this share. For participants it doesn't matter at all that others use a different X, because their own payments are exactly like in uniform PPLNS. For the operator it can matter, because there's no guarantee that the total paid is equal to the block reward, but longterm it will average out and I don't think the variance will be much of a problem. This is consistent with some ideas I have for moving away from traditional reward systems and using a more general "futures market" for pool shares. Instead of distributing block rewards, the operator keeps block rewards but allows miners to trade shares for "bets" on blocks found in the future. This way there's no fundamental need for different miners to take the same bets. If the bets conform to one of the known reward systems, the system will reduce to them, and if the bets are offered in a way that the total obligation per block is equal to the block reward, you have 0 operator variance. And these contracts could be traded on an exchange, so investors who are not riskaverse and not mining themselves, can trade instant money for a contract that will have a higher eventual expected return. This will also allow miners to get cheap PPS. But I'm getting ahead of myself... In the more immediate future, you can have a system where a miner can configure in the pool's website what reward system and parameters he wants to use, and get a quote for the fee the operator demands to compensate for the induced variance. If there are 10 pools like this, can't I set them all up to be .1N a day in advance or whatever, mine for a bit at one, and then bump up the N and jump to the next .1N pool? Especially if you allow people to change their N at will, they can just make it float along so that their last batch of mined blocks is always in focus, until they drop it back to the minimum and begin mining again.




Meni Rosenfeld
Donator
Legendary
Offline
Activity: 2044
Merit: 1000


September 01, 2011, 03:14:20 PM 

If there are 10 pools like this, can't I set them all up to be .1N a day in advance or whatever, mine for a bit at one, and then bump up the N and jump to the next .1N pool? Especially if you allow people to change their N at will, they can just make it float along so that their last batch of mined blocks is always in focus, until they drop it back to the minimum and begin mining again.
I'm not sure I understand what you mean, but I think you missed the point that you can configure what X will be for the future shares you submit to the pool, not for past shares. Although there's no problem with changing X for past shares, as long as they're rescaled to maintain the same expected payout.




sirky


September 01, 2011, 04:12:50 PM 

If there are 10 pools like this, can't I set them all up to be .1N a day in advance or whatever, mine for a bit at one, and then bump up the N and jump to the next .1N pool? Especially if you allow people to change their N at will, they can just make it float along so that their last batch of mined blocks is always in focus, until they drop it back to the minimum and begin mining again.
I'm not sure I understand what you mean, but I think you missed the point that you can configure what X will be for the future shares you submit to the pool, not for past shares. Although there's no problem with changing X for past shares, as long as they're rescaled to maintain the same expected payout. You are right, I misunderstood. Thanks!




DrHaribo
Legendary
Offline
Activity: 2520
Merit: 1020
Bitminter.com Operator


September 02, 2011, 03:34:15 PM 

I am currently considering this variation for my pool: PPLNS=Pay Per Last N Shifts D = difficulty N = number of shifts eligible for payment D2S = difficulty to shift ratio Number of shares that go in a shift = D/D2S Stored for each shift: Number of shares for each user When receiving any proof of work: Increment the user's number of shares in the current shift Unless the total number of shares in the shift exceeds D/D2S, in that case start a new shift and mark the old as completed When receiving a generating proof of work: For the last N completed shifts, weight=total_shares_in_shift Distribute income proportionally among shifts according to their weight, and proportionally within shifts according to how many shares each user has. As long as shifts are weighted, it might work out ok to pay for last N hours as well. Just start new shifts every hour instead of when the current shift reaches a certain size. Benefits:  Fairly simple; easier to understand and to audit.
 More transparent; easier to display all the data from which a user's payment was calculated.
 Much lower storage and processing costs for server. Sideeffect: easier to show live statistics and future payment estimates.
To avoid the time around difficulty changes from being hoppable it may be necessary to weight shifts also by their difficulty. Any thoughts?




Meni Rosenfeld
Donator
Legendary
Offline
Activity: 2044
Merit: 1000


September 03, 2011, 06:07:24 PM 

I am currently considering this variation for my pool: PPLNS=Pay Per Last N Shifts
This is less resourceintensive than shiftless 01 PPLNS, but I don't find it simpler. I think exponential PPLNS is simplest in both presentation and resources (since you only need to keep track of one number per worker). For a full description of this, take the double geometric method with o=1. Note that for display purposes the relevant quantity is S/s. I'd base shifts on a specified quantity of score. Suppose X=0.1, if a shift starts at D=1M, 50K shares are submitted, then D increases to 2M and 100K more shares are submitted, this completes a shift (50K/1M + 100K/2M = 0.1). It's ok to change X between shifts and to base shifts on units of time, as long as you don't end shifts based on number of blocks found. Any block found in a shift of size X, gives a reward of (B*S)/(N*X) to any worker whose total score in the previous N shifts is S. The idea is: If I submit a share, I get score p which qualifies me to an expected reward of pB. For each of the next N shifts, the expected number of blocks found is X (where X is specific to that shift), so if I'm rewarded (B*p)/(N*X) per block that's on average pB/N for any future shift, and since there are N the average reward is pB.




Jine


February 25, 2012, 09:18:15 PM 

Doing a bit of bumping right now, but i think it's appropriate. We at Bitlc.net is changing from Propotional to PPLNS as soon as possible, but first I want to clarify something. I'm struggling to understand your algorithm in the first post, i don't really get how X=2 results in payments for difficulty*2 (?) This is my algorithm (in PHP), more or less: <?php $total = 0; $N = 0;
$X = 2; // Magic number $D = 1376302.267886; // Curr difficulty $s = 1/$D; // Share score $B = 50; // Block reward
$reward = ($s * $B) / $X; // per share
while($X > $total) { $N++; // Increment the share count, just to check how many shares that actually would be paid. $total = $total + $reward; // Total score } Results in:$total = 2.0000148689956; // Total score $N = 110105; // So 110105 shares was paid(?) I've seen that people are using diff/2 (N = 688151 shares) and diff*2 (N = 2752604 shares) What is it that i don't understand? Why does my code above results in N = 110105? :/ Thanks for any help that i can get.  Regards, Jim EDIT: Oh crap, while writing this i just realized that i might have read wrong in the original post. Each share is worth $s  NOT $reward ? Please confirm if this is the case

Previous founder of Bit LC Inc.  I've always loved the idea of bitcoin.



Meni Rosenfeld
Donator
Legendary
Offline
Activity: 2044
Merit: 1000


February 25, 2012, 09:35:16 PM 

You need to distinguish score (which in some other places I call "units") from reward. Score is s=1/D and is the thing that should total X. (from the OP, "a score of 1/D... until you reach a share which brings the total score of the shares counted above X".) Reward is what you pay for each included share, and is s*B/X.
I hope there are some pieces to the computation you're not showing here, because some things are missing with respect to the accurate variant. In particular, you need D and B to be the values at the time the share was submitted rather than at the time payments are handed out (the OP clarifies this for D, but was written before I realized this is also true for B), and for absolute accuracy you need to proportionally discount the reward for the earliest share (the one that brings the total score to X).




roy7


April 22, 2013, 08:28:43 PM 

A substantially different variant is to pay for every share at most once. If, when going backwards in the list of shares, we encounter some that were already paid, we skip them and move on to older shares. X needs to be less than 1 to make sure that eventually we will have enough unpaid shares to draw on. I'm not sure what's the correct way to handle difficulty changes with this variant. Is this in effect what CPPSRB does? It pays all shares only once, starting with the most recent and going back as far as needed to pay out the full block (or until every share is paid). Your % of the block reward is the sum of all of your d/D since last block, where the total shares we're paying is = block difficulty of the block we just found. Your comment on X being less than 1 to avoid an endless backlog is what caught my attention. Is the way I should think of that, if X is .99 then miners are making 99% of the reward and 1% is being kept back to pay shares older than the miners normally being paid. In effect, like a pool charging a 1% fee but paying that fee to pastdue shares instead of it going to the operator?




LukeJr
Legendary
Offline
Activity: 2422
Merit: 1011


April 22, 2013, 08:33:46 PM 

A substantially different variant is to pay for every share at most once. If, when going backwards in the list of shares, we encounter some that were already paid, we skip them and move on to older shares. X needs to be less than 1 to make sure that eventually we will have enough unpaid shares to draw on. I'm not sure what's the correct way to handle difficulty changes with this variant. Is this in effect what CPPSRB does? It pays all shares only once, starting with the most recent and going back as far as needed to pay out the full block (or until every share is paid). Your % of the block reward is the sum of all of your d/D since last block, where the total shares we're paying is = block difficulty of the block we just found. The difference I see, is that if CPPSRB pays off all shares, it saves the excess for the next block.




Meni Rosenfeld
Donator
Legendary
Offline
Activity: 2044
Merit: 1000


April 23, 2013, 10:16:21 AM 

A substantially different variant is to pay for every share at most once. If, when going backwards in the list of shares, we encounter some that were already paid, we skip them and move on to older shares. X needs to be less than 1 to make sure that eventually we will have enough unpaid shares to draw on. I'm not sure what's the correct way to handle difficulty changes with this variant. In effect, like a pool charging a 1% fee but paying that fee to pastdue shares instead of it going to the operator? Not really. If for example X=0.5 then still normally a block will be paid out 100% to recent miners  each share will be paid twice the PPS rate. But in lucky times when there aren't enough unpaid shares, past miners can be paid. Payment always starts at the last share and continuously moves backward as much as possible, skipping any already paid shares.




roy7


April 23, 2013, 03:26:17 PM 

Not really. If for example X=0.5 then still normally a block will be paid out 100% to recent miners  each share will be paid twice the PPS rate. But in lucky times when there aren't enough unpaid shares, past miners can be paid. An X < 1 will further increase the time to maturity on old shares, won't it? Is there a way in a payoncePPLNS model to avoid an unbounded time to maturity?




