Bitcoin Forum
October 11, 2024, 07:14:08 PM *
News: Latest Bitcoin Core release: 28.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Multi-PPS  (Read 12038 times)
Meni Rosenfeld (OP)
Donator
Legendary
*
Offline Offline

Activity: 2058
Merit: 1054



View Profile WWW
August 25, 2013, 09:21:07 PM
Last edit: June 13, 2014, 11:53:48 AM by Meni Rosenfeld
 #1

tl; dr: Like Mine in multiple pools to reduce variance, but for PPS. I describe a system that allows enjoying the benefits of PPS without the downsides. In particular it can dissolve the problem of concentrating mining within a few pools. I believe this is what pooled mining will look like in the future; it's kind of a big deal.


There is a variety of mining pool reward methods. Among other things, they differ in the trade-off they choose between several performance metrics, or in other words, their position on the reward method triangle. In particular there is a spectrum of the amount of risk taken by the pool operator, from PPLNS where there is no risk to PPS where the risk is completely assumed by the operator. Higher-risk methods allow better variance and maturity time, but the operator will demand more fees to compensate for his risk.

Low-risk methods are popular now, but I don't believe they will stay with us forever. They are more complicated and it's difficult for miners to figure out exactly how much they should get and verify that they get it, which has given rise to a vigilant neighbourhood pool watch. That is fine if the complication is necessary, but as I intend to show, it is not; we can have a well-performing system with the pure simplicity of PPS. Furthermore, low-risk methods were designed with a constant block reward in mind. Going forward, the coinbase reward will be negligible, and the reward will consist completely of transaction fees, which are variable as more transactions are added or placed in published blocks. The methods can be adapted to remain hopping-proof even in this scenario, but they then no longer pose zero risk for the operator. These methods will look so much like PPS that we may as well just go with PPS.


For understanding the problem that I'd like to solve for PPS, it is illustrative to consider the no-risk methods (such as PPLNS) a bit more. With a choice of parameter, we can determine the trade-off between variance, the difference between what miners get in practice and what they should expect on average, and maturity time, the time it takes until miners get their payments. You can improve one at the cost of the other, but the only way to improve both is to have a bigger pool. A big pool can offer better performance to its miners, causing a "the rich get richer, the poor get poorer" effect - miners will flock towards the biggest pools, making them even bigger and resulting in most of the hashrate concentrated in a few large pools. This is very bad for the Bitcoin network health, as it makes it easier to maliciously obtain majority hashrate to attack the network with double spends, transaction denial of service and so on.

I have offered a solution to this in Mine in multiple pools to reduce variance - mining with several pools simultaneously, splitting your hashrate in proportion to the size of each pool. This allows enjoying performance equivalent to a pool of the combined size of all pools, which is better than any single pool, however large; and the macroscopic effect of pursuing the best performance is maintaining the current size distribution, so pools can compete on their fundamental merits and small pools are still attractive.

But as mentioned, I don't believe PPLNS is long for this world, and a similar problem exists for PPS which this doesn't solve. In Analysis of Bitcoin Pooled Mining Reward Systems (appendix "Safety nets for PPS pools"), I analyzed the requirements for a PPS pool to minimize its chance of bankruptcy. For every share submitted to a pool, there is a chance of p to find a block, in which case the pool gets a block reward of B; this means the expectation of the pool's reward per share is pB, and the variance is pB^2. We will denote the ratio between variance and expectation by t; in this case t=B. I have shown that the probability of bankruptcy is exp (-2fR/t), where f is the pool's fee and R is the pool's reserve. This means that to function normally (and without exhorbitant fees) the pool must have a fairly large reserve - agents without sufficient capital are out of this game.

Another way to look at this, different from probabilities of bankruptcy, is considering the expectation of a utility function logarithmic in net worth. If the pool's current net worth is R, then its gain from a reward of expectation E and variance V is roughly E-V/R. The variance creates an additional cost which the pool must compensate with a fee. The minimal fee must satisfy fE=V/R, or f = (V/E)/R = t/R. Bigger pools, owned by an agent with a higher net worth, are less sensitive to risk and can afford lower fees, again pushing out smaller agents.

Having miners split their hashrate among several PPS pools is completely useless for combating this. For every share the pool does get, the expected reward is still pB and the variance is still pB^2, meaning f = B/R, which is still high unless R is large. Changing the share difficulty also has no effect.


To explain my proposed solution, it is necessary to understand the concept of smart miners, also known as split pools. In traditional pools, the pool serves two roles, a network node that builds blocks and assigns work, and an insurance agent that reduces the variance of miners.

However, these two agents needn't be the same. A smart miner contacts separately a node that assigns work, and an insurance agent to smooth out payments. (I will refer to such insurance agents as "pools" as they are the more important component of traditional pools.) The pool gives the miner a Bitcoin address to which it wishes to collect block rewards. The node builds a block with all transactions but the generation transaction, and gives the miner a block header (without Merkle root and nonce) and a "complement branch", a set of hashes (the number of which is the depth of the tree, logarithmic in number of transactions) which, combined with the generation transaction, leads to a Merkle branch going all the way to the root. The miner builds a generation transaction (with output going to the pool's address) and calculates the root; he then hashes with different nonces. If he finds a hash matching the share difficulty, he submits the Merkle branch and the header to the pool; if he finds a hash matching the block difficulty, he also submits it to the node to build a complete block and broadcast it.

For every share the miner submits to the pool, he is rewarded just like in traditional pools. The Merkle branch proves that he has done work which has probability p to result in a block giving the pool B, just like with any other pool. The node doesn't need to be big, just enough to be able to run a network node, so there can be many such nodes offering their services.

It can be asked, how does the pool know that the complete block which credits it will be broadcast if found, or that "the rest of the block" even exists and it is not just a random set of hashes. It doesn't; but this is no different than the current situation with block withholding attacks. The miner can't fake work or reuse work, so he has incentive to lie only in some edge cases; the node will typically be involved in finding several such blocks over its career (unlike a miner which might never find a block in his lifetime), so it can demonstrate its trustworthiness in actually building blocks and broadcasting them. There will always be some small percentage of withholding, but it can be assessed over time and be accounted for in fees.


So we've separated pools from building blocks, and in the case of PPS, the pool will pay out (1-f)pB for every share it gets, as it gives it a probability of p to get a reward of B. The problem still remains, how to reduce the risk of the pool. And the solution is simply to let the miner credit several different pools in his generation transaction. He collects addresses from several pools, and in the generation transaction he builds, he pays out b1 to pool1 1, b2 to pool 2 and so on, for a total of B. When he finds a share, he submits it to all pools; a pool that sees that it was credited with b, will pay him pb.

And here's the crux: A share has a probability of p to reward the pool with b, so the expected reward is pb and the variance is pb^2. The ratio is t=b, and since b<B, the ratio is better than before. If we have n pools, each with a net worth of R, with the naive method each would demand a fee of t/R = B/R. but if the miner splits the transaction between the pools, each has a ratio of b = B/n, meaning it is satisfied with a fee of t/R = B/(nR), an improvement by a factor of n.

More generally, PPS pools have traditionally taken a fee as a fraction of the expected gain, because there was no way to decouple it from the variance. But now we can, so the fee policy should be different. The value of a share to the pool is pb-pb^2/R, so that's exactly what it will pay for it - the fee will be pb^2/R. (I'm disregarding fees for the service itself, which should be quite low and are separate). This is the recommendation based on the pool's net worth, but of course the pool can choose a value of R how it sees fit regardless of what it considers its "net worth". Each pool will publish its fee policy; if there are pools of size R1, R2, ..., the miner can split the reward b1, b2, ... for a total fee of pb1^2/R1 + pb2^2/R2 + ... . It can be shown that the minimal fee is obtained when each bi is proportional to Ri, and then the total fee will be pB^2/(R1+R2+...), just like mining with a single huge pool with reserve equal to the total of all reserves.

And again, this allows every pool, however small, to participate; it will simply obtain a smaller portion of each block reward, so it doesn't get more risk than it can handle. There can come a point where a pool is so small that considering it isn't worth the resource cost of broadcasting messages; however, technology advancements will help push that limit. The total fee for a pool will likely have 3 components - risk fee, service fee and resource fee (proportional to b^2, b and 1 respectively).

And of course, all these negotiations between miner, pools and node are done in software, which can also track the number of found shares and easily compare the reward it should get with the reward in practice. The miner just plugs and plays, and can easily verify the results.

I used to call this arrangement by a variety of names, but I will now simply refer to it as "Multi-PPS".


Trivia: I do my best thinking while traveling, apparently. I invented DGM while sitting in a train. I invented multi-PPS while sitting in an airplane, thinking about the vision I wanted to present for the future of pooled mining in my talk, and realizing it was very different from what I originally thought. And the inspiration to write this down now, after 3 months of procrastination, also came while sitting in a train.

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
crazyates
Legendary
*
Offline Offline

Activity: 952
Merit: 1000



View Profile
August 26, 2013, 01:48:05 AM
 #2

I have a few questions, so please bear with me:

First of all, am I reading this right that a block can have more than one payout address? Rather than one pool getting all 25BTC, a simple example would be 5 pools getting 5 freshly minted BTC each, directly credited by the block generation and not credited to one pool and then distributed?

Second, rather than current pools that act as a portal for miners and a bitcoind for approving transactions, you would have a bitcoind node, and a miner portal that's really a relay server. Each miner relay would be verifying that all incoming shares are properly crediting all bitcoind nodes that have been previously set up by the relay.

Third, what happens when the difficulty goes beyond 100x what it is today? Most PPS for diff1 shares are going to be below 8 decimal places. I'm assuming pools (bitcoind or relays) would need to keep track of things in more precise digits?

Fourth, who pays the miners? Do the pools pay the miners? Or do the pools pay the relay node and the node pays the miners?

Fifth, how does this offer more protection from a block withholding attack? Any miner not submitting a block solver to a relay node but still getting credit for his shares doesn't seem all that different from today's PPS block withholding.

I read through your post, but I have a feeling I didn't quite understand everything 100%. Just trying to get a feel for what you proposed, and how this affects the average miner. I'm actually very curious about this, and thing it sounds pretty interesting! Thanks.

Tips? 1crazy8pMqgwJ7tX7ZPZmyPwFbc6xZKM9
Previous Trade History - Sale Thread
Meni Rosenfeld (OP)
Donator
Legendary
*
Offline Offline

Activity: 2058
Merit: 1054



View Profile WWW
August 26, 2013, 05:27:51 AM
Last edit: August 26, 2013, 06:07:33 AM by Meni Rosenfeld
 #3

First of all, am I reading this right that a block can have more than one payout address? Rather than one pool getting all 25BTC, a simple example would be 5 pools getting 5 freshly minted BTC each, directly credited by the block generation and not credited to one pool and then distributed?
Yes. The generation transaction can have as many outputs as it wants, as longs as their total value is at most new coins + tx fees. Some pools already make use of this fact, such as p2pool and eligius.

Second, rather than current pools that act as a portal for miners and a bitcoind for approving transactions, you would have a bitcoind node, and a miner portal that's really a relay server. Each miner relay would be verifying that all incoming shares are properly crediting all bitcoind nodes that have been previously set up by the relay.
This doesn't sound right. I don't think the relay server exists. The miner's client software independently contacts the bitcoind node, and the various pools. A relay server that sits between the miner and pools (assuming that's what you meant) would just add latency and centralization.

Third, what happens when the difficulty goes beyond 100x what it is today? Most PPS for diff1 shares are going to be below 8 decimal places. I'm assuming pools (bitcoind or relays) would need to keep track of things in more precise digits?
You can use shares of difficulty other than 1 (which will be needed to reduce the load of both miners and pools). If need be, the pools can also track payouts in more precision and pay in batches.

Fourth, who pays the miners? Do the pools pay the miners? Or do the pools pay the relay node and the node pays the miners?
The pools pay the miners. The way it could work is that on initial contact, the miner sends the pool his own payment address and his desired share difficulty, and the pool sends him an address which is matched in its database with these particular settings. As the pool gets shares which credit its address, it increases the balance of the miner's address, and when it is large enough it settles by sending a Bitcoin transaction to the miner's address.

Fifth, how does this offer more protection from a block withholding attack? Any miner not submitting a block solver to a relay node but still getting credit for his shares doesn't seem all that different from today's PPS block withholding.
It doesn't offer more protection, it offers just as much. But unlike block variance, which affects smaller pools more profoundly, block withholding affects pools in the same way so it is not a barrier of entry. If statistics show that 1% of blocks are withheld, pools can just add a fee of 1% of the expected value to compensate.

Actually, it does offer more protection in a few ways:
1. A pool can expect a wider range of miners (since all miners mine in all pools), so there will be less variability in withholding.
2. Pools will be smaller and more numerous, so there will be less incentive to do sabotage. Targeted sabotage will not work because the pool will demand a huge fee for a concentrated reward, and sabotaging all pools simultaneously isn't effective.
3. PPS is immune to lie in wait, so there is no direct profit from withholding.

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
Meni Rosenfeld (OP)
Donator
Legendary
*
Offline Offline

Activity: 2058
Merit: 1054



View Profile WWW
August 26, 2013, 12:01:01 PM
 #4

I've realized a potential vulnerability, not with multi-PPS specifically, but in general with smart miners in the variable block reward era.

Without having the entire block data, the pool cannot verify what is the total amount of transaction fees due for this block. The miner can create a generation transaction which does not correspond to any valid block, with a bogus quantity of transaction fees, to pump up the payout he gets from the pools.

To solve this, the node should digitally sign a message per block containing a complement branch, incomplete block header and total tx fees. (The same incomplete block can be used for all miners, which could simplify things.) The miner will deliver this signature to the pools together with shares, and the pool will trust the reputation of the node. The pool can also quiz the node to see that the underlying block exists.

The simplest method to quiz is to request the entire block. This however has a big communication and verification overhead. There are also some relatively simple statistical techniques that queries pieces of the block and has a good chance to detect significant cheating.

There may be more advanced statistical and cryptographic techniques to do the verification; for example, a technique called "Succinct computational integrity and privacy" allows proving that data with certain features exist by providing a short, easily verifiable authentication message. This way the node can prove the block it constructed exists, without much resource costs for the miner and pools.

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
iddo
Sr. Member
****
Offline Offline

Activity: 360
Merit: 251


View Profile
May 28, 2014, 04:19:13 AM
 #5

Two comments:

1) So far this proposal doesn't explicitly describe how to pay the nodes who construct a block that contains all the transactions minus the coinbase, for their service. If it should be some sort of a subscription service where the PoW miner pays in advance, then this adds to the overhead because the miner has to identify himself when requesting a new block, and there's room for abuse/freeloading i.e. one miner pays and then shares his account (login/password) with other miners, or shares the constructed block (minus the coinbase) with other miners. Another option is that it'd be some kind of an honor system, where miners donate some portion of their profits to the nodes who provide this service, but I'm not sure if that'd be sustainable.

2) In an old thread the issue of performance was discussed, slush's reply (link) is rather pessimistic. He considers the straightforward setting where the miner submits the entire block to the pool, unlike your followup post about quizzing or using SNARK/SCIP as an improvement. Though unlike the old thread, with multi-PPS there's the added complexity of interacting with separate nodes that construct blocks for the miners, and this should also be taken into account since the miner might request several such blocks during the average 10 minutes interval, as new transactions are being broadcasted over the network. I think that BIP0022 (which probably isn't being used by anyone yet?) was inspired in part by that old thread, so I'm not sure what should be the current assessment regarding the severity of the performance issues.
Meni Rosenfeld (OP)
Donator
Legendary
*
Offline Offline

Activity: 2058
Merit: 1054



View Profile WWW
May 28, 2014, 09:36:22 AM
 #6

1) So far this proposal doesn't explicitly describe how to pay the nodes who construct a block that contains all the transactions minus the coinbase, for their service. If it should be some sort of a subscription service where the PoW miner pays in advance, then this adds to the overhead because the miner has to identify himself when requesting a new block, and there's room for abuse/freeloading i.e. one miner pays and then shares his account (login/password) with other miners, or shares the constructed block (minus the coinbase) with other miners. Another option is that it'd be some kind of an honor system, where miners donate some portion of their profits to the nodes who provide this service, but I'm not sure if that'd be sustainable.
I think it's solvable in the following way: The node will require that the miner pays him some fee in the generation transaction. When the miner finds a valid nonce, the node will only release the full block if the miner shows him that the nonce matches a generation transaction paying the required fee. This way the node guarantees a fair share of the revenue enabled by his contribution.

2) In an old thread the issue of performance was discussed, slush's reply (link) is rather pessimistic. He considers the straightforward setting where the miner submits the entire block to the pool, unlike your followup post about quizzing or using SNARK/SCIP as an improvement. Though unlike the old thread, with multi-PPS there's the added complexity of interacting with separate nodes that construct blocks for the miners, and this should also be taken into account since the miner might request several such blocks during the average 10 minutes interval, as new transactions are being broadcasted over the network. I think that BIP0022 (which probably isn't being used by anyone yet?) was inspired in part by that old thread, so I'm not sure what should be the current assessment regarding the severity of the performance issues.
I think slush is simply wrong in that post (either that or remarkably forward-thinking), as he ignores the Merkle tree structure. For the foreseeable future, the mining revenue will consist primarily of newly minted coins - and in this case, protection against directly profitable attacks (though not against sabotage) is easy by sending Merkle branches, without quizzing or advanced methods.

And, statistical quizzing methods do exist, and by the time this is relevant I hope SCIP will be practical.

(Actually GBT and similar methods like Stratum are the norm currently, they're needed to deal with the rapid rate at which ASICs exhaust nonce ranges).

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
iddo
Sr. Member
****
Offline Offline

Activity: 360
Merit: 251


View Profile
May 31, 2014, 01:36:48 AM
Last edit: May 31, 2014, 08:23:23 PM by iddo
 #7

I think it's solvable in the following way: The node will require that the miner pays him some fee in the generation transaction. When the miner finds a valid nonce, the node will only release the full block if the miner shows him that the nonce matches a generation transaction paying the required fee. This way the node guarantees a fair share of the revenue enabled by his contribution.

Actually, there isn't supposed to be anything secret in the data that the node prepared, right? So in the rare occasion that the miner solves the block, he can broadcast it immediately to the network, and then he (or other members of the pool) can collect the transactions that the node used to create the block, and send all these txns to Bitcoin peers so that the solved block would be valid? In fact, the users who created those txns (and other Bitcoin nodes who just wish to see smooth continuation of the blockchain) have an interest to also pitch in and help with making the solved block valid? The only way to avoid this freeloading issue is if the node that created the block will incorporate a "dummy" txn that has never been broadcasted to the network? That might be messy because of the headers-first sync optimization that Bitcoin clients will probably have by default, i.e. while the broadcasted solved block is considered to be a valid candidate by the network, the miner could say to the node that he agrees to pay only half the fee in exchange for releasing the dummy transaction, or other such forms of abusive behavior?

Edit2: Actually I was very much confused, the data is indeed not secret, but I missed the point that the miner only has one branch of the Merkle tree, therefore it should be infeasible to try different permutations with unconfirmed txns, especially if the volume of unconfirmed txns is high (which is one reason why we need multi-PPS in the first place).

The extra round-trips of communication between the node and the miner imply that the current form of centralized pools will have an advantage over multi-PPS, especially if the average blocktime is less than 10 minutes as with Litecoin etc., right? Wouldn't this advantage override the benefits of multi-PPS, meaning that miners will prefer not to use multi-PPS because of this?
Meni Rosenfeld (OP)
Donator
Legendary
*
Offline Offline

Activity: 2058
Merit: 1054



View Profile WWW
May 31, 2014, 10:18:05 PM
 #8

I think it's solvable in the following way: The node will require that the miner pays him some fee in the generation transaction. When the miner finds a valid nonce, the node will only release the full block if the miner shows him that the nonce matches a generation transaction paying the required fee. This way the node guarantees a fair share of the revenue enabled by his contribution.

Actually, there isn't supposed to be anything secret in the data that the node prepared, right? So in the rare occasion that the miner solves the block, he can broadcast it immediately to the network, and then he (or other members of the pool) can collect the transactions that the node used to create the block, and send all these txns to Bitcoin peers so that the solved block would be valid? In fact, the users who created those txns (and other Bitcoin nodes who just wish to see smooth continuation of the blockchain) have an interest to also pitch in and help with making the solved block valid? The only way to avoid this freeloading issue is if the node that created the block will incorporate a "dummy" txn that has never been broadcasted to the network? That might be messy because of the headers-first sync optimization that Bitcoin clients will probably have by default, i.e. while the broadcasted solved block is considered to be a valid candidate by the network, the miner could say to the node that he agrees to pay only half the fee in exchange for releasing the dummy transaction, or other such forms of abusive behavior?

Edit2: Actually I was very much confused, the data is indeed not secret, but I missed the point that the miner only has one branch of the Merkle tree, therefore it should be infeasible to try different permutations with unconfirmed txns, especially if the volume of unconfirmed txns is high (which is one reason why we need multi-PPS in the first place).
Right, as I was reading your comment, my first thought was that even if the miner knows which txs went into the block, there are still 2^n possibly orderings which only the node knows.

The extra round-trips of communication between the node and the miner imply that the current form of centralized pools will have an advantage over multi-PPS, especially if the average blocktime is less than 10 minutes as with Litecoin etc., right? Wouldn't this advantage override the benefits of multi-PPS, meaning that miners will prefer not to use multi-PPS because of this?
I don't think it's a significant overhead, because the data that needs to be communicated is small, and because there will likely be nodes in physical proximity to the miner, so latency shouldn't be high.

Furthermore, the advantage of Multi-PPS is significant, commensurable with several percent of the revenue. For example, if miner-node latency is 0.1s, and time between blocks is 600 s, the lost revenue is 0.017% while the gain is 3%.

This does indeed worsen with faster block times, however this might be solvable with new block graph structures.

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
organofcorti
Donator
Legendary
*
Offline Offline

Activity: 2058
Merit: 1007


Poor impulse control.


View Profile WWW
July 01, 2014, 12:42:57 AM
 #9

Bumping this post due to its current relevance.

Bitcoin network and pool analysis 12QxPHEuxDrs7mCyGSx1iVSozTwtquDB3r
follow @oocBlog for new post notifications
davejh
Full Member
***
Offline Offline

Activity: 136
Merit: 100


View Profile
December 31, 2014, 11:53:36 AM
 #10

I know this is an old post, but I'm curious how you'd plan to solve the problem of actually knowing pool sizes. Given that the only directly observable data is from blocks found then this seems troublesome. It seems like incorrect choices here by large numbers of miners would actually risk leading to runaway increases in hash rates for smaller pools that have good initial luck?
Pages: [1]
  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!