Use multiple pieces of stake for proposing

scravy commented 5 years ago

Proof-of-Stake v3 as adapted from particl uses every spendable coin (utxo) to propose, but not the sum of them. The proposer iterates through every spendable coin, checks according to the kernel protocol whether it can propose using this stake, and does so if possible. When building the block it then includes all spendable coins (up to maxStakeCombine which is a user-settable configuration setting) and uses that to propose.

The chances to propose are proportional to the amount of the spendable coin which is used for staking. They are not adjusted by the sum of all the spendable coins (which would increase the chance) but by just one coin.

The reason for this design is that a block is also signed by the public key of the proposer, that is: The public key that unlocks the stake. In more technical detail: By the public key which is in the witness for vin[1] of the coinstake transaction (vin[0] is the so called meta input which carries the block height, the snapshot hash, and potentially other things). The pieces of stake are not guaranteed to all be unlocked by the same public key, in fact this is quite improbable: The recommendation is to have every transaction sent to a newly generated address, thus all the transactions/coins a wallet can reign over have to be assumed to be unlocked by different public keys).

The reason for signing the block by the public key of the proposer is because otherwise somebody else could include someones stake and include a different set of transactions and – more importantly – could also send the reward to a different address. For example when receiving a block the receiver could just hijack that block, use somebody elses stake, and propose instead. By requiring the block to be signed this is impossible, as the signature can only be created by the proposer holding the private key associated with the public key.

This design has the following implications:

vin[1], spending the stake used to propose, has to have a public key in it's witness and that public key must be crucial to unlock the coin (this might affect the design of the remote staking script also @Nizametdinov)
in order to combine coins that contribute to the chances of proposing these should have the same public key (which, as argued above, is unlikely)

A proposer could still use multiple coins to stake at the same time. The requirement would than be for the block to be signed by each of the public keys which are used to unlock pieces of stake.

@castarco Could you reproduce you're considerations regarding compounding effects with single-coin-staking vs multi-coin-staking as a comment to this issue (I just made up these terms)?

single-coin-staking vs multi-coin-staking is a valid concern. Probability theory tells us that

The probability for A or B is: P(A ∪ B) = P(A) + P(B) if A and B are mutually exclusive and P(A ∪ B) = P(A) + P(B) - P(A ∩ B) if they are not mutually exclusive.
Two events are mutually exclusive if they can not occur at the same time. It is possible though that two coins are eligible at the same time, thus not mutually exclusive. Hence the probability of proposing using two coins is not the same as the probability of proposing using one coin with the same amount as the sum of the two coins (the system is supposed to be designed in such a way that X% of stake should be able to propose X% of times)

kostyantyn commented 5 years ago

@scravy @castarco what if the probability of winning with 1 coin was slightly higher than when splitting it by 2? Then everyone would have an incentive to keep as little coins as possible, and it would be good for the system.

scravy commented 5 years ago

@kostyantyn That is already the case (see last paragraph). That is specifically what this issue tries to combat. I do think it would be valid to resolve this issue by simply saying exactly that -> it's an incentive to reduce your coins (after all this issue is not an issue if you manually zap your coins or if you propose ones and the proposer code already combines your stake).

But you can not always guard against having many outputs and you might not want to pay transaction fees just for zapping. If you have very little stake this difference becomes highly relevant, I guess.

EDIT: The mechanism proposed here would be good for the system and do it automatically as it ups the chances for everyone to zap without fees by proposing

castarco commented 5 years ago

@scravy the explanation is precisely written in your last two points. But this is not a big problem, since the probabilities are very small, hence their product is much smaller and the difference is almost negligible ( P(A ∩ B) = P(A) * P(B) because they're independent events ).

I'm not sure of having correctly understood the whole issue, but I had the impression that the possibility of summing UTXOs to stake was considered, the next paragraph only applies on that case (not if the proposal was only about taking advantage of the block proposal to decrease the number of UTXOs after having proposed): On the other hand, I don't think that using multiple UTXOs at the same time is a good idea at all, because, then... how do we compute the kernel hash? The fact that we can combine multiple stakes opens the door to generate more kernel hashes with different combinations and obtain a probability not linearly correlated to the stake amount (it's true that others could do the same, but then this could create incentives to increase the number of UTXOs... and I don't think we want this). Example, if we have coins A, B, C & D, we could use the following combinations: A, B, C, D, AB, AC, AD, BC, BD, CD, ABC, BCD, ABCD (and that's considering that we enforce a canonical order, if we do not enforce a canonical order, then we have even more combinations).

And, yes, we could see the fact that having bigger/less coins gives higher probabilities of becoming a proposer as an incentive to keep under control the size of the UTXO set. Anyway, there are clear tradeoffs here (privacy, ability to spend part of the owned money, ability to stake with the owned money), and it's perfectly OK, every person should chose whatever is more convenient for her case.

scravy commented 5 years ago

Yes, that is a problem. Being able to basically increase the number of tickets to the lottery by basically trying to propose with every subset (that's exactly what you get with a defined order, right?). This would degrade proposing to a proof-of-work problem. Also one could possibly split the stake to forge a combination of stakeable coins that wins, and that sounds bad enough for me.

This I guess is a bigger problem than having just one coin to use as stake when proposing a block.

I opened this issue as it came up several times and I would like to have it documented and discussed and agreed upon by everyone. I think a very valid outcome would be if the ticket was closed and the current design accepted. I would nevertheless like to keep it open for a while to see more opinions.

Once we have an outcome I might finalize that decision in an ADR.

kostyantyn commented 5 years ago

@scravy I meant more an explicit advantage of having one coin. For instance: kernelhash * amount^1.05. Not sure it’s good though, but it should incentivize keeping as fewer coins as possible.

castarco commented 5 years ago

@kostyantyn I'm not sure about that, that would make much worse the compounding effect, drastically in fact.

Gnappuraz commented 5 years ago

I think the proposed solution looks good.

scravy commented 5 years ago

@Gnappuraz

I think the proposed solution looks good.

I assume you mean this solution:

I think a very valid outcome would be if the ticket was closed and the current design accepted.

Once we have an outcome I might finalize that decision in an ADR.

Where the current design is the one outlined with just one coin contributing to stake/kernel?

Gnappuraz commented 5 years ago

@scravy yes, sorry for not being precise.

Nizametdinov commented 5 years ago

Copying here my messages from slack about splitting and joining coins.

There are two forces at play:

Coin-stake maturity encourages to split coins;
The way to adjust the difficulty for the UTXO value encourages to join coins. When the value of UTXO is large it's better to split it. If UTXOs are small it's better to join them.

It is possible to adjust the difficulty for the value in such a way that splitting coins won't decrease the probability of staking. If the probability of proposing with the 1 UTE is p then the difficulty for the value a can be adjusted to give probability 1 - (1 - p)^a. In this case, splitting UTXOs won't change the probability of proposing. To check it let's calculate the probability of proposing with two coins with the values a and b:

P(proposing | a&b) = P(proposing|a) +P(proposing|b) - P(proposing|a)P(proposing|b) = 
1 - (1 - p)^a + 1 - (1 - p)^b - (1 - (1 - p)^a)(1 - (1 - p)^b) = 
2 - (1 - p)^a - (1 - p)^b - 1 + (1 - p)^a + (1 - p)^b - (1 - p)^a (1 - p)^b =
1 - (1 - p)^(a+b)

Hence, the resulting probability is the same as the probability of proposing with one UTXO with the value a+b.

About implementation: we use the following inequality to choose a proposer:

kernelHash < value * difficulty

to get the aforementioned probability it must be changed to:

p = difficulty / 2^256
kernelHash < (1 - (1 - p)^value) * 2^256

But If we used this formula the best strategy would be to split coins to dust because of coin-stake maturity. So I think we should not use this formula.

scravy commented 5 years ago

So I think we should not use this formula.

I take it that this is a unique form of agreement to the proposal of keeping the proposer as it?

Nizametdinov commented 5 years ago

@scravy yes :)

dtr-org / unit-e

Use multiple pieces of stake for proposing #290