*From*: Adam Back <adam@xxxxxxxxxxxxxxx>*To*: hashcash@xxxxxxxxxxxxx*Date*: Thu, 27 May 2004 07:33:57 -0400

Hubert Chan wrote: | I think you are mixing up your distributions. The *time* taken to | find a collision follows a geometric distribution, which is a | discrete distribution, and is approximated by the exponential | distribution, which is a continuous distribution. Yes I've been using geometric. On Tue, May 25, 2004 at 07:01:40AM +0200, Anonymous wrote: > Call v the product of the probability of a success on each trial times > the number of trials. For a 20 bit hashcash collision, v of 1 would > correspond to approximately 1 million trials. Then the chance of having > exactly n hits in time v is: > > P_v(n) = v^n * exp(-v) / n! > > Now, with hashcash we don't run past our first hit. So for this analysis > I will calculate the probability of 1 - P_v(0) for various values of v. so P_{1/16} = 1 - exp(-1/16) = 0.0605 P_{1/8} - P_{1/16} = 0.0569 P_{1/4} - P_{1/8} = 0.103696 etc with (discrete) geometric distribution: P(i=n) = q^{n-1}.p P(i>=n) = q^{n-1} or P(i<n) = 1-q^{n-1} so take b=10, n = 2^b = 1024, p = 1/n, q = 1-p v range probability ----------------------- 0 - 1/16 .05969735974105994696 1/16 - 1/8 .05699703132405127909 1/8 - 1/4 .10383875234535864133 1/4 - 1/2 .17249160475988258728 1/2 - 1 .23891607963302808331 1 - 2 .23272391049199429143 2 - 4 .11703751500437658655 4 - 8 .01796326612642484726 8 or over .00033448057382373679 I think poisson will approximate to q^n rather than q^n-1, obviously as b and so n=2^b gets larger (recall p=1/n,q=1-p) they get asymptotically close. Adam

**Follow-Ups**:

**References**:**[hashcash] Statistics of hashcash collisions***From:*Anonymous

- » [hashcash] geometric vs poisson (Re: Statistics of hashcash collisions)
- » [hashcash] Re: geometric vs poisson (Re: Statistics of hashcash collisions)