Nothing-at-Stake & Long Range Attack on Proof-of-Stake (Consensus Research)

[jonald_fyookball]

James,

I don't know if I have any deep insights,
and I don't claim to be any expert.

My thoughts on this:

With proof of stake, there's no
external resource being spent
on security as with proof of work.

The holy grail which is sought after
with proof of stake, is costless
security (everyone just has their stake,
that's enough to secure the network).
 
But by the same token, if nothing
of significance is being spent on
securing the network (as with
miners in PoW), then it costs
basically nothing to try to fool
the network (attack it).

For example,  people can forge
on multiple chains at the same
time without penalty.

They can send themselves
coins back and forth to
try to get more fees.
 
That's why Vitalik proposed
security deposits, to try to
solve this nothing at stake
issue.
  
Or you could even try to
double spend.  This easy
way would be to try to
spend coins that you sold.

Since you still have the keys,
how would nodes know you
spent the coins except by
looking at the blocks after
yours?  Unlike proof of
work, you don't really need
any resources to try this attack.

This nothing-at-stake issue
is nothing new -- this is
what people have been talking
about for months and months.

https://github.com/ethereum/wiki/wiki/Problems

That's what the paper is about.
They are trying to explore possibilities
with multi branch structures instead
of the traditional blockchain, but with
no clear solutions so far.

[l8orre]

I can't tell if jonald_fyookball is trolling or serious.

The content lacks the most obvious and outward attributes of open trolling- maybe many people simply are so superficial...

[jonald_fyookball]

I can't tell if jonald_fyookball is trolling or serious.

Wasn't meaning to be trolling but I guess I'm done in this thread.

Read the whitepaper in the OP or
the ethereum blog if you want to know
more about the Nothing at Stake problem.

https://github.com/ethereum/wiki/wiki/Problems

(Or, just pretend its not a problem. 
Whatever floats your boat.)

later!

[Este Nuno]

So anyone is seeing double spend in any of the PoS coins we have so far since 2013 ? I think not.
This whole conversation about that PoS supposed to be a vulnerable and PoW not ? Lol give me a break.... maybe you should check how easy is it to make a 51% Attack on PoW with Ascis ? You don't need more then 70k~ $ btw... so do your research where it is needed.

I'm a huge supporter of PoS and I think everyone should be working towards that as a goal for all crypto, but there have been double spends and attacks on PoS coins this year. Off the top of my head I remember Navajo Coin had a problem with that and then the big one being Vericoin which really hurt its market cap after they rolled back.

[Daedelus]

So anyone is seeing double spend in any of the PoS coins we have so far since 2013 ? I think not.
This whole conversation about that PoS supposed to be a vulnerable and PoW not ? Lol give me a break.... maybe you should check how easy is it to make a 51% Attack on PoW with Ascis ? You don't need more then 70k~ $ btw... so do your research where it is needed.

I'm a huge supporter of PoS and I think everyone should be working towards that as a goal for all crypto, but there have been double spends and attacks on PoS coins this year. Off the top of my head I remember Navajo Coin had a problem with that and then the big one being Vericoin which really hurt its market cap after they rolled back.

Weren't they both related to exchanges holding a large proportion of the coins and being hacked? Or maybe being 'hacked'?

[Daedelus]

The logical answer is:  I wanted to highlight the conclusions
of the paper, since people have linked to it, misquoted it,
and misrepresented it as some kind of "debunking".

*snip*...Some people
aren't even reading the paper and throwing
around their worthless opinions.  

I'm pretty sure he is referring to me here   when I said there are still some issues but

"it's nearly impossible to attack a proof-of-stake currency with "1% stake even" as stated by Buterin"

After implying I'm a liar    I pointed out that is a direct quote of the OP in this thread   Then I was called a muppet so I quoted the whole paragraph. And now I have a worthless opinion? For the record (and repeating myself again), it isn't my opinion. It is that of the authors And you are refusing to engage honestly with it.


I think we have a flat-earther on our hands, it won't matter what research Kushti & andruiman produce. He'll cling to the unproven claims he has parroted for months. We need open minds and a technical demolition (if one is even possible) of the paper to move forward. Kushti has even provided the tools and models to do it! But make no mistake, this is a big step for everyone

[Este Nuno]

So anyone is seeing double spend in any of the PoS coins we have so far since 2013 ? I think not.
This whole conversation about that PoS supposed to be a vulnerable and PoW not ? Lol give me a break.... maybe you should check how easy is it to make a 51% Attack on PoW with Ascis ? You don't need more then 70k~ $ btw... so do your research where it is needed.

I'm a huge supporter of PoS and I think everyone should be working towards that as a goal for all crypto, but there have been double spends and attacks on PoS coins this year. Off the top of my head I remember Navajo Coin had a problem with that and then the big one being Vericoin which really hurt its market cap after they rolled back.

Weren't they both related to exchanges holding a large proportion of the coins and being hacked? Or maybe being 'hacked'?

Not sure exactly what the circumstances were. Exchanges had something to do with though yeah. Maybe the exchanges weren't staking their reserves or something. I thought that the exchanges got doubled spent against, but I'm not sure.

[kushti]

PoS opponents usually citing two sources, "A Treatise on Altcoins" by A. Poelstra & statements made by V. Buterin(mostly in the form of blogposts). Poelstra's paper contains only kinda philosophical statements(like "consensus inside a system could be achieved only by external resources spending"), and we won't to deal with it at all: the only way for us is not to participate in philosophical disputes, but make a constructive proof of opposite(like Satoshi Nakamoto made constructive proof decentralized currency could exists with his revolutionary paper).

V. Buterin statements are much more clear so we started with them.

However, this algorithm has one important flaw: there is ”nothing at stake”. In the event
of a fork, whether the fork is accidental or a malicious attempt to rewrite
history and reverse a transaction, the optimal strategy for any miner is to
mine on every chain, so that the miner gets their reward no matter which
fork wins. Thus, assuming a large number of economically interested miners,
an attacker may be able to send a transaction in exchange for some digital
good (usually another cryptocurrency), receive the good, then start a fork of
the blockchain from one block behind the transaction and send the money to
themselves instead, and even with 1% of the total stake the attacker’s fork
would win because everyone else is mining on both.

Well, in the first place it's not possible to mine on every chain as number of them is growing exponentially with time(and no special hardware could helps, as processing is needed for each block in each branch with storing final balances, it consumes both CPU and memory a lot), so the only strategy is to keep N best branches (we have another paper on multibranching forging called "PoS forging algorithms: formal approach and multibranch forging" https://github.com/ConsensusResearch/articles-papers/blob/master/multibranch/multibranch.pdf ).

In the second place, the possibility of the attack with 1% stake is negligible. Even with big enough stake the outcome of an attack is unpredictable for an attacker and could be done only in short-range(so with raising number of confirmations to 30 in our experiments attacks are always failed). And in practice
 attacker needs to feed part of network with one transaction, another part with other and both parts need to be large enough I guess, and that's hard to get done also.

Also we've found "long-range attack" stated by Buterin should be renamed to "short-range attack", see the paper or tl/dr in the first post.

While other PoS researchers think forging on multiple branches is the problem and working on avoiding it with punishments or incentives, we don't think
it's the problem at all. Multiple branches are okay, if the consensus property met: after k confirmations it's impossible(or extremely expensive) to change system state in the past. So we're working on PoS model corresponds to the property in a proven or evident enough way without throwing multibranch forging away.

[r0ach]

I haven't kept up with PoS developments lately, but how do people address the following issue.  PoW and DPOS have coin ownership and network control as separate parts.  For other PoS models, coin ownership grants network control.  Since exchanges and "bitcoin banks" tend to monopolize the control of coins into a small number, or single entity, shouldn't regular PoS be called, "proof of trust in exchange platform"?  Then you also have the possibility of a rogue exchange performing a history attack.

[achimsmile]

So anyone is seeing double spend in any of the PoS coins we have so far since 2013 ? I think not.
This whole conversation about that PoS supposed to be a vulnerable and PoW not ? Lol give me a break.... maybe you should check how easy is it to make a 51% Attack on PoW with Ascis ? You don't need more then 70k~ $ btw... so do your research where it is needed.

I'm a huge supporter of PoS and I think everyone should be working towards that as a goal for all crypto, but there have been double spends and attacks on PoS coins this year. Off the top of my head I remember Navajo Coin had a problem with that and then the big one being Vericoin which really hurt its market cap after they rolled back.

Weren't they both related to exchanges holding a large proportion of the coins and being hacked? Or maybe being 'hacked'?

Not sure exactly what the circumstances were. Exchanges had something to do with though yeah. Maybe the exchanges weren't staking their reserves or something. I thought that the exchanges got doubled spent against, but I'm not sure.

A lot of Vericoins were stolen off of Mintpal, this had nothing to do with PoS/PoW.

There were doublespends in Navajo (PoS), and there were doublespends on Worldcoin, Whitecoin etc. (PoW)

PoS1 != PoS2

[jl777]

I haven't kept up with PoS developments lately, but how do people address the following issue.  PoW and DPOS have coin ownership and network control as separate parts.  For other PoS models, coin ownership grants network control.  Since exchanges and "bitcoin banks" tend to monopolize the control of coins into a small number, or single entity, shouldn't regular PoS be called, "proof of trust in exchange platform"?  Then you also have the possibility of a rogue exchange performing a history attack.

for a young coin, it is indeed an issue where a large percentage of coins could and have been on a single exchange, which then gets hacked.

However for a mature PoS, like NXT, even the largest exchange has less than 5% of all NXT, so even if they went all evil, not much they can do. It also seems quite unlikely for an exchange that is earning regular revenues from a coin to effectively sabotage it by attacking it.

With decentralized exchanges getting more and more traction, this issue will get smaller over time. Over time there is more distribution, not less, so not sure where you get this assumption about monopoly control. I guess the fact that bitcoin mining pools have this exact mechanism might be predisposing you to this false assumption

James

[jl777]

So anyone is seeing double spend in any of the PoS coins we have so far since 2013 ? I think not.
This whole conversation about that PoS supposed to be a vulnerable and PoW not ? Lol give me a break.... maybe you should check how easy is it to make a 51% Attack on PoW with Ascis ? You don't need more then 70k~ $ btw... so do your research where it is needed.

I'm a huge supporter of PoS and I think everyone should be working towards that as a goal for all crypto, but there have been double spends and attacks on PoS coins this year. Off the top of my head I remember Navajo Coin had a problem with that and then the big one being Vericoin which really hurt its market cap after they rolled back.

Weren't they both related to exchanges holding a large proportion of the coins and being hacked? Or maybe being 'hacked'?

Not sure exactly what the circumstances were. Exchanges had something to do with though yeah. Maybe the exchanges weren't staking their reserves or something. I thought that the exchanges got doubled spent against, but I'm not sure.

A lot of Vericoins were stolen off of Mintpal, this had nothing to do with PoS/PoW.

There were doublespends in Navajo (PoS), and there were doublespends on Worldcoin, Whitecoin etc. (PoW)

PoS1 != PoS2

correct.

Also the current NXT PoS is more like PoS4 or PoS5 and from what I can tell it is more advanced than PoS2, though PoS2 is starting to incorporate some aspects of NXT PoS

more improvements are in the pipeline for NXT PoS

James

[Daedelus]

I haven't kept up with PoS developments lately, but how do people address the following issue.  PoW and DPOS have coin ownership and network control as separate parts.  For other PoS models, coin ownership grants network control.  Since exchanges and "bitcoin banks" tend to monopolize the control of coins into a small number, or single entity, shouldn't regular PoS be called, "proof of trust in exchange platform"?  Then you also have the possibility of a rogue exchange performing a history attack.

"Proof of trust in exchange platform" - only if the scenario you describe actually applies. BTER is the biggest Nxt exchange and had problems in the summer. Even then, the wallet was only 50 million Nxt = ~5% of all tokens. What you describe might be true for smaller POS but broadbrush generalising isn't representative of POS.

There is no reason to think Nxt will follow the centralisation of bitcoin. You can already trade NXT <> BTC from within the platform in the most decentralised way to date through Multigateway. BTCD, Blackcoin, Veri, Doge are in development and there is no reason other coins couldn't be added. Additional security of Nxt account will come next year with Account Control and 2-Phased transactions (you will be able to 'lock' an account for N blocks, or limit transfers to nominated accounts only so even if someone gets your password they can't move your Nxt). Smart Contracts will also take the risk away from dealing P2P and not use exchanges. Through Monetary System, coins built on top of Nxt can be traded in a completely decentralised way through Nxt itself.


Nxt is still maturing but there is less and less reason to use exchanges or even centralised services at all. Even now it is no where near the scenario you describe.

[r0ach]

I haven't kept up with PoS developments lately, but how do people address the following issue.  PoW and DPOS have coin ownership and network control as separate parts.  For other PoS models, coin ownership grants network control.  Since exchanges and "bitcoin banks" tend to monopolize the control of coins into a small number, or single entity, shouldn't regular PoS be called, "proof of trust in exchange platform"?  Then you also have the possibility of a rogue exchange performing a history attack.

"Proof of trust in exchange platform" - only if the scenario you describe actually applies. BTER is the biggest Nxt exchange and had problems in the summer. Even then, the wallet was only 50 million Nxt = ~5% of all tokens. What you describe might be true for smaller POS but broadbrush generalising isn't representative of POS.

There is no reason to think Nxt will follow the centralisation of bitcoin. You can already trade NXT <> BTC from within the platform in the most decentralised way to date through Multigateway. BTCD, Blackcoin, Veri, Doge are in development and there is no reason other coins couldn't be added. Additional security of Nxt account will come next year with Account Control and 2-Phased transactions (you will be able to 'lock' an account for N blocks, or limit transfers to nominated accounts only so even if someone gets your password they can't move your Nxt). Smart Contracts will also take the risk away from dealing P2P and not use exchanges. Through Monetary System, coins built on top of Nxt can be traded in a completely decentralised way through Nxt itself.


Nxt is still maturing but there is less and less reason to use exchanges or even centralised services at all. Even now it is no where near the scenario you describe.

Come on man, let's try to stick to the topic of general PoS mechanics instead of NXT shilling.  Anytime PoS is mentioned, there's always some NXT guy crawling out of the woodwork with a multi-level marketing campaign.  Before you try to shill NXT to me, you should probably read one of the posts I've made before regarding IPOs:

http://bitcointalk.org/index.php?topic=443196.0

[Daedelus]

Name a POS you want your Proof-of-Trust to apply to and we can look at that one. The above is the answer for Nxt. And which parts aren't true or you object to?

Generalising is helpful to you as it is easier to create strawman arguments. Have some POS come unstuck having too much on an exchange? Yes. Is that justification for calling all POS "Proof-of-Trust in exchanges"? No. Especially in the case of Nxt.


This topic is actually about reviewing Kushti's research findings, not generalising POS based on opinion.

[r0ach]

Name a POS you want your Proof-of-Trust to apply to and we can look at that one. The above is the answer for Nxt. And which parts aren't true or you object to?

The general public, and even experienced Bitcoiners themselves, aren't very good at securing coins.  This problem has been almost completely addressed for PoW by smartcard, hardware wallets for $30.  With PoS, it's a different ballgame.  You're required to keep coins online to stake, opening up the system to problems the general public will never be able to deal with unless they outsource that activity to someone else, aka a Bitcoin bank.

PoS systems that don't utilize coin age don't seem to provide benefit to small stakers at all.  You have a combination of the small staker not being rewarded to stake factor, plus the general public tendency to outsource their staking to a Bitcoin bank since they don't want to deal with the risk and technology.  This means a large movement to staking centralization and exchange centralization.  It's really no different from Bitcoin PoW centralization.  The exception is that circumstances that lead to double spend attacks for PoS coins, are much more dangerous long term for most PoS models than circumstances that lead to double spends for PoW coins.

I'm not particularly positive or negative on Bitshares, but DPOS, just like PoW, separates coin ownership from network control, so it doesn't have the above drawbacks where the general public is expected to jump through hoops that they aren't going to do, and will either not stake at all, which network security requires them to do, or will just outsource their staking to a Bitcoin bank, making it possibly more centralized than PoW.

I'm aware of NXT pool forging to try and combat the issues I've stated, which is, hilariously, almost like recreating PoW pool mining.  It does have significantly less energy use than PoW, but once again, this is something that most or all NXT holders are expected to participate in to maintain network security, and the general public is just not going to do it.  Once you start trying to fix the core issues of PoS, you start to run into issues that make it so the system might be too complex for the general public to use, since it seems to demand much more active participation than PoW, while also assuming everyone walking the planet is a combination of computer science and finance major.

The biggest issue of DPOS, is even if it's 100% positive your initial 101 delegate rollout can't and won't collude, how can you make a system to ensure that when they either stop delegating or die, that their replacements won't be colluding.  Delegating as a DPOS participant should be a revenue stream, but maybe you will receive a more attractive, instant lump sum to sell out.

In summary, if Bitcoin PoW is ever found to be an inferior system to whatever PoS system emerges, Bitcoin PoW still has a large chance of beating it without even factoring in the network effect, just from being a much more simple and straightforward system.

[kushti]

I haven't kept up with PoS developments lately, but how do people address the following issue.  PoW and DPOS have coin ownership and network control as separate parts.  For other PoS models, coin ownership grants network control.  Since exchanges and "bitcoin banks" tend to monopolize the control of coins into a small number, or single entity, shouldn't regular PoS be called, "proof of trust in exchange platform"?  Then you also have the possibility of a rogue exchange performing a history attack.

In PoW centralized bank could be robbed by a centralized miner    All those issues are out of scope of our research at the moment.

Regarding history attack, it exists but as rollback is limited(e.g. max 1440 blocks for Nxt now and could be much less in future) the only result is new nodes being mislead i.e. network partitioning. The current solution is to use checkpoints but we're looking for more elegant approach.

[neoranga]

Regarding history attack, I will introduce in this topic another very interesting idea from NXT that is not yet implemented but could solve concerns with hidden history rebuilding, it's called Economic Clustering.

In Economic Clustering, basically, all transactions have to include a signed reference to an older block or transaction in the history, so if an attacker gets the keys of an account that used to have huge amounts of stake (those close to the genesis of the coin) and tries to reconstruct his/her own version of history in isolation it's impossible to rebuild it including the transactions of the rest of the economy and collect any of their fees, simply because the hashes of the new history will never match those included in the transactions previously broadcast.
If you already belong to the network and see the hidden branch being released your client can immediately spot the fake history as not including any transaction that you know about (from you or from a list of known companies/entities).

I see it as a social consensus: to fool the history you need to pro-actively involve a majority of the network signing the scam.

[siameze]

@r0ach I actually liked your poll at:

http://bitcointalk.org/index.php?topic=443196.0

It is an evolution backwards in the technical domain of distribution, and in the ethics domain of corruption issues

[jl777]

I haven't kept up with PoS developments lately, but how do people address the following issue.  PoW and DPOS have coin ownership and network control as separate parts.  For other PoS models, coin ownership grants network control.  Since exchanges and "bitcoin banks" tend to monopolize the control of coins into a small number, or single entity, shouldn't regular PoS be called, "proof of trust in exchange platform"?  Then you also have the possibility of a rogue exchange performing a history attack.

In PoW centralized bank could be robbed by a centralized miner    All those issues are out of scope of our research at the moment.

Regarding history attack, it exists but as rollback is limited(e.g. max 1440 blocks for Nxt now and could be much less in future) the only result is new nodes being mislead i.e. network partitioning. The current solution is to use checkpoints but we're looking for more elegant approach.

Couldnt we have reference NXT nodes that a new node queries to find the right chain?
Just look at the block explorer sites, it becomes quite clear if you are on the wrong chain (assuming the block explorers are on the right chain, seems safe assumption).

So having a list of websites/nodes to query about the right chain would seem to prevent any new node from using the false chain.

Why is this a big problem? Maybe I am missing something significant.

Pick half a dozen websites that are the NXT main websites, have a way for the user to add new ones to add to the consensus list. All these sites would need to agree about the hash value for the chain as of 1440 blocks ago and closer. Some checking could be done for the initial blocks during the time of vulnerability against the false chain.

This simple method seems to prevent any new node from believing the history attack created false chain (not that it is likely to be achieved).

James