(Copied, with minor edits, from my recent contribution to
https://en.bitcoin.it/wiki/Talk:Proof_of_Stake.)
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,
https://en.bitcoin.it/wiki/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!
