Rewriting History: A Brief Introduction to Long Range Attacks

Proof of Stake protocols are in the spotlight as more and more high-profile blockchains attempt to switch over from Proof of Work protocols. Many of them explore the option of hybrid systems (PoW/PoS) while others aim for a pure PoS implementations.

One of the greatest threats against Proof of Stake protocols is Long Range attacks. Due to the existence of Weak Subjectivity and Costless Simulation, these attacks are more dangerous than in Proof of Work protocols.

During my research on the topic, I found that information about Long Range attacks is sparse and a lot of times misleading. Even when diving into academic papers, at times I was not able to understand the very nature of this attack group. Below you will find my attempt to fledge out Long Range attacks.

In short, a Long Range attack is a scenario where an adversary creates a branch on the blockchain starting from the Genesis block and overtakes the main chain. This branch may contain different transactions and blocks and is also referred to as Alternative History or History Revision attack.

For the rest of this article the terms Long Range, Alternative History, Alternate History, History Revision will be used interchangeably.

The main reason on why Long Range attacks exist is a notion called Weak Subjectivity.

Weak Subjectivity

This term is used to describe a problem that affects new nodes of a blockchain network and nodes who are brought online after a significant amount of time being offline. Online nodes are not affected by weak subjectivity.

When a new node is added to the network, it is always provided with the genesis block. This is the only block that all nodes accept as the first one. Along with the genesis block, the node will be presented with all of the currently published branches of that blockchain. Unfortunately, the node will not be able to tell right away which branch is the main chain.

The same applies to nodes that have been offline for a long period of time e.g. a few months. At some point in time, these nodes knew which branch was the main-chain but after all that time being offline, they no longer do.

Online nodes follow and monitor the blockchain in real-time. They cannot be duped into accepting a different branch as the main chain unless a branch legitimately becomes the main chain.

Sample blockchain, the green block is the genesis block, purple denotes the orphaned/branches and the black blocks the main chain

As you can see, the above blockchain snapshot has many different branches. Some of them are longer than others. The main chain could be any of the branches that are presented.

The first rule we’re going to talk about in this article is the longest chain rule. According to this rule, the main chain will always be the branch with the greatest number of blocks. In Proof of Work blockchains where physical resources are needed to produce a block, the longest chain rule is a great way to identify how much work has been invested in a branch.

Weak Subjectivity on PoW

In Proof of Work blockchains, we’re based on the assumption that unless the network is under a 51% attack it is not possible to have competing branches deriving from the genesis block. For a branch, in order to reach the length of the main chain, it would require a tremendous investment of computational power. For PoW blockchains, the longest chain rule is enough to counter Weak Subjectivity.

Costless Simulation

In Proof of Stake protocols, the longest chain rule is not enough to determine the main chain. This happens due to a notion we refer to as Costless Simulation.

PoS protocols employ validators to secure the network, and this is performed with virtual goods, the so-called stake. There are no miners, there are no computational puzzles to solve. No one is bound to compute useless hashes forever. There is just trust, trust in the fact that the validators are so invested in that particular blockchain that they will work in its favor.

As a result, no computational power is used. In reality, some of it is used but it’s so insignificant that we refer to block generation as a Costless process. The validators just take a bunch of transactions from the transaction pool, put them into a block and publish it. As simple as that. Therefore, Costless Simulation is the ability to create up-to-date branches without effort.

PoS Blockchain sample where multiple branches have the same length

Any new node to the network will be presented with multiple branches of the blockchain and many of those branches can have the same length. With Costless Simulation and Weak Subjectivity, the Longest Chain rule is challenged. It is not enough to determine the main chain of a blockchain. Long Range attacks exploit these two notions.

Long Range Attacks

There are three different types of Long Range attacks to this date. Most of the publications usually mix the first two cases which are the Simple and Posterior Corruption, or they just accept Posterior Corruption as the only case of these attacks. Stake bleeding is fairly new research, published in 2018.

Unfortunately, I wasn’t able to find a more descriptive name for the first case. We may refer to that case as “Simple” as it was originally referred to in the Stake Bleeding research paper.

To summarize, we have the following cases:

  1. Simple
  2. Posterior Corruption
  3. Stake Bleeding

As stated in the introduction, a Long Range attack is a scenario where an attacker goes back to the genesis block and forks the blockchain. The new branch will be populated with a completely (or partially) different history of the main chain. Once the newly crafted branch becomes longer than the main chain, it will overtake it.

Starting off with the simplest case of Long Range attacks, we will build up to more complex scenarios. In our examples, we have a validator pool with 3 validators, Bob, Alice, and Malory. For the sake of simplicity, all of them own the same portion of the system’s stake, 33,3%.

Key Detail: Information about validators and their stake is located in the Genesis block.

Simple

The first case refers to a naive implementation of the Proof of Stake protocol. In this scenario, nodes do not check block timestamps.

In a normal cycle of the PoS protocol, every validator will get the chance to validate blocks.

Snapshot of the example blockchain, each validator has an equal chance of getting elected

Malory decides to perform a Long Range attack and creates an alternative branch of the blockchain. Malory goes back to the genesis block, forks the blockchain and starts minting her branch.

Since the validator information is located inside the Genesis block, Malory will not be able to produce blocks faster than she would in the main-chain. Malory produces blocks with the same rate. With all those conditions, the only way for Malory to advance her branch and overtake the main-chain will be to produce blocks ahead of time.

In Malory’s branch the chances of being elected are the same as on the other branch. “Parenthesis” blocks are forfeited blocks. The current length of Malory’s branch is 2 blocks
Triple dots denote multiple forfeited blocks. In order for Malory to compete with the main-chain, she will have to compute blocks ahead of time. In the above blockchain snapshot both branches have 5 blocks

Malory will have to forge timestamps, and since she is the sole active stakeholder in that branch it is possible to do so. In implementations where nodes do not take into consideration timestamps, both branches will be valid and nodes won’t be able to spot Malory’s trick.

Posterior Corruption

Assuming forging timestamps is no longer possible, Malory understands that in order to successfully perform this type of attack she will need something more. She needs to achieve a higher number of minted blocks in the same time frame as the main-chain. Since she has a fixed chance of producing blocks she has to improvise.

What if she could use Bob’s blocks as well? That would increase her chances of competing with the main chain but why would Bob ever agree to that? This is a good time to introduce the concept of validator rotation.

It wouldn’t be fair if validators were static. A Proof of Stake system has to begin with something, it has to have a static set to begin with but eventually, for the fairness of the system validators have to rotate.

Validators should have the option to retire and the system should rotate or remove them under certain conditions.

For the sake of our example, Bob decides to retire after 10 thousand blocks. Bob removes his stake, cashes out and goes on a long vacation. While a validator, Bob used security best practices regarding his private keys. Now that Bob no longer owns any stake on the platform, the security of his private key is not a priority.

Bob no longer gives a fuck

Key Detail: Even though Bob no longer can sign new blocks (he is no longer a validator), he is capable of signing again the first 10 thousand blocks. This is useful if he needs to sign the first 10 thousand blocks in a different branch.

Since there is nothing at stake for Bob, he has no disincentive for performing an attack against the system.

There are two possible scenarios for this attack.

  1. Malory hacks Bob, steals his private key
  2. Malory bribes Bob, Bob joins the attack

Now that Bob’s private key is in the disposal of Malory, Malory can sign valid blocks as Bob, increasing her chances of successfully outpacing the main-chain. This attack is called Posterior Corruption.

Bob joins Malory’s Long Range attack. Now the alternative branch is much more competitive and the chances to overtake the main-chain are greater

Since Bob is partaking in the attack, every time he is elected as a slot leader in Malory’s branch he will produce a block. As seen in the image above, Bob’s blocks are no longer empty and Malory’s branch is much more competing to the main chain.

This type of Long Range attack can be countered by the use of Key-Evolving Cryptography and Moving Checkpoints. Further details about mitigation techniques will be presented later in this document.

Stake Bleeding

The third type of Long Range attacks is Stake Bleeding.

Malory, once again, decides to perform a Long Range attack against the blockchain, this time she will attempt a Stake Bleeding attack. We have the same setup as the previous scenarios. Malory is a validator on the main chain and starts her own branch from the Genesis block.

Again, when the branch occurs, the chances of being elected as a slot leader are the same in all branches of the blockchain. Remember, the information about the validators is inside the Genesis block. Malory keeps her branch hidden and doesn’t publish it up until she outpaces the main-chain.

Malory mines her branch (dotted branch) locally and does not publish it

This time, Malory, in order to increase her chances of achieving this attack, starts to stall the main chain. Depending on the percentage of the overall stake Malory has this could result in a Liveness Denial attack. Every time Malory is elected as a slot leader in the main-chain she skips her turn, forfeiting her position. This does not mean that another validator will take her place, instead, for that slot/epoch, no new block will be added to the blockchain. This is used as an elaborate scheme from Malory to stall the blockchain.

Malory forfeits her blocks in the main chain in order to gain a competitive advantage on the alternative branch

As a result, Malory will not get any rewards from the system and her stake will gradually decrease. All of the other validators will publish blocks and get the block rewards/transaction fees. For this scenario, we assume that validator rewards are compound on their stake.

On the other hand, on her own branch, Malory will be the only validator publishing blocks, and for every single chance she gets she will publish a block. For this scenario, Malory will try to increase her stake in every possible way. As an extra step, she will copy transactions from the main chain and publish them into her own branch as well. This is done to maximize the number of transaction fees she will get and use them to increase her stake.

By following this tactic, stalling the main chain while trying to publish as many blocks as possible in the alternative chain, Malory will eventually get the majority of the stake on her branch and it will start expanding faster than the main-chain. Once her branch outpaces the main-chain, she makes one last transaction where she redistributes the stake to other validators and then goes on to publish her branch.

Malory gradually increases her stake in her branch while she keeps losing stake in the main chain for forfeiting blocks

This scenario as you might have noticed is way more complex than the previous ones. Two new concepts have been introduced, stalling the main-chain with Liveness Denial and copying transactions off the main chain.

It is important to state that this kind of attack would require a lot of blockchain time to conduct. According to its research paper, approximately a 6 year worth of blockchain history for an attacker with 30% stake was needed to successfully perform this attack (With Costless Simulation, creating a branch with that amount of blockchain history is effortless and quite fast).

Stake Bleeding can be countered by the use of Moving Checkpoints. The Plenitude Rule can also be used to identify the malicious branches.

Mitigation

Various mitigation techniques have been researched the last few years. Even though all of them offer some kind of protection against Long Range attacks none of them is a complete mitigation technique. As such, a combination of those is needed to counter this type of attacks.

Longest Chain Rule

This is the simplest technique to defeat weak subjectivity. For PoS protocols this technique is always used in conjunction with others. PoW protocols can counter weak subjectivity by using only this technique.

The main chain is the branch with the greatest number of blocks, in this image, it is the chain with the black colored blocks

According to this rule, the main chain is the branch with the greatest number of blocks. The main chain can change from time to time and blocks can be reorganized. Reorganization of the chain will occur when another branch of the chain becomes longer than the main chain.

Moving Checkpoints

Checkpoints or moving checkpoints is a mitigation technique used by almost all PoS protocols. Its simplicity and ease in implementation made it one of the first mitigation techniques to be enforced in PoS powered blockchains, after the longest-chain rule of course.

The idea behind moving checkpoints is that only the latest X number of blocks of the chain can be reorganized. The number of reorganizable blocks depends on the protocol implementation and it could range from one month’s worth of blocks e.g. Peercoin to those of just a few days or hours e.g. NXT.

In this example only the last 2 blocks can be reorganized. With the use of moving checkpoints the grey boxes have become immutable. The red branch is invalid as it tries to reorganize immutable blocks (grey). The only blocks that can be reorganized in this blockchain snapshot are the purple ones.

Wait! If you can reorganize the latest X blocks isn’t it still a Long Range attack?

Well yeah, you can still reorganize the latest blocks and cause a confusion on the system but this attack now falls under a different category. A Long Range attack starts at the Genesis block.

An attack on a very limited number of blocks would be considered a Short Range a.k.a. Bribery attack (reorganizing blocks of few days up to a few months). Short-Range attacks have different incentives, execution methods, impact, and mitigation techniques. Even though Short Range attacks are interesting they will not be covered in this post.

With moving checkpoints the main chain becomes truly immutable up to the latest X blocks. I know this sounds weird, you’re used to referring to the blockchain as “the immutable ledger” but have you ever wondered if it truly is? Truth is, it isn’t.

You might not be able to change a transaction from within a block but you can branch the chain, craft your own blocks, bypass the main-chain, reorganize the blocks and Taa-Daa, you just modified the immutable chain. To be accurate, we didn’t modify any block, we just created another history. The previous main-chain even though still immutable is no longer valid. It no longer has any trust from the system.

Key-Evolving Cryptography

Moving on to more complex solutions, this technique is used to counter Posterior Corruption attacks. On Posterior Corruption scenarios, retired validators, even though their keys are no longer valid, can be used to sign older blocks in the blockchain.

By using key-evolving cryptography and more specifically key-evolving signatures (KES) a slot leader signs a block and immediately destroys the used key.

With ever-evolving keys and without the capability to return to an older version of the key, if Bob decides to sign blocks of a different branch, he won’t be able to connect his key to that of the genesis block (as it has already evolved by signing for another branch).

This is an experimental idea and more research is needed to ensure all of these assumptions hold for key-evolving cryptography.

Context-Aware Transactions

Every block in the blockchain contains the hash of the previous block in its header. This is used to identify the branch in which a block is placed to. With Context-Aware Transactions, we are moving one step further into this concept and we include the hash of a previous block inside a transaction.

This way, we can associate a transaction with a specific block in a specific branch of the blockchain. Since a transaction contains a historical reference of the blockchain it cannot be copied to another branch and still be valid (unless the historic reference exists in that branch as well).

A great in-depth resource on how context-aware transactions can work is a presentation by Jeff Coleman on Universal Hash Time which is a type of Context-Aware Transactions.

Malory copies transactions off the purple branch in order to progress her chain but the transactions are linked to Bob’s block. Malory’s branch (red) will be rejected by honest nodes as inconsistent.

This type of mitigation technique can be used to obstruct Long Range attacks. With context-aware transactions, adversaries won’t be able to copy transactions from the main chain to their own branches. Even though it does not eliminate the attack, it does present a substantial obstacle.

The attacker is forced to create a completely different history. Even if they do manage to succeed in this attack, it won’t be subtle.

Plenitude Rule

A more sophisticated countermeasure for Long Range attacks is the Plenitude Rule. This mitigation technique is based on detecting the sparsity and density of blocks in conflicting branches.

Validator stake at the genesis block

Adversaries cannot manipulate their stake. An adversary with a starting stake of 20% will have the same stake on all branches of the blockchain, assuming that all branches derive from the same starting block.

In Long Range attacks, the adversary starts with a small chance to produce blocks and as block rewards are gained and stake is accumulated more and more stake will add up for the adversary. The more stake a validator has, the more chances he gets to produce blocks. What we’re looking for in this stage is to identify that acceleration phase.

Blockchain snapshot up till point X. Validators have the same chance of producing blocks at any given branch.

Before the malicious validators get enough stake to accelerate their block generation frequency, the rest of the validators, the honest ones, will be elected for generating 80% of blocks (in regards to our example). With this information alone it is possible to identify that one branch will produce only a portion of the blocks the other branch does (One branch has 80–100% percent of generating a block at a given slot and the other has maximum of 20%).

Blockchain snapshot where the density of the malicious branch is sparse for the first segments.

In the above blockchain snapshot, we can see how stake accumulation could work. The upper branch is the malicious one, and in the first two segments, block generation is much more sparse in contrast to the third. On the other branch, we can see a more smooth distribution in block generation throughout all segments.

Having empty blocks doesn’t necessarily mean that a validator is blocking the chain on purpose (Alice). Sometimes, slots can be empty, maybe no transactions were performed during that period.

On the third segment, the upper chain has accumulated enough stake and block generation begins to be denser.

Stake redistribution on Malory’s branch after time X.

At that point, the adversary’s stake will keep increasing in their own branch and the honest validator’s stake will gradually decrease. Blocks will be presented more often in the alternate branch and eventually overtake the main-chain.

The plenitude rule attempts to determine the block density of a branch from the moment the branch is formed, up to that point in time where block density substantially changes. Assuming that the malicious validators will always be a minority (The system collapses if more than 34% of validators are malicious) the main branch will always be denser than the competing branches.

By following this rule, it is fairly easy to identify the main chain and defeat weak subjectivity.

Conclusion

In this article, we covered one of the most interesting type of attacks against Proof of Stake protocols, the Long Range attacks and peeked into its subcategories. Upon covering the Simple, Posterior Corruption and Stake Bleeding types of Long Range attacks we presented their mitigation techniques.

While the Longest Chain rule is sufficient for PoW systems, in PoS more techniques must be combined in order to completely counter Long Range attacks. Moving Checkpoints, Context-Aware Transactions, Key-Evolving Cryptography and the Plenitude Rule can all be used in conjunction with the Longest Chain Rule to ensure the safety of a PoS blockchain.

Special thanks to George Papakyriakopoulos for research collaboration and Arseny Reutov and @firek1d for proofreading.


Rewriting History: A Brief Introduction to Long Range Attacks was originally published in ICO Security on Medium, where people are continuing the conversation by highlighting and responding to this story.



*** This is a Security Bloggers Network syndicated blog from ICO Security - Medium authored by Evangelos Deirmentzoglou. Read the original post at: https://blog.positive.com/rewriting-history-a-brief-introduction-to-long-range-attacks-54e473acdba9?source=rss----820ff037acec---4