Decentralized Timestamp

[gmaxwell]

The nothing-at-stake problem can be overcome by GHOST protocol or similar

This is far from clear to me, the obvious formulations of that would seem to have infinite convergence time to me.

You've given a pretty clear explanation of one aspect of the problem— though another one with common causes is costless simulation: e.g. some early large number of stake holders can go fork it off and with no cost produce a simulated chain which a new node cannot distinguish from the original. They can do this at any point, even after exiting the system, years later— so it doesn't seem possible that any inside-system incentives can prevent them from doing so.

[telepatheic]

The GHOST protocol seems to be able to mitigate real time forking (although I haven't analysed in depth the assumptions of that model) however it is not effective against historical forking.

Their are ways of mitigating historical forking but none are secure without some unrealistic assumptions. The primary assumption is that a majority of past coin holders will not conspire together to rewrite the history of the chain. That may be true when past coin holders are still holding coins but it falls apart when the coins change ownership over time. I've yet to see any decentralised proposal which is secure against this form of attack without invoking some form of proof of work.

It is important to remember that the purpose of the block chain is to achieve consensus. If consensus is actually achieved via an alternative method (software patches, checkpoints, consensus between coin service providers etc.) then there is little point having a block chain at all and there will likely exist more secure and efficient ways of doing the same thing without a block chain.

[Cryddit]

The nothing-at-stake problem can be overcome by GHOST protocol or similar

This is far from clear to me, the obvious formulations of that would seem to have infinite convergence time to me.

You've given a pretty clear explanation of one aspect of the problem— though another one with common causes is costless simulation: e.g. some early large number of stake holders can go fork it off and with no cost produce a simulated chain which a new node cannot distinguish from the original. They can do this at any point, even after exiting the system, years later— so it doesn't seem possible that any inside-system incentives can prevent them from doing so.

Hmmm.  That's a fine example of withdrawing your support from a blockchain (by creating an attack chain) without making the repudiation or withdrawal of support visible on that blockchain (because it hasn't happened yet). 

And you're right, the GHOST protocol doesn't address it.  Darn.

There are partial protections such as checkpoints in the downloaded wallet, but the most they can do is limit the length of the 'simulation' or attack chain.

[mczarnek]

The way Nxt does it is actually quite clever and solves the nothing at stake problem, there is more to it than this but the part of it that I understand is that choosing who forges next is every forger does SHA(last forger public key) Somehow how long ago an account forged and how many nxt owned by that account and information from the last block is factored in as well.  The winner is the one who has the largest hash.

So, in order to crack it, you need to use proof of work in order to find accounts that would have higher hashes for every block along the way.

This would take a network that does the same thing the Bitcoin network does but would be many magnitudes of order greater than the Bitcoin network to hash numbers in order to fast enough determine how an attacker would move around their coins into the right accounts in order to be able to author blocks.  And if it's not enough security, do SHA(SHA()) and you've squared the amount of processing power required by an attacker.  So an attacker would basically have to build a very expensive and long fork faster than the network does these light-weight operations.  He also needs to be able to plan 1440 blocks into the future in order to know where to place these Nxt in order for the network to accept his hash as valid.

There are some other things, such as not allowing block that have timestamps greater than X blocks ago.  And there is some other secret sauce that has been discussed behind the scenes that I'm not going to reveal here.

Point is though, this works in a completely different way to Bitcoin and the nothing at stake problem doesn't apply here because it works so differently.  Also, I believe there aren't 'forks' in the same sense that regularly pop-up as they do in the Bitcoin network because forgers aren't submitting their 'fork' to the network that they can re-write(short of that ultra high processing power), they are submitting their individual block.

Basically we aren't getting much further into the details though because they want to implement it and having working first before telling our competitors the right way to implement POS.  There are a number of people who have reviewed it however and it works.

You want to further discuss it, I recommend checking out this thread: https://nxtforum.org/general/how-does-nxt-fix-the-nothing-at-stake-problem/

[gmaxwell]

Point is though, this works in a completely different way to Bitcoin and the nothing at stake problem doesn't apply here because it works so differently.

Bitcoin is not a POS coin so it's a bit weird to say that a thing that is completely inapplicable to Bitcoin is inapplicable to your thing because its different from Bitcoin, especially if that reason is "secret sauce".

The simulation example is probably the hardest to convincingly wave away. Say tomorrow half the NXT value holders decide to sell their coin. Six months after that their old NXT keys fall into evil hands. The evil people create a fork of the NXT chain and in seconds mine it up to the current day. How do existing nodes know not to reorg onto the new one? If there is a threshold where they won't reorg, what prevents the malicious parties from producing blocks right at the threshold and making one half of the network stick to one chain, one half to another?  And most importantly, a NXT node that has been offline for seven months comes back, how does it know what chain to follow?  If there are protections here what assumptions do they make and how might they fail? Costless simulation isn't the only problem that arises out of nothing at stake, but its one of the simplest seemingly hard to resolve.

If you're going to not only claim that you've solved those cases but that the solution is both "secret sauce" and trade-off free I'm going to have to say bullshit. If someone else is making those kinds of claims to you and you buy them, I've got a nice bridge to sell you.

[jonald_fyookball]

so whats the ETA on delivery of the secret sauce so we can all taste it?

[mczarnek]

Point is though, this works in a completely different way to Bitcoin and the nothing at stake problem doesn't apply here because it works so differently.

Bitcoin is not a POS coin so it's a bit weird to say that a thing that is completely inapplicable to Bitcoin is inapplicable to your thing because its different from Bitcoin, especially if that reason is "secret sauce".

The simulation example is probably the hardest to convincingly wave away. Say tomorrow half the NXT value holders decide to sell their coin. Six months after that their old NXT keys fall into evil hands. The evil people create a fork of the NXT chain and in seconds mine it up to the current day. How do existing nodes know not to reorg onto the new one? If there is a threshold where they won't reorg, what prevents the malicious parties from producing blocks right at the threshold and making one half of the network stick to one chain, one half to another?  And most importantly, a NXT node that has been offline for seven months comes back, how does it know what chain to follow?  If there are protections here what assumptions do they make and how might they fail? Costless simulation isn't the only problem that arises out of nothing at stake, but its one of the simplest seemingly hard to resolve.

If you're going to not only claim that you've solved those cases but that the solution is both "secret sauce" and trade-off free I'm going to have to say bullshit. If someone else is making those kinds of claims to you and you buy them, I've got a nice bridge to sell you.

No, I'm saying that the algorithm I've discussed should largely provide that protection but is more to come that has been largely discussed but not as openly.

I highly recommend the link I posted as they, especially Come-From-Beyond knows what he is talking about better than I do.

How does Bitcoin solve people downloading the wrong chains?  You could simulate the Bitcoin blockchain from genesis block with less forging power, the difficulty would therefore be lower and people would download the wrong one, right?  Surely the current miner doesn't pass back all the info needed to build a chain from the genesis block every time he solves a hash, right?

[gmaxwell]

How does Bitcoin solve people downloading the wrong chains?

The new block refers to the prior block. If you don't know the prior block you fetch that too, until you connect to the chain you know. Because the rate of difficulty change is capped a possibly longer chain cannot have difficulty below some threshold (since it can't just be minimum diff blocks), so creating a long bogus fork would be very very expensive. If you did go and make a long bogus fork that was shorter than the real ones, nodes would happily go and fetch them (not saving the blocks) back to where it connects and then realize that it was shorter and just reject it, so the harm would only be wasting bandwidth.  They might download some of the wrong one, but they'd notice when exposed to the right one and deterministically switch to it. This logic is used every day with ordinary 1/2 block forks.

If there ever were a large number of attacks trying to waste nodes bandwidth with expensively created short forks— it's possible to construct log() scale proofs of a blockchains' whole difficulty... we need to have them for some other applications in any case, and they could be employed there.. but considering the cost of the attack and the minimal effects, I doubt that will ever be required.

[DeathAndTaxes]

How does Bitcoin solve people downloading the wrong chains?  You could simulate the Bitcoin blockchain from genesis block with less forging power, the difficulty would therefore be lower and people would download the wrong one, right?  Surely the current miner doesn't pass back all the info needed to build a chain from the genesis block every time he solves a hash, right?

You can trick a node into download a chain with less difficulty, but you can't trick the node into using it.  The former is a potential resource wasting attack, the later is required to defraud nodes.

This attack is most disruptive against bootstrapping nodes (because the difficulty was low for a very long time) which is why many clients use checkpoints to limit the disruption a node can accomplish.  It is important to understand that even without checkpoints a peer will still be able to determine the chain with the longest difficulty it just may take additional resources.  Bitcoin nodes may be a little too trusting and they can be hardened against "disrputors" but I doubt it will ever become a useful attack.  Even if a node is naive an entire chain of headers it is only 8MB per 100,000 blocks (two years of blockchain history) even modestly "smart" nodes can limit the scope significantly and thus put an upper bound on the resources a disruptive node can waste.

[DeathAndTaxes]

The way Nxt does it is actually quite clever and solves the nothing at stake problem, there is more to it than this but the part of it that I understand is that choosing who forges next is every forger does SHA(last forger public key) Somehow how long ago an account forged and how many nxt owned by that account and information from the last block is factored in as well.  The winner is the one who has the largest hash.

Saying you know something is solved because of "somehow" kinda implies you don't know it is solved right?

The network can't require a specific account solve a given block as if it did then it would be easy to halt the chain by just not solving a block when it is your turn.  The network instead favors one block over another one at a given height.  However what happens when both chains have blocks that are worse than the block on the other chain at a given height.  Ultimately the attacker (which had 51% of the stake at the point of the split) will build the best chain overall despite each chain having better or worse blocks at any given height.  

Does the secret sauce in NXT prevent a 51% attack by a stakeholder who had a majority of the stake but no longer has it?  Maybe.  Saying "somehow" or "secret stuff" makes it stronger is hardly compelling though. No explanation of what is publicly available provides a credible reason why the network can't be attacked.  If it really does solve it then eventually it will be publicly available and clear to everyone right?

[gmaxwell]

Does the secret sauce in NXT prevent a 51% attack by a stakeholder who had a majority of the stake but no longer has it?  Maybe but saying "somehow" isn't sufficient.  No explanation of what is publicly available provides a credible reason why the attack does not work.  Claiming it is solved based on what is not publicly available is well not very useful.  If it really does solve it then eventually it will be publicly available and clear to everyone right?

A key point here isn't that I believe it's impossible— it's that I believe its impossible absent some trade-off— some other attack the system becomes vulnerable to, for example— or consideration/cost, or assumption (e.g. that no past majority of shareholders will ever act against the interest of the system, even if they've long since left it), so what exactly is that tradeoff?  Keeping the solution secret also implies keeping the vulnerabilities it creates secret, which means that people will be all the more exposed to them.

[dogisland]

The way Nxt does it is actually quite clever and solves the nothing at stake problem, there is more to it than this but the part of it that I understand is that choosing who forges next is every forger does SHA(last forger public key) Somehow how long ago an account forged and how many nxt owned by that account and information from the last block is factored in as well.  The winner is the one who has the largest hash.

That's not how I understand it from looking at the code. You don't so much choose who forges next, rather the node can decide wether a block is valid or not.

For the block to be excepted.

1. Hash the hash of the previous block.
2. Take the first six bytes of that. Let's call that rnd_selector
3. Take the current time since the last block in millis i.e. 100000
4. Take the effective balance of the account that generated the block.

If balance * time_in_millis > rnd_selector then the block is valid.

Code here https://bitbucket.org/JeanLucPicard/nxt/src/046e59e4df43309a37c2789efd39dba4a873bbe2/src/java/nxt/Generator.java?at=master#cl-160

Basically any account that meets the above criteria can generate the block, if no one can (or someone is offline)  time_in_millis will grow and eventually someone will be able to generate the block.

So to build a competitive chain in NXT, I would have to alter the block message so that rnd_selector keeps on selecting one of my accounts.

The above was drawn from the code so perhaps one of the NXT guys would clarify if this is inaccurate.

[telepatheic]

For the block to be excepted.

1. Hash the hash of the previous block.
2. Take the first six bytes of that. Let's call that rnd_selector
3. Take the current time since the last block in millis i.e. 100000
4. Take the effective balance of the account that generated the block.

If balance * time_in_millis > rnd_selector then the block is valid.

My understanding based on this code is that I can sign a new block if:

base_target * my_balance * time_in_millis > SHA256(previous_block_signature + my_public_key)

So you can very easily iterate through thousands of possible current block signature such that it is guaranteed that you will be the person able to mine the following block. Since the whole process is transparent (public keys and balances are known to everyone), a moderate amount of computation power and coins assures that once you get to create one block you can sign all the blocks following it.

I'm not an NXT developer so I may be wrong.

[ChuckOne]

For the block to be excepted.

1. Hash the hash of the previous block.
2. Take the first six bytes of that. Let's call that rnd_selector
3. Take the current time since the last block in millis i.e. 100000
4. Take the effective balance of the account that generated the block.

If balance * time_in_millis > rnd_selector then the block is valid.

My understanding based on this code is that I can sign a new block if:

base_target * my_balance * time_in_millis > SHA256(previous_block_signature + my_public_key)

So you can very easily iterate through thousands of possible current block signature such that it is guaranteed that you will be the person able to mine the following block. Since the whole process is transparent (public keys and balances are known to everyone), a moderate amount of computation power and coins assures that once you get to create one block you can sign all the blocks following it.

I'm not an NXT developer so I may be wrong.

What do you mean by iterating through thousands of possible current block signatures?

[telepatheic]

What do you mean by iterating through thousands of possible current block signatures?

Signatures are dependent on the data they are signing and my public key, my public key is fixed but the data I am signing is not. I can add and remove transactions to the block to change the output of the signature. (Technically with ECDSA signatures you don't even need to do that, you just change the nonce used in signing to get a different signature)

[ChuckOne]

Signatures are dependent on the data they are signing and my public key, my public key is fixed but the data I am signing is not. I can add and remove transactions to the block to change the output of the signature. (Technically with ECDSA signatures you don't even need to do that, you just change the nonce used in signing to get a different signature)

The generation signature only depends on the previous block generation signature and your public account number. Nothing more.

Part of the generation signature (called hit) is used to determine a queue of forgers. First in this queue is allowed to forge. If he did not, it is the turn of the second in the queue and so on.

[DeathAndTaxes]

Signatures are dependent on the data they are signing and my public key, my public key is fixed but the data I am signing is not. I can add and remove transactions to the block to change the output of the signature. (Technically with ECDSA signatures you don't even need to do that, you just change the nonce used in signing to get a different signature)

The generation signature only depends on the previous block generation signature and your public account number. Nothing more.

In a double spend attack (including a "51% attack) the attacker would be the one generating the sequence of blocks.  That means each block relies on the prior block also made by the attacker.  The attacker signs a block and if it doesn't allow him to forge the next block, just keeps resigning it until it does (as pointed out a single digest can have an infinite number of unique signatures by changing the k value). The attacker attempts signatures until he produces a one which allows him to sign the next block as well.  The attacker then moves on to the next block.  If this seems kind of like a PoW it is.

Part of the generation signature (called hit) is used to determine a queue of forgers. First in this queue is allowed to forge. If he did not, it is the turn of the second in the queue and so on.

The attacker won't be publishing his chain until it is longer. As long as one of his accounts is valid for signing the next block (and thus somewhere in the queue even last) there will be nobody ahead of him in the queue that knows about the block.  The network doesn't require a specific signer from the queue be used, it just favors a higher signer over a lower one but all signers are equally valid.  If the attacker had* >51% of the network stake e will produce the longest/best chain.  Note: it isn't actually a "queue" but this doesn't materially change the scenario.

As a side note: deterministic (or quasi deterministic) signing/minting/forging is an interesting idea.  It has some advantages but it isn't some magical 51% proof shield and the "nothing at risk" issue around PoW remains unchanged when compared to other PoS systems.

* It is "had" not "has" because in PoS the critical resource is not a physical item, it is a record in the blockchain. A miner who no longer has any hashpower can no longer mine but a forger who had but no longer has a stake can forge a parallel chain starting from where he had the stake and double spending the tx resulting in him losing the stake. An attacker with 51% of the stake as of block X can sell that stake and still perform a 51% attack starting from block X using the stake he had but no longer has on the main chain.

[telepatheic]

A 51% attacker would be the one generating the previous block generation signature.  If the signature doesn't produce an output that allows him to sign the next block he just changes the k value and generates a new signature.  A good CPU can do 40,000 ECDSA signatures a second (per core).  When he finds one that allows one of his accounts (51% of the stake) to sign the next block he moves on to the next block.

The attacker doesn't even need a 51% stake. They only need a small stake, once you can forge once, you can ensure that you will always gets to forge the next block (if you have enough computational power), regardless of how small your stake is. I can easily see this attack being possible with 0.1% stake and a standard processor.

As a side note: deterministic (or quasi deterministic) signing/minting/forging is an interesting idea.  It has some advantages (outside of a 51% attack) if combined with a PoW.  It would make long reorgs with a minority of the hashrate more difficulty to achieve which means confirmations have more "weight".  It also allows "legit" miners to achieve consensus quicker.  In the case where two miners produce blocks at the same block height it could provide a fair and deterministic manner for all nodes to choose one over the other. If miners are confident that 51% of the network follow these rules then they would be best served by working on the "best" block not just the first one.  It is beneficial in a split to get the network behind a single chain as quickly as possible (orphaned work is simply wasted work and reduces effective network security).  The full implications both good and bad should be looked at more closely.  It isn't however some magical 51% proof shield and the "nothing at risk" issue around PoW remains unchanged when compared to other PoS systems.

The problem is that you are still vulnerable to historic attacks. Whilst doing analysis for conceptcoin I have found that deterministic proof of stake (even where the mechanism to select who gets to sign each block is unaffected by the actions of the forgers/miners) is still vulnerable to people signing two blocks at a given block height and releasing one of those blocks whilst keeping one hidden to build an attacking chain in the future. Whilst clients who are always online can tell the difference between the real and fake chain, new clients can't.

One way to tell them apart is by assigning work to the chain, this work does not decide who gets to sign blocks. I have proposed a scheme where when a block is being signed it must optionally include a piece of work which is as close to the previous block hash as possible. This work doesn't have to be produced by the signer themselves, everyone submits work to the network to show that they endorse a particular block. It is in the interest of the honest block signers to include the maximum amount of work in their blocks in order to prevent attacks.

Now new clients can see which chain is more likely to be the real one by measuring the cumulative work included in each chain. This successfully decouples proof of work from the rewards handed out, people do work as they feel necessary to secure the network. The problem is without direct economic incentives, the amount of work done and hence security may be very low.

[DeathAndTaxes]

The attacker doesn't even need a 51% stake. They only need a small stake, once you can forge once, you can ensure that you will always gets to forge the next block (if you have enough computational power), regardless of how small your stake is. I can easily see this attack being possible with 0.1% stake and a standard processor.

I agree with the fact that it can be attacked with less than 51% stake.  How little stake can be used depends on a couple of factors.  The time since last signing and balance are weighted in the "difficulty" of finding a hash so I am not comfortable putting an exact value on how little stake can be used.  That would require some simulations. 

In general though one could say that the structure allows a forger (any forger) to use computing power as a proxy for stake.  The effective share of the network is dependent on not just what share of the stake one has but also what share of the computing power.

While NXT claims to not be PoW if forgers aren't already using computing power to boost their returns they will.  Even non malicious miners would have no incentive to not increase their computing power in order to boost their forging rate.

As a side note: deterministic (or quasi deterministic) signing/minting/forging is an interesting idea. ... The full implications both good and bad should be looked at more closely.

The problem is that you are still vulnerable to historic attacks. ...

That is a good point.  I agree and it requires some careful analysis.  I do think it an interesting idea and has some potential.  On your idea of cummulative work it may be possible to incorporate a way to compensate those worker.  I also believe despite my reservations about PoS that there is some way it can be used in conjunction with PoW to raise the cost of an attacker.  PoW for Bitcoin is already beyond the point where any economic attack is possible however there is the non-economic attack.  The network will continue to grow and as miners become more efficient ($/GH and J/GH) the cost for an attacker will rise but eventually margins will be paper thin and further improvements will be limited to the growth of the reward (Moore's law doesn't make the network more secure as it is kinda like GH inflation).  I believe PoS could be used to raise the cost for an attacker further.  To date all the concepts I have sketched out have limitations I a find unacceptable but I believe there is a solution. Imagine if someday the hardware cost to attack the network was $5B but it also required another $50B in stake as well.

[bluemeanie1]

I believe PoS could be used to raise the cost for an attacker further.  To date all the concepts I have sketched out have limitations I a find unacceptable but I believe there is a solution. Imagine if someday the hardware cost to attack the network was $5B but it also required another $50B in stake as well.

Here you are admitting that Bitcoin as it stands has a significant weakness.

-bm