Bitter to Bitter. The Stanford Research Paper.

Bitter to Better - How to make Bitcoin a better currency - Simon Barber, Xavier Boyen, Elaine Shi, and Ersin Uzun

One of the suggestions made in this authoritative paper from 2012 is designed to improve the Blockchain’s resilience to a 51% attack; specifically a History Revision Attack. 

I implore anyone interested to read the paper, or at least Section 4 which concerns possible attacks on the Blockchain and makes a suggestion to improve its resilience. For those who do not wish to read the paper this I will give a brief outline of a History Revision Attack. 

Firstly, the attacker will make some purchase with Bitcoins. They will make a Bitcoin transaction and a record of that transactions will be made in the Blockchain as it would for any normal transaction. Once that transaction has been completed and the attacker has received the goods they purchased then the attacker will reverse their spending. 

In order to reverse their spending and delete the record from the Blockchain, the attacker will release an alternative blockchain that has a higher level of total (summed) difficulty than the 'accurate' blockchain - the one that honest nodes are working on. Creating this alternate history is computationally very difficult but as the Bitter to Better paper correctly notes, if the attacker had about double the hashing power of all the honest nodes then they have a 1-2 year window in which they could feasibly create an entirely new blockchain that did not contain their transaction. This new blockchain would be accepted because it would have a greater total difficulty than the 'accurate' blockchain. 

The  authors propose a technical solution to this problem. 

With regard to people and conventional institutions, humans are suspicious of any record that contradicts thier own recollection of events (See Gaslighting if you’re interest in the damage that can be done by abusing this). Analogously to this, the authors suggest that all nodes keep a record of the transactions they have witnessed pass through the network and when there are two blockchains on the network and one has a greater difficulty than the other, each node will compare both blockchains against their own record of transactions and demand an increasingly high margin of difficulty for the blockchain that differs most from their own record. Younger verifiers will then look to their older peers for information on which blockchain is closer to their timestamped and offline records and there might be phase transition back to the ‘accurate’ Blockchain. 

However, this solution could create problems of its own. In a case where an attacker cannot muster the necessary hashing power in order to create an alternative history but is sufficently patient or able to impersonate ‘older’ verifiers they could perform an alternative attack. If the authors' suggestion was implemented then an attacker could create a blockchain which was shorter than the ‘accurate’ blockchain and it may not be properly rejected if they can use mature verifiers on the network.

An attacker could feasibly control a number of older verifiers which would either have been online for a great amount of time or could be made to look as if they have been verifying for a great amount of time. When a shorter (and fraudulent) blockchain is released onto the network, those fraudulent verifiers reject the ‘accurate’ blockchain and instead endorse the attack’s blockchain - since they are controlled by the attacker. Despite the fact that one blockchain has a great total difficulty, it may be rejected because it fails to reach the artificially created greater margin of required difficulty due to dishonest nodes controlled by the attacker.

This would give rise the possibility of another type of attack. An attack could have a shorter blockchain supersede a longer one by having control of at least 51% of the seasoned verifiers (or verifiers that appear seasoned). In this case, younger verifiers that are on the fence will 'flip' to the fraudulent and shorter blockchain instead of the longer and accurate one, based on the activity of their peers. They would demand an unreasonable margin of greater difficulty for the accurate blockchain based on the illegitimate endorsement of an 'easy' blockchain by dishonest verifiers.

In summary, the techniques proposed by Barber et al. to address the History Revision attacks identified are interesting, but they still seem to allow for a malicious and patient attacker to successfully insert fraudulent blockchains into the ecosystem.

Reference: 

Simon Barber, Xavier Boyen, Elaine Shi and Ersin Uzun [2012]:  Bitter to Better - How to make Bitcoin a Better Currency.  Financial Cryptography (FC 2012). Volume 7397 of Lecture Notes in Computer Science, pages 399-414. Springer, 2012.  Available from here.  

 

[Link: http://ai.stanford.edu/~xb/fc12/index.html]