Stopping 51% attacks

[MrFlay]

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

[1715009237]

1715009237

[1715009237]

1715009237

[1715009237]

1715009237

[d5000]

This proposal has already been made by Dan Larimer in 2014, and is part of the so-called "Transactions as Proof of Stake" or TaPoS concept. I'm not finding the original whitepaper anymore , but there is an explanation in the Bitshares forum (the original link to the whitepaper is also there).

It is even used in some proof of stake altcoins - for example, the Bitshares family and NXT/Ardor (where it's called "Economic Clustering").

However, the approach has a problem, which you also mention in your post: In the case of an attack, the attacker could also fake (or simply create) transactions with references to a block in his own attack chain. Unfortunately, there is no scoring algorithm that could ensure that the attacker always loses if he doesn't own a large proportion of the coins - e.g. he could simply acquire lots of BTC, transfer them to an exchange (in the "real chain" and in the "fake chain", but both after the "fork block") and sell them - so in the end he doesn't need any "stake" in the network he's attacking, but there is enough transaction volume in his fake chain (with "correct" references to his attack chain blocks).

That does not mean that the concept is useless. But the protection it offers has to do a lot with trust. For example, if your Bitcoin client has to decide between two blockchains and doesn't know which one is the "real" chain and which one the attack chain, you can choose to use the chain where your own transactions, those of your friends, or those of your preferred services (e.g. exchanges) are recorded. But you must know the addresses of these participants.

That's OK for Proof of Stake coins, because they are necessarily employing a kind of trust system as PoS is not an "objective" consensus system. But Proof of Work coins like Bitcoin are meant to be "objective", so a trust layer does not add so much security - and it adds new complexities, for example, in chain reorganizations transactions may be lost because their block reference is no longer valid.

However, TaPoS could be part of a broader "security enhancement" system that also applies standard proof of stake mechanisms on top of PoW, for example, additional Proof of Stake blocks like in hybrid PoW/PoS coins.

[Pmalek]

Unfortunately the link to the whitepaper doesn't work and opens https://coingi.com/ instead.
I was able to find the whitepaper in a different place though, I guess this is the one you are referring to @d5000. (Sorry for the way the link looks, it is quite long so you have to copy the whole thing).

http://www.wanglutech.com/LoadFiles/file_1483944101721_[%E7%99%BD%E7%9A%AE%E4%B9%A6]Daniel%20Larimer-%E5%B0%86%E4%BA%A4%E6%98%93%E4%BD%9C%E4%B8%BA%E6%9D%83%E7%9B%8A%E8%AF%81%E6%98%8E[%E8%8B%B1%E6%96%87][PDF%E4%B8%8B%E8%BD%BD].pdf

There is also a similar document called:

Delegated Proof of Stake:
Features & Tradeoffs
Myles Snider, Kyle Samani, and Tushar Jain

https://multicoin.capital/wp-content/uploads/2018/03/DPoS_-Features-and-Tradeoffs.pdf

[d5000]

Unfortunately the link to the whitepaper doesn't work and opens https://coingi.com/ instead.
I was able to find the whitepaper in a different place though, I guess this is the one you are referring to @d5000. (Sorry for the way the link looks, it is quite long so you have to copy the whole thing).

http://www.wanglutech.com/LoadFiles/file_1483944101721_[%E7%99%BD%E7%9A%AE%E4%B9%A6]Daniel%20Larimer-%E5%B0%86%E4%BA%A4%E6%98%93%E4%BD%9C%E4%B8%BA%E6%9D%83%E7%9B%8A%E8%AF%81%E6%98%8E[%E8%8B%B1%E6%96%87][PDF%E4%B8%8B%E8%BD%BD].pdf

Thanks! So it's available on some obscure website still, cool. I've searched it even on archive.org, but it seems not available.

DPoS is a completely different topic though - even if some incarnations use TaPoS, it isn't related to the system the OP proposed.

[mixoftix]

there is also another version of these kinds of attempts against 51% attack in link bellow:

https://vitalik.ca/general/2018/08/07/99_fault_tolerant.html

in this approach the owner of proposal - by adding some special nodes that he calls them "Observer nodes" and also do not involve in mining process - tries to protect the network. based on lessons from system architecture, adding any special nodes into a decentralized network with voting power, somehow will push the entire of the network into a centralized version.

[MrFlay]

Thanks for the extensive replies and the links. Very interesting. Slightly scary how similar my ideas were to that TaPoS paper

[aliashraf]

there is also another version of these kinds of attempts against 51% attack in link bellow:

https://vitalik.ca/general/2018/08/07/99_fault_tolerant.html

in this approach the owner of proposal - by adding some special nodes that he calls them "Observer nodes" and also do not involve in mining process - tries to protect the network. based on lessons from system architecture, adding any special nodes into a decentralized network with voting power, somehow will push the entire of the network into a centralized version.

Vitalik Buterin is bullshitting too much recently. The 99% fault tolerance he is talking about is based on encrypted messaging which is neither new nor applicable in crypto ecosystem. He is just moving his pieces to make another attack against decentralized crypto ecosystem in favor of his agenda for making  Ethereum Foundation some-shit like the central hub of world finance, such an idiot he is  

[aliashraf]

Transactions committing to the blockchain is a great idea and could be used in resisting 51% attack but not from a PoS perspective: By transferring her funds, the sender has already taken the most advantage of her ownership and there is nothing left to be considered as a value that is added to network security, without added value there would be no added security, it is basic.

Alternatively, accumulating work in transactions and incentivizing wallets to participate in consensus by committing to the most recent blocks is another story, an interesting one. It has a lot of implications and requirements to become practical tho.
I have been studying/discussing it lately and will post a link as soon as I could find one.  

[buwaytress]

However, the approach has a problem, which you also mention in your post: In the case of an attack, the attacker could also fake (or simply create) transactions with references to a block in his own attack chain. Unfortunately, there is no scoring algorithm that could ensure that the attacker always loses if he doesn't own a large proportion of the coins - e.g. he could simply acquire lots of BTC, transfer them to an exchange (in the "real chain" and in the "fake chain", but both after the "fork block") and sell them - so in the end he doesn't need any "stake" in the network he's attacking, but there is enough transaction volume in his fake chain (with "correct" references to his attack chain blocks).

Could it not also be a possibility for this mechanism to increase the likelihood for false positives, and how else would they be able to identify them as false positives? As unlikely as it may seem, what happens when there is an actual large-sized transaction also with a lot of coins (I'm thinking as a rough example a huge consolidation effort by a big exchange, where a score of txs could fill up a significant portion of block and represent a lot of coins)?

It would appear on first impression by the rest of competing public that an attack could be taking place if I understand correctly. Suppose observer nodes learning lessons from false positives would improve the system.

[mixoftix]

Vitalik Buterin is bullshitting too much recently. The 99% fault tolerance he is talking about is based on encrypted messaging which is neither new nor applicable in crypto ecosystem. He is just moving his pieces to make another attack against decentralized crypto ecosystem in favor of his agenda for making  Ethereum Foundation some-shit like the central hub of world finance, such an idiot he is  

Yes, we have discussed it before about avoiding software tricks while thinking about a solution - and that 99% thing was the most tricky topic that I have ever seen. and about the central hub of world finance I just can say: "Pooouuuufffff" 

[d5000]

Could it not also be a possibility for this mechanism to increase the likelihood for false positives, and how else would they be able to identify them as false positives? As unlikely as it may seem, what happens when there is an actual large-sized transaction also with a lot of coins (I'm thinking as a rough example a huge consolidation effort by a big exchange, where a score of txs could fill up a significant portion of block and represent a lot of coins)?

I hope I understood what you meant ... In my opinion false positives are exactly the big problem if you let decide the client without intervention. There is a certain risk in both ways:

1) clients could think no attack is going on because the attack chain has enough TaPoS stake in it,
2) a "refined" algorithm could detect and mark a chain as "suspicious", if it contains very large transactions - it could suppose it's an attacker trying to add stake to his chain (I think that's the scenario you describe, right?). But in this case the attacker could actually do the opposite: he adds some large transactions to the "real" chain and fills his attack chain with lots of small transactions, but which add up to a similar stake value than in the real chain. That would generate indeed a false positive - the "fake chain" would look more trustworthy to the algorithm because it contains less extremely big transactions.

So I think it is close to impossible to generate an "automatic" scoring algorithm for TaPoS. It will be always necessary that the client operators themselves chose trustworthy addresses which they follow in the case of a chain split.