Talk:Proof of Stake - Revision history

Cunicula: /* Adaptive Difficulty */

2012-11-23T02:23:54Z

Adaptive Difficulty

← Older revision		Revision as of 02:23, 23 November 2012
Line 1:		Line 1:
	== Adaptive Difficulty ==		== Adaptive Difficulty ==
	~~[Edit:~~ Deleted old discussion and am including link to page that summarizes Ian Stewart's ideas:[[Adaptive_difficulty\|adaptive difficulty]]		Deleted old discussion and am including link to page that summarizes Ian Stewart's ideas:[[Adaptive_difficulty\|adaptive difficulty]]

			== New Discussion Here ==

Cunicula: Replaced content with "== Adaptive Difficulty == [Edit: Deleted old discussion and am including link to page that summarizes Ian Stewart's ideas:adaptive difficulty"

2012-11-23T02:23:23Z

Replaced content with "== Adaptive Difficulty == [Edit: Deleted old discussion and am including link to page that summarizes Ian Stewart's ideas:adaptive difficulty"

← Older revision		Revision as of 02:23, 23 November 2012
Line 1:		Line 1:
	== ~~Malicious forking~~ ==		== Adaptive Difficulty ==
			[Edit: Deleted old discussion and am including link to page that summarizes Ian Stewart's ideas:[[Adaptive_difficulty\|adaptive difficulty]]
	~~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?~~ [~~[User~~:~~Ids\|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. [[User:~~Cunicula\|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\|adaptive difficulty]] proposal. ''[and (edit 2012-05-21) a stake-based proposal (or the bare beginnings thereof) which '''seems''' to achieve the impossible and stand up to a >>50% attack! see teaser section at end of [[Adaptive_difficulty\|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. [[User:Ids\|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, for example, a miner or set of miners with 10% of the deployable stake, who so far has ''less'' than 10% occupation fraction of the blockchain (maybe they've barely started mining at all), can have each block they mine (and help bring their share closer to the "ideal" 10%) be deemed to contribute '''more''' incremental height to the chain than an atomistic sum formula would have given. And conversely, if they overshoot and already have 15%, a structure-aware chain height formula can allocate '''less''' incremental chain height for the overshooting fraction 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 '''asymmetrically different goals'''.

	The attacker, or attacker cartel, wants (in the scenario we're traditionally most worried about) to either bring down Bitcoin, or keep it going but with control over what transactions are "acceptable" - e.g. to act like a know-your-customer bank, or to harass targeted persons or economic sectors by rejecting their transactions. To achieve this, 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 symmetrically 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 by comparison (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 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.) To speed up progress, I thought it only fair to throw open this challenge to all mathematically-minded Bitcoin folk - after all, there are doubtless others far more talented than me! [[User:Ids\|Iain Stewart]] 16:41, 21 May 2012 (GMT)

Ids: /* Malicious forking */ made it clear I'm fully aware p.o.b.f.s. is hopelessly unfinished

2012-08-07T23:20:06Z

Malicious forking: made it clear I'm fully aware p.o.b.f.s. is hopelessly unfinished

← Older revision		Revision as of 23:20, 7 August 2012
Line 15:		Line 15:
	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. [[User:Cunicula\|Cunicula]] 27 March 2012		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. [[User:Cunicula\|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\|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\|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. [[User:Ids\|Iain Stewart]] 22:23, 6 May 2012 (GMT)		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\|adaptive difficulty]] proposal. ''[and (edit 2012-05-21) a stake-based proposal (or the bare beginnings thereof) which '''seems''' to achieve the impossible and stand up to a >>50% attack! see teaser section at end of [[Adaptive_difficulty\|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. [[User:Ids\|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! ==		== Proof of stake - done right - is maybe, just maybe, the way to eliminate 51% (even 90%!) attack worries altogether! ==

Ids: /* Proof of stake - done right - is maybe, just maybe, the way to eliminate 51% (even 90%!) attack worries altogether! */ further wording clarity improvements

2012-05-25T04:42:54Z

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

← Older revision		Revision as of 04:42, 25 May 2012
Line 29:		Line 29:
	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.		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''' incremental chain height~~, ~~for~~ each block they ~~''do'' now put in~~ and help bring their share closer to the "ideal" 10%, than an atomistic sum formula would have given. And conversely, if they overshoot and already have 15%, a structure-aware chain height formula can allocate '''less''' incremental chain height for the overshooting fraction than an atomistic formula would have given.		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, for example, a miner or set of miners with 10% of the deployable stake, who so far has ''less'' than 10% occupation fraction of the blockchain (maybe they've barely started mining at all), can have each block they mine (and help bring their share closer to the "ideal" 10%) be deemed to contribute '''more''' incremental height to the chain than an atomistic sum formula would have given. And conversely, if they overshoot and already have 15%, a structure-aware chain height formula can allocate '''less''' incremental chain height for the overshooting fraction 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 '''asymmetrically different goals'''.		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 '''asymmetrically different goals'''.
Line 43:		Line 43:
	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 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).		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 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, there are doubtless others far more talented than me! [[User:Ids\|Iain Stewart]] 16:41, 21 May 2012 (GMT)		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.) To speed up progress, I thought it only fair to throw open this challenge to all mathematically-minded Bitcoin folk - after all, there are doubtless others far more talented than me! [[User:Ids\|Iain Stewart]] 16:41, 21 May 2012 (GMT)

Ids: /* Proof of stake - done right - is maybe, just maybe, the way to eliminate 51% (even 90%!) attack worries altogether! */ more technically precise wording

2012-05-23T21:18:44Z

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

← Older revision		Revision as of 21:18, 23 May 2012
Line 33:		Line 33:
	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 '''asymmetrically different goals'''.		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 '''asymmetrically 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.)		The attacker, or attacker cartel, wants (in the scenario we're traditionally most worried about) to either bring down Bitcoin, or keep it going but with control over what transactions are "acceptable" - e.g. to act like a know-your-customer bank, or to harass targeted persons or economic sectors by rejecting their transactions. To achieve this, 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 symmetrically 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.		By contrast, the honest 10% do '''not''' have to aim for the symmetrically 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 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 by comparison (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!		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).		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 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! [[User:Ids\|Iain Stewart]] 16:41, 21 May 2012 (GMT)		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, there are doubtless others far more talented than me! [[User:Ids\|Iain Stewart]] 16:41, 21 May 2012 (GMT)

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

2012-05-21T17:42:03Z

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

← Older revision		Revision as of 17:42, 21 May 2012
Line 31:		Line 31:
	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''' incremental chain height, for each block they ''do'' now put in and help bring their share closer to the "ideal" 10%, than an atomistic sum formula would have given. And conversely, if they overshoot and already have 15%, a structure-aware chain height formula can allocate '''less''' incremental chain height for the overshooting fraction than an atomistic formula would have given.		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''' incremental chain height, for each block they ''do'' now put in and help bring their share closer to the "ideal" 10%, than an atomistic sum formula would have given. And conversely, if they overshoot and already have 15%, a structure-aware chain height formula can allocate '''less''' incremental chain height for the overshooting fraction 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'''.		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 '''asymmetrically 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.)		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.		By contrast, the honest 10% do '''not''' have to aim for the symmetrically 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 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!'''

Ids: /* Proof of stake - done right - is maybe, just maybe, the way to eliminate 51% (even 90%!) attack worries altogether! */ clarity improvements here and there

2012-05-21T17:03:17Z

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

← Older revision		Revision as of 17:03, 21 May 2012
Line 29:		Line 29:
	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.		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.		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''' incremental chain height, for each block they ''do'' now put in and help bring their share closer to the "ideal" 10%, than an atomistic sum formula would have given. And conversely, if they overshoot and already have 15%, a structure-aware chain height formula can allocate '''less''' incremental chain height for the overshooting fraction 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'''.		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'''.

Ids: /* Malicious forking */ made section header same font size as prevailing elsewhere

2012-05-21T16:47:37Z

Malicious forking: made section header same font size as prevailing elsewhere

← Older revision		Revision as of 16:47, 21 May 2012
Line 1:		Line 1:
	= Malicious forking =		== 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?		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?

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

2012-05-21T16:41:41Z

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

← Older revision		Revision as of 16:41, 21 May 2012
Line 16:		Line 16:

	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\|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\|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. [[User:Ids\|Iain Stewart]] 22:23, 6 May 2012 (GMT)		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\|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\|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. [[User:Ids\|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! [[User:Ids\|Iain Stewart]] 16:41, 21 May 2012 (GMT)

Ids: /* Malicious forking */ "teaser paragraph" -> "teaser section"

2012-05-21T02:33:31Z

Malicious forking: "teaser paragraph" -> "teaser section"

← Older revision		Revision as of 02:33, 21 May 2012
Line 15:		Line 15:
	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. [[User:Cunicula\|Cunicula]] 27 March 2012		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. [[User:Cunicula\|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\|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 ~~paragraph~~ at end of [[Adaptive_difficulty\|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. [[User:Ids\|Iain Stewart]] 22:23, 6 May 2012 (GMT)		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\|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\|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. [[User:Ids\|Iain Stewart]] 22:23, 6 May 2012 (GMT)