Topic: Decentralized Timestamp - page 4. (Read 5325 times)

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.

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.

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?

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.

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.

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?

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

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.

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/

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.

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.

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.

The central issue with proof-of-stake is that when the chain forks, the stakeholders on the left side of the fork, with very few exceptions, are also stakeholders on the right side of the fork.  Whichever fork wins, they still have their stake.  In fact, they have an incentive to use it to mine both sides of the fork at once.  There's literally no rational reason for them not to; whichever fork eventually fails is eliminated from history, but until they know for sure which one that's going to be, why would they stop mining it?  And as a result of that dysfunction, why does a choice between forks ever get made at all?

Proof-of-work is the expenditure of a finite resource (hashing power) in real time.  You cannot use the same hashing power to support both sides of a fork; you are forced by physics to choose one side or the other, and therefore a decision on the local level perforce actually gets made - leading to a decision on the wider level.

The nothing-at-stake problem can be overcome by GHOST protocol or similar; it must not be possible to support one side of a fork without your repudiation or withdrawal of support being visible to the other. 

DeathandTaxes has been schooling us on the same issue in the last 24 hours, I believe.
He makes some good distinctions, as usual:

see here:  
 
https://bitcointalk.org/index.php?topic=27787.80

You've been told some pretty weird stuff then. Nothing has been taken down, and it's not that complicated a point.

In POW to contribute to a consensus you must burn a resource, which means you must make an exclusive choice among all the possible consensus you could contribute to, to the exclusion of all others... and for your effort to not be wasted you should be spending it on the chain you think most likely to survive.  In pure POS schemes, there is no such exclusivity created.  This leads to fun outcomes like old stake holders can exit the system (sell their coins) and then sell their old keys to people go fork off the chain at a point in the past, at no cost to themselves. Someone who is later handed two histories— the real one and the simulated one— cannot distinguish them, they can tell— perhaps— that someone was naughty, but that doesn't help them decide which chain is the good one.  There are a number of other related implications.  A number of different modifications have been proposed, but so far all of them seem to be obfuscation and not actually fix the underlying issue, which seems a bit fundamental.

You can read more about this in Section 5 of https://download.wpsoftware.net/bitcoin/asic-faq.pdf

PPC was attacked utilizing this fact the moment POS mining became possible on it— a savvy miner tried all possible forks finding a sequence of forks which selected their stake as the winning stake as much as possible. PPC prevented this with block signing and discouraged it by hard forking the protocol so that POW blocks were required.

GPS is unauthenticated. Any local-to-you jammer can spoof it with nothing more complex than a USRP and some software. It's also run by US space command, and the US has been quite up front that they are willing to manipulate or disrupt the signal to achieve military objectives, they're able to perform geo-targeted alterations of the signal too.  It's pretty useful on average, but it's not a secure solution by itself.

Don't the GPS satellites transmit an accurate time signal that could be used for this purpose?


Martin

gmaxwell,

  could you point us to some sort of an official statement on the 'nothing-at-stake problem'?  No one seems to really be all that clear on what this problem actually is.  From what I was told the person who first proposed it took it down?  So far I've heard many different takes on this particular subject.

  a big problem for NXT is that the stakeholders in the project are very decentralized, so their 'PR' seems a bit off at times.  There's really no one to handle these kinds of questions and an adopter/investor really has no where to get to them resolved.

thanks, -bm

I'm familiar with that paper and have linked to it on the forum before. Note that Lamport is talking about a distributed system, not a decenteralized one.  As I recall process he describes is not byzantine robust, requires a jamming proof broadcast network, and does not have anonymous membership (the players must be selected in advance, so it cannot meet our definitions of decenteralized— in particular it needs a consensus arbitrary ordering of player identities to break ties).

As far as POS goes, I've not seen anyone tender a solution to the nothing at stake problem, and so I still consider it non-viable for a decentralized consensus. PPC makes it work by requiring POW and using centralized block signatures. NXT was previously making it 'work' by not releasing the complete source to their software, I haven't checked lately.  So far POS schemes all suffer from attacks like former quorums (e.g. people who held coins at some point in the past) can costlessly replace the history by forking off from a point where they did have a quorum after they no longer do, and from things like the optimal income producing mining strategy is to mine all forks (because there is ~0 marginal cost in mining a fork) instead of a single one. Schemes like honesty bonds do not help a node decide between two different networks— the real one and a simulated one, and cannot punish someone if they perform the attack after exiting the network completely.

Very nice!  Will have to further review this paper later.



Read my mind

In fact I think it was one of your posts that lead mthcl to start talking about it with us.. which lead to this post.

Sure.... You meanies only take no for an answer