Bitcoin Forum
March 19, 2024, 03:10:18 AM *
News: Latest Bitcoin Core release: 26.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1] 2 3 4 5 6 »  All
  Print  
Author Topic: Analysis of Bitcoin Pooled Mining Reward Systems  (Read 36473 times)
Meni Rosenfeld (OP)
Donator
Legendary
*
Offline Offline

Activity: 2058
Merit: 1054



View Profile WWW
July 29, 2011, 03:56:37 PM
Last edit: September 26, 2013, 08:42:35 PM by Meni Rosenfeld
Merited by ABCbits (21), EFS (12), joniboini (5), suchmoon (4)
 #1

(Updated November 17, 2011)

I have completed my Analysis of Bitcoin Pooled Mining Reward Systems.

This document analyzes the foundations of mining pools and explores the various reward systems in existence, as a resource to anyone who would like to know more about the subject. It includes both discussion and mathematical results, some of which I have already haphazardly posted around the forum.

It is technical, though it is my intention that it will be approachable to everyone. Any feedback is welcome, and there used to be a bounty for helping improve it.

If you're looking for a more concise overview, also available is Summary of mining pool reward systems. There are also slides prepared for the San Jose conference.

Enjoy!


Table of contents:

1 Introduction
1.1 Bitcoin and mining
1.2 Variance of solo mining
1.3 Pooled mining
2 Simple reward systems
2.1 Proportional
2.2 Pay-per-share (PPS)
3 Score-based methods
3.1 Slush's method
3.2 Geometric method
3.3 Pay-per-last-N-shares (PPLNS)
3.4 Score-based methods myths
4 Attempts for risk-free pay-per-share
4.1 Maximum pay-per-share (MPPS)
4.2 Shared maximum pay-per-share (SMPPS)
4.3 Equalized SMPPS (ESMPPS)
5 Advanced methods
5.1 Double geometric method
5.2 General unit-based framework
5.3 PPLNS variants
6 Attack vectors
6.1 Pool-hopping
6.2 Block withholding
7 Nonstandard reward systems
7.1 Shares as a future payment contract
7.2 Variable block rewards
7.3 Hybrid reward methods
7.4 Heterogeneous pools
7.5 Variable difficulty shares
7.6 Proxy mining
7.7 Score cashout
7.8 Score markets
7.9 Streamlined PPS investments
8 Conclusion
A Properties of proportional pools with constant hashrate
B Pool-hopping in proportional pools
C Safety nets for PPS pools
D The hopping immunity theorem
E Properties of the geometric method
F Properties of *MPPS pools
G Hashrate fluctuation pool-hopping

1EofoZNBhWQ3kxfKnvWkhtMns4AivZArhr   |   Who am I?   |   bitcoin-otc WoT
Bitcoil - Exchange bitcoins for ILS (thread)   |   Israel Bitcoin community homepage (thread)
Analysis of Bitcoin Pooled Mining Reward Systems (thread, summary)  |   PureMining - Infinite-term, deterministic mining bond
1710817818
Hero Member
*
Offline Offline

Posts: 1710817818

View Profile Personal Message (Offline)

Ignore
1710817818
Reply with quote  #2

1710817818
Report to moderator
1710817818
Hero Member
*
Offline Offline

Posts: 1710817818

View Profile Personal Message (Offline)

Ignore
1710817818
Reply with quote  #2

1710817818
Report to moderator
1710817818
Hero Member
*
Offline Offline

Posts: 1710817818

View Profile Personal Message (Offline)

Ignore
1710817818
Reply with quote  #2

1710817818
Report to moderator
The Bitcoin network protocol was designed to be extremely flexible. It can be used to create timed transactions, escrow transactions, multi-signature transactions, etc. The current features of the client only hint at what will be possible in the future.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
1710817818
Hero Member
*
Offline Offline

Posts: 1710817818

View Profile Personal Message (Offline)

Ignore
1710817818
Reply with quote  #2

1710817818
Report to moderator
iopq
Hero Member
*****
Offline Offline

Activity: 658
Merit: 500


View Profile
July 29, 2011, 04:21:20 PM
 #2

just write the PPLNS section now, because it is intuitively the easiest to understand hopping-proof method that doesn't penalize or reward pool-hopping since each share has the same chance of making the window (as long as the window crosses round boundaries)
twmz
Hero Member
*****
Offline Offline

Activity: 737
Merit: 500



View Profile
July 29, 2011, 04:26:19 PM
 #3

Looking good so far.  Looking forward to sections 3-5 as those are the the most interesting parts to me.

Was I helpful?  1TwmzX1wBxNF2qtAJRhdKmi2WyLZ5VHRs
WoT, GPG

Bitrated user: ewal.
Jack of Diamonds
Sr. Member
****
Offline Offline

Activity: 252
Merit: 251



View Profile
July 31, 2011, 09:00:05 PM
 #4

Why is this on page 2? Probably the most valuable research paper on Bitcoin since the Satoshi document.

Still, I agree with iopq, PPLNS has a strong future esp. for new startup pools (in fact it might even be the perfect reward model)
would be good if everyone got an in-depth review on it.

1f3gHNoBodYw1LLs3ndY0UanYB1tC0lnsBec4USeYoU9AREaCH34PBeGgAR67fx
btcmonkey
Newbie
*
Offline Offline

Activity: 20
Merit: 0


View Profile
August 01, 2011, 01:30:06 PM
 #5

Excellent write up so far.  Clear and concise.  Technical but easy to understand.  I look forward to reading the rest.

Meni Rosenfeld (OP)
Donator
Legendary
*
Offline Offline

Activity: 2058
Merit: 1054



View Profile WWW
August 01, 2011, 01:55:06 PM
 #6

Thanks for the positive comments. My motivation to work on this is directly related to how useful people consider it. But I have some much bigger things right now so it might take a while.

I agree that PPLNS is a wonderful method and I'll get to it. I need to write the sections in order to get the logical flow right.

1EofoZNBhWQ3kxfKnvWkhtMns4AivZArhr   |   Who am I?   |   bitcoin-otc WoT
Bitcoil - Exchange bitcoins for ILS (thread)   |   Israel Bitcoin community homepage (thread)
Analysis of Bitcoin Pooled Mining Reward Systems (thread, summary)  |   PureMining - Infinite-term, deterministic mining bond
Sukrim
Legendary
*
Offline Offline

Activity: 2618
Merit: 1006


View Profile
August 01, 2011, 04:20:27 PM
 #7

I was discussing a method I'd call "PPLNShifts" via PM a while ago. It would work like this:

To make it easier for pool operators on the database calculations and to allow for potentially huge "N"s, freeze the database in "blocks" of (for example) 500 000 shares. If a block is found, only pay the shares in the last (for example) 5 "shifts" proportionally, which you already have put in a nicer and leaner database format.

|---| means a complete block of X shares
* means a block was found

|---|---|---|---|---|-*

^ these last 5 "shifts" get paid, the "shareholders" in the shift during which the block was found have to hope for another block. It's not hoppable in my opinion, as you cannot benefit from jumping in on lucky "shifts" as they only benefit past shifts.

This makes it also much easier to for example dump all 500 000 getworks + solutions + account id in a csv and put it (seeded with bitTorrent) in a public archive on the pool's website, so anyone can verify and audit all solutions. This should keep a database small enough to still function well, while having all benefits of PPLNS.
Maybe this helps to have PPLNS pools with huge "N"s (I've sometimes seen now in the forum that people think "N" means "current difficulty"... maybe also clarify that N is just a radnom number - if it is "1", it is equal to solo mining) so the "I don't get paid anything on long blocks with PPLNS!!!11112" critics can calm down.

About PPLNS I'd also like to see if it is relevant and changes expectation values that some pools implement an "N" that is dependent on (and changes with) the current difficulty. As far as I understood it, N should be a constant, not a dynamic value that changes every 2 weeks.

https://www.coinlend.org <-- automated lending at various exchanges.
https://www.bitfinex.com <-- Trade BTC for other currencies and vice versa.
twmz
Hero Member
*****
Offline Offline

Activity: 737
Merit: 500



View Profile
August 01, 2011, 04:50:01 PM
 #8

My motivation to work on this is directly related to how useful people consider it.

I think it is extremely useful.  There is a lot of misinformation floating around and having a thorough and transparent analysis of the various methods will help clear the fog.

Was I helpful?  1TwmzX1wBxNF2qtAJRhdKmi2WyLZ5VHRs
WoT, GPG

Bitrated user: ewal.
sirky
Sr. Member
****
Offline Offline

Activity: 404
Merit: 250



View Profile
August 02, 2011, 12:09:26 AM
 #9

I was discussing a method I'd call "PPLNShifts" via PM a while ago. It would work like this:

To make it easier for pool operators on the database calculations and to allow for potentially huge "N"s, freeze the database in "blocks" of (for example) 500 000 shares. If a block is found, only pay the shares in the last (for example) 5 "shifts" proportionally, which you already have put in a nicer and leaner database format.

|---| means a complete block of X shares
* means a block was found

|---|---|---|---|---|-*

^ these last 5 "shifts" get paid, the "shareholders" in the shift during which the block was found have to hope for another block. It's not hoppable in my opinion, as you cannot benefit from jumping in on lucky "shifts" as they only benefit past shifts.

This makes it also much easier to for example dump all 500 000 getworks + solutions + account id in a csv and put it (seeded with bitTorrent) in a public archive on the pool's website, so anyone can verify and audit all solutions. This should keep a database small enough to still function well, while having all benefits of PPLNS.
Maybe this helps to have PPLNS pools with huge "N"s (I've sometimes seen now in the forum that people think "N" means "current difficulty"... maybe also clarify that N is just a radnom number - if it is "1", it is equal to solo mining) so the "I don't get paid anything on long blocks with PPLNS!!!11112" critics can calm down.

About PPLNS I'd also like to see if it is relevant and changes expectation values that some pools implement an "N" that is dependent on (and changes with) the current difficulty. As far as I understood it, N should be a constant, not a dynamic value that changes every 2 weeks.

I am not sure what advantage your system has over traditional PPLNS. I mean, is it really simpler from the database side or from the auditing side? I mean, if you want to have estimates, they would only need to be updated every N, instead of every share, but still, this seems like overkill. Having stats update every minute, or every 5, or something else is probably easier for everyone.

Not paying out the most recently submitted shares seems like it would disincentivize people from joining? After all, they can mine somewhere else where they will be paid right away. Especially at the beginning of an N round, they are going to be theoretically N - current shares in N round + difficulty shares away from being paid. It seems that theoretically you would be getting paid sooner at a pool where the N round was almost over, so you would rather mine there. Especially when you think of small pools compared to the current difficulty. If it takes a really long time just to reach the end of N, you would never mine there since you wouldn't be paid for a long time at minimum. In regular PPLNS, you don't have this 'waiting period', so it makes no difference.

The way Meni and I have discussed N for traditional PPLNS, the N would be a factor of the difficulty, so it wouldn't change. However, since Meni suggested that the payout is score based, with difficulty as a factor, the "N" as you are referring to it would change based on difficulty.

In my opinion, having N only update sparingly (and not having it score based) is much better than a proportional pool, or something like that, but know that it does allow a bit of pool hopping around difficulty changes (you would mine at a fair pool at the end of a difficulty, and at a PPLNS pool at the beginning of a new difficulty). You need score based (which relies on difficulty) to defeat this.
Sukrim
Legendary
*
Offline Offline

Activity: 2618
Merit: 1006


View Profile
August 03, 2011, 12:12:32 PM
 #10

As far as I understood the "difficulty scored N" value, it devaluates shares (a bit) that were submitted during lower difficulty rounds if difficulty changes. This can be done with a static N as well - I don't see the need to change N at all other than to make sure the percentages of getting paid for a share are constant (if you set N to 1 million fixed and difficulty goes up to 10 millions the ration between N and difficulty goes from ~1/2 to 1/10 - meaning you are less likely to be paid for a share - but you get paid proportionally more, once one gets paid).

Any exploitability there (especially since at the end of the 2016 blocks, it's easy to estimate what the next difficulty will be) is bad in my opinion and I fear there IS some exploitation potential left, if N can change.

https://www.coinlend.org <-- automated lending at various exchanges.
https://www.bitfinex.com <-- Trade BTC for other currencies and vice versa.
sirky
Sr. Member
****
Offline Offline

Activity: 404
Merit: 250



View Profile
August 03, 2011, 12:36:59 PM
 #11

As far as I understood the "difficulty scored N" value, it devaluates shares (a bit) that were submitted during lower difficulty rounds if difficulty changes.

You actually need to devalue the shares that are submitted at higher difficulties, not lower ones. Because it's less likely you will find a block at a higher difficulty.

This can be done with a static N as well - I don't see the need to change N at all other than to make sure the percentages of getting paid for a share are constant (if you set N to 1 million fixed and difficulty goes up to 10 millions the ration between N and difficulty goes from ~1/2 to 1/10 - meaning you are less likely to be paid for a share - but you get paid proportionally more, once one gets paid).

Any exploitability there (especially since at the end of the 2016 blocks, it's easy to estimate what the next difficulty will be) is bad in my opinion and I fear there IS some exploitation potential left, if N can change.

There is no way to exploit the score based PPLNS system that Meni suggested. You get paid exactly what you should. What difficulty changes to does not matter, as it will be reflected in the score.

If you have constant N value (where N is shares, and not score), that is where it can be exploited. You wouldn't want to mine at the end of a round if a difficulty jump is coming up in a PPLNS pool that isn't scorebased, because you are going to be underpaid for your efforts.
Sukrim
Legendary
*
Offline Offline

Activity: 2618
Merit: 1006


View Profile
August 03, 2011, 12:58:35 PM
 #12

As far as I understood the "difficulty scored N" value, it devaluates shares (a bit) that were submitted during lower difficulty rounds if difficulty changes.

You actually need to devalue the shares that are submitted at higher difficulties, not lower ones. Because it's less likely you will find a block at a higher difficulty.

Could you paste a link to Meni's suggestion then? I recall lower difficulty being devalueted with the reasoning that the current block (found in the higher diff.) was more difficult to find and this means that shares from a lower diff. are worth less. I could be wrong though... I don't want to say any more until I have read through the suggestion again, but I can't seem to find it.


Oh and on a side note: I'd love to have chapters markings in the document! I guess you're using LaTeX, Meni? Please embed a library to automatically create these, thanks!

https://www.coinlend.org <-- automated lending at various exchanges.
https://www.bitfinex.com <-- Trade BTC for other currencies and vice versa.
sirky
Sr. Member
****
Offline Offline

Activity: 404
Merit: 250



View Profile
August 03, 2011, 01:15:36 PM
 #13

As far as I understood the "difficulty scored N" value, it devaluates shares (a bit) that were submitted during lower difficulty rounds if difficulty changes.

You actually need to devalue the shares that are submitted at higher difficulties, not lower ones. Because it's less likely you will find a block at a higher difficulty.

Could you paste a link to Meni's suggestion then? I recall lower difficulty being devalueted with the reasoning that the current block (found in the higher diff.) was more difficult to find and this means that shares from a lower diff. are worth less. I could be wrong though... I don't want to say any more until I have read through the suggestion again, but I can't seem to find it.


Oh and on a side note: I'd love to have chapters markings in the document! I guess you're using LaTeX, Meni? Please embed a library to automatically create these, thanks!

Your score for each share is 1/difficulty, so a lower difficulty makes for a higher score.
Meni Rosenfeld (OP)
Donator
Legendary
*
Offline Offline

Activity: 2058
Merit: 1054



View Profile WWW
August 03, 2011, 01:54:11 PM
Last edit: August 03, 2011, 02:07:18 PM by Meni Rosenfeld
 #14

I still need to research if score-PPLNS works exactly the way I think. But the idea is as sirky said - each share gets a score of 1/difficulty, and the fixed quantity is the total score. So you can set S=2 which means that the number of shares is twice the difficulty, and if the difficulty changed mid-round you take shares up to a total score of 2.

Could you paste a link to Meni's suggestion then? I recall lower difficulty being devalueted with the reasoning that the current block (found in the higher diff.) was more difficult to find and this means that shares from a lower diff. are worth less. I could be wrong though... I don't want to say any more until I have read through the suggestion again, but I can't seem to find it.
That discussion started here.

Oh and on a side note: I'd love to have chapters markings in the document! I guess you're using LaTeX, Meni? Please embed a library to automatically create these, thanks!
LaTeX indeed. I've uploaded a new version, is this what you wanted?

1EofoZNBhWQ3kxfKnvWkhtMns4AivZArhr   |   Who am I?   |   bitcoin-otc WoT
Bitcoil - Exchange bitcoins for ILS (thread)   |   Israel Bitcoin community homepage (thread)
Analysis of Bitcoin Pooled Mining Reward Systems (thread, summary)  |   PureMining - Infinite-term, deterministic mining bond
Sukrim
Legendary
*
Offline Offline

Activity: 2618
Merit: 1006


View Profile
August 03, 2011, 06:00:36 PM
 #15


As far as I understood the "difficulty scored N" value, it devaluates shares (a bit) that were submitted during lower difficulty rounds if difficulty changes.


You actually need to devalue the shares that are submitted at higher difficulties, not lower ones. Because it's less likely you will find a block at a higher difficulty.

Could you paste a link to Meni's suggestion then? I recall lower difficulty being devalueted with the reasoning that the current block (found in the higher diff.) was more difficult to find and this means that shares from a lower diff. are worth less. I could be wrong though... I don't want to say any more until I have read through the suggestion again, but I can't seem to find it.


Oh and on a side note: I'd love to have chapters markings in the document! I guess you're using LaTeX, Meni? Please embed a library to automatically create these, thanks!

Your score for each share is 1/difficulty, so a lower difficulty makes for a higher score.
A higher score, yes but on the other hand it also lowers the chance to be included in the payout.

Example: dif10 --> diff40, N=difficulty*1

diff10 shares have a score of 1/10, diff40 shares of 1/40.

Once let's say 10 diff40 shares have been submitted, a block is found.
Now we sum up 10/40 from diff40 shares and 7 (0.75 "left") diff10 shares.
The 7 diff10 shares get paid 70% of the block, the 10 diff40 shares get paid 25% and 5% have to be otherwise distributed (10 and 40 are too small numbers for this, however current difficulties still are - but increases are rarely 4-fold). Here you could even use prop. between these 17 shares (maybe also scored with these scores), put it in some kind of jackpot or whatever is fitting to your pool.


This means there are 2 different approaches to PPLNS:
fixed N --> no scoring needed, payout variance changes with difficulty
dynamic N (N is dependent on difficulty) --> scoring needed, payout variance is constant

The biggest issue I see with dynamic N, is that you can not predict how big your active database might get.
Still it might be the preferred method of miners, since you can in-/decrease variance at will at the cost of delayed payouts (it takes longer until you have the full payout in your hands).
Fixed N on the other hand might scare away random miners, as variance is already an issue for them and it only increases with growing difficulty.

In any case I would really recommend to any PPLNS pool operator to give out estimates how much can be earned per share in percentages rather than in BTC (xx% chance of not being paid, yy% chance of being paid once, zz% chance of being paid twice etc.) + a sum below and maybe even an overview how this correlates with real data already submitted. Already earned/pending amounts of course can be in BTC.

https://www.coinlend.org <-- automated lending at various exchanges.
https://www.bitfinex.com <-- Trade BTC for other currencies and vice versa.
sirky
Sr. Member
****
Offline Offline

Activity: 404
Merit: 250



View Profile
August 03, 2011, 07:02:24 PM
 #16


A higher score, yes but on the other hand it also lowers the chance to be included in the payout.

Example: dif10 --> diff40, N=difficulty*1

diff10 shares have a score of 1/10, diff40 shares of 1/40.

Once let's say 10 diff40 shares have been submitted, a block is found.
Now we sum up 10/40 from diff40 shares and 7 (0.75 "left") diff10 shares.
The 7 diff10 shares get paid 70% of the block, the 10 diff40 shares get paid 25% and 5% have to be otherwise distributed (10 and 40 are too small numbers for this, however current difficulties still are - but increases are rarely 4-fold). Here you could even use prop. between these 17 shares (maybe also scored with these scores), put it in some kind of jackpot or whatever is fitting to your pool.


This means there are 2 different approaches to PPLNS:
fixed N --> no scoring needed, payout variance changes with difficulty
dynamic N (N is dependent on difficulty) --> scoring needed, payout variance is constant

The biggest issue I see with dynamic N, is that you can not predict how big your active database might get.
Still it might be the preferred method of miners, since you can in-/decrease variance at will at the cost of delayed payouts (it takes longer until you have the full payout in your hands).
Fixed N on the other hand might scare away random miners, as variance is already an issue for them and it only increases with growing difficulty.

In any case I would really recommend to any PPLNS pool operator to give out estimates how much can be earned per share in percentages rather than in BTC (xx% chance of not being paid, yy% chance of being paid once, zz% chance of being paid twice etc.) + a sum below and maybe even an overview how this correlates with real data already submitted. Already earned/pending amounts of course can be in BTC.

I don't understand what you are saying in the first few paragraphs. But fixed N without scoring invites hoppers. You will not get full value at the end of the difficulty in this pool. So you should hop away. This is because your extra % of finding a block at lower difficulty will not be rewarded at the new difficulty.

Basically, your work should be worth more at a lower difficulty. It isn't in a fixed N system with no scoring.
Sukrim
Legendary
*
Offline Offline

Activity: 2618
Merit: 1006


View Profile
August 03, 2011, 07:16:54 PM
 #17

Ah, now I understood, yes, you're of course 100% correct - scoring is necessary in both scenarios.

I was just mixing the system with p2ppool's PPLNS approach, but there the difficulty of the shares themselves is also dynamic, so they factor in hash rate of the pool+ the network via this value.
In the beginning I gave an example of Meni's PPLNS share scoring, might be a bit confusingly written.

https://www.coinlend.org <-- automated lending at various exchanges.
https://www.bitfinex.com <-- Trade BTC for other currencies and vice versa.
Meni Rosenfeld (OP)
Donator
Legendary
*
Offline Offline

Activity: 2058
Merit: 1054



View Profile WWW
August 03, 2011, 07:22:36 PM
 #18

I was just mixing the system with p2ppool's PPLNS approach, but there the difficulty of the shares themselves is also dynamic, so they factor in hash rate of the pool+ the network via this value.
I think p2pool's method isn't 100% hopping-proof, but I don't understand it well enough to be sure.

In the beginning I gave an example of Meni's PPLNS share scoring, might be a bit confusingly written.
About that example, I wanted to point out that if there's 0.75 score left and the shares are 0.1 each, you use a score of 0.1 for the last 7 and 0.05 for the 8th.


You still need to tell me if the chapter marking are what you were looking for.

1EofoZNBhWQ3kxfKnvWkhtMns4AivZArhr   |   Who am I?   |   bitcoin-otc WoT
Bitcoil - Exchange bitcoins for ILS (thread)   |   Israel Bitcoin community homepage (thread)
Analysis of Bitcoin Pooled Mining Reward Systems (thread, summary)  |   PureMining - Infinite-term, deterministic mining bond
Sukrim
Legendary
*
Offline Offline

Activity: 2618
Merit: 1006


View Profile
August 03, 2011, 09:04:15 PM
 #19

No, that's not how I meant it.

You could include a package like hyperref (http://www.tug.org/applications/hyperref/), this should by default already create clickable references to every chapter + section as well as create a pdf index in the document.

https://www.coinlend.org <-- automated lending at various exchanges.
https://www.bitfinex.com <-- Trade BTC for other currencies and vice versa.
xcooling
Member
**
Offline Offline

Activity: 145
Merit: 10


View Profile
August 03, 2011, 09:27:31 PM
 #20

@Meni Rosenfeld thanks for the excellent research.

Pages: [1] 2 3 4 5 6 »  All
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!