@rico666
"....Because we assume the private keys to addresses with funds on them are also uniformly distributed in the search space, this means that the effective search space until any collision for these is found is 160bit - log2(9000000)bit = ~137bit."
I might be wrong, but because of this (wolfram alpha expression):
1-(((2^21)! * (2^160 über 2^21))/((2^160)^(2^21)))
I'm not sure I follow this. (mathematically I do, but semantically I don't)
Where do you get the 2
21 from? Thats 2M.
I assume the possibilty of hitting one of your approximately 2,5 mil target addresses is:
1.5*10^-36 or 1/(2^119)
We have 14 mil target addresses at the moment.
If you agree with the things written above, I would recommend to expand the target address space to 2^23 (8.x mil pub keys)
and gain a 4 times higher possibility to hit one of your targets:
2.4*10^-35 or or 1/(2^115)
It's still 160 - log
2(14000000) = ~ 136.26bit search space
Rico
Hello Rico,
what I wanted to submit was that in terms of prohability you should consider to expand your public address list for comparision from about 2.x million to 8.y million pub keys. I have read somewhere, maybe in some older postings, that your address list covers only 2.5 million addresses. As you know the birthday paradox (
https://en.wikipedia.org/wiki/Birthday_problem) says with an increasing number of persons (in our example: public addresses) the prohability to find 2 with the same birthdays (in our example: RIPEMD-160 hash number) increases exponentially.
2 million addesses give us a prohability of:
1-(((2^21)! * (2^160 über 2^21))/((2^160)^(2^21))) = 1.504 × 10^-36
or differently:
1-e^((-2^21*(2^21-1))/(2*2^160)) = 1.504 × 10^-36
8 million addesses give us a prohability of:
1-e^((-2^23*(2^23-1))/(2*2^160)) =2.407 × 10^-35
4 times more public addresses give a 16 times higher prohability to hit one target. That´s why I suggested to expand the public key address space. Want I did not know at the time of writing that you already expand your list to 14 million addresses.
So your prohability with 14 million addresses for each key you are generating at the moment is about:
1-e^((-2^23.7389*(2^23.7389-1))/(2*2^160)) = 6.70521 × 10^-35
or simpler as we have big numbers:
(2^23.7389)^2/(2*2^160) = 6.70521 × 10^-35
Besides that, I came across an interessting article about increasing the prohability of collision through interating hash functions:
https://security.stackexchange.com/questions/61756/wont-all-hashes-collide-after-enough-iterations-with-a-static-saltand
http://crypto.stackexchange.com/questions/15068/entropy-when-iterating-cryptographic-hash-functionsN(hash1)>N(hash2)>N(hash3)>N(hash4)....>N(hashx)
due to collisions and the lacking to use the full 256 rsp. 160 bit space.
4 hashes have to be done to create a bitcoin address. This is surely reducing the number of different pub addresses further.
The collisions and mapping errors of each hash level causing an exponential effect in reducing the output.
That is giving you a better prohability than 6.70521 × 10^-35.
Reagrds,
Janu$$