Pool of Stake: Improved POS to Prevent Multiple Voting

[tnxgrid]

Multiple Voting in POS Cannot be Detected and It Weakens Security

A POS blockchain can be less secure than POW because of multiple voting of some miners - there is a group of miners in POS that does not exist in POW, the selfish or rational miners.  

Most POS system work by selecting one miner stochastically each time to sign and add one block, based the recent blockchain history, a miner’s stake data, and the current time (in seconds).  The probability a miner is selected is proportional to the stake shares of the miner (in most cases stake is the number of coins a miner owns).  In case of a fork, the branch with the most stakes is the winner, which is similar to POW in that the branch with the most hash power wins.

In case of an attack, there are three groups of miners in POS.  One group is the above mentioned selfish miners.  They will vote on any braches they can to optimize reward, since it does not cost much to do so.  The two other groups are the attackers and the honest or altruistic miners.  The attacker will always vote on his own branch and the honest miners will always follow the rules to vote on just the main branch.  The breaking point is when both branches have equal amount of stakes

Attacker% + Selfish Miner% = Honest Miner% + Selfish Miner%   or
Attacker% = Honest Miner%  

also

Honest Miner% + Attacker% + Selfish Miner% = 100%

These give us the stake percentage an attacker needs to control in order to succeed

Attacker% = (100% - Selfish Miner%) / 2

In POW Selfish Miner% = 0, so it takes at least 50%, or majority, to attack the blockchain.  In POS, however, it all depends on the percentage of selfish miners.  It only takes 25% to attack successfully if there are 50% selfish miners.  You can argue that there will not be a high percentage of selfish miners because doing so will destroy the value of their stakes, therefore against their interest, but technically there is nothing in POS that can prevent the selfish miners from existing.  This is the essence of the so called “nothing at stake” attack.  Multiple voting by the selfish miners weakens the security of POS and turns the “51% attack” to less than 51%.

There have been proposals to penalize multiple voting.  The difficulty, however, is that it is easy to multiple vote and avoid being detected.  In case of a fork, for example, a miner with a 10% of total stakes in the system has a probability of 10% to be selected on each branch.   He can sign 1 out 10 blocks on average on each branch.  As shown in Fig. 1, double voting can only be detected if the miner voted on both branches at the same block height.  This only happens with a probability of 10% x 10% = 1%.  In 200 blocks (100 each branch) a selfish miner will gets a chance to double sign 20 of them (10 on each branch) with only 1 block getting detected (overlapped in the 2 branches).  All he needs to do is to not to sign that 1 block and he still gets to sign 19 of them.  He can do even better by spreading his stakes.  For example, ten 1% stakes still get the same 10% probability of double signing 20 blocks out of 200.  The chance of being detected is now reduced to 1% x 1% x 10 = 0.1%.  The hard problem is really how to detect multiple voting, which the current POS fails.


http://intocrypto.com/images/fork.png


Fig. 1.  Multiple voting cannot be detected (it is not against the rules either) if a miner signs blocks in 2 branches at different heights.


Pool of Stake

In order to solve the POS weakness described above and also not to burn valuable resources like POW, we propose a new way of building blockchain.  Like POS intangible stake is used in our system.

• Miners are grouped into multiple stake pools.  A pool is formed by a leading “representative stake” and other stakes joining the pool.  The joining process is like paying one’s stake to the representative so a stake can join only one pool at a time.  Stakes have the rights to leave a pool at any time.  A pool’s stake is the sum of all the stakes joined.
  
• One pool is selected based the recent history (or take turns) to propose transactions to be included in a block.  All pools can sign the proposed transactions using their representative’s private keys to create a block.  The block with the most stakes signed is the winner in a fixed time period (like 10 minutes).  All the pools signed the winning block share the reward coins based the pool’s stake amount.  The proposing pool can get extra reward.  
• To control the total number of pools in the system the number of signatures is capped in one block and the pools with more stakes should be included first.  To make the stakes spread more evenly among the pools the maximum award a pool can get can be capped as well, for example, at maximum of 5% of total coins rewarded for a block.  This way a pool with 10% stake will earn the same amount of coins as a 5% stake pool.  5% will leave the pool since they can earn more reward somewhere else.
• A pool will be disbanded if it is caught double signing on blocks at the same height.  The representative’s stake in the pool is destroyed permanently.  Other stakes can form a new pool or join other pools.
• Like other systems, the blockchain with the most stakes is the consensus.
• Although this is not necessary, a separate cryptocurrency can be introduced into the system to represent shares of stake in the system and the reward coin can be in a different currency.  This way the miner stakes are kept stable and the reward coins can be spent without affecting the stake shares.  The total amount of stakes in the system can be capped.  Once all the stakes are distributed no more new stakes can be issued.  The number of coins rewarded for one block can be fixed forever or based on a target inflation rate.

We name our new system Proof of Representation (POR).  The major differences of POR from POS include 1) Miners can join pools to form a hierarchal structure.  Only pools or stakes with enough shares get a chance to sign blocks.  2) All stakes represented by pools vote at every block height instead of just one or some miners representing minority stakes.  As a result, multiple voting can be detected in our new system.  This is crucial to the security of blockchain without burning valuable physical resources.

POR has some advantages over POW as well.  For details please see http://intocrypto.com/por.pdf

Thoughts?

[Daedelus]

Multiple Voting in POS Cannot be Detected and It Weakens Security

I stopped at this bit. From what I have seen, the research says that the opposite is true.

There is a group called Consensus Research who look into concrete implementation POS algos and they have found that, as the work required to vote on all chains you see grows exponentially over time then restricting nodes to vote on only a single chain weakens security. As it takes less computing power to 'stake grind a better chain' (one with a better cumulative difficulty).

Their research is here: https://bitcointalk.org/index.php?topic=897488.0

I thought I would just start here before trying to look into your idea. I can get help if you have any really hard questions to ask too 

[tnxgrid]

Glad to know there is some work done on PoS modeling and simulation.  I'll take a closer look.  I did some simple simulation myself.

Intuitively it will not work if all nodes vote on all chains even if you can make it scalable.  All chains will have the same accumulated stakes at the end and you won't be able to tell which chain is the winner.  I am proposing a hierarchical node structure to make all stakes participate in voting at every block height, but not all nodes have to vote - this solves lots of PoS/PoW issues including grinding.  There is nothing to grind at all. 

[Daedelus]

I pointed Kushti here, one of the authors of the work. I'll keep watching 

[kushti]

Well, in the first place, PoS currency MUST use some better blockchain quality function than longest chain rule, by using latter it's fundamentally flawed(and majority of known PoS around are flawed. Nxt uses so-called "cumulative difficulty" function, which is more or less okay though it's better to be replaced with more sophisticated option(details will be published later).

In the second place to avoid grinding, mutable values should be excluded from hit calculation(as in Nxt). This creates other problems(e.g. long block delays sometimes, as in Nxt), but safe.

In the third place, double-voting isn't a problem itself. Read our papers please.

In the fourth place, I would like to see any details on pools forming in the decentralized environment & cheating evidence publishing.

[tnxgrid]

In the third place, double-voting isn't a problem itself. Read our papers please.

It is hard to imagine double-voting won't be a problem or N@S attack is of no concern.  Can you give a link?

[tnxgrid]

In the fourth place, I would like to see any details on pools forming in the decentralized environment & cheating evidence publishing.

Pool forming can be based on a few simple rules.  The goal is to limit the total number of pools and make stakes spread evenly among the pools. 1. Multiple pools can sign a block.  2. The maximum number of pool signatures a block can take is capped, for example at 20.  3. The reward coins a pool can get from one block is capped, for example at 5%.  4. The winning block is the one with the most stakes.  The miners can join pools freely and a miner gets his reward from the pool he joined.  Since each miner is after max reward, there will be 20 pools and each pool will have roughly 5% stakes at the end.

With the above rules the 20 pools will sign every block in the blockchain.  In the ideal situation each block gets 100% stake voting.  To prevent double-voting, each pool can only sign only one block at the same height.  In case of a fork, a pool can sign either branch but not both.  If a pool is caught signing 2 blocks at the same height the pool owner's stake is destroyed with the 2 signatures at the same height as evidence.

[kushti]

In the third place, double-voting isn't a problem itself. Read our papers please.

It is hard to imagine double-voting won't be a problem or N@S attack is of no concern.  Can you give a link?

https://github.com/ConsensusResearch/articles-papers/blob/master/multistrategy/multistrategy.pdf and further papers You can run simulations on your machine as well

[kushti]

If a pool is caught signing 2 blocks at the same height the pool owner's stake is destroyed with the 2 signatures at the same height as evidence.

More details on that please The most interesting question is how to caught this in retrospective, e.g. how can I ensure downloading the chain that pool was caught and punished for a reason 100K blocks ago?

[tnxgrid]

More details on that please The most interesting question is how to caught this in retrospective, e.g. how can I ensure downloading the chain that pool was caught and punished for a reason 100K blocks ago?

It can be very simple.  A pool is penalized at the point it is caught - the earliest block where evidence is submitted.  There are 2 possibilities at that point.  1) The pool is still live - the owner's stake is destroyed and the pool is disbanded in this case.  2) The pool is old and does not exist anymore - simply do nothing in this case.  No harm can be done unless the attacking branch (can be long range attack) can get more signatures than the main chain.  The point is that if we can catch and penalize double-voting at the present moment, changing the history later is hard, unless an attacker can compromise most private keys of the pools. 

[kushti]

More details on that please The most interesting question is how to caught this in retrospective, e.g. how can I ensure downloading the chain that pool was caught and punished for a reason 100K blocks ago?

It can be very simple.  A pool is penalized at the point it is caught - the earliest block where evidence is submitted.  There are 2 possibilities at that point.  1) The pool is still live - the owner's stake is destroyed and the pool is disbanded in this case.  2) The pool is old and does not exist anymore - simply do nothing in this case.  No harm can be done unless the attacking branch (can be long range attack) can get more signatures than the main chain.  The point is that if we can catch and penalize double-voting at the present moment, changing the history later is hard, unless an attacker can compromise most private keys of the pools. 

Well, in this case another attacks vector is possible - creating fake evidences. Unfortunately, authors of all proposals like that dont' describe details, so it's hard to propose concrete attack.

And why pools are needed? Evidence could be published against concrete forger. Pools are adding unnecessary centralization imho.

[tnxgrid]

Well, in this case another attacks vector is possible - creating fake evidences. Unfortunately, authors of all proposals like that dont' describe details, so it's hard to propose concrete attack.

It is impossible to create fake evidence - you will need the private key of the pool's owner.  2 digital signatures of the same pool for 2 different blocks at the same block height are the evidence.  The same block height must be digitally signed twice by the pool.  No one can do this other than the pool's owner.

And why pools are needed? Evidence could be published against concrete forger. Pools are adding unnecessary centralization imho.

Do you have details on how to detected and publish evidence against concrete forger?  As I explained in my initial post I don't think it is possible if a forger does not have to sign each and every block.  I have not seen anything concrete so far.  You'll need pooling to put all stakes into each and every block and detect double-voting.

[kushti]

Well, in this case another attacks vector is possible - creating fake evidences. Unfortunately, authors of all proposals like that dont' describe details, so it's hard to propose concrete attack.

It is impossible to create fake evidence - you will need the private key of the pool's owner.  2 digital signatures of the same pool for 2 different blocks at the same block height are the evidence.  The same block height must be digitally signed twice by the pool.  No one can do this other than the pool's owner.

Private key is not needed sometimes. Evidence is just some bytes + signature. So attacker is going to find any signed byte sequence of needed length  in the history  to re-publish it as "evidence". Ok, bytes are height+hash(as in Tendermint paper), so height could be checked, so not every message is appropriate. But you can't verify hash.

But okay, that's not a pools-specific issue. Problems I see with pools:
1. Blockchain bloat with mining rules inclusion
2. Even harder to make SPV client(no SPV is possible for PoS of today , but there're some proposals e.g. https://github.com/billlwhite/ledgertheory ).
3. Ok, we'll get 2-3 pools signing all the blocks. It would be centralized as hell system. What's the decentralization incentive?

[tnxgrid]

Private key is not needed sometimes. Evidence is just some bytes + signature. So attacker is going to find any signed byte sequence of needed length  in the history  to re-publish it as "evidence". Ok, bytes are height+hash(as in Tendermint paper), so height could be checked, so not every message is appropriate. But you can't verify hash.

In my proposal all the pools will sign each and every block.  All the pool signatures will be included in each block (this is different from Tendermint which only saves hashes of old signatures to save space).  No evidence can be faked as a result.

3. Ok, we'll get 2-3 pools signing all the blocks. It would be centralized as hell system. What's the decentralization incentive?

It is still decentralized.  An individual miner who is not a pool owner can still participate by watching for attacks and leave or join the pools. The miners are just taking different roles.  The system is so designed that when a pool behaves badly the interest of the joining miners will be harmed and this will drive the miners away to other pools.

The purpose of pools is to detect N@S double-voting.  It is not possible to detect double-voting without major stakes in each and every block.  The total number of pools can be controlled - see the details.  I am not sure what is the optimum number of pools but 2-3 pools is definitely not decentralized enough.  The number of pools should be a balance between efficiency (network traffic and block size) and security. POR pools are no different than Bitcoin hash pools.  I don't think Bitcoin hash pools turned it into a centralized system.  Actually Pools will help improve PoS to get more reliable and scalable in transaction volume, as hash rate in Bitcoin get improved.  There is an incentive to become a pool owner.      

[Daedelus]

Bump 


Anyone else anything to add? (though Kushti has been busy so will still chip in, I'd bet)

[tnxgrid]

I just put my simple simulation results together at https://github.com/txngrid/posmodels/blob/master/POS_model.pdf.  Hope it helps understand the current PoS issues and why I am proposing this Pool of Stake solution.  It covers 2 models and here is the summary.

http://intocrypto.com/images/pos_100_90.png

1. A single miner is selected stochastically each time to create a block.  These are the issues with this model if too many miners are multiple voting

• It is difficult to tell which branch is the winner, even if a miner wants to be honest, because there is no clear winner in the short term (a few hundred blocks).
• Blockchain reorganization can happen frequently - each crossover in the above graph can be a reorganiztion.
• Forking happens naturally.

http://intocrypto.com/images/por_100_90.png

2. Multiple miners are selected to sign each and every block.  The issues above are greatly improved but the N@S attack is still an issue.  Still need a way to control double-voting.

[lordoliver]

simple as always:
I just divide my coins into more accounts and stake each of them...

[Daedelus]

@tnxgrid

Talking of modelling, Kushti has started a topic for his "Ultracompact Cryptocurrency Engine for Hackers" known as Scorex > https://bitcointalk.org/index.php?topic=1060567.0

It would be interesting to run your models through this as a comparison. It is based around Nxt and Qora POS (you can switch by just changing a constant, I'm told). Might show up any differences in your approach and lead to more light.

[tnxgrid]

It would be interesting to run your models through this as a comparison. It is based around Nxt and Qora POS (you can switch by just changing a constant, I'm told). Might show up any differences in your approach and lead to more light.

Yes it will be interesting to see what we can learn.  Adding my model may take some work since it is quite different but I'll look.  I'd like to make sure that POR is solid and N@S proof before I start a new coin

[50cent_rapper]

What about Bitshares's and Crypti's DPOS