On Mon, Nov 04, 2013 at 09:31:04AM -0430, Karn Kallio wrote: > > The paper "Majority is not Enough Bitcoin Mining is Vulnerable" may be of > interest. > > > http://arxiv.org/abs/1311.0243 > > Abstract. The Bitcoin cryptocurrency records its transactions in a pub- > lic log called the blockchain. Its security rests critically on the > distributed > protocol that maintains the blockchain, run by participants called miners. > Conventional wisdom asserts that the protocol is incentive-compatible > and secure against colluding minority groups, i.e., it incentivizes miners > to follow the protocol as prescribed. > We show that the Bitcoin protocol is not incentive-compatible. We > present an attack with which colluding miners obtain a revenue larger > than their fair share. This attack can have significant consequences for > Bitcoin: Rational miners will prefer to join the selfish miners, and the > colluding group will increase in size until it becomes a majority. At this > point, the Bitcoin system ceases to be a decentralized currency. > Selfish mining is feasible for any group size of colluding miners. We pro- > pose a practical modification to the Bitcoin protocol that protects against > selfish mining pools that command less than 1/4 of the resources. This > threshold is lower than the wrongly assumed 1/2 bound, but better than > the current reality where a group of any size can compromise the system.
I replied on the bitcoin-development email list with what I believe is a better solution than presented in the paper. In particular my solution returns the attack threshold to 51%, rather than the 25% they achieve: Remember that the selfish miner strategy outlined in the paper is essentially a way to use knowledge of what blocks miners will be mining on, from the "first seen" rule, and the ability to broadcast blocks you have mined more widely than other miners. That knowledge and ability is then used in conjunction with a small lead (obtainable by chance) to outpace the rest of the network. By making all miners easily identifiable you make gaining that informational and broadcast capability easier to obtain rather than harder. The attacker now only needs to connect to every identified miner with especially fast nodes. With judicious use of DoS attacks and low latency they can still gain the informational and broadcast "upper hand" over other miners and carry out the attack. Where the paper goes wrong is they don't recognize the fundemental nature of the strategy being based on an informational advantage. Their "pick a random side of the fork" strategy may work to some extent, but it's incomplete and isn't necessarily rational for the miners individually. The correct, and rational, approach for a miner is to always mine to extend the block that the majority of hashing power is trying to extend. The current relay rules don't give you that information at all, but they can if we do two things: 1) Relay all blocks that meet the PoW target. (as suggested in the paper) 2) Relay block headers that nearly meet the PoW target. Mining strategy is now to mine to extend the first block you see, on the assumption that the earlier one probably propagated to a large portion of the total hashing power. But as you receive "near-blocks" that are under the PoW target, use them to estimate the hashing power on each fork, and if it looks like you are not on the majority side, switch. This very effectively defeats the paper's selfish-miner strategy, as all miners will very quickly be mining on the block that truly has the majority of hashing power trying to extend it. This is also a better overall outcome, because it puts the 51% attack threshhold back at 51% http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg03137.html -- 'peter'[:-1]@petertodd.org 0000000000000002229a07d0a264dd3f687d3d93d6eb14f26205d5dab8db5afa
signature.asc
Description: Digital signature
_______________________________________________ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography