[Bitcoin-development] The Bitcoin Freeze on Transaction Attack (FRONT)
I would like to share with you a vulnerability in the Bitcoin protocol I've been thinking of which might have impact on the future of Bitcoin. Please criticize it! *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. -- Meet PCI DSS 3.0 Compliance Requirements with EventLog Analyzer Achieve PCI DSS 3.0 Compliant Status with Out-of-the-box PCI DSS Reports Are you Audit-Ready for PCI DSS 3.0 Compliance? Download White paper Comply to PCI DSS 3.0 Requirement 10 and 11.5 with EventLog
Re: [Bitcoin-development] The Bitcoin Freeze on Transaction Attack (FRONT)
On Sun, Oct 5, 2014 at 4:00 PM, Sergio Lerner sergioler...@certimix.com wrote: I would like to share with you a vulnerability in the Bitcoin protocol I've been thinking of which might have impact on the future of Bitcoin. Please criticize it! The Freeze on Transaction Problem I should point you to some of the tools that have been discussed in the past which are potentially helpful here: The first is the use of locktime on normal transactions. This behavior is already in Bitcoin core git: The idea is that users of the system should locktime their transaction at a point as high as they expect it to get included. If used well this means that there should always be a base of fees which can only be collected by future blocks, creating an incentive to move forward. This may be particularly effective if the limitations on blocksize mean that there is always a healthy standing load. The second is having block commitments in transactions (https://en.bitcoin.it/wiki/User:Gmaxwell/alt_ideas). The idea is that the data under signature in a transaction could commit to some recent block which _must_ be in the chain or the transaction's fee cannot be collected (or, at least, not all of the fee). This would allow transacting users to 'vote with their fees' on the honest chain. Arguably this could also be used to pay for doublespending forks, but you can already do that by paying fees via a chain that stems from the doublespend. This greatly complicates strategy for forking miners, since future transactions which you haven't even seen yet may have fees conditional on the honest chain. I think both of the above are obviously useful, should be done, but don't completely address the concern, they may be adequate. The third is fee forwarding. An example form would be that the miner gets half the fees, the rest are added to a pool which pays out half in every successive block. This can prevent unusually high fees from making as much reorg pressure and more correctly models what people would like to pay for: getting their txn buried. The huge problem with this class is that miners can demand users pay fees out of band, e.g. with additional txouts (just make a different version of the tx for each miner you wish to pay) and escape the process. I have had some notions about fees that come in the form of adjusting the difficulty of creating a block slightly (which is something that can't be paid out of band), but such schemes becomes very complicated very fast. I am unsure if any form of fee forwarding is workable. Something you might want to try to formalize in your analysis is the proportion of the network which is rational vs honest/altruistic. Intuitively, if there is a significant amount of honest hashrate which is refusing to aid the greedy behavior even at a potential loss to themselves this strategy becomes a loser even for the purely greedy participants. It would be interesting to characterize the income tradeoffs for different amounts of altruism, or whatever convergence problems an attempt by altruistic participaints to punish the forkers might create. -- Meet PCI DSS 3.0 Compliance Requirements with EventLog Analyzer Achieve PCI DSS 3.0 Compliant Status with Out-of-the-box PCI DSS Reports Are you Audit-Ready for PCI DSS 3.0 Compliance? Download White paper Comply to PCI DSS 3.0 Requirement 10 and 11.5 with EventLog Analyzer http://pubads.g.doubleclick.net/gampad/clk?id=154622311iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] The Bitcoin Freeze on Transaction Attack (FRONT)
On Sun, Oct 5, 2014 at 4:40 PM, Gregory Maxwell gmaxw...@gmail.com I should point you to some of the tools that have been discussed in the past which are potentially helpful here: Ah, I should also mention a somewhat more far out approach which helps here as a side effect: If transactions were using the BLS short signature scheme (a very compact EC signature based on pairing cryptography) there is a scheme so that you securely can aggregate the signatures from multiple messages into a single signature (also has nice bandwidth properties) and still verify it. It also works recursively, so aggregates can be further aggregated. A consequence of this is that you cannot remove a (set of) signature(s) from the aggregate without knowing the (set of) signature(s) by itself. If the coinbase transaction also contains a signature and if some non-trivial portion of fee paying users relayed their transaction privately to miners it, then other miners would only learn of the transaction in aggregated form. Without knowing the transaction by itself they could not pull it out of a block separately from the coinbase payment and add it to their own block in a fork. (In general this provides several anti-censorship properties, since if someone passed you an aggregate of several transactions you could only accept or reject them as a group unless you knew the members separately). The use in aggregation can be done in a way which is purely additive (e.g. in addition to regular DSA signatures), so even if the cryptosystem is broken the only harm would be allowing disaggregation... but unfortunately the pairing crypto is pretty slow (verification takes a 0.5ms-ish pairing operation per transaction). -- Meet PCI DSS 3.0 Compliance Requirements with EventLog Analyzer Achieve PCI DSS 3.0 Compliant Status with Out-of-the-box PCI DSS Reports Are you Audit-Ready for PCI DSS 3.0 Compliance? Download White paper Comply to PCI DSS 3.0 Requirement 10 and 11.5 with EventLog Analyzer http://pubads.g.doubleclick.net/gampad/clk?id=154622311iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] The Bitcoin Freeze on Transaction Attack (FRONT)
On Sun, Oct 5, 2014 at 4:54 PM, Jorge Timón jti...@blockstream.io wrote: In any case, it is interesting to think about this things since mining subsidies will eventually disappear and then transaction fees will ALWAYS be higher than subsidies. You can imagine that instead of subsidy Bitcoin came with a initial set of nlocktimed transactions that pay fees, one block at a time, for each block from the start until the subsidy goes away. Perhaps that mental model might make it clear why some people think that the nlocked transactions and the block size being lower than the instant offered demand (there is always a backlog) are both things which address the concern of this thread. :) -- Slashdot TV. Videos for Nerds. Stuff that Matters. http://pubads.g.doubleclick.net/gampad/clk?id=160591471iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] The Bitcoin Freeze on Transaction Attack (FRONT)
On Mon, Oct 6, 2014 at 1:40 AM, Gregory Maxwell gmaxw...@gmail.com wrote: Something you might want to try to formalize in your analysis is the proportion of the network which is rational vs honest/altruistic. Intuitively, if there is a significant amount of honest hashrate which is refusing to aid the greedy behavior even at a potential loss to themselves this strategy becomes a loser even for the purely greedy participants. It would be interesting to characterize the income tradeoffs for different amounts of altruism, or whatever convergence problems an attempt by altruistic participaints to punish the forkers might create. Not only that, greedy miners may actually have an incentive to just follow the longest chain. Say I'm a small miner and I know that the chances of re-mining the high tx and getting that block into the longest chain are minimal or null. Then I will probably prefer to just mine on top of the longest chain. So 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 is not necessarily true. p * 50 can be lower than q * 25 if p 2*q. P and q depend on what everyone is doing, not just you. In any case, it is interesting to think about this things since mining subsidies will eventually disappear and then transaction fees will ALWAYS be higher than subsidies. -- Slashdot TV. Videos for Nerds. Stuff that Matters. http://pubads.g.doubleclick.net/gampad/clk?id=160591471iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
