[hashcash] Re: Statistics of hashcash collisions

  • From: Hubert Chan <hubert@xxxxxxxxx>
  • To: hashcash@xxxxxxxxxxxxx
  • Date: Thu, 27 May 2004 01:08:19 -0400

>>>>> "Anonymous" == Anonymous  <cripto@xxxxxxx> writes:

[...]

Anonymous> The time for hashcash collisions of a substantial number of
Anonymous> bits, 10 or more, can be represented by a Poisson
Anonymous> distribution.

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.

The number of hashcash collisions that we will find after N trials
follows a binomial distribution, which is approximated (for large N) by
a Poisson distribution.

so:
time to mint a single token ~ exponential distribution
number of tokens minted after a fixed time ~ Poisson distribution

Your analysis seems to be correct, though.  But it could be rendered
simpler by using the right distribution (and your introductory sentence
could benefit from the precision).

-- 
Hubert Chan <hubert@xxxxxxxxx> - http://www.uhoreg.ca/
PGP/GnuPG key: 1024D/124B61FA
Fingerprint: 96C5 012F 5F74 A5F7 1FF7  5291 AF29 C719 124B 61FA
Key available at wwwkeys.pgp.net.   Encrypted e-mail preferred.


Other related posts: