Pages:
Author

Topic: Pool of Stake: Improved POS to Prevent Multiple Voting (Read 1628 times)

newbie
Activity: 17
Merit: 0
What about Bitshares's and Crypti's DPOS  Huh

There are a couple of differences, if I understand DPOS correctly:

1. A miner needs to trust a delegate in DPOS while a miner joins a stake pool in POR - there is no trust.  A miner can monitor the pool and leave if the pool misbehaves.

2. The major difference is that ONE delegate signs a block at a time in DPOS while ALL pools sign each and every block in POR.  This is critical b/c this allows detection of multiple voting and bad behavior of the pools.  Is there any mechanism in DPOS to defend against N@S?
legendary
Activity: 1344
Merit: 1000
What about Bitshares's and Crypti's DPOS  Huh
newbie
Activity: 17
Merit: 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.

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 Smiley
hero member
Activity: 574
Merit: 500
@tnxgrid

Talking of modelling, Kushti has started a topic for his "Ultracompact Cryptocurrency Engine for Hackers" known as Scorex > https://bitcointalksearch.org/topic/pre-ann-scorex-ultracompact-cryptocurrency-engine-for-hackers-1060567

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.
legendary
Activity: 1666
Merit: 1020
expect(brain).toHaveBeenUsed()
simple as always:
I just divide my coins into more accounts and stake each of them...
newbie
Activity: 17
Merit: 0
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.
hero member
Activity: 574
Merit: 500
Bump  Wink


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

newbie
Activity: 17
Merit: 0
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.      
full member
Activity: 315
Merit: 103
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?
newbie
Activity: 17
Merit: 0
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.
full member
Activity: 315
Merit: 103
More details on that please Smiley 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.

newbie
Activity: 17
Merit: 0
More details on that please Smiley 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. 
full member
Activity: 315
Merit: 103
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 Smiley 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?
full member
Activity: 315
Merit: 103
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 Smiley You can run simulations on your machine as well
newbie
Activity: 17
Merit: 0
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.
newbie
Activity: 17
Merit: 0
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?
full member
Activity: 315
Merit: 103
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.
hero member
Activity: 574
Merit: 500
I pointed Kushti here, one of the authors of the work. I'll keep watching  Smiley
newbie
Activity: 17
Merit: 0
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. 
hero member
Activity: 574
Merit: 500
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://bitcointalksearch.org/topic/nothing-at-stake-long-range-attack-on-proof-of-stake-consensus-research-897488

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  Cheesy
Pages:
Jump to: