kjj
Legendary
Offline
Activity: 1302
Merit: 1000


December 26, 2011, 02:49:04 PM 

I still prefer my idea of adding exponential difficulty deltas beyond a shallow reorg. It doesn't require that the client track any new data sources and it doesn't require an AI to interpret trends. It also allows a recipient to calculate a waiting time (depth really) for an incoming transaction that provides them with whatever level of concrete mathematical security they desire.
How it would work if you missed all of my posts on this last summer and fall:
First, we want to be able to handle ordinary "honest" reorgs exactly like we've been doing it. The usual estimate I use for this is once every 300 blocks on average for a single block shuffle. The reorglog on block explorer says there have been 29 reorgs in the 23523 blocks, or about 1 in 800. In practice, blockexplorer will be on the winning side about half the time (and thus not record a reorg), so the real number is 1 in 400, which means that my 1 in 300 estimate is fairly close, and is on the conservative side.
That means that on average, we will get a single block reorg every other day. And a two block reorg every other year. And a three block reorg twice per millennium. Beyond that, it gets silly, because there probably won't be an honest six block reorg before the sun burns out.
So, we pick a parameter, call it S, and set it to a number higher than we ever expect to see from an ordinary reorg. 6 would probably be good here, but just to be really safe, I'll go with 12 in my example.
Now, any reorg of depth <= S is handled normally. The fun happens when an attacker wants to replace more than S blocks in a single shot.
I'm going to call the second parameter P, and it is the base of the exponential function. Any number greater than 1 will work here. Bigger numbers work more quickly, but small numbers still work great. For this example, I'm going to go with 1.05.
Now, we do some calculating. We go back in our chain to the last common ancestor, the point where the potential new chain split off. We add up all of the difficulty stored in the blocks after this point, and we call it X, while we are doing that, we count how many of our blocks will need to be thrown out if the reorg succeeds, and we call that D. Then we add up all of the difficulty beyond this point in the new chain, and we call it Y. Finally, we calculate F=P^(DS).
With me so far? We have:
D  depth of the reorg from our point of view, the number of blocks that will be invalidated X  difficulty of the reorg, again from our point of view, the amount of work that will be discarded Y  difficulty of the new chain, the amount of work that will replace X S  the number of blocks we are discarding F  The exponential difficulty function that starts small, but grows more or less rapidly
Again, if D <= S, then the comparison is just is Y>X? If yes, then reorg, if no, then no reorg. This is simply the current logic. However, if D > S, then the comparison is Y>(X*F).
If we assume blocks of constant difficulty, P=1.05 and S=12, we get:
12 blocks requires 12 * 1.00 blocks = 12.00 = 13 blocks (the new chain must be longer) 13 blocks requires 13 * 1.05 blocks = 13.65 = 14 blocks 14 blocks requires 14 * 1.10 blocks = 15.43 = 16 blocks 15 blocks requires 15 * 1.15 blocks = 17.36 = 18 blocks 21 blocks requires 21 * 1.55 blocks = 32.57 = 33 blocks (the chain is 50% stronger after just 3.5 hours) 24 blocks requires 24 * 1.79 blocks = 43.10 = 44 blocks 27 blocks requires 27 * 2.08 blocks = 56.13 = 57 blocks (twice as strong after 4.5 hours) 36 blocks requires 36 * 3.22 blocks = 116.10 = 117 blocks 60 blocks requires 60 * 10.4 blocks = 624.07 = 625 blocks (ten times the work needed after 10 hours) 144 blocks requires 144 * 626 blocks = 90229 blocks (after a day, the attacker needs to do over 600 times as much work)
The typical objections to my scheme involve honest network partitions. I don't see that as a problem. The worst case would be the network split exactly in half (by hashing power, not node count or geography), and staying divided for about 4 hours (assuming S=12), which is something we would notice, since it would involve aliens blowing up all of our communication satellites and putting the earth on a gigantic bandsaw to cut it into halves along a great circle through Minnesota and Texas.
