Proof of blockchain fair sharing

Proof of blockchain fair sharing is a draft Bitcoin protocol change proposal by Iain Stewart, with the goal of allowing the network to continue to settle on a sensible consensus blockchain even when subject to a considerably-greater-than-50% attack.

The protocol is under construction. The following description is a "teaser", establishing its basic flavour and sketching how it exploits an asymmetry in the goals of the honest (<50%) and malicious (>50%) miners to avoid the usual reductio ad absurdum argument against any protocol surviving a >50% attack.

Teaser description

Iain Stewart writes: Proof of blockchain fair sharing is of proof-of-stake flavour (which makes me nervous in some ways, but that's another story), and it relies on the fact that stakeholders are pseudonymously trackable, unlike proof-of-work contributors, and therefore a formula for blockchain height can reward closeness to fair-share proportions in such a way that a 90% attacker finds they can't stop the honest 10% contributing too-expensive-for-the-attacker-to-reverse blocks which, to the attacker's chagrin, incorporate the accumulated transactions the attacker has been endlessly reversing and re-excluding in an effort to ruin the credibility of Bitcoin. (And any change to the attacker's pseudonymous identity/identities destroys their bitcoin-days' stake and takes them out of the running as a big attacker for a long time.)

To expand a little on the above teaser: One might think that by reductio ad absurdum no system can protect against a >50% attack, because in a purported proof of immunity of the honest <50% from the malicious >50%, the labels "honest" and "malicious" ultimately have no technical meaning, and so just swapping the labels would, absurdly, give a second proof, saying that the <50% community can't "attack" (i.e. save us all from) the >50% community, in contradiction to the first proof. That reductio argument is false here - there is an asymmetry between the two communities' goals, as follows. (I'm talking about an attack to destroy the usability of Bitcoin. An attack to achieve double spending is a much lower-impact event, the analysis of which I'm therefore postponing, although on general grounds the situation is probably neither especially better nor worse than with other protocols.) The >50% "community" [the attacker(s)] is trying to exclude transactions - perhaps all of them, perhaps those of specific people it wants to harass, perhaps random ones just to create fear that "I could be next" - from entering the winning blockchain. Thus it has to achieve total exclusion of the would-be blocks originating from the <50% community, who keep including the transactions to try and earn an honest profit from the fees. By contrast, the <50% community [the just-trying-to-earn-a-living honest miners] doesn't have to achieve exclusion of the attacker's blocks - they're happy with a mixed blockchain where, reasonably often, another honest block gets in and stays in. So long as they can get transactions bedded down into the blockchain, they've avoided the ruining of Bitcoin as a usable system. It's this crucial asymmetry between the two communities which lets the honest miners win - a chain height formula which suitably rewards diversity of pseudonymous composition will stop even a 90% attacker "community" from achieving its, tougher, goal. I hope this indicates the general direction I'm headed. Iain Stewart 11:15, 21 May 2012 (GMT)

A more discursive description, but still of a "teaser" nature...

Iain Stewart writes: I contributed a more discursive description of the proof of blockchain fair sharing idea, though still ultimately of a "teaser" nature (sorry!), to the proof of stake talk page. That talk page has since moved on to other things; but you can find my contribution in its archive, namely, the gloriously-named "Proof of stake - done right - is maybe, just maybe, the way to eliminate 51% (even 90%!) attack worries altogether!" section thereof. Enjoy! Iain Stewart 23:18, 24 November 2012 (GMT)

Broader approaches to the >50% attack problem

Iain Stewart writes: I apologise for the unfinished state of the above teaser description. It's a hard problem, and it may even be impossible in its "pure" form, without help from fallible heuristics and the like.

In the spirit of exploring broader approaches with rough-and-ready fallible heuristics, I reproduce below my forum post about how a cryptocurrency might resist a >50% attack from (in Cunicula's opening post's example) a central bank. It's not fair sharing as defined above - but maybe it doesn't need to be. Iain Stewart 08:45, 23 November 2012 (GMT)

(The quoted forum post...)

Well! This thread has certainly got us all thinking about the robustness or lack thereof of various cryptocurrency designs! Cunicula's opening post paints (possibly provocatively or tongue-in-cheek?) a central bank's hypothetical successful 51% attack as a good thing. I think most of us on this forum would disagree. We want our cryptocurrency to stop any would-be central bank / central planner from saying "you can only spend your coins in a style approved by our macroeconomic policies". (In just the same way as we want it to stop a present or future PayPal from saying "you can only buy what we think you ought to buy, and donate to who we think you ought to donate to". - Or, more precisely, they can say it, but we can reply "we don't need you any more".)

That's what we want. How do we get it?

For attacks falling short of 51%, there's some mileage to be had in changing the "proof-of-..." choice from one thing to another. Proof-of-work, proof-of-stake, proof-of-activity... they all have interesting advantages and disadvantages and are all debated vigorously in various corners of this forum. Indeed, I'm planning to add to the list myself real soon now, with something I call "proof-of-burn". But they all crumple under a 51% attack. (That includes my proof-of-burn too! It's not immune!) So, when facing an adversary wealthy enough to acquire and use 51% of whichever "proof-of..." resource is being measured by the network - hashing work, stake, burn rate, signature activity, you name it - we need new techniques to stand up to such an attacker.

I think the good news here is that a 51% attacker's chain has to behave visibly strangely when excluding "technically fully sensible but politically unapproved" transactions, such as the "no, I'm not going to pay your coin-year-demurrage level of fees!" transactions Cunicula's example central bank would like to exclude. Such transactions sit in every node's memory pool. Then, every time any such transaction gets into a block (mined by an honest miner who's perfectly happy with its "ordinary" competitive-mining-market-clearing level of fee), the winning chain always ends up building on the previous block, orphaning the honest block and orphaning the transaction back into the memory pool. Whereas, every time no such transactions get into a block, the winning chain always ends up building on that block - it being a block produced by the 51% attacker (or by an honest miner who happens to have inadvertently followed the attacker's policy by happening not to have included those transactions for whatever mundane reason).

This behaviour is visibly strange in a statistical sense. It may not seem strange the first time, or the second time, or the tenth time, but as the politically-unapproved transactions hop in and out of everyone's memory pool more and more often, it becomes ever more absurd to ascribe their exclusion to bad luck.

(Contrast this with an attack whose motive is double-spending, rather than political control of the cryptocurrency. In the double-spending scenario, the network has no real opinion about which of the incompatible transactions ought to succeed and which ought to fail. An attacker can choose whichever one profits them and hurts the recipients[-until-later-reversed] of its double-spending sibling(s). Recipients just have to learn to wait long enough that even the attacker loses interest in further reversing their own chain - their own reversal-attack upon some earlier apparently winning chain - to that block-depth extent. But in the transaction-excluding scenario, the network's honest users do have an opinion about which treatment of the single [no double-spending siblings] transaction ought to succeed and which ought to fail. Namely: the transaction's presence is what ought to succeed, and its absence is what ought to fail!)

This visibly strange behaviour opens up the possibility of a "heuristic defence". I'm certainly not claiming I have such a defence in polished form ready to implement; but in broad outline, nodes would try to compute a "probability (or plausibility) rating" for each new block they encounter. How long has an in-again-out-again transaction been in (and out and in...) my memory pool? What fraction of my network neighbours agree it's been stuck like this for ages? (And recursively, can they report the statistics of their neighbours' opinions, in cheap aggregated form?) If it's ever more obvious that essentially the whole network knows about it, it becomes ever more ridiculous (exponentially so, I'd suspect) to believe that a whole sequence of miners can have not heard of it. Even more so, since it was sitting there inside an expensive object to produce - namely, a later-to-be-orphaned block produced by an honest miner - and a thousand websites could spring up, listing (unfakeably! the orphaned blocks are expensive things to produce!) all the transactions therein that are compatible with, but mysteriously excluded for ages by, the current winning chain.

The naive height-strength (difficulty or its proof-of-whatever equivalent) of a block would then be multiplied by that probability or plausibility rating, and it would be the sum of such plausibility-adjusted height-strengths, not the sum of the naive strengths, which would be used to judge a winning chain.

Yes, this does have the danger that different nodes would compute somewhat different plausibility ratings to multiply naive strengths by; and network consensus convergence could be placed in jeopardy if their opinions were too divergent. So, one would not want to be too eager to deprecate a block by a large factor. Still, in really extreme cases (say down into one-in-a-million territory for a transaction to have been excluded by bad luck - the power of exponential shrinkage means we get down there quite fast!), a sizeable deprecation becomes sensible (e.g. if we deprecate by the sixth root of plausibility, the attacker's blocks are deprecated by a factor of 10 in the one-in-a-million example - enough that 10% honest miners win out over a 90% attacker).

So... there's hope for us yet! Even with a billionaire central bank as adversary!

(A final note: who's running those "thousand websites" [or tor-sites... whatever] listing the suspiciously excluded transactions? Well, anyone can set one up; and serious, big full nodes, such as those run by serious professional miners, should be eager to subscribe to such sites, for a micropayment or subscription fee or the like if necessary. After all, if you're a miner, and you know that other nodes are going to deprecate your block if you don't make an effort to include that gaggle of suspiciously excluded transactions, that's a powerful incentive to keep yourself up to date with the general state of play! - And yes, we should of course aim for the network itself to achieve such functionality, without external sites' involvement. Perhaps nodes could report to their neighbours a standardised-mathematical-language set of reasons why they attached such-and-such a deprecation factor to such-and-such a block? The challenge would be to handle one's neighbours' reasons-descriptions in a way that, while stopping short of naive slavish agreement therewith, still encourages a helpful consensus to emerge.)

(end of quoted forum post)

Related work

• Gavin Andresen has proposed looking at a block's transactions' coin-age priority, when deciding a best chain, as a possible way of standing up to some forms of >50% attack.

• John Tobey has proposed a scheme which studies the detailed distribution of fees and difficulty over a chain and its side-chains, including detection of any tendency for transactions to be orphaned, with a view to deprecating a chain that exhibits symptoms likely in an attack. For now, he has placed a description of his scheme, and some simulation code and results, on this page's talk page. (In most browsers this is accessible via a "Discussion" link at the top of this page; if not, here's a direct link.)