Unclear assertion re Nakamoto consensus about cosmos HOT 28 CLOSED

This is not a public chain.

I want to define "public chain" differently than most... Some say that a "public chain" requires permissionless participation by those committing blocks (e.g. miners). I think this should be revised, because at the application-logic layer in Bitcoin, only those with coins can commit valid transactions. So holding tokens does not make a "permissioned" system, but it's still considered "permissionless". Likewise, requiring staking tokens to be a validator might still be "permissionless", as long as validators don't collude to censor new validators from bonding.

So, I like to say that in a Gnuclear-like proof-of-stake system, whether the blockchain is public or private depends on the will of the current stakeholders.

from cosmos.

Oh sure!

from cosmos.

ye. you can assume block latency is much greater than network latency because producing blocks is economically expensive (takes around ten minutes). if you can break the economic factor with unlimited hash power or breaking the hash function, the synchrony assumption crumbles because you can make blocks as fast as you want.

of course, additionally, bitcoin hedges the failure of its synchrony assumption with the randomness of the PoW lottery, so we can eventually make progress with high probability no matter what.

If normal PoW is a weak synchrony assumption (because it says only that net. latency is much less than block latency) then my intuition is that ghost is a means to strengthen the assumption (ie. net latency is a little less than block latency), possibly at the risk of making it more difficult to ensure you get convergence with probability 1 in the event of synchrony failure

from cosmos.

Oh sure!

🎉🙌🎊😄

from cosmos.

My head is overloaded with this right now, and so I'm going to take a nap and then re-focus on work, but real quick, just realized:

There are two totally separate concerns/concepts that seem to be getting mixed up sometimes in the language:

1. The number of node failures that Tendermint can handle. This is where the 1/3, 3t + 1 seem to make sense.
2. The amount of stake that votes for something.

These are two completely different concepts.

It can totally be fine to say, require that 80% of the stake must be behind a proposal for it to pass, and then go on talking about byzantine actors—where in this context "byzantine actors" does not mean 'byzantine actors' (as far as I can tell) but node failures / network partitions.

I think you guys can figure this stuff out and word it better than I can, but, this seems like a vital/important point of confusion in the existing documentation that needs to be cleared up.

Thanks for all the super helpful commentary helping me wrap my head around all this!

goes to nap

from cosmos.

@taoeffect Updated wording: 33df4cd

from cosmos.

"and the communication is synchronous" is the second of two qualifications in this sentence where in the juxtaposition it stands alone so that is at least one difference. and Afaik Actually what is unclear is it isn't actors at all but the amount of bonded stake. It's only actors if all actors have an equal amount of bonded stake. Remember proof of stake.

from cosmos.

and Afaik Actually what is unclear is it isn't actors at all but the amount of bonded stake. It's only actors if all actors have an equal amount of bonded stake. Remember proof of stake.

Yes I remember, but that can equally be modeled by forcing the stake into equal chunks.

I.e. if there's a validator with 30% stake bonded, and everyone else has 10% of their stake bonded, then that validator can be thought of as three validators voting in unison.

Another (clearer) place where this fundamental difference shows up is in the permissionless nature of PoW. Whereas you can always participate in PoW, the same is not true of PoS or BFT.

from cosmos.

Sure they are fundamentally different. Known actors may choose to participate or not. Unknown must be whitelisted. That's my basic understanding. This is not a public chain.

from cosmos.

That last bit, "and the communication is synchronous", seems to stand in contrast with the statement made in the blog; i.e. indicating that even a synchronous environment can only handle 1/3 byzantine actors.

Yeah that's a really good point. That quoted section is referring to a message-passing system without cryptographic signatures. (The paper came out before even RSA became well adopted, I believe). The next section says that with signatures, any number of Byzantine nodes can be tolerated. For the latter, the intuition is that once you've received all the signed messages, you can know whether a person is a traitor or not.

But with PoW, the cost of producing a block is incurred prior to generation, so it doesn't have the same element of lying or double-signing as in PoS or the signed-messages-scenario of Lamport's paper. It is possible to create a malformed block, or one that violates the rules, or even one that attempts to fork the longest chain, but in theory the longest-chain scoring rule works as long as the honest nodes are >= 51%. (Except http://arxiv.org/abs/1311.0243, and maybe there's been counter-arguments to that).

But if the network were partially-asynchronous, with perhaps even long delays in messaging, or a very slow network, or occasional network-partition, such that we can't assume that a block can be broadcast with 100% certainty, even Satoshi Nakamoto's proof goes out the window, even with shorter block times. So that's what was meant.

This person on YCombinator said it best (https://news.ycombinator.com/item?id=7553418):

Anyone who thinks GHOST is a good idea, has not understood Bitcoin at all. the whole point of the blocks is that nodes can work on the global state in a chain. so the idea that nodes should work on greedy subtrees is about the worst possible idea. Bitcoin solves not only the Byzantine generals problem, but a latency variance problem, to achieve logical broadcast.

I don't believe any GHOST-like scheme can help get around the latency variance problem, with PoW. Do you know any good peer-reviewed studies that dive into partial-synchrony and how it affects PoW?

from cosmos.

Actually, I believe that Lamport shows that byzantine generals have a solution with only 3 generals (including 1 traitor) if they can use signatures and the network is synchronous (http://research.microsoft.com/en-us/um/people/lamport/pubs/byz.pdf). If they can't use signatures, then even if the network is sync they need 3f+1, but with synchrony and signatures you can do it.

I believe the way to understand bitcoin is that it relies on economics to secure a synchrony assumption. Hence it ought to be able to work with majority hash power, but as others have shown, subtleties in the economics mean fractions of majority can mount successful attacks. I don't think the important thing is that it is based on % computation vs % actors, but that computation is dominated by an economic element (which induces this magic synchrony thing). Indeed, it would seem Casper is an attempt to bring that fine grained economics to PoS my putting value at stake with every signature.

from cosmos.

Interesting about GHOST. My intuition now around GHOST is that the economics of normal PoW let you make a weak synchrony assumption (message latency << block latency), and that GHOST lets you strengthen it, if you get the economics right

from cosmos.

Can you elaborate on "the economics of normal PoW let you make a weak synchrony assumption (message latency << block latency)"? So it's still assumed that block-latency is much greater than network latency. (That still sounds like a synchronous system, strictly speaking)

from cosmos.

So, I like to say that in a Gnuclear-like proof-of-stake system, whether the blockchain is public or private depends on the will of the current stakeholders.

Ah yes I do realize that I meant that one should absolutely be aware it is not a public chain in the traditional sense of Bitcoin or Ethereum where anyone can just pick it up do whatever they want without being held directly accountable through bonding .

from cosmos.

That still sounds like a synchronous system, strictly speaking

Yes, sorry. I just mean the assumption itself is a weak one (we expect message latency to be an order of magnitude or two below block latency). Not "weak synchrony" as in DLS partial synchrony or the ilk.

from cosmos.

So really it's a synchrony assumption of the form:

"block latency is X greater than message latency". By making block production more expensive, we can increase X, thus weaking the network latency (ie. messages can take longer). Since Bitcoin block production is really expensive, messages can take minutes to be delivered, a pretty weak assumption about the network. With ghost, blocks are made cheaper, so they come faster, and thus messages must be delivered sooner (a stronger assumption). To make this more likely, additional economic elements are added in (rewards both for including uncles and having found them). PoW is clever because it uses economics to motivate synchrony, and relies on randomness to recover when synchrony fails!

from cosmos.

aye, this byzantine stuff is making my head spin. I'm only just now becoming more familiar with it.

I still feel there's something off about the original language:

This means that if 1⁄3 or more validators are Byzantine, they could halt or fork the blockchain ledger. Satoshi Nakamoto wrote that Bitcoin can handle up to 1⁄2, but that only works because clients are suppose to wait on the order of an hour for confirmation, thereby allowing the network to be modeled as a (slow) fully-synchronous system.

There is this talk of "validators are Byzantine" business there. That doesn't have much meaning in PoW. I disagree with @ebuchman, and still maintain that the fundamental difference here is that it's % computation vs. % actors. The "economic element" @ebuchman mentions seems to exist in both bonded-PoS and PoW, so it's not what really distinguishes them.

but in theory the longest-chain scoring rule works as long as the honest nodes are >= 51%.

Again, here's that word, "honest nodes"... and even if something along those lines might have appeared in Satoshi's paper, all of his math was not based on nodes, but on computation. That "hour" (i.e. 6 conf figure, which is just a recommendation), has absolutely nothing to do with nodes, and everything to do with expended work (computation).

There could be 100000 byzantine nodes in Bitcoin and 1 honest one. It doesn't matter. As long as that 1 honest one has a bigger rig than the rest of them combined, he wins.

from cosmos.

the "economic element" @ebuchman mentions seems to exist in both bonded-PoS and PoW, so it's not what really distinguishes them.

Its a different kind of economics. PoW incurs the economic cost first, PoS only later, and only if you misbehave. Casper moves toward PoW on the spectrum by forcing validators to take gambles towards the beginning of rounds - ie. you can still get punished in Casper for being honest (like in PoW), but not in Tendermint.

I still think this is what's significant about % computation (economics before and always) vs agents (economics after and only if you misbehave). Of course the computation bit solves the long-range nothing at stake, but I think that's another discussion

from cosmos.

As long as the hashing power behind the honest nodes is >= 51%

from cosmos.

I find it very confusing how language that was meant for BFT-style consensus is being applied and used in the context of PoS and PoW.

BFT-style consensus is not weighted by anything, but PoS and PoW is (stake & computation, respectively).

In BFT, therefore, the number n plays a huge and meaningful role.

There are important equations and numbers that are based on this n, like 3n > t and 1/3, etc.

But all of those equations and numbers fly out the window the second you start weighting your votes!

cries

from cosmos.

At the very least ya'll need to replace every instance of "validators" and "nodes" with "stake". Otherwise the documentation doesn't make any sense.

from cosmos.

@taoeffect don't throw it out the window! If a validator in Tendermine PoS has 100 voting power, it can be modeled as 100 nodes in traditional BFT, all voting simultaneouslt. The same equations work.

A Byzantine miner could be one that is intentionally mining on the wrong chain, to disrupt consensus.

@ebuchman I see, about rewarding for block discovery. Fair to say that it doesn't actually help in active adversary network disruptions?

from cosmos.

@taoeffect don't throw it out the window! If a validator in Tendermine PoS has 100 voting power, it can be modeled as 100 nodes in traditional BFT, all voting simultaneouslt. The same equations work.

I won't throw it out the window if you change this:

This means that if 1⁄3 or more validators are Byzantine

To say:

This means that if 1⁄3 or more stake is Byzantine

& similar throughout the entire document.

from cosmos.

This means that if 1⁄3 or more stake is Byzantine

That's definitely always the intention. The analysis is mostly the same, just simplified if we weight them equally. But in certain places there are important caveats like "at least one honest node" where we're not talking about stake, but witnesses.

@ebuchman I see, about rewarding for block discovery. Fair to say that it doesn't actually help in active adversary network disruptions?

you mean GHOST? It helps in the sense that it more explicitly rewards being able to connect across partitions, "disrupt the disruption" if you will (ie. if you can see someone elses block and include it, you both get rewards). But I think actually tuning GHOST is really difficult and still a wide open problem.

from cosmos.

I think in a public blockchain everything being economically weighted, whether by work or by stake, is kinda implied.

from cosmos.

Here's the GHOST paper, it goes into latency considerations, but I don't know yet what it means for tx finality, or the contended statement that taoeffect pointed out about PoW.

https://eprint.iacr.org/2013/881.pdf

Vbuterin, thoughts?

from cosmos.

@jaekwon Awesome! Surprised you got that done so quickly. On a quick skim through the changes look good. 😄 👍

from cosmos.

I'll close this issue for now, but I recommend also (just to avoid any upset and/or legal issues) updating the copy on the blog/website as well at some point.

from cosmos.