In this blog post we briefly discuss the concept of long range attacks, which is considered to be one of the biggest unsolved problems in Proof-of-Stake protocols. We then cover two solutions presently used in live or proposed protocols, namely weak subjectivity and forward-secure keys. Finally, we present a new fork choice rule that makes long range attacks significantly more expensive. The fork choice rule presented can be combined with either or both existing solutions, and can serve as an extra measure against the long range attacks.
This write-up is part of an ongoing effort to create high quality technical content about blockchain protocols and related topics. See our blog posts on Layer 2 approaches, Randomness, and our sharding paper that includes a great overview of the current state of the art.
Follow us on Twitter or join our discord channel to make sure you don’t miss the updates.
The adversary then uses the keys to build a longer chain. Since no scarce resource is used in a Proof-of-Stake system, the adversary can do it very quickly.
We want a fork choice rule such that no matter how long the chain the adversary has built is, and how many of the corrupted validators signed on it, no client, including the clients that start for the first time, will see the chain built by the adversary as the canonical.
The proposed fork choice rule is the following: start from the genesis, and at each block greedily choose one of its children as the next block by doing the following:
Thus, if the adversary can realistically acquire the keys as of block B that correspond to 80% of all the accounts that issued at least one transaction on the canonical chain at a discount, they still need to pay the amount of money that is at least 0.2p.
Note that this fork choice rule only works for long range fork decisions, since for the canonical chain to be resilient to forks, it needs to accumulate a large number of accounts issuing transactions. One way to combine it with more classic fork choice rules would be to first build a subset of the blockchain that only consists of blocks finalized by a BFT finality gadget, run the fork choice rule described above on such a sub-blockchain, and then starting from the last finalized block on the chain chosen by the fork choice rule use a more appropriate fork choice rule, such as LMD GHOST.
Long Range Attacks
Proof-of-Work with the heaviest chain fork choice rule has a very desirable property that no matter what malicious actors do, unless they control more than 50% of the hash power, they cannot revert a block that was finalized sufficiently long ago. Proof-of-Stake systems do not have the same property. In particular, after the block producers that created blocks at some point in the past get their staked tokens back, the keys that they used to create blocks no longer have value for them. Thus, an adversary can attempt to buy such keys for a price significantly lower than the amount of tokens that was staked when the key was used to produce blocks. Since, unlike in Proof-of-Work, Proof-of-Stake has no mechanism to force a delay between produced blocks, the adversary can then in minutes create a chain that is longer than the canonical chain, and have such chain chosen by the fork choice rule. There are two primary ways to get around this problem: Weak subjectivity. Require that all the nodes in the network periodically check what is the latest produced block, and disallow reorgs that go too far into the past. If the nodes check the chain more frequently than the time it takes to unstake tokens, they will never choose a longer chain produced by an adversary who acquired keys for which the tokens were unstaked. The weak side of the weak subjectivity approach is that while the existing nodes won't be fooled by the attacker, all the new nodes that spin up for the first time will have no information to tell which chain was created first, and will choose the longer chain produced by the attacker. To avoid it, they need to somehow learn off-chain about the canonical chain, effectively forcing them to identify someone whom they trust in the network. Forward-secure keys. Another approach is to make the block producers destroy the keys that they used to produce blocks immediately or shortly after the blocks were produced. This can be done by either creating a new key pair every time the participant creates blocks, or by using a construction called Forward-secure keys, which allows a secret key to change while the corresponding public key remains constant. This approach relies on nodes being honest and following protocol strictly. There's no incentive for them to destroy their keys, since they know in the future someone might attempt to buy them, thus the key has some non-zero value. While it is unlikely that a large percentage of block producers at a certain moment all decide to alter their binaries and remove the logic that wipes the keys, a protocol that relies on the majority of participants being honest has different security guarantees than a protocol that relies on the majority of participants being reasonable. Proof-of-work works for as long as more than half of the participants are reasonable and do not cooperate, and it is desirable to have the fork choice rule and a Sybil resistance mechanism that have the same property.Proposed Fork-Choice Rule
Consider the figure below. There’s a block B sufficiently far in the past on the canonical chain such that the majority (or all) the block producers who were building the chain back when B was produced have their stake unstaked. The adversary reaches out to all those block producers and acquires the private keys of ~⅔ of them. At that point the keys have no value to the block producers, so the adversary can purchase them for a price significantly lower than the actual amount that was staked.- Snapshot the state as of after the current block is applied.
- Enumerate all the accounts that have tokens at that moment, as a list of pairs (public key, amount).
- For each child block, identify all the public keys from the set that signed at least one transaction in the subtree of that child block.
- Choose the child block for which the score, computed as the sum of the amounts on the accounts that signed at least one transaction in its subtree, is the largest.