I would like to propose a new score-based payout method for mining pools. It was designed to resist pool-hopping, a form of cheating where a miner only participates at the beginning of a round, when his expected payout is too high compared to his efforts and contribution to the pool. This is of course at the expense of honest participants whose payouts will decrease. This cheat was discussed in
this paper by Raulo.
I claim, and will later supply a proof as time permits, that this method is 100% immune to this attack. The expected payout per share submitted is always the same no matter when it was submitted. Note that this does not purport to resist any other type of attack.
The greatest disadvantage of this method - which is very mild in my opinion - is that it has the counter-intuitive property that the fee collected per block by the pool operator varies depending on the length of the round. In this sense it is a bit similar to the pay-per-share model (in fact, pay-per-share is a special case). It can be shown, under some very reasonable assumptions, that a variable fee must be introduced to make a scoring scheme cheat-proof without reducing it to solo mining.
I had originally planned to discuss this with slush before posting, but he is working on more important things now so I decided to go ahead.
I will first describe the method and then provide some analysis.
Choose parameters f and c, where f determines the fixed portion of the fee, and c determines the variable fee, or "score fee".
Let p = 1/difficulty be the probability that a share will solve a block.
Let r = 1-p+p/c be a decay factor.
When a participant submits a share, his score for the current round increases by r^i, where i is the number of shares already submitted at the time.
At the end of the round, when a block with reward B is found, each participant receives a payout of (1-f)*B*S*(r-1)/r^I, where S is the score accumulated by the participant in this round and I is the total number of shares submitted by all participants in this round. The rest is kept with the pool operator. For this discussion it is assumed that B is constant.
The intuition behind this payout is: The operator first takes a fixed cut of f from the block reward. He distributes the rest among all participants in proportion to their score, where he assigns himself a score of 1/(r-1) = c/(p-p*c) (which is equivalent to submitting infinitely many shares, in the beginning of the round, at the chosen decay rate).
It can be shown that the expected payout per share submitted is exactly (1-c)*(1-f)*p*B, no matter when the share was submitted. For solo mining this would have been p*B.
The fee collected by the operator varies and is less the longer the round is. The expected fee is (c+f-cf)*B per block.
The variance of a participant's payout, per share, is approximately (p*B)^2 / (2c+p). For solo mining this would have been p*B^2. This is a decrease of roughly (1+2c/p) times.
The variance of the operator's fee, per block, is approximately c*B^2/(2-c).
If the value c+f-cf (or roughly c+f), which is the average fee rate, is kept fixed while c increases and f decreases, the variance for the operator is increased and for participants it is decreased. By choosing c=0.001 and making up the rest of the fee with f, a reasonable variance can be achieved for both. As long as f is positive, the operator will never lose money on a round. If the operator chooses to absorb more variance in behalf of the participants, he can let f be negative and push c further, effectively adding his own money to the block reward, which will lead him to lose from especially long rounds. He can even choose f = (-c)/(1-c) and have an expected fee of 0.
In the limit c=0, only the winning share is rewarded and the participants are effectively mining solo (and paying for it, if f>0). In the limit c=1, with f being correspondingly highly negative, this reduces to pay-per-share (note that the approximate variances given above assume c and f are small and so don't apply for this case). c shouldn't be outside the range (0, 1).
If a participant has only a small part of the pool mining rate, the payouts of his submitted shares will be roughly uncorrelated, and his variance scales linearly with the number of shares (this is a good thing, as it means the standard deviation scales by its square root). As a participant's part approaches 100% of the pool rate, his shares will be adjacent and correlated, reducing to effectively mining solo.
I have not addressed in this description the case that the difficulty changes in the middle of the round, but this is solved with a simple tweak I will describe at a later time.
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).
