Yesterday evening a person ask me:
"If bitcoin keys are generated randomly by the software,
isn't there a probability that two different people can generate the same
private key?"
This probability is astronomically small and we can compute it approximately.
To solve this we need to take into account that there are N = 2^256 = 10^77
possible private keys, but what we should look is the space of bitcoin addresses,
because to spend a P2PKH or P2WPKH output it suffices to have a
private key that produces the
same public key hash in the transaction output, ie. some private key that
produces a specific bitcoin address.
Since bitcoin addresses are computed from RIPEMD160 hashes, this means that the
space of bitcoin address is M=2^160=10^48.
If we consider x=10^10 people (8 billion at the time of writing)
in the world would generate y=10^6 addresses in their lifetime;
to put into perspective there are 800000 hours
in the lifetime of a 100 year old person.
Then the probability of no collision at all
is the number of possible ways to hit different addresses in the address space:
M (M-1) (M-2) ... (M-xy+1) = M! / (M-xy)!
divided by the number of possible choices:
M^(xy)
hence the probability of no collisions is
prob0 = M! / (M-xy)! / M^{xy}
since M!/(M-xy)! is approximately
M^{xy} - (1+2+...+xy) M^{xy-1} = M^{xy} - (xy)^2 /2 M^{xy-1}
we have
prob0 = 1 - (xy)^2 / 2 / M
Now, the probability of having at least one collision is prob1 = 1-prob0
which for large numbers at leading order becomes
prob1 = (xy)^2 / 2 / M
The square in the numerator the responsible for the so called
birthday paradox, ie. in a group of 20 people the chances of a birthday
collision is very high because 20^2/2 = 200 which is comparable to the number of
days in the year.
The collisions in the case of bitcoin are so unlikely because (xy)^2 = 10^32
while M=10^48 so that
prob1 = 1/10^16 = 0.000 000 000 000 000 1
not as small as the probability of a private key collission but still very
unlikely.
Lagrange
npub1qq…y7nsu
2023-07-07 13:01:16
Author Public Key
npub1qq30cwhsrwh7zanyx7u8mykmfhfze0gs32cyf24qq57dctuanaus5y7nsuPublished at
2023-07-07 13:01:16Event JSON
{
"id": "1f9454e2790f7681a135ccb437b36b84e897b232cdafc77a07dc9753531eea8b",
"pubkey": "0022fc3af01bafe1766437b87d92db4dd22cbd108ab044aaa0053cdc2f9d9f79",
"created_at": 1688727676,
"kind": 1,
"tags": [],
"content": "Yesterday evening a person ask me:\n\"If bitcoin keys are generated randomly by the software,\nisn't there a probability that two different people can generate the same\nprivate key?\"\n\nThis probability is astronomically small and we can compute it approximately.\nTo solve this we need to take into account that there are N = 2^256 = 10^77\npossible private keys, but what we should look is the space of bitcoin addresses,\nbecause to spend a P2PKH or P2WPKH output it suffices to have a \nprivate key that produces the \nsame public key hash in the transaction output, ie. some private key that\nproduces a specific bitcoin address.\nSince bitcoin addresses are computed from RIPEMD160 hashes, this means that the\nspace of bitcoin address is M=2^160=10^48.\n\nIf we consider x=10^10 people (8 billion at the time of writing) \nin the world would generate y=10^6 addresses in their lifetime;\nto put into perspective there are 800000 hours \nin the lifetime of a 100 year old person.\nThen the probability of no collision at all\nis the number of possible ways to hit different addresses in the address space:\nM (M-1) (M-2) ... (M-xy+1) = M! / (M-xy)!\n\ndivided by the number of possible choices:\nM^(xy)\n\nhence the probability of no collisions is\nprob0 = M! / (M-xy)! / M^{xy}\n\nsince M!/(M-xy)! is approximately \nM^{xy} - (1+2+...+xy) M^{xy-1} = M^{xy} - (xy)^2 /2 M^{xy-1}\n\nwe have\nprob0 = 1 - (xy)^2 / 2 / M\n\nNow, the probability of having at least one collision is prob1 = 1-prob0\nwhich for large numbers at leading order becomes\nprob1 = (xy)^2 / 2 / M\n\nThe square in the numerator the responsible for the so called\nbirthday paradox, ie. in a group of 20 people the chances of a birthday\ncollision is very high because 20^2/2 = 200 which is comparable to the number of\ndays in the year.\n\nThe collisions in the case of bitcoin are so unlikely because (xy)^2 = 10^32\nwhile M=10^48 so that\nprob1 = 1/10^16 = 0.000 000 000 000 000 1\n\nnot as small as the probability of a private key collission but still very\nunlikely.\n",
"sig": "34d47c0b5b73955c769cc8ce47d1979e47e38080beecd5611e02dce60c36d3286a25c58aa368a7c4d5974dea7e0544a0b59a04d7ee9955d7f9c17ffdf50ac525"
}