[hashcash] empirical results (Re: Statistics of hashcash collisions)

On Tue, May 25, 2004 at 07:01:40AM +0200, Anonymous wrote:
> 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%
> 
> 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.

Not having time to run 10k 23 bit collisions, I ran 10k 8 sets of
7-bit collisions, using the same ranges as above for comparison I have
(these are close matches for predicted):

  range     Probability
-----------------------
  0  - 1/16      0.000%
1/16 - 1/8       0.000%
1/8  - 1/4       0.06%
1/4  - 1/2       4.8%
1/2  - 1         50%
  1  - 2         44%
  2  - 4         0.97%
  4  - 8         0.000%
  8 or over      0.000%

for comparison the empirical 10k 10-bit figures are:

  range     Probability
-----------------------
  0  - 1/16      6.0%
1/16 - 1/8       5.8%
1/8  - 1/4       11%
1/4  - 1/2       17%
1/2  - 1         24%
  1  - 2         24%
  2  - 4         11%
  4  - 8         2.0%
  8 or over      0.000%

(very closely tying with the predicted).

Adam

Other related posts: