Bitcoin Forum
February 16, 2019, 12:31:15 AM *
News: Latest Bitcoin Core release: 0.17.1 [Torrent]
 
   Home   Help Search Login Register More  
Pages: « 1 2 [3] 4 5 6 7 8 9 »  All
  Print  
Author Topic: Nothing-at-Stake & Long Range Attack on Proof-of-Stake (Consensus Research)  (Read 15141 times)
kushti
Full Member
***
Offline Offline

Activity: 210
Merit: 100


View Profile
December 22, 2014, 03:39:36 PM
 #41

Couldnt we have reference NXT nodes that a new node queries to find the right chain?

Sounds too centralized. However, only initial part of history could be downloaded(e.g. first 100K or 200K blocks in case of Nxt), as its irreversible anyway. And that's  equivalent to checkpoints.

Btw, I think the importance of history attack is overestimated and its solved though in pretty rough way.

Ergo Platform. Part-time IOHK Research. Previously Nxt core dev / SmartContract.com cofounder.
1550277075
Hero Member
*
Offline Offline

Posts: 1550277075

View Profile Personal Message (Offline)

Ignore
1550277075
Reply with quote  #2

1550277075
Report to moderator
Bitcoin mining is now a specialized and very risky industry, just like gold mining. Amateur miners are unlikely to make much money, and may even lose money. Bitcoin is much more than just mining, though!
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1550277075
Hero Member
*
Offline Offline

Posts: 1550277075

View Profile Personal Message (Offline)

Ignore
1550277075
Reply with quote  #2

1550277075
Report to moderator
Daedelus
Hero Member
*****
Offline Offline

Activity: 574
Merit: 500



View Profile
December 28, 2014, 06:34:10 PM
 #42

Congratulations Kushti on an apparently flawless paper  Cheesy
Daedelus
Hero Member
*****
Offline Offline

Activity: 574
Merit: 500



View Profile
January 06, 2015, 09:55:29 AM
 #43

This paper has been added to the thread Nxt Papers: Whitepapers, Academic and Economic at https://bitcointalk.org/index.php?topic=847868
kushti
Full Member
***
Offline Offline

Activity: 210
Merit: 100


View Profile
January 14, 2015, 03:53:27 PM
 #44

To summarize the discussion, known claimed attacks on proof-of-stake distributed consensus algorithm(and concrete implementations) at the moment:

1. Short-range attack  - attacker can offer better chain started few blocks behind current canonical chain. The attack is possible at the moment, the only likely outcome though is just gathered fees increase for an attacker. In our simulations this kind of attack is possible mostly when a long delay occurs due to low target. By the way, the attack has positive aspect for network, as it shorten delays average between blocks. So attacker gets extra fees for a good job done  Grin

2. Long-range attack - attacker can start fork hundreds or thousands blocks behind current chain. From our investigations the attack isn't possible.  

3. Nothing-at-stake attack - not possible at the moment! Will be possible when a lot of forgers will use multiple-branch forging  to increase profits. Then attacker can contribute to all the chains(some of them e.g. containing a transaction) then start to contribute to one chain only behind the best(containing no transaction) making it winner.  Previous statements on N@S attack made with assumption it costs nothing to contribute to an each fork possible and that makes N@S attack a disaster. In fact, it's not possible at all to contribute to each fork possible, as number of forks growing exponentially with time. So the only strategy for a multibranch forger is to contribute to N best forks. In such scenario attack is possible only within short-range e.g. with 25 confirmations needed 10% attacker can't make an attack. And attack is pretty random in nature, it's impossible to predict whether 2 forks will be within N best forks(from exponentially growing set) for k confirmations. So from our point of view the importance of the attack is pretty overblown.

4. History attack - attacker can buy whale's private key for $5 and build alternative story. Solved with some checkpoints now, located behind max rollback possible, so the solution is not so scary in terms of centralization etc.


If you know any other kind of attack, please add. Please note IPO properties of a concrete coins etc isn't related to proof-of-stake distributed consensus problems.

And Consensus Research is going to work on better proof-of-stake prototyping & implementation !

Ergo Platform. Part-time IOHK Research. Previously Nxt core dev / SmartContract.com cofounder.
Tobo
Hero Member
*****
Offline Offline

Activity: 763
Merit: 500


View Profile
January 14, 2015, 05:19:19 PM
 #45

How about the Sybil attack? I know that the Sybil attack may be not unique to PoS?
r0ach
Legendary
*
Offline Offline

Activity: 1260
Merit: 1000


View Profile
January 14, 2015, 07:52:55 PM
 #46


4. History attack - attacker can buy whale's private key for $5 and build alternative story. Solved with some checkpoints now, located behind max rollback possible, so the solution is not so scary in terms of centralization etc.

HOW is that solved???  Centralized checkpoints = not decentralized currency. 

......ATLANT......
..Real Estate Blockchain Platform..
                    ▄▄▄▄▄▄▄▄▄
                    ████████████░
                  ▄██████████████░
                 ▒███████▄████████░
                ▒█████████░████████░
                ▀███████▀█████████
                  ██████████████
           ███████▐██▀████▐██▄████████░
          ▄████▄█████████▒████▌█████████░
         ███████▄█████████▀██████████████░
        █████████▌█████████▐█████▄████████░
        ▀█████████████████▐███████████████
          █████▀████████ ░███████████████
    ██████▐██████████▄████████████████████████░
  ▄████▄████████▐███████████████░▄▄▄▄░████████░
 ▄██████▄█████████▐█████▄█████████▀████▄█████████░
███████████████████▐█████▄█████████▐██████████████░
▀████████▀█████████▒██████████████▐█████▀█████████
  ████████████████ █████▀█████████████████████████
   ▀██▀██████████ ▐█████████████  ▀██▀██████████
    ▀▀█████████    ▀▀█████████    ▀▀██████████

..INVEST  ●  RENT  ●  TRADE..
 ✓Assurance     ✓Price Discovery     ✓Liquidity     ✓Low Fees





███
███
███
███
███
███





███
███
███
███
███
███
███
███
███
███
███
███

◣Whitepaper ◣ANN ThreadTelegram
◣ Facebook     ◣ Reddit          ◣ Slack


███
███
███
███
███
███
███
███
███
███
███
███





███
███
███
███
███
███








Hero/Legendary members
ArticMine
Legendary
*
Offline Offline

Activity: 2268
Merit: 1037


Monero Core Team


View Profile
January 15, 2015, 01:08:39 AM
 #47

Stake does not equal exposure:

Consider for example a pirateat40 style "trust" on a POS coin. The "trust" has a very significant stake combined with a very significant short exposure, and consequently a vested interest in the collapse of the currency, and can vote the stake accordingly. https://en.bitcoin.it/wiki/Pirateat40. POS rewards the creators of ponzi schemes.
 
A variant of this is an exchange gone bad. Again the exchange operator controls a massive stake via customer deposits but no exposure, and if fraud occurs creating a fractional reserve. The exchange has a vested interest in the collapse of the currency in order to cover losses and can vote the stake accordingly.

Buying the currency while at the same time selling a greater amount on a derivatives market, creating a large stake with a short exposure and vested interest in the collapse of the currency. Again the stake can be voted accordingly.

Need I go on ...

Cross posted from https://bitcointalk.org/index.php?topic=924725.msg10158797#msg10158797

Concerned that blockchain bloat will lead to centralization? Storing less than 4 GB of data once required the budget of a superpower and a warehouse full of punched cards. https://upload.wikimedia.org/wikipedia/commons/8/87/IBM_card_storage.NARA.jpg https://en.wikipedia.org/wiki/Punched_card
r0ach
Legendary
*
Offline Offline

Activity: 1260
Merit: 1000


View Profile
January 15, 2015, 01:49:12 AM
 #48


4. History attack - attacker can buy whale's private key for $5 and build alternative story. Solved with some checkpoints now, located behind max rollback possible, so the solution is not so scary in terms of centralization etc.

HOW is that solved???  Centralized checkpoints = not decentralized currency. 
rolling checkpoints are not centralized

So where's the whitepaper on how you created decentralized checkpoints?

......ATLANT......
..Real Estate Blockchain Platform..
                    ▄▄▄▄▄▄▄▄▄
                    ████████████░
                  ▄██████████████░
                 ▒███████▄████████░
                ▒█████████░████████░
                ▀███████▀█████████
                  ██████████████
           ███████▐██▀████▐██▄████████░
          ▄████▄█████████▒████▌█████████░
         ███████▄█████████▀██████████████░
        █████████▌█████████▐█████▄████████░
        ▀█████████████████▐███████████████
          █████▀████████ ░███████████████
    ██████▐██████████▄████████████████████████░
  ▄████▄████████▐███████████████░▄▄▄▄░████████░
 ▄██████▄█████████▐█████▄█████████▀████▄█████████░
███████████████████▐█████▄█████████▐██████████████░
▀████████▀█████████▒██████████████▐█████▀█████████
  ████████████████ █████▀█████████████████████████
   ▀██▀██████████ ▐█████████████  ▀██▀██████████
    ▀▀█████████    ▀▀█████████    ▀▀██████████

..INVEST  ●  RENT  ●  TRADE..
 ✓Assurance     ✓Price Discovery     ✓Liquidity     ✓Low Fees





███
███
███
███
███
███





███
███
███
███
███
███
███
███
███
███
███
███

◣Whitepaper ◣ANN ThreadTelegram
◣ Facebook     ◣ Reddit          ◣ Slack


███
███
███
███
███
███
███
███
███
███
███
███





███
███
███
███
███
███








Hero/Legendary members
Daedelus
Hero Member
*****
Offline Offline

Activity: 574
Merit: 500



View Profile
January 15, 2015, 02:01:23 AM
 #49


4. History attack - attacker can buy whale's private key for $5 and build alternative story. Solved with some checkpoints now, located behind max rollback possible, so the solution is not so scary in terms of centralization etc.

HOW is that solved???  Centralized checkpoints = not decentralized currency. 
rolling checkpoints are not centralized

So where's the whitepaper on how you created decentralized checkpoints?

The network won't accept reorgs deeper than 720 blocks so block 721 back from the current block is the rolling checkpoint. That's how it is done, though there isnt a whitepaper.

There is a general Nxt whitepaper, I can get the link if you haven't seen it.
r0ach
Legendary
*
Offline Offline

Activity: 1260
Merit: 1000


View Profile
January 15, 2015, 03:16:58 AM
 #50


4. History attack - attacker can buy whale's private key for $5 and build alternative story. Solved with some checkpoints now, located behind max rollback possible, so the solution is not so scary in terms of centralization etc.

HOW is that solved???  Centralized checkpoints = not decentralized currency. 
rolling checkpoints are not centralized

So where's the whitepaper on how you created decentralized checkpoints?

The network won't accept reorgs deeper than 720 blocks so block 721 back from the current block is the rolling checkpoint. That's how it is done, though there isnt a whitepaper.

There is a general Nxt whitepaper, I can get the link if you haven't seen it.

Kind of hard to keep up with what exactly NXT is and whether it works or not:

Quote from: Sunny King
As far as I know at least the first version of NXT's PoS is a direct clone of PPC's with some modifications, appeared lacking a good understanding of the security involved in PPC's PoS.

......ATLANT......
..Real Estate Blockchain Platform..
                    ▄▄▄▄▄▄▄▄▄
                    ████████████░
                  ▄██████████████░
                 ▒███████▄████████░
                ▒█████████░████████░
                ▀███████▀█████████
                  ██████████████
           ███████▐██▀████▐██▄████████░
          ▄████▄█████████▒████▌█████████░
         ███████▄█████████▀██████████████░
        █████████▌█████████▐█████▄████████░
        ▀█████████████████▐███████████████
          █████▀████████ ░███████████████
    ██████▐██████████▄████████████████████████░
  ▄████▄████████▐███████████████░▄▄▄▄░████████░
 ▄██████▄█████████▐█████▄█████████▀████▄█████████░
███████████████████▐█████▄█████████▐██████████████░
▀████████▀█████████▒██████████████▐█████▀█████████
  ████████████████ █████▀█████████████████████████
   ▀██▀██████████ ▐█████████████  ▀██▀██████████
    ▀▀█████████    ▀▀█████████    ▀▀██████████

..INVEST  ●  RENT  ●  TRADE..
 ✓Assurance     ✓Price Discovery     ✓Liquidity     ✓Low Fees





███
███
███
███
███
███





███
███
███
███
███
███
███
███
███
███
███
███

◣Whitepaper ◣ANN ThreadTelegram
◣ Facebook     ◣ Reddit          ◣ Slack


███
███
███
███
███
███
███
███
███
███
███
███





███
███
███
███
███
███








Hero/Legendary members
go1111111
Full Member
***
Offline Offline

Activity: 185
Merit: 100


View Profile
January 15, 2015, 06:24:39 AM
 #51

So where's the whitepaper on how you created decentralized checkpoints?

The basic idea is what Vitalik talks about in his blog post on weak subjectivity: https://blog.ethereum.org/2014/11/25/proof-stake-learned-love-weak-subjectivity/

It is decentralized in that if you've been away from the network for the past 720 (or whatever # of) blocks, when you come back online you have to ask someone or some set of people which chain is the real one. So if you know your best friend has been keeping a node online, you can ask him, or you can ask Vitalik, or you can ask Gavin Andressen, or you can ask some combination of any # of people you want -- the choice is up to you.
achimsmile
Legendary
*
Offline Offline

Activity: 1225
Merit: 1000


View Profile
January 15, 2015, 06:49:19 AM
 #52


Kind of hard to keep up with what exactly NXT is and whether it works or not:

Quote from: Sunny King
As far as I know at least the first version of NXT's PoS is a direct clone of PPC's with some modifications, appeared lacking a good understanding of the security involved in PPC's PoS.

It isn't and never was:

Quote from: BCNext
After thinking about the mining algorithm I came to conclusion that original proof-of-stake used by PPC and NVC is a bit flawed.  Bob could accumulate small amounts on different accounts during a long period of time and then attempt a 51% attack.  Artificial limits like max 90 days don't seem to work as intended.  Nxt will use a different proof-of-stake approach.

you would have to present a source code comparison between ppc and the first version of Nxt to make me think otherwise.
alphaBar
Newbie
*
Offline Offline

Activity: 36
Merit: 0


View Profile
January 15, 2015, 07:27:15 AM
 #53

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.

This solution is already implemented in BitShares, though called something different (TaPoS):
https://bitcointalk.org/index.php?topic=354573.0
Daedelus
Hero Member
*****
Offline Offline

Activity: 574
Merit: 500



View Profile
January 15, 2015, 08:53:07 AM
Last edit: January 15, 2015, 12:54:46 PM by Daedelus
 #54

So where's the whitepaper on how you created decentralized checkpoints?

The basic idea is what Vitalik talks about in his blog post on weak subjectivity: https://blog.ethereum.org/2014/11/25/proof-stake-learned-love-weak-subjectivity/

It is decentralized in that if you've been away from the network for the past 720 (or whatever # of) blocks, when you come back online you have to ask someone or some set of people which chain is the real one. So if you know your best friend has been keeping a node online, you can ask him, or you can ask Vitalik, or you can ask Gavin Andressen, or you can ask some combination of any # of people you want -- the choice is up to you.


Come-from-Beyond described Economic Clustering in May when he committed it. Not sure it is quite the same idea as rolling checkpoints but it is in the same area.
https://nxtforum.org/news-and-announcements/economic-clustering/msg26267/#msg26267

Consensus research have also shown that the "Nothing-at-stake problem" (described in Vitalik's post) has been overstated. A lot. On the contrary, multibranch forging (aka mining on every chain you see) actually helps with security as you can't mine on every chain as they grow exponentially with time. You have to choose what you think are the best N chains and the results can't be predicted so the 'attack' is pretty useless.

I believe this also removes the need for Vitaliks security deposit as it makes it unnecessary as it protects against something that can't happen. It could even be damaging as it restricts the number of branches in multibranch forging so it is no longer exponentially growing in size but is finite, for practical purposes. Equal to the number of nodes in the network? Given they can only forge only 1 branch they see without being penalised. Have I understood correctly, Kushti?


All CfB's descriptions and Q&A on Economic Clustering are collated in this thread...

https://nxtforum.org/economic-clustering/cfb's-announcement-of-economic-clustering/ (you need an account to see the whitepaper section of the forum)



Here is the most recent whitepaper, though it may not have been updated with most recent features:

Nxt Whitepaper
https://www.dropbox.com/s/cbuwrorf672c0yy/NxtWhitepaper_v122_rev4.pdf

cynicSOB
Member
**
Offline Offline

Activity: 106
Merit: 10

yes, sometimes I'm a cynical SOB


View Profile
January 15, 2015, 10:03:45 PM
 #55

To summarize the discussion, known claimed attacks on proof-of-stake distributed consensus algorithm(and concrete implementations) at the moment:

1. Short-range attack  - attacker can offer better chain started few blocks behind current canonical chain. The attack is possible at the moment, the only likely outcome though is just gathered fees increase for an attacker. In our simulations this kind of attack is possible mostly when a long delay occurs due to low target. By the way, the attack has positive aspect for network, as it shorten delays average between blocks. So attacker gets extra fees for a good job done  Grin


I just performed this type of attack in APEXcoin. Please see here: https://bitcointalk.org/index.php?topic=897493.0
It was a short-range attack, but the consequences are not just more fees: I successfully double-spent.

You may want to expand this "Short-range attack" category, since there can be many different ways to achieve this.
I did it by splitting the coins and waiting for age to accumulate, and as I mention in the linked thread, I think it may be possible to do something similar in nxt.

Just like with POW, 51% guarrantees success but if you have 10% of the hashrate you will eventually have the chance to double spend. Same thing here: small stake + patience = double-spend. Only worse because in most POS coins the % of actively staked coins is low.

For more secure coins: 1EqekC9YVhiWLYjG3mfKNJwrf5s3YS46WW
For the lulz:1EqekC9YVhiWLYjG3mfKNJwrf5s3YS46WW
cynicSOB
Member
**
Offline Offline

Activity: 106
Merit: 10

yes, sometimes I'm a cynical SOB


View Profile
January 16, 2015, 01:07:58 PM
 #56

you did it with a dead coin lol

its not impressive when you only do it to a dead coin. thats liek stabbing a dead deer and saying you hunted it. do it even with a nxt clone and then people will take notice.

I think it's more like stabbing a tied up deer to prove that stabs can be deadly, but let's skip the animal killing analogies please. Poor Bambi...

That's being discussed on the other thread. This doesn't directly apply to nxt becase it doesn't have coin age, but I think the attack can be adapted for it.

For more secure coins: 1EqekC9YVhiWLYjG3mfKNJwrf5s3YS46WW
For the lulz:1EqekC9YVhiWLYjG3mfKNJwrf5s3YS46WW
EvilDave
Hero Member
*****
Offline Offline

Activity: 854
Merit: 1000



View Profile
January 16, 2015, 01:40:17 PM
Last edit: January 16, 2015, 01:53:21 PM by EvilDave
 #57

May I suggest NAS as the NXT clone target ?
https://bitcointalk.org/index.php?topic=523187.2060

Poor little things been dead in the water for a long time, so the code is pretty much out of date as far as current NXT code goes, but I reckon it'd be a good next step.
And I've got a couple of million NAS lying around somewhere I could lend ya........

Edit: Has there been any contact with or any sign of life from the Apexcoin devs/BlockNet crew?


Nulli Dei, nulli Reges, solum NXT
Love your money: www.nxt.org  www.ardorplatform.org
www.nxter.org  www.nxtfoundation.org
kushti
Full Member
***
Offline Offline

Activity: 210
Merit: 100


View Profile
January 16, 2015, 01:43:47 PM
 #58

I just performed this type of attack in APEXcoin. Please see here: https://bitcointalk.org/index.php?topic=897493.0
It was a short-range attack, but the consequences are not just more fees: I successfully double-spent.

You may want to expand this "Short-range attack" category, since there can be many different ways to achieve this.
I did it by splitting the coins and waiting for age to accumulate, and as I mention in the linked thread, I think it may be possible to do something similar in nxt.

Just like with POW, 51% guarrantees success but if you have 10% of the hashrate you will eventually have the chance to double spend. Same thing here: small stake + patience = double-spend. Only worse because in most POS coins the % of actively staked coins is low.

Could you describe attack scenario in details? After reproducing it in simulation we would like to pay you pretty good bounty Smiley

P.S. Good description on practical impossibility of N@S by JordanLee http://www.peercointalk.org/index.php?topic=2976.msg27303#msg27303

Ergo Platform. Part-time IOHK Research. Previously Nxt core dev / SmartContract.com cofounder.
cynicSOB
Member
**
Offline Offline

Activity: 106
Merit: 10

yes, sometimes I'm a cynical SOB


View Profile
January 16, 2015, 02:00:19 PM
 #59

May I suggest NAS as the NXT clone target ?
https://bitcointalk.org/index.php?topic=523187.2060

Poor little things been dead in the water for a long time, so the code is pretty much out of date as far as current NXT code goes, but I reckon it'd be a good next step.
And I've got a couple of million NAS lying around somewhere I could lend ya........

Edit: Has there been any contact with or any sign of life from the Apexcoin devs/BlockNet crew?

thanks, I'll look into it. No contact from Apex devs yet.

For more secure coins: 1EqekC9YVhiWLYjG3mfKNJwrf5s3YS46WW
For the lulz:1EqekC9YVhiWLYjG3mfKNJwrf5s3YS46WW
EvilDave
Hero Member
*****
Offline Offline

Activity: 854
Merit: 1000



View Profile
January 16, 2015, 02:06:42 PM
 #60

Hmmm....if I get some spare time I'll fire up a NAS node and see how the network looks.

I posted on the Apexcoin and BlockNet ANN threads, maybe we'll hear something from their devs about your attack.

Apexcoin ANN
BlockNet ANN

Nulli Dei, nulli Reges, solum NXT
Love your money: www.nxt.org  www.ardorplatform.org
www.nxter.org  www.nxtfoundation.org
Pages: « 1 2 [3] 4 5 6 7 8 9 »  All
  Print  
 
Jump to:  

Bitcointalk.org is not available or authorized for sale. Do not believe any fake listings.
Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!