[hashcash] Re: stamp collisions

On Sun, Aug 29, 2004 at 03:46:59PM -0400, Atom 'Smasher' wrote:
> has anyone researched the probability of two stamps being minted the same?

So according to the birthday paradox it takes about 2^(n/2) stamps to
get a collision between 2 of them.  

> how is that affected by stamp value?

However an additional problem with hashcash v0 format is the same
collision space is used by the minting process.  This means larger v0
stamps are more likely to collide.  (Well the random string can be any
size you like, but the implementation did not vary it; earlier
versions used 64 bits, later versions 96 bits.)

So looking at a 96 bit random string v0 stamp, if it had 0 bits of
collision it would take average approx. 2^48 operations.  However if
you had 20 bit stamps, that consumes average 20 bits of the random
string leaving 2^38 stamps.  (Same exercise with the older 64 bit
random string gives a likely collision after 2^22 stamps).

Also you can look at it a different way which is eg. what probability
of a stamp collision after k stamps.  This is not good either about 3%
probability of collision after 1 million stamps with 64-bit random
string (and 20 bit stamps).  (The bc program below gives birthday
function (type b(365,23) gives about 0.5, so b(2^44,1000000) gives
3%))

define b(n,r) {
  a = 1;
  for ( i = n; i > n-r; i-- ) {
    a = a * i / n;
  }
  return ( 1 - a );
}

With v1 stamps the full collision string is used for avoiding stamp
collisions because there is a separate field for counting to find
partial hash collisions.  With the C implementation this defaults to
96-bits or 2^48 stamps before 1st collision, which is pretty small.

Adam

Other related posts: