How does the 'secret chain' catch up with the real chain in the long range attack?

Question

I'm trying to dig deep into Casper and one of the things that keep coming up is the long-range attack in PoS. I understand the attack at a high level - basically you would go back some large amount of blocks where you had a large stake in the network and start forging blocks such that when you arrived at the height of the main chain, you would hold a large amount of the currency and take over the chain.

I saw a similar question here regarding the attack whose answer quoted the below excerpt from the Ethereum blog:

In a naively implemented proof of stake, suppose that there is an attacker with 1% of all coins at or shortly after the genesis block. That attacker then starts their own chain, and starts mining it. Although the attacker will find themselves selected for producing a block only 1% of the time, they can easily produce 100 times as many blocks, and simply create a longer blockchain in that way.

The question I have regarding this quote is how exactly would the secret chain outpace parent chain? From my understanding, the general way to mine a block in PoS 3 is to solve this equation:

hash(kernel) ≤ target × balance of UTXO

Where the kernel is derived from the below:

• nTimeTx : current timestamp (incremented every second)
• nTxPrevTime: Timestamp of the UTXO
• nPrevoutNum: Output number of the UTXO
• nTxPrevOffset: Offset of the UTXO inside the block
• nTimeBlockFrom: Timestamp of the block which provided the UTXO
• nStakeModifier : a 64-bit string seeded from the block chain

How can you manipulate this to mine blocks faster than the parent chain? Would it be the timestamps?

Thanks!

EDIT: After thinking about this a bit more, I'm not sure if this attack is actually feasible... it seems purely theoretical. My logic is as follows: suppose the attacker created his own chain with even 50% of the total 'mainchain' coins. Since he is on his own chain, he will have 100% of the total staked coins on his own chain. With the 100% of the total coins on his own chain, he will certainly be the only minter on the secret chain and will be selected for half of the total possible 'minting opportunities' on the chain.

Indeed, because he is the only staker online in his own chain, he will mint every block, but the issue is the attacker is still subject to the 1 transaction per UTXO per second, so he cannot produce blocks faster. He can certainly produce a massive blockchain much larger than the mainchain because the time for him to accelerate through a couple years is only maybe a couple seconds in the simulation, but the issue will be that the head timestamp might be twice as long as the mainchain (perhaps a year), and clients will simply not accept a chain whose head is years into the future.

If anyone has any additional insight or has another approach to thinking about the problem, I would appreciate it! I found this source to be quite good.

Answer 1

As the author of the quoted article noted himself:

Originally, I thought that this problem was fundamental, but in reality it’s an issue that can be worked around. One solution, for example, is to note that every block must have a timestamp, and users reject chains with timestamps that are far ahead of their own. A long-range attack will thus have to fit into the same length of time, but because it involves a much smaller quantity of currency units its score will be much lower.

So your conclusion about the impossibility of the 'secret chain' with only 1% stake outpacing the main chain is correct, given that the clients validate the block timestamps (they can't go too far into the future).

---

The term Long-Range Attack can refer to different things depending on the cryptocurrency and the chosen algorithm. The formula that you included in your question

hash(kernel) ≤ target × balance of UTXO

doesn't apply to Ethereum and Casper as there is no UTXO there.

The Preprogrammed long-range attack described in the NeuCoin whitepaper that stems from the fact that the stake modifier of a given stake is static and due to the use of coin age in the mining equation, doesn't apply to Ethereum either.

---

I am by no means an expert in PoS but I'll try to outline the logic behind the Long-range attack described in On Stake by V. Buterin that will work even with less than 50% stake on 'non-secret' chain:

1. If we are given the simplest PoS algorithm where every account has a certain chance per second of generating a valid block. This chance is described with the formula:

SHA256(prevhash + address + timestamp) <= 2^256 * balance / diff

2. "There is nothing at stake" problem: a rational miner will choose to mine on 2 chains or more whenever there is an opportunity, to maximise his expected value.

   • Miners who mine only on single chain are called altruistic. Miners who mine on as many chains as they can (rational) are called non-altruistic.
   • An attacker only needs to outpace altruistic miners to perform an attack, thus it's possible to perform this attack even having less than 50% stake (as long as non-altruistic miners' and attacker's stakes add up to 51%).

3. To overcome this issue the Slasher algorithm can be used. If a miner creates a block on 2 chains he will be punished. For that, anyone can submit the block from the other chain into the original chain in order to steal the mining reward and penalize the double-voter.

   • Miners will have to make security deposits so there is way for penalizing in case of double voting
   • The miner has to have the right to withdraw the security deposit eventually, and once the deposit is withdrawn there is no longer any incentive not to vote on a long-range fork starting far back in time using those coins (reference). E.g. after 1000 blocks the miner will have the right to withdraw his deposit.

4. Long-range attack is when a miner starts mining a sidechain 1000 or more blocks back.

   • Other non-altruistic miners will mine on that chain too since there is no punishing and the expected value is higher.
   • In fact, it's even expected to see a black market of people selling their old private keys, culminating with an attacker single-handedly acquiring access to the keys that controlled over 50% of the currency supply at some point in history and performing the attack (reference).

The solution as the author noted is to introduce a rule into each client not to accept forks going back more than 1000 blocks. The problem is, however, what happens when a new user enters the picture. Then he considers hybrid PoW/PoS and social graph systems as a possible solution.

---

With the finality gadget described in the Mauve Paper:

even majority collusions cannot conduct medium or long-range 51% attacks without destroying all of their ether.

Answer 2

After a long road of research, I understand this attack more clearly now. I would first like to note that this attack does not apply to Ethereum since Ethereum is proof-of-work, nor does it apply to Ethereum with Casper FFG overlayed on-top since that is actually still proof-of-work as the proposal mechanism.

First, to be more clear, the long range attack described in the question is a specific type of long-range attack. It's probably best to call it the 'history revision with old private keys' attack. There are other attacks that involve 'long ranging' such as the pre-programmed long range attack described by the NeuCoin whitepaper, but that is a long range into the actual future - this one is in the past.

The actual steps of the attack is as follows:

1. The attacker gains control over old private keys in the blockchain at some height N-1000000 in the past and the total value of coins held by the attacker is some fraction, q, of the total amount of coins presently being staked on the mainchain. N is the current height of the mainchain.
2. The attacker modifies her client to switch to her own secret blockchain that starts N-1000000 in the past. She disables any incoming or outgoing client connections.
3. The attacker starts minting blocks, copying each block's transactions from the mainchain in order. The idea is that the history will be exactly the same because each block will have the exact same transactions, but she will have mined every block since no one else is on the chain. Note that she could include her own new transactions but in reality this serves no purpose since she cannot gain more than q of the total coins anyways. So what she will do is take all the transactions from block N-1000000+1 in the mainchain, put them in her block N-1000000+1 on the secret chain, and try to mint it by trying a time t+1, where t is the timestamp in UNIX ticks of block N-1000000. If time t+1 doesn't work, she will try t+2 and so on. See the equation in the question for what she is trying to solve.
4. Eventually she will find a time t+s seconds where block N-1000000+1 mints on the secret chain. She will get the coinstake reward from that.
5. Repeat step 3 for each block until height N+n where n is some amount of blocks past the head of the mainchain (this is possible because she can just take transactions pending on the mainchain mempool and put it in her secret chain). At this point, she will have gained all the coinstake rewards from minting all of the 1000000 blocks. She can submit her secret blockchain now back to the network and as long as clients accept it, the chain will be valid and she will have effectively 'rewrote history'.

The actual execution of steps 3 to 5 might only take a couple minutes in a script and honestly probably less. The issue though is that this attack is not feasible with the reason being the attacker is still subject to the one-hash-per-UTXO-per-second rule. Even though she can simulate the whole thing in a couple minutes, once she gets to block N+n, she will likely be at time t+T where T is very large and t+T is significantly further than the present time. It might be two years ahead in terms of timestamps for the head of her chain and the timedrift rule of clients not accepting blocks more than 2 hours in the future will reject the chain.

For a bit more intuition on this, consider if q=1/3, i.e., she has a third of all the coins presently being staked on the mainchain. In this case, she will be minting every block on the secret chain, but at a rate of only a third of the mainchain's rate. So she will get 1/3 of the opportunities to stake on her secret chain and no more. Effectively, she will be missing 2/3 of the opportunities to stake on her secret chain by the one-hash-per-UTXO-per-second rule. Probabilistically, for her to catch-up to the mainchain in time t+T where T is less than 2 hours is effectively zero, and approaches zero as the timelag increases, i.e., it is much more impossible with a timelag of 2000000.