Quote from: daemonfox on November 07, 2013, 01:16:35 PM

I fail to see how this is even relevant... are they trying to claim a small network making up about 10% of the total BTC hashrate has event he REMOTEST chance to outpace the 90% in block solutions... it is mathematically impossible... the 10% on average would only be able to generate blocks at this difficulty 1/10th as quickly as the main network...

Am I missing something here... or is that just a blatant oversight by the university? 10% of the hashrate cannot generate the same amount of blocks as 90% in the same time period at the same difficulty... paper debunked.

The paper isn't quite that crazy. To begin with, they're assuming 33% of the hashrate, not 10%. The idea is that someone with full control over 1/3 of the hashrate might be able to find two blocks in the time it takes the rest of the network to find one, which is certainly possible. When the rest of the network finds its first block the attacker can release both blocks. At that point the rest of the network has wasted a block's worth of hashing, since the block it found doesn't make it into the blockchain. The attacker's costs are 1/3 of the total, or about half of what was spent on the main blockchain, and the attacker gets the reward for both blocks while the rest of the network gets nothing. On the flip side, of course, the attacker can't claim the rewards for all the times it only found one block rather than two, since it has to keep the first block private.

If the attacker holds out for three blocks rather than publishing after the first two, the situation gets a bit worse. At that point they can wait until the network finds a new block (N) and then release two (N, N+1), while maintaining a one-block head start. Then they can continue working on finding a successor to their remaining hidden block (N+2) while the network is still searching for N+1. If the attacker wins that race they can keep going, releasing the older blocks and holding the newer ones in reserve. If not, they'll have to start over, but in the meantime they get all the rewards and the rest of the miners get nothing (while spending twice as much).

There are some suggestions that the minority pool could improve its ability to stay ahead by carrying out a Sybil attack and promoting its own blocks just ahead of the "honest" miner's blocks through superior connectivity, but I just don't see that working in any realistic environment. Resistance against Sybil attacks is always welcome, of course, as is better connectivity among "honest" miners.

The main flaw, as I see it, is that the paper assumes 33% of the hashrate is controlled by someone willing to undermine the network in this way. There are pools with 33% of the hashrate, but the pool's administrators can't do this on their own, and I can't see a majority of the miners going along with this scheme to make some short-term cash at the expense of long-term trust in Bitcoin. If miners were purely profit-oriented we'd probably end up with a monopoly anyway--larger pools are more efficient and have less variance than smaller pools. As long as miners continue to keep an eye on the pool operators' policies with an eye toward maintaining the long-term value of Bitcoin, there is no issue.

The paper suggests selecting the active blockchain out of two equal-length candidates randomly to thwart Sybil attacks. My own proposal is a bit different: implement a hysteresis function to make it more difficult to switch blockchains. Instead of switching whenever a new chain is strictly more difficult than the current chain, switch when the new chain's total difficulty is strictly greater than the current chain's difficulty, plus the square of the difficulty of all the blocks which are only in the old chain. To extend the old chain by one block, no penalty. To undo/replace one block, your chain has to be at least two blocks longer rather than just one. To undo two blocks, your chain has to be more than four blocks longer. To undo six blocks, more than thirty-six blocks longer, etc. As a bonus, this could probably replace the current checkpoint system, since no one is going to get the four million block lead which would be necessary to undo the last two weeks (2016 blocks) of progress on the main blockchain, and checkpoints are generally less frequent than that.