If bitcoin ever became worth alot of money say where you could buy an entire country of people a pizza for every one of them, I bet people would be working on brute forcing all the bitcoin private keys. That is one way to get ahold of it without "computing" it. Luckily though bitcoin p2pkh addresses are secure. So that can never happen. I mean you would have to start at 0x0000...000 and work your way up to 2^256? Who needs more security than that?
It should be fine...
as long as the algorithms hold.
But consider that a megabyte was thought to be all a person would ever
need:
https://www.wired.com/1997/01/did-gates-really-say-640k-is-enough-for-anyone/Perhaps there will be dramatic computing or algorithm performance increases over time.
Individuals have more than one address so that also changes the requirements.
If quantum computing (or just computing) became powerful enough, then bitcoin could counteract this
new space perhaps by increasing key lengths. A few bytes goes a very long way.
It's hard to say what the future holds though. There may be algorithms that were considered impossible, that become possible.
The proof for Fermat's last theorem comes to mind. The FLT current proof relies on properties of elliptic curves, which are also related
to encryption algos. There are all sorts of mathematical problems, such as the millenium problems, Goldbach's or Beal's conjectures,
that remain unproven yet could impact these encryption through new number theories.
One hopes that with any of these changes that bitcoin could transition at an appropriate
rate to better algos or key/address spaces.
Elliptic curves are pretty neat.
(Below is on birthday paradox, not the main topic..)
That's little similar how the Birthday Paradox is calculated, the prob of no collision is:
For no 2 people in a group of size "M" have same Birthday (N
Prob(all different)= 1* 364/365*363/365*...*(365-X+1)/365]
(The 1st person can have any birthday, the 2nd only 364 for this to be wrong, the 3rd only 363,..)
Then it was found out that X as small as 25 can make this probability < 0.5
Except your space is much larger than 365, since it is 2^160.
So,
Probability(all different; eg. no collision) = 1 * [(2^160-1)/(2^160)] * [(3^160-1)/(3^160)] ... * [(2^160-X)/(2^160)]
If you want to calculate this, you are going to struggle with even most modern software.
You can calculate the probability by converting to exponents.
exp(y) = 1+y for very small y
(2^160-1)/(2^160) = 1-1/2^160 = exp(-1/2^160)
For X tries of addresses, the probability is
P(all different) = exp(-sum(i)/2^160)
where sum(i) is the sum of numbers from 1 to X: sum(i) = 1+2+3+...X.
If you want a 50% chance, then
P(a.d.) = .5 = exp(-sum(i)/2^160) ---> log(0.5) = -0.3 = -sum(i)/2^160
sum(i) = 0.3 * 2^160
sum(i) has a closed form solution, sum(i) = X(X+1)/2
So, X(X+1)/2 = 0.3 *2^160
X(X+1) = 0.6 *2^160
X^2 + X = 0.6 * 2^160
Because the number is so large, we can drop out the single powered term, X, and solve:
X^2 ~= 0.6 *2^160
X ~= 0.77*2^(160/2) ~= 2^80 ~=10^24
So, if birthday paradox applies, you'd still have to search a space that is quite large (10^24) for a
50% chance to collide with one address -- but requires that there are X = 10^24 addresses worth finding, which isn't true.
Birthday paradox requires that the number of searches is also the number of interesting birthdays/addresses, which isn't true
in a collision search, where the searches can easily outnumber the interesting birthdays/addresses.
----
There are several things that change this from a birthday problem:
1) keys/addresses will not overlap between individuals, as one can assume that individuals want
to keep their addresses unique from others
[so that 364/365*363/365...(365-X)/365 doesn't apply, raising the difficulty]
2) the reward for any given collision is not equal
3) not all individuals with addresses are searching the entire space
4) Birthday paradox doesn't change the probability of finding the key to a single specific address
Using either point one, three or four above reduces the chances of a collision, i.e. the X^2+X term goes to a simple X.
That's because you are searching for a simple match of one address per go, reducing your search space by that amount per search.
Probability(no collision) = 1 * [(2^160-1)/(2^160-0)] * [(2^160-1)/(2^160-1)] ... * [(2^160-1)/(2^160-X)]
which is probability(no collision) = 1 * [(2^160-1)/(2^160)]^X due to the insignificant effect of the -X term on 2^160.
P = 0.5 = exp(-X/2^160)
-log(0.5) = -X / 2^160
X = log(2) * 2^160
Thus, fancy mathematics shows that to obtain a 50% collision with a single address, you have to search just under half of the space. A bit of a weird result, but does not use birthday paradox.
To change the functions to include that you might have N number of addresses that are not empty worth searching, so the needed searches is smaller (by the factor of interesting addresses):
Probability(no collision) = 1 * [(2^160-N_interesting)/(2^160)]^X
X = log(2) * 2^160 / N_interesting
I think I got that correct... but there are obviously a lot of pitfalls in stats.
For those that disagree with me, wikipedia agrees with you:
https://en.wikipedia.org/wiki/Birthday_problemYou can raise the probability of collisions with using a priori knowledge (public states, pollard's kangaroo, poor randomisation, poor k),
but that's no longer birthday paradox.
