Talk:Proof of Stake

Malicious forking

Surely proof-of-stake is vulnerable to malicious forking of the blockchain, whether motivated by double spending or just sowing destructive confusion of multiple versions?

Each version of the blockchain is a full, self-contained "version of reality". If you (the malicious party engineering a fork) burn through your "stake" - whether bitcoins owned, bitcoin days destroyed, or anything similar - on one version of the blockchain, that still doesn't stop you creating another version, starting from the same block-before-yours as you started from for your first effort, where your same "stake" still exists and hasn't been burned through. (And then another, and another... All forking from the blockchain-as-was (just before you started your malicious antics), which records your untouched stake.) So with trivial computational effort, you can create huge multiple forks; and there's no easy way for the network to pick a winner.

Proof-of-work doesn't suffer from this problem. A malicious party trying the above trick would have to perform fresh work for each fork, since the work done in finding a difficulty-satisfying hash on one fork has no transferable value to the task of finding one on the other fork(s).

Am I missing something? Iain Stewart 23:24, 24 March 2012 (GMT)

This is a good point, but perhaps what you are missing is the mixed proof-of-stake/proof-of-work concept. Your argument applies to pure proof-of-stake, but I don't believe that it applies to a mixed proof-of-stake/proof-of-wrok system, even one where work is a very small component. Please let me know if you think otherwise. Here are some thoughts:

1) The creation of multiple forks is only a problem if there is doubt about which chain is the correct one. This happens when multiple chains have equal cumulative difficulty (measured as the sum of all difficulties in the chain). In the case of a tie in cumulative difficulty, other miners can pick a chain to extend at random. One well-intentioned miner will get lucky and find the first block after the attacker. He will pick one of the attacker's chains, extend it, and broadcast this to the network. Even though they may have been working on other chains before, other miners will also extend this chain because it is now longer and thus more likely to survive. As usual, users awaiting txn confirmation just wait for a chain to become sufficiently long that there is no significant probaility that it will get overtaken. Once this happens, txns become extremely costly to reverse.

2) Perhaps you are worried that all other miners will extend every single competing chain. If so, all chains will grow at the same rate and it won't work to pick the winner at random. This is a problem in pure proof-of-stake. As you point out, in pure proof-of-stake extending multiple chains simultaneously has no resource cost. However, under a mixed-system, there is a non-trivial work component to any chain extension. Miners would not find it worthwhile to extend chains that have a low probability of becoming the dominant chain. I think even a pretty small computational cost would be sufficient to discourage this. Cunicula 27 March 2012

Thanks for your reply Cunicula, and apologies for taking so long to even acknowledge it. (I log in rather intermittently, although hopefully I'll be logging in more often now that I'm working on my adaptive difficulty proposal. [and (edit 2012-05-21) a stake-based proposal which seems to achieve the impossible and stand up to a >>50% attack! see teaser section at end of adaptive difficulty page for now...]) I'll not try to form a proper opinion of the mixed work/stake case until I've cleared my mind of some, ah, heavy-going skeptical Bayesian analysis of my own proposal (which for now is entirely within the proof-of-work universe, by the way, so not directly relevant here); but yes, thank you for making the general point that the mixed case is likely to be more robust than the pure stake case. Iain Stewart 22:23, 6 May 2012 (GMT)

Proof of stake - done right - is maybe, just maybe, the way to eliminate 51% (even 90%!) attack worries altogether!

The vigorous debate about which of various systems, on a spectrum from pure proof of work to pure proof of stake via hybrids in between, is very enjoyable and thought-provoking. But when all is said and done, the evaluation process always boils down to "which system is least likely to allow the horror of a 51% attacker getting total control?". It's just assumed, by everybody as far as I can tell reading through the forums etc, that a 51% attack is a sure-fire route to total control, and that there's nothing anyone can ever do about that.

(And make no mistake, total control will not stay benevolent, even if it starts off that way. The temptation of the total controller to start acting exactly like the banking system as we know it today - inventing ever more elaborate rules for what sort of transactions it will deign to process, how much it feels like "knowing" about its "customers", and so on - and, beyond that, the temptation of the political system to put unstoppable pressure on the controlling entity to do all these things and more - will be huge, permanent and irresistible. "Decentralisation" will become worthy only of a hollow laugh.)

But, I would like to ask: are we thinking imaginatively enough about this? What about seeking a protocol where even a much more than 50% attack still fails? (Where the "%" figure refers to whatever the scarce resource is - work, stake, an optimum Cobb-Douglas mix of the two in a hybrid system... whatever.)

It's been taken as "obvious" that a 51% attack will succeed. One unit of the scarce resource is the same as another, and 51% beats 49%, and that's all there is to it! But proof of stake means the scarce resource is not the fungible "stuff" we're used to from proof of work. Stakeholders (unlike proof-of-work miners) are pseudonymously trackable. (They sign with a pseudonymous identity when they supply bitcoin days destroyed into a coinbase transaction, or whatever similar thing they have to do to establish they're a stakeholder.) And they can't cheaply change their pseudonymous identity (sloshing bitcoins around before landing them on a coinbase throws away all those lovely bitcoin days that could have been destroyed into the coinbase).

This opens up wonderful new possibilities. We no longer have to compute the "height" of a candidate blockchain as just the sum of atomistic contributions from each block (like the sum of their difficulties, in the case of the current Bitcoin). We can reward preferred structures and patterns in the way the pseudonymously-trackable stakeholders are interleaved in the chain.

In particular: we can reward "closeness", in some mathematical sense yet to be pinned down, to a sort of proportionality or "fair sharing" pattern - so that, for example, a 10% stakeholder who hasn't yet come near 10% occupation fraction of any recent candidate blockchain (maybe they haven't started mining at all) is deemed to contribute more chain height than an atomistic sum formula would have given, for each block they do now put in and help bring their share closer to the "ideal" 10%. And conversely, if they overshoot and already have 15%, a structure-aware chain height formula can allocate less chain height for the overshooting contribution than an atomistic formula would have given.

I believe that if we choose such a formula cleverly, we may well be able to protect against attacks that have been considered an obvious lost cause - 51%, 80%, 90%. For note that the attacker(s), say with 90% of the stake resource, and the honest miners, with the remaining 10%, have asymetrically different goals.

The attacker, or attacker cartel, wants the frisson of sheer, unadulterated power. Power to starve rivals and enemies by mysteriously never quite accepting their bitcoin transactions; power to accept and reject transactions on whim; power to bring down Bitcoin altogether by just not accepting any transactions (or accepting/rejecting so whimsically and arbitrarily that the system becomes unusable). To achieve this power, the attacker has to keep all blocks generated by the honest 10% out of the winning blockchain. (If even an occasional one got through, in a way the attacker couldn't reverse, it would of course include all the accumulated pool of "ordinary, reasonable" transactions the attacker is trying to reject - the 10% just want to earn an honest profit by collecting all those fees.)

By contrast, the honest 10% do not have to aim for the symetrically opposite goal (of excluding the malicious 90%). They merely have to aim for achieving a reasonable interleaving of their honest blocks into the winning blockchain. Then ordinary users will get their transactions handled (albeit more slowly than they might have got used to); and the honest miners will collect their fees.

The challenge, then, is to design the structure-aware chain height formula so that the attacker's would-be chain loses (even though, of course, a mere sum of stake-achievements block by block would allow a 90% attacker to effortlessly win). The idea is that, if closeness to fair share interleaving is being especially highly rewarded, then the attacker's chain gets penalized for being far away from fairness: the 90% have 100% occupancy, and the 10% have 0%. The competing chain with some honest blocks here and there gets strongly rewarded (say for example the 90% have 93% and the 10% have 7% - that's closer to fair shares than the attacker-only chain). It wins!

The exasperated attacker fumes, "Why the hell can't I reverse these pesky honest blocks? I'm deploying 90% of the network's entire power! My chain without them should be the winner!" Ah, but structure-awareness is rewarding their presence and penalizing their absence. And with a strong enough such effect, who knows, perhaps any percentage level of such a style of attack can be thwarted!

I've created a draft page, Proof_of_blockchain_fair_sharing, for ideas fitting into this general milieu. At the moment it just has a teaser description of the general idea (pretty much similar to what you've just finished reading here). I had hoped to spring a polished structure-aware height formula on the world; sadly, my first effort I believe has subtle economies and diseconomies of scale (giving stakeholders perverse incentives to either club together, cartel-like, or disaggregate, taking on multiple pseudonymous identities each). That's not the end of the world perhaps - especially since the whole point of this revolutionary new approach is that a cartel (even going above 50%) is no longer something to be terrified of - but I'd prefer long-run linearity [scale-neutrality] if possible. More importantly, I now also believe my first effort doesn't achieve a strong enough bias in favour of fair-shares chains to make much difference (it maybe means a 67% attack is needed to gain total power, rather than 51%... mildly helpful I suppose, but I still aspire to the dream case where no finite attack succeeds in the long run).

Naturally, I'm hoping to invent a formula that achieves the miracle of letting any honest minority, no matter how small, achieve a non-zero occupation fraction of the winning chain. (Their achieved occupation fraction might not be exactly the "fair" one; but any non-zero fraction would let Bitcoin continue, albeit slowly and creakily, and with luck the attacker eventually concedes defeat.) But I thought it only fair to throw open this challenge to all mathematically-minded Bitcoin folk - after all, others are doubtless far more talented than me! Iain Stewart 16:41, 21 May 2012 (GMT)