I’ve had some thoughts on stopping 51% attacks, so I thought I’d post them on here to see if I have come up with anything novel.
TL;DR Secure POW blockchain by encoding block hashes in transaction signatures.
Passive Proof Of Stake
A Proposal To Increase The Difficulty of 51% Attacks On Proof of Work Blockchains.Cryptocurrencies like Bitcoin[1] provide a very secure way to send value over the internet. However they can become vulnerable when a single miner controls more than 50% of the hash rate. This is mainly an issue for smaller ‘market cap’ blockchains with less hashing power, especially with the increasing amount of cloud computing available to rent. This paper describes a simple proposal to make these attacks harder, without changing the structure of the blockchain, and only requiring a small amount of extra work in making and validating transactions and blocks.
Possibly the most revolutionary aspect of the Bitcoin protocol is how it deals with two or more competing versions of the blockchain. How do participants in the network all come to the same decision on which is the correct version? Bitcoin’s answer to this is that participants should simply chose the longest chain. This works because creating a long chain requires a lot of computational work (by design), so it is not feasible for an individual to artificially create a long blockchain unless they have more computing power than the rest of the network put together.
In a simple 51% attack, an attacker will publish a transaction to the network, then secretly make an alternative version of the blockchain with a different version of their transaction. When the initial transaction has been confirmed on the public blockchain, the secret blockchain can be released. The nodes in the network will choose the longest of the two competing chains. As the attacker has more mining power than the rest of the network, their blockchain will be longer, and replace the ‘correct’ version. The attacker will have effectively spent their coin twice - a double spend.
However if each transaction contains a hash of a recent block, and is only considered valid if it is put in the blockchain after that block, then the attacker will only be able to put a few of the public transactions into their secret blockchain. It would be easy to tell the difference between the attacking chain and the public chain, as the public chain will have far more transactions. This system can be thought of as being ‘passive proof of stake’, where each person making a transaction is effectively voting on the blockchain they want to support, but these stakeholders play no role in creating the blocks. (The stake holders in a standard proof of stake blockchain play an active role in creating the blocks[2])
Obviously the attacker could make their own transactions to fake the kind of transactions that happen in the public blockchain. To chose the ‘correct’ chain, the network needs a way to analyse the competing chains and give them a score. The chain with the highest score is selected with others being thrown away. For example a simple scoring system would be the number of blocks multiplied by the number of coins affected by transactions in the chain. This means that an attacker would need control of a lot of coins to fake the transactions convincingly, and someone with a lot invested in a network is unlikely to want to attack that network. Much more complex scoring functions could be made, based on statistical analysis of the chains. However this is probably application dependent, and outside the scope of this document.
The implementation described above would be more secure than a standard proof of work blockchain. However if a 51% attack was successful then potentially thousands of transactions would become invalid, and it would not be possible to re-add them to the blockchain. The blocks they referenced would no longer exist. Consequently, referencing a previous block should be optional, and transactions that do reference a previous block should contain two signatures. One with and one without the reference. Then if the worst happens the signature without the reference can be used. The scoring function for choosing a branch should ignore transactions that don’t have a block reference, as an attacker could easily copy them.
Adding an extra hash to every transaction would cause a significant increase in blockchain data. Fortunately this data can be completely stripped out of the transaction before it is added to the blockchain as it can be recreated using the blockchain and the transaction signature. This involves guessing which of the recent blocks a transaction was linked with until one is found that passes the signature test. This guessing process can be greatly optimised by sorting the transactions based on which block they have referenced (e.g. Most transactions will use the same block as the previous one, so will be easy to guess). The number of signature tests required to validate a block will be N+M compared to N for a standard cryptocurrency (where N is the number of transactions, and M is the maximum allowable age of a referenced block in blocks). As M can be chosen to be much less than N, the number of signature tests should only increase by a few percent.
If it is known that a blockchain is in danger of being attacked, large stakeholders can choose to secure the network by moving their funds, giving the public chain a higher score. This would be a good option for exchanges as they are the most likely targets of double spends, and they tend to have large amounts of cryptocurrency. It may be desirable to reward large transactions like this in order to encourage them. For example each block could award a fraction of the mining reward to the highest value transaction of funds that have been untouched for a set time. This could be limited to transactions with a single output to avoid confusion on where the reward should go. Miners that try to exclude high value transactions to get the reward for themselves run the risk of their block being rejected in favour of one with a higher score. Miners will have an advantage as they will be able to see the other transactions in the block before they decide whether to add theirs, or not. However this should not harm the network, and can be considered a perk of being a miner.
Some additional points:
- It should be possible to implement Passive Proof of Stake using soft forks.
- As Passive Proof of Stake increases the security of the blockchain, less proof of work is needed, potentially allowing lower mining rewards and lower energy usage.
- In an extreme implementation the blockchain would be secured entirely by proof of stake, with proof of work just used to control the rate that new blocks are created.
- When making a transaction, the age of the block referenced can be chosen. Using an older block will ensure the signature is not tied to a discarded branch. A newer block will secure the blockchain better.
- If two competing blocks are created roughly simultaneously, the score function can be used to decide which one should be selected.
- Miners have an incentive to include transactions with block references as it makes their branch stronger.
- Transactions with block references are more likely to be accepted onto the blockchain, so users have an incentive to use them.
- A more sophisticated scoring system would be to score each transaction based on its value, how long since the inputs were last used, and how recent the block that it references is. The score for a block is then the sum of its transaction scores, plus an amount for the block, and a chain’s score is the sum of its block scores.
- Block hashes encoded in transaction signatures can be used for replay protection.
- A potential downside is that this proposal makes it easier for someone with a very large amount of cryptocurrency to launch a 51% attack. However it would be against the interests of a large stake holder to attack the thing that they have a stake in.
- A ‘light’ wallet provider may be able to trick people into supporting a secret blockchain. However interested parties can monitor popular wallets and take appropriate action if they detect a problem.
References
[1] Nakamoto, Satoshi (31 October 2008). "Bitcoin: A Peer-to-Peer Electronic Cash System"
[2]
https://en.wikipedia.org/wiki/Proof-of-stake