[hashcash] Statistics of hashcash collisions

One of the surprising properties of hashcash type collisions is the
variation in how long it takes to find them.  A collision which takes
a nominal or expected time of 1 minute sometimes seems to happen in
just a few seconds, and other times drags on for several minutes.
Here is some information on the statistical nature of this variation.
(Note: these are not actually collisions, but rather outputs of the hash
function which are distinguished by having several bits in predefined
states, for example a certain number of leading zero bits.)

The time for hashcash collisions of a substantial number of bits,
10 or more, can be represented by a Poisson distribution.  This is a
distribution characteristic of a low-probability event which has many
independent attempts at success.  For such collision sizes, this is
exactly how hashcash works.  Each individual hash has a low probability
of success, but the program calculates many hashes until it finds a hit.

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.
This will tell us the probability that we will have seen a hit by that
value of v.  By taking the difference of successive values this will
tell us the probability of a hit in various intervals of v.

Without further ado, here is the table:

v range     Probability
-----------------------
  0  - 1/16      6%
1/16 - 1/8       6%
1/8  - 1/4      10%
1/4  - 1/2      17%
1/2  - 1        24%
  1  - 2        23%
  2  - 4        12%
  4  - 8         1.8%
  8 or over      0.03%

To use an example, suppose you have a computer and a collision size which
you calculate (based on the counts needed and the speed of the iteration
in counts/second) will take 1 minute on average to create a collision.
Then there is a 6% chance it will take less than 4 seconds; 6% for 4-7
seconds; 10% for 7-15 seconds; 17% for 15-30 seconds; 24% for 30-60
seconds; 23% for 1-2 minutes; 12% for 2-4 minutes, 1.8% for 4-8 minutes,
and roughly 0 for any time over that.

This was pretty surprising to me, as it seems like I often spend more
time waiting for a collision to happen in my tests.  Another peculiarity
is that if we run for the time corresponding to v=1, there is actually
a greater than 1/2 chance of having seen a hit.  The chance is 1 - 1/e
or 63%.  So the median time to a collision is somewhat less, about 69%
of the nominal time.  In the one minute nominal trial case (calculated
on the basis of trials/second), the median time would be 42 seconds.

One way to smooth these values would be instead of calculating, say,
a single 23-bit collision, calculate 8 20-bit collisions.  You'd have
to make the hashcash field bigger to hold 8 collisions rather than
just one.  But this would even out the compute time by averaging over
several attempts, making the time more predictable.  My calculations
indicate that with 8 collisions, there is a 5% chance of it taking half
as long as it "should", and a 1% chance of it taking twice as long,
compared to 39% and 14% respectively with a single collision.

Other related posts: