Quote from: Potent on December 01, 2017, 10:18:36 AM

If 10 billions people use bitcoin and everyone makes 1000 addresses, how much is probability of cross privkey between them?
I am uncomfortable for holding bitcoin because of this for long time.

Let's start with the binomial distribution:

Given a private key K, the event of interest is independently generating a matching private key, K'=K. So, we're just looking for the probability of any given private key. According to this source, the following range are valid private keys: "any 256-bit number from 0x1 to 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4140"

Rounding the upper bound down to 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE 0000 0000 0000 0000 0000 0000 0000 0000 gives the following decimal number:

U = 2²⁵⁶-1 - 2¹²⁹-1

(U for "Upper Bound") Simplifying exponents, changing the base to 10 and rounding:

U ~= 10⁷⁶-10³⁹ = 10³⁸(10³⁸-10)

This bound is quite approximate but it will work for back-of-the-envelope calculations. And since we're approximating anyway, we ignore the lower bound of 1, because it is negligible.

Our range has size 10³⁸(10³⁸-10) and every private key is equally probable. Thus, the probability of any given private key K' is p(K') = 1/(10³⁸(10³⁸-10)). Since we can represent the key-collision as a binomial experiment, to find the average number of collisions after n experiments, we just multiply n x p(K'). Let's find the average number of attempts we have to make at finding a key collision in order to have the same odds of success as winning the Powerball (1 in 175,000,000):

175 x 10^-6 = n x 1/(10³⁸ x (10³⁸-10))
n = 175 x 10^-6 x (10³⁸ x (10³⁸-10))
n = 175 x 10³² x (10³⁸-10) = 175 x (10⁷⁰ - 10³³) ~= 10⁷²-10³⁵

To avoid bignums, we reduce the largest exponent by one and throw away the error term:

n = 10⁷¹

This number has no standardized name - using standardized names it's about 100 septillion septillion sextillion. So, after making 100 septillion septillion sextillion attempts, the probability that you will find a private key collision is about the same probability as winning the Powerball. Note that the key fingerprint collision is not nearly as hard, I think we just have to divide the number of attempts by 2⁹⁶ ~= 10²⁹, so you'd only have to make about 10⁴² attempts, or a trillion nonillion attempts. Not bad odds when you think about it. I think I'll get to work on this right now.

(Apologies to the math professors... this is the kind of chainsaw arithmetic we use in engineering.)