Two month passed since my last post and the reason is I’ve been terribly busy working for Coinspect and also helping with Bitcoin Core security. A rainy Sunday evening is a great moment to write, so here is my new post, with some new thoughts.
People are trying to understand the security guarantees Bitcoin provides. Bitcoin game theoretic model is complex has not been completely analyzed. For example, some time ago I presented the extravagant ECDSA attack on Bitcoin, which I still can’t fit into any known formalization, although Bitcoin is being recently more mathematically modeled. Nevertheless, as always, interesting discussions and information is scattered in the forums and generally not well referenced. With this post I’ll start a series of post on some not so well known “attacks” that may affect in the future when the subsidy becomes non-existent or negligible, and I’ll also propose a new idea to replace the current longest-branch choosing rule (which is actually the branch with highest difficulty).
The Freeze on Transaction Problem
The freeze problem occurs if someone publishes a transaction with fees much higher than the block subsidy. I don’t remember who described the attack first. Suppose that, by mistake, a transaction is published with 50 BTC in fees. The transaction is included in a block at height n. If everyone acts rationally in his own interest, then the best choice for the remaining miners is to try to mine a competing block at the same height n including the high-fee transaction, to collect the fee for themselves. All the miners having solved the block at height n, now move on mining at height (n+1). But they won’t choose each other branches until one branch is sufficiently longer so that it is better to switch to it and abandon their own branch rather than try to keep the block with the high fee. This case is different from the real block competition case we see periodically on the blockchain, where the miners are generally split between two branches. Here there are multiple branches competing. If there are 10 “top” miners each having 10% of the network hashing power, then 10 different branches will compete. The analysis for this case is similar to the Gambler’s Ruin problem analysis present in the Satoshi paper, but with a fixed constant monetary incentive not to switch. Since the incentive to switch grows exponentially with the branch length difference, any initial constant is diluted. In the special and rare case that all the miners have exactly the same hashing power, then the network diverges, and this is equivalent as having two miners having exactly 50% of the hashing power each. So in principle the freeze on transaction problem is just a temporary disruption in the network, but not a fatal halt. Nevertheless, since during the freeze period each miner is mining on his own branch, it also means that moving forward with blocks is a lot slower. Assuming 10 miners having 10% of the total hashing power each (+/- 3%), the network becomes 10 times slower. I simulated it with a 50 BTC tx freeze fee, and 10 miners, and it takes approximately 6 blocks to converge, so the freeze time is approximately 60 times the block interval, or 10 hours. If the distribution is approximately 25% of the hashing power for each top miner, the freeze time is 4 hours.
Obviously what’s needed for the freeze problem to occur is that miners are 100% rational, greedy and prepared. They need to have a modified version of bitcoind which can automatically detect a high-fee transaction and prevent adding to the best chain a not-owned block containing such transaction. There will be no time for the miners to patch bitcoind if such transaction is manually spotted. Also the latest versions of bitcoind have preventions not to allow high fees by mistake. So the freeze problem is currently non-existent, but may pop up in the future in form of a state-sponsored attack.
The Freeze problem as an Attack
If an attacker plans to repeat such attack periodically at the expense of wasting a lot of BTC, there is little the current protocol can do, because miners will be prepared to take advantage of the attack. If the attacker issues a new fee burning transaction before the network converges, then the attacker can maintain incentives to keep every miner separated in his own branch. So wasting 50 BTC every 4 hours, an attacker can maintain the network frozen forever. Even if we restrict the maximum fee per transaction, the scripting system has infinite ways to create transactions whose output can be taken by anyone, and the attacker can announce the method miners can use to collect those BTC and even prepare and publish the bitcoind patches to automate collecting those transaction outputs.
The best thing the community can do is act together and cooperate to share the high transaction fee. This will neutralize the attack completely and allow miners to earn extra bitcoins. But cooperation in the Bitcoin community has never been easy. There is a technical solution which is to modify the Bitcoin protocol so that every transaction output has a maturity time of 6 blocks, and if a transaction output is redeemed multiple times in a 6 block interval, then the BTC amount is split between all redeemers, and also fees would be automatically shared in a 6 block sliding window. At a first glance, this provides a way for miners to cooperate even anonymously and there is no immediate drawback, but an in depth analysis is necessary.
In my next post I will talk about another theoretical attack on Bitcoin with a more fancy name that works if a large percentage of miners are rational and they know they are: the Chained Kickback Double-spend Attack (or “CHAKIDO”) 🙂
#1 by Cory Barnes on October 7, 2014 - 10:43 pm
Eventually, just switch to proof of stake with a fixed yearly growth. What’s the harm?
#2 by SDLerner on October 9, 2014 - 7:51 pm
A proof-of-stake system with a punishment system that you loose all your stake if you vote twice for two competing blocks may solve the problem.
#3 by hashman on October 15, 2014 - 1:17 pm
How would proof of stake change this? A large TX fee on NXT for example would be subject to the same considerations, just substititute stake for hashpower in Sergio’s analysis. And even if it did help somehow, the harm in such a swtich is obvious: everybody’s bitcoins become less valuable as the supply is inflated.