Quote from: Meni Rosenfeld on May 07, 2014, 11:21:23 AM

Quote from: jl2012 on May 07, 2014, 06:54:42 AM

Quote from: Meni Rosenfeld on May 07, 2014, 06:28:19 AM

Quote from: jl2012 on May 07, 2014, 04:17:14 AM

I don't think this is really interesting as we won't have infinite time.

Could someone calculate the probability of A outpacing B in T years, given that:

The hashrate ratio of A:B = 1:4
B started mining 1 year before A

For T = 10^3, 10^6, and 10^9. I bet even with the 10^9 years the probability is still very tiny.

Actually, the probabilities for T = 10^3, 10^6, and 10^9 are 82.2%, 96.8%, 99.4%. Even for T=1 the probability is 15.9%.

I'm assuming of course the simplest case. In general, with a head start of S and a hashrate ratio of 1:H, the chance to succeed in time T is
1 - \exp ( - int_S^{S+T} 1/(Ht) dt )

It sounds really unbelievable for T=1 the probability is 15.9%. To outpace B, A has to outpace the work done in the first year (which the expected time is 4 years), while at the same time B is still working 3 times faster than A.

Would you please present your integration in https://www.wolframalpha.com ? Thanks.

Sure, http://www.wolframalpha.com/input/?i=1+-+Exp%28-Integrate%281%2F%284+t%29%2C+{t%2C+1%2C+2}%29%29

By the way, I've edited to add the simpler form of this expression, 1 - (1 + T/S) ^ (-1/H).

I parsed your scenario as Attacker:Honest = 1:4 and that the attacker never contributed to the honest network. If instead it's Attacker:Total = 1:4, so Attacker:Honest = 1:3 (but the attacker was honest in the first year), it's even higher, 17.0%.

It's actually quite intuitive. Suppose he tries a weaker strategy of trying throughout the year to find a single huge block that is equal to 2 years of the honest network's work. This is equal to 8 years of the attacker work, so the chance to find such a huge block in a year is 1/8 = 12.5%. But in his actual strategy he spends the first day trying to find a block equal to 1 year, in the second day a block equal to 1.03 years, and so on, so the probability is higher.

Needless to say, if instead of a huge block he tried to find several normal blocks, he would have no chance. The variance then is much lower so he can't luck out.

How about another scenario:

Hash rate A:B = 1:H . A is attacker, B is honest

A wants to outpace the latest X year's blocks. What is the probability for him to succeed in Y years? (A only wants to outpace the latest blocks. For example, with X=1, on 1 Jan 2014, A wants to mine a single block to outpace all the blocks since 1 Jan 2013; on 15 Jan 2014, the target will be the blocks since 15 Jan 2013). I think it's even easier, right?