Topic: Nothing at stake robust Pure Proof of stake (Read 5365 times)

@ Ben, research in the the 'Nothing at Stake' assertions has been published >>> https://bitcointalksearch.org/topic/nothing-at-stake-long-range-attack-on-proof-of-stake-consensus-research-897488

Please comment in the thread >>> https://bitcointalksearch.org/topic/nothing-at-stake-long-range-attack-on-proof-of-stake-consensus-research-897488. It would be good if we could get heads together from all aspects of cyrpto in the same place.

Bump to draw attention to updated answer in above post (#44).

Sorry I didn't read this carefully enough. Mea culpa. My previous answer was wrong. I have edited my answer.
In your example, Satoshi x mints on one chain at time x and sends a txn at time x+t on a second chain. So yes, you are correct.
I should have defined the rule as follows:

That should cover all possible cases.
  


 


It is not difficult to track Satoshi serial numbers. Recall that you cannot send txns that use more than one input. Thus, you can only split inputs into two or more outputs. You can never recombine two or more outputs into one input. This implies that we can record the set of satoshi numbers associated with each output using just two numbers.
e.g. This output contains satoshi 10,000,000,000,000,000 (inclusive) up to satoshi 20,000,000,000,000,000 (exclusive).
Whereas before the blockchain would simply write this output contains 10,000,000,000,000,000 satoshis.

You don't actually have to record any new data in the blockchain. Instead, you can derive the data from the blockchain. Just define the output listed first in a txn as containing the lowest numbered satoshis and scan the blockchain.
Even if you recorded the data directly in the blockchain, the extra space required would be tiny.
The added data would be equivalent to writing the amount of sent coins twice instead of once.
That's like an extra 7-8 bytes per txn, almost nothing.

Finally, I included these rules to provide a simplified example. The rules are restrictive and probably not a sensible arrangement. However, the simplified rules define a long-run consensus. There is no use of checkpoints here (outside of agreement on a common genesis block).
 

the incentive to mine multiple chains is not only the payout for finding a block, but the possibility to perform a double spend!

if you give something to everyone, it's the same as doing nothing. Everyone ends up with the same % of the market cap. So this doesn't make much sense.

I'm still not convinced... I have problems with the following:

So if you send and then mint you get blacklisted. But that doesn't cover all the cases. If I get past ownership of coins that never minted, I can use that to mint in a second chain, at least up to the moment were those coins changed ownership. So I used "past input ownership" to create part of a second chain. By jumping thru different past ownerships I can get very close to the present and accumulate more work in my chain to the point that I might not even need current ownership.

you say "this satoshi" however there are no satoshis, only ins and outs. You can have colored coins and forbid loss of color, and that would be ok, but unless you color every satoshi (which is not practical), I don't see how you could match one satoshi from one chain to one in another chain. Colored coins can track coins in one chain, but when you have 2 competing forks, it's not that straightforward

I have an idea about changing they way the fees work in a pure POS currency.

Could you smooth the amount of fees generated over time alongside Proof of Stake as a low curve over a long medium of time such as a couple weeks? The way I see this working is that it would create a type of floating number which is the difference between the expected inflation and it's actual inflation and could be used to check past work through checks of the oldest, most trusted nodes? I feel like this kind of stuff will be some of the bigger changes to Proof of Stake, because then every block gets paid a minimum amount of fees depending on the amount of volume in a period. Make the whole general consensus that either you are supporting it's security or you are losing a small amount per year. Say you have lower inflation but higher fees then all nodes would be incentivized to claim their blocks and support consensus.

Thanks gatra. That about covers my worries for long range attacks.

Thinking about the internal chain consensus rules, maybe a different approach might produce some new ideas.

It seems the 'issue' is that a rational miner will try to mine multiple chains, not just because he can, but more importantly because he might make more money that  way.

Why not remove that incentive altogether instead of punishing/blacklisting him for trying.

Currently in Pure POS systems, the miners still 'compete' for who gets to mint the next block. Whoever does, gets the spoils. Thereby incentivising multiple chain mining. I know TF in NXT picks a miner, but that does not stop miners trying to extend earlier chains in history to find a different TF path through the miners. If you see what I mean..

What if you say anyone can mint the next block, and then pay EVERYONE, EVERY block. Therefore every chain pays the same. Therefore there is no incentive to mine multiple chains.

You could use a 'Hash Clock' to pick a miner at random every 10 seconds or so (Like POW but more hashing power has no effect), and then you would calculate the value BLOCK FEES / TOTAL COINS.

This would give you a tiny percentage that you could multiply ALL ACCOUNT balances by to spread the fees proportionally to everyone..

So if the block fees were 1 unit, and the coin had 100 coins in all, every account would increase by 1/100, 1%.

This would mean that you would not need to actually run a node to be paid, BUT, if you were a large stakeholder and wanted your investment to be secured, why wouldn't you run a node ?

I can see that there are issues with the idea, why anyone would run a node, as there would be no gain financially from doing so.

The network would not run if enough miners did not choose to run a node. So I wonder - would stake holders choose to run a node - for the good/health of the network ?
 

As a side note, if you prevent multiple input, you will end up with blockchain bloat very quickly.

An attacker can blacklist his coin by signing multiple chain,
then he can switch his coin for new ones on an exchange,
and then blacklist them again,
rise and repeat.

Most of the coin would end up been blacklisted -> centralization -> poor security.

I also agree that you need some sort of arbitrary assignment of initial ownership to bootstrap a PoS currency. That is not my focus here.

My point is as follows:
Given the txn rules I defined, the current owners of the majority of clean inputs always control long-run chain selection. Attackers can exploit past input ownership to blacklist current inputs. This reduces the set of clean inputs and therefore reduces attack costs. However, you can never attack soley through past input ownership. Attackers always need current input ownership as well, otherwise their attack will fail.

Does anyone disagree with the bolded statement at this point? Or have we reached consensus on this point?


If we accept these ideas, I will describe a system for removing inputs from the blacklist.


 

I find your criticism valid and it applies to all forms of POS that I know of. However I don't see it as problematic, as long as you have a way to get that "external 'number'" in a secure/trusted/decentralized enough way.

Pure POS.

I'm not trying to debunk POS. I really like certain aspects of it. Just some points, as with POW, still seem unfinished \ problematic.

This thread is about pure POS N@S resistance, and I have not seen an answer to that yet. Anywhere..

Can you refer me to \ explain a version of POS which can compare valid chains without any external 'number' to bootstrap the process?

(I'm not talking short range attacks, but long-range-total-chain rewrites)

Thanks.

Just realised I posted this in the wrong thread earlier...



Just so you don't miss it benjamin_bit...

https://nxtforum.org/consensus-research/multibranch-forging-approach/

First findings of the POS research group.

What makes you think the same isn't true in some POS implementations

Which POS are you criticising, an actual one or a straw man you invented?

ok, I didn't understand blacklisting worked this way. I'll have to think about it a little more, but this at least gives me a new way to blacklist coins in the "valid" chain, now I have two methods for making it's V(u) lower.

For V(u) you should count accumulated work according to difficulty, not number of blocks.

The more I read your posts the more retarded I become 

I think it doesn't work.

1) If I get control of a private key that in the past had lots of coins that were used for staking, by creating a parallel chain I can make some inputs of the valid chain "unclean", effectively reducing its V(u).

2) If I get control of a private key that in the past had lots of coins that were not used for staking, then my coins are "clean" and I can rewrite history from that moment in time by creating a chain with more V(u).

By combining 1 and 2, the nothing at stake problem is still a problem.

I'm working on a variation of PoS that will help with this. Please wait for it, the whitepaper is still being reviewed.

In the thread, I defined chain selection criteria that allow you to do exactly this. So yes, you can do this with POS. That is the whole point of this thread.
If you don't think I have defined criteria that allow proof that one POS chain is better than other chains in a comparison set, please explain why not.  

There is some distinction in that the ordering over sets of POW chains are transitive.
Orderings over sets of POS chains are not transitive. However, given a set of pos chains with at least one clean Satoshi, there is a well-defined ordering of chains from best to worst within the reference set. 
 

Ideally, I'd like someone knowledgeable to comment on this AND either
a) agree that the system defines a long-run consensus that is robust to nothing@stake.
b) disagree and explain how a nothing@stake attack would disrupt consensus

If (b), then we could debate a substantive issue.
If (a), then we could move on to replenishing minting Satoshi. It's an interesting issue. However, there is no point in discussing it if we don't reach consensus on the existence of consensus here.

No, it is not.

As I said - the VALID POW chain can still be determined without any outside assistance.

Once you have hacked the repo - i can always / later verifiably proove that this POW chain is better than that one. By summing the work.

You can't with POS.