Is it possible to generate an already existing seed?

[rocky3xr]

Hi guys, I'm reading "Mastering Bitcoing" and I'm curious about this topic, I read that with 64 hexadecimal you can generate 10^77 seeds and there is 10^80 atoms in the visible universe, but is it possible that you have a seed that already exist? I'm not focus on the probability, just the possibility.

Thanks and regards!

[1713581588]

1713581588

[1713581588]

1713581588

[ranochigo]

Ignoring the fact that its god damn hard, then yes. There is no mechanism to prevent your wallet to generate seeds/addresses that is already generated by someone else.

I would regard that possibility as negligible though, its too large of a number.

[Xynerise]

As long as the probability isn't zero, then it's theoretically possible, but, like Ranochigo says, the probability of it occuring is so low that it's virtually impossible.

[DannyHamilton]

Hi guys, I'm reading "Mastering Bitcoing" and I'm curious about this topic, I read that with 64 hexadecimal you can generate 10^77 seeds and there is 10^80 atoms in the visible universe, but is it possible that you have a seed that already exist? I'm not focus on the probability, just the possibility.

Thanks and regards!

You need to clarify your question.

Do you mean "mathematically possible" or do you mean "realistically possible"?

Here's an example to explain what I mean...

We humans need to breath oxygen in order to stay alive.  If we don't get enough oxygen, then we suffocate and die.  As such, we have a few face holes that allow us to bring the air that is near our face into our bodies.

Now, if we are in a typical room, that air is almost 21% oxygen.  That oxygen is RANDOMLY distributed throughout the room.  It is RANDOMLY bouncing off the walls, ceiling, other air molecules, and ourselves.  As such, EVERY POSSIBLE configuration of oxygen molecules in the room are EQUALLY possible.  There are a very Very VERY large number of possible configurations of those oxygen molecules that result in there being enough oxygen near your face holes to keep you alive.  Relatively, there are a very Very VERY small number of configurations that result in there NOT being enough oxygen near your face holes to keep you alive.

That being said...

It is "mathematically possible" that the oxygen molecules might bounce around randomly into a configuration where there isn't enough oxygen near you and you die.

However, I think we can agree that in a standard room with a standard amount of oxygen, NOBODY would agree to say that it is "realistically possible" that you will suffocate from oxygen randomly moving away from you.

[nullius]

Hi guys, I'm reading "Mastering Bitcoing" and I'm curious about this topic, I read that with 64 hexadecimal you can generate 10^77 seeds and there is 10^80 atoms in the visible universe, but is it possible that you have a seed that already exist? I'm not focus on the probability, just the possibility.

Theoreticians call this “possible”, because it is indeed possible in theory.  But your question cannot be adequately answered without focusing on the probability:  The precise reason why it is theoretically “possible” is that there is a nonzero probability.  To understand what that means requires discussing probabilities.

Humans generally have a problem grasping large numbers.  That is why comparisons are given, such as to the estimated number of atoms in the observable universe.  Otherwise, the reader may fail to grasp that the number is not only large:⁰  It is astronomically, unthinkably huge.

On a much smaller scale, this is also the failing which causes many people to buy lottery tickets—whereas a typical large-jackpot lottery typically has on the order of 10⁸ combinations.  N.b. that 10⁷⁷ is 10⁶⁹ times bigger than 10⁸.  This difference is itself so vast that it is difficult to explain in understandable terms.

The size of these numbers is why I must draw an important distinction:  Theoretically, it is possible for two people with working random number generators to pick the same keys.  However, in real-world, practical terms, such a thing is impossible.  The aforestated “nonzero probability” is so close to zero that we can safely ignore it.

Aside:

Terminology note:  You refer to 256-bit numbers.  Such numbers indeed have “64 hexadecimal” digits; but computers handle them in binary, that is to say, in bits. 

Also, you refer to a “seed”; I presume that you refer to Bitcoin’s private keys, which are 256-bit numbers.  A BIP 32 seed is 512 bits in total.

Most Bitcoin addresses (excepting the new P2WSH) have “only” 160 bits of substantial information.  Thus there are “only” on the order of 10⁴⁸ potential addresses of each other type (P2PKH, P2WPKH, P2SH).  That is still an astronomically large number.

If one billion Bitcoin users each generated one million addresses per second for the next thousand years, that would only come to on the order of 10²⁵ addresses.  Granted, at that point, the probability of a birthday collision in the 10⁴⁸ address space would be non-negligible.  I may consider that a long-term worry when there exist one billion Bitcoin users, each generating one million addresses per second—day and night.

0. My apologies to mathematicians who consider “huge” to start with Graham’s Number.  This discussion pertains to numbers so puny that they can be written in exponential notation.

[klamz]

You need to clarify your question.

Do you mean "mathematically possible" or do you mean "realistically possible"?

Here's an example to explain what I mean...

We humans need to breath oxygen in order to stay alive.  If we don't get enough oxygen, then we suffocate and die.  As such, we have a few face holes that allow us to bring the air that is near our face into our bodies.

Now, if we are in a typical room, that air is almost 21% oxygen.  That oxygen is RANDOMLY distributed throughout the room.  It is RANDOMLY bouncing off the walls, ceiling, other air molecules, and ourselves.  As such, EVERY POSSIBLE configuration of oxygen molecules in the room are EQUALLY possible.  There are a very Very VERY large number of possible configurations of those oxygen molecules that result in there being enough oxygen near your face holes to keep you alive.  Relatively, there are a very Very VERY small number of configurations that result in there NOT being enough oxygen near your face holes to keep you alive.

That being said...

It is "mathematically possible" that the oxygen molecules might bounce around randomly into a configuration where there isn't enough oxygen near you and you die.

However, I think we can agree that in a standard room with a standard amount of oxygen, NOBODY would agree to say that it is "realistically possible" that you will suffocate from oxygen randomly moving away from you.

That is a very decent analogy. I might use that myself.

[mvrcrypto]

Yes it is possible to generate an existing seed. But hard. And it is harder to find a collision with a particular one.
If you want to know more about the odds, you can take a look at the birthday problem https://en.wikipedia.org/wiki/Birthday_problem.
You can also find someone who did the math here : https://download.wpsoftware.net/bitcoin-birthday.pdf

[DannyHamilton]

That is a very decent analogy. I might use that myself.

Note, that the odds are not the same.  That is NOT an example of HOW UNLIKELY it is to encounter a private key collision.  It is just an example of WHY something can be considered to be "realistically impossible" even if it has a non-zero mathematical probability.

[codewench]

Relatively, there are a very Very VERY small number of configurations that result in there NOT being enough oxygen near your face holes to keep you alive.

And yet there are (e.g. industrial) situations where exactly that can happen!

An analogous situation is when a random number generator isn't sufficiently random - the crypto seeds it generates may be a small population. The lack of randomness may have insidious causes, for example seeding the RNG with the microsecond timestamp of a keypress. But it may turn out that USB is polled at a rate derived from the same microsecond clock. You may think the timestamp has 10 bits of entropy, but it really only has 3. This may seem to generate unique seeds, but alas, they're not good enough.

[DannyHamilton]

Relatively, there are a very Very VERY small number of configurations that result in there NOT being enough oxygen near your face holes to keep you alive.

And yet there are (e.g. industrial) situations where exactly that can happen!

Which is why I specified in my example:
"a typical room"
and
"oxygen is RANDOMLY distributed throughout the room.  It is RANDOMLY bouncing off the walls, ceiling, other air molecules, and ourselves"

and I stated that I was talking about a situation where:
"EVERY POSSIBLE configuration of oxygen molecules in the room are EQUALLY possible"

You are talking about a non-typical room, where the distribution of the oxygen is no longer RANDOM (as it is being influenced directly by some industrial process) and most importantly you are talking about a situation where some configurations of oxygen molecules in the room are either impossible, or at least less likely than others.

An analogous situation is when a random number generator isn't sufficiently random - the crypto seeds it generates may be a small population.

Correct.  Private keys that are randomly chosen from the entire set of valid private keys are secure.  Private keys that are randomly chosen from a small definable subset of valid private keys can be VERY insecure.

The lack of randomness may have insidious causes, for example seeding the RNG with the microsecond timestamp of a keypress. But it may turn out that USB is polled at a rate derived from the same microsecond clock. You may think the timestamp has 10 bits of entropy, but it really only has 3. This may seem to generate unique seeds, but alas, they're not good enough.

Which is why it is generally a bad idea to try to reinvent cryptography on your own without a SIGNIFICANT amount of education, study, and expertise.  When it comes to maths and physics, what "feels intuitive" to someone that has a limited knowledge can often be COMPLETELY WRONG.

Slightly off topic for this thread, but related to our discussion about why it can be important to know the actual correct calculations:
Here's an example I recently heard about of how an intuitive feel for something that we ALL think we have good general knowledge of can be quite wrong...

Read the following and just think about this intuitively. This is not a "trick question", the answer just isn't as intuitive as most people might think it would be.

Assume a two lane road.
Assume two identical vehicles both traveling on the road in the same direction (one vehicle in each lane).
Assume that one vehicle is traveling at 70 miles per hour.
Assume the other vehicle is traveling at 100 miles per hour.

Assume that at the exact moment that the two vehicles are exactly next to each other, BOTH drivers simultaneously notice an obstruction up ahead that entirely blocks the road perpendicular to their direction of travel (in other words they both have exactly the same distance to travel at that moment before they will hit the obstruction).
Both drivers simultaneously hit their brakes and both apply the exact same maximum stopping force available to vehicle. Both vehicles are on identical surfaces and continue in a straight line towards the obstruction without any rotation of the vehicle.
The driver that was traveling at 70 miles per hour manages to stop within a fraction of a millimeter of colliding with the obstruction.
Which of the following is an accurate description of what happens with the vehicle that was traveling at 100 miles per hour:

The faster vehicle also stops before it collides with the obstruction
The faster vehicle collides with the obstruction and is traveling at a speed between 0 and 20 MPH when it collides.
The faster vehicle collides with the obstruction and is traveling at a speed between 20 and 40 MPH when it collides.
The faster vehicle collides with the obstruction and is traveling at a speed between 40 and 70 MPH when it collides.
The faster vehicle collides with the obstruction and is traveling at a speed between 70 and 100 MPH when it collides.
The faster vehicle collides with the obstruction and is traveling at a speed greater than 100 MPH when it collides.


Answer (copy/paste the following text or simply hit the "quote" button to read): Intuitively, most people that are very familiar with general concepts of driving and stopping a vehicle could easily rule out the first and last options. However, intuition from common experience will generally lead someone to believe that the vehicles will both lose 70 MPH of speed, resulting in the faster vehicle colliding at 30 MPH.  Some might realize that the faster vehicle has less time available to stop (since it is covering ground faster) and so they might guess between 40 and 70.  Surprisingly, the correct answer is that the faster vehicle is traveling between 70 and 100 MPH when it collides (approximately 71 MPH)

[cr1776]

Danny, speaking of things where people are non-intuitive, a interesting book if you haven’t seen it is The Undoing Project.

[nullius]

An analogous situation is when a random number generator isn't sufficiently random - the crypto seeds it generates may be a small population.

Correct.  Private keys that are randomly chosen from the entire set of valid private keys are secure.  Private keys that are randomly chosen from a small definable subset of valid private keys can be VERY insecure.

This is why in my own post above, I specified, “with working random number generators”.  This is imperative for any cryptographic software of any kind; if you do not have a working CSPRNG, where the CS stands for Cryptographically Secure, then you have nothing else, either.

The lack of randomness may have insidious causes, for example seeding the RNG with the microsecond timestamp of a keypress. But it may turn out that USB is polled at a rate derived from the same microsecond clock. You may think the timestamp has 10 bits of entropy, but it really only has 3. This may seem to generate unique seeds, but alas, they're not good enough.

Which is why it is generally a bad idea to try to reinvent cryptography on your own without a SIGNIFICANT amount of education, study, and expertise.  When it comes to maths and physics, what "feels intuitive" to someone that has a limited knowledge can often be COMPLETELY WRONG.

In my preferred kernel (FreeBSD), as of last time I read those portions of the code, the entropy harvester does not feed the PRNG an estimate of more than 1–2 bits of entropy for any hardware event.  I am of the school of thought that entropy estimation as a concept is problematic at best; but if and when it must be done, it must be done conservatively.

Estimating 10 bits of entropy off a single instance of any microsecond timer event seems suicidal to me.  Among other problems, this translates to an assumption that all precision below one millisecond in the timing of that event be completely unpredictable in all circumstances—even to unprivileged code running on the same CPU as handles the interrupt!

DannyHamilton is right:  The acquisition of cryptographically secure randomness is not only an expert domain, but a specialist expert domain which invokes both maths and physics.  Even professional mathematicians who are not cryptographers will probably get this wrong.  Almost all working programmers will get it wrong.  Once upon a time, the individual entrusted to maintain Debian’s vendored OpenSSL got it very, very wrong—causing a spectacular blow-up of most cryptography involving Debian systems from 2006–08.  Conventional wisdom gets an awful lot wrong.  There is a high probability (hah!) that you will get it wrong, too.

Worst of all, there is no certain means to prove that you got it right.  Statistical tests can easily demonstrate that a given bag of bits is not random; but no test can prove that one is.  Passing the DieHard suite (or similar) does not mean that your numbers are sufficiently random for cryptographic purposes.  The only way to be sure is to possess a deep theoretical knowledge matched by practical knowledge of real-world cryptanalytic attacks which target insufficiency of entropy.

Don’t take any chances with your randomness!

On Unix or Linux, read() off /dev/urandom; or use whatever special nonportable APIs may be offered to obtain randomness directly from the kernel (getrandom(), a special sysctl, etc.).  On other platforms, find the equivalent.  If writing a web application, use getRandomValues() (for most any current browser) or, if feasible, the generateKey method; then, pray to whatever gods you believe in that the browser is not too stupid.

Do not roll your own.  Do not conflate distinct meanings of the overloaded word “entropy”, then gather “entropy” the same measurements as taken by Panopticlick (!) (!!) (for Bitcoin!).  Also, do not roll your own using C’s rand(), e.g.:

Code:

/* true_random -- generate a crypto-quality random number. */
static int true_random(void)
{
    /* crap. this isn't crypto quality, but it will be Good Enough */
    srand((unsigned int)(((time_now >> 32) ^ time_now) & 0xffffffff));

    return rand() & 0x0FFFF;
}

Let that horror be a lesson.  For unless you have considerable specialist expertise, you cannot rely on your results being any better.  And I repeat:  If you do not have a working Cryptographically Secure PRNG, then you have nothing else, either.

[AGD]

Relatively, there are a very Very VERY small number of configurations that result in there NOT being enough oxygen near your face holes to keep you alive.

And yet there are (e.g. industrial) situations where exactly that can happen!

Which is why I specified in my example:
"a typical room"
and
"oxygen is RANDOMLY distributed throughout the room.  It is RANDOMLY bouncing off the walls, ceiling, other air molecules, and ourselves"

and I stated that I was talking about a situation where:
"EVERY POSSIBLE configuration of oxygen molecules in the room are EQUALLY possible"

You are talking about a non-typical room, where the distribution of the oxygen is no longer RANDOM (as it is being influenced directly by some industrial process) and most importantly you are talking about a situation where some configurations of oxygen molecules in the room are either impossible, or at least less likely than others.

An analogous situation is when a random number generator isn't sufficiently random - the crypto seeds it generates may be a small population.

Correct.  Private keys that are randomly chosen from the entire set of valid private keys are secure.  Private keys that are randomly chosen from a small definable subset of valid private keys can be VERY insecure.

The lack of randomness may have insidious causes, for example seeding the RNG with the microsecond timestamp of a keypress. But it may turn out that USB is polled at a rate derived from the same microsecond clock. You may think the timestamp has 10 bits of entropy, but it really only has 3. This may seem to generate unique seeds, but alas, they're not good enough.

Which is why it is generally a bad idea to try to reinvent cryptography on your own without a SIGNIFICANT amount of education, study, and expertise.  When it comes to maths and physics, what "feels intuitive" to someone that has a limited knowledge can often be COMPLETELY WRONG.

Slightly off topic for this thread, but related to our discussion about why it can be important to know the actual correct calculations:
Here's an example I recently heard about of how an intuitive feel for something that we ALL think we have good general knowledge of can be quite wrong...

Read the following and just think about this intuitively. This is not a "trick question", the answer just isn't as intuitive as most people might think it would be.

Assume a two lane road.
Assume two identical vehicles both traveling on the road in the same direction (one vehicle in each lane).
Assume that one vehicle is traveling at 70 miles per hour.
Assume the other vehicle is traveling at 100 miles per hour.

Assume that at the exact moment that the two vehicles are exactly next to each other, BOTH drivers simultaneously notice an obstruction up ahead that entirely blocks the road perpendicular to their direction of travel (in other words they both have exactly the same distance to travel at that moment before they will hit the obstruction).
Both drivers simultaneously hit their brakes and both apply the exact same maximum stopping force available to vehicle. Both vehicles are on identical surfaces and continue in a straight line towards the obstruction without any rotation of the vehicle.
The driver that was traveling at 70 miles per hour manages to stop within a fraction of a millimeter of colliding with the obstruction.
Which of the following is an accurate description of what happens with the vehicle that was traveling at 100 miles per hour:

The faster vehicle also stops before it collides with the obstruction
The faster vehicle collides with the obstruction and is traveling at a speed between 0 and 20 MPH when it collides.
The faster vehicle collides with the obstruction and is traveling at a speed between 20 and 40 MPH when it collides.
The faster vehicle collides with the obstruction and is traveling at a speed between 40 and 70 MPH when it collides.
The faster vehicle collides with the obstruction and is traveling at a speed between 70 and 100 MPH when it collides.
The faster vehicle collides with the obstruction and is traveling at a speed greater than 100 MPH when it collides.


Answer (copy/paste the following text or simply hit the "quote" button to read): Intuitively, most people that are very familiar with general concepts of driving and stopping a vehicle could easily rule out the first and last options. However, intuition from common experience will generally lead someone to believe that the vehicles will both lose 70 MPH of speed, resulting in the faster vehicle colliding at 30 MPH.  Some might realize that the faster vehicle has less time available to stop (since it is covering ground faster) and so they might guess between 40 and 70.  Surprisingly, the correct answer is that the faster vehicle is traveling between 70 and 100 MPH when it collides (approximately 71 MPH)

I was right by intuition.

[nullius]

[snip]

I was right by intuition.

I infer to the point to be that you may risk your life on your intuition, when travelling in an automobile at x miles per hour.  But would you risk your Bitcoin on your intuition?  Perish the thought!

Well, the latter is exactly what you’d be doing if you were to cook up your own RNG based on intuition, “a little knowledge” (a dangerous thing!), or anything else other than studied expertise.

[DannyHamilton]

I was right by intuition.

Glad to hear it.  It was just an example. The fact that your intuition didn't fail you in this one example is by no means proof that it will never fail you.

[pebwindkraft]

Hi guys, I'm reading "Mastering Bitcoing" and I'm curious about this topic, I read that with 64 hexadecimal you can generate 10^77 seeds and there is 10^80 atoms in the visible universe, but is it possible that you have a seed that already exist? I'm not focus on the probability, just the possibility.

Thanks and regards!

just as another thought on top:
and let's just assume, a collision was found - what is the probably that exactly this bitcoin address contains some spendable funds?

[nullius]

Hi guys, I'm reading "Mastering Bitcoing" and I'm curious about this topic, I read that with 64 hexadecimal you can generate 10^77 seeds and there is 10^80 atoms in the visible universe, but is it possible that you have a seed that already exist? I'm not focus on the probability, just the possibility.

Thanks and regards!

just as another thought on top:
and let's just assume, a collision was found - what is the probably that exactly this bitcoin address contains some spendable funds?

Assuming uniform distribution of the Hash160 (SHA256→RIPEMD160) output, each Bitcoin address can be spent by approximately 2⁹⁴ different keys.   (160+94=256)  There are numerous posts (indeed, entire threads) on this topic in the forum archives.  I regret that I don’t have any links handy.

Thus, te proper number to examine in this context is 2¹⁶⁰.  As I said above in this thread, that is on the order of 10⁴⁸.

Given that n addresses control spendable funds, where n is a number which can be determined from the public blockchain at any given point in time; and assuming that the n addresses are uniformly distributed throughout the 2¹⁶⁰ search space (viz. that people have working CSPRNGs); what you are asking is the probability of colliding with any of them, when you pick a new address randomly from a uniform distribution.

Working out the precise answer is left as an exercise to the reader.  A reader who is more solid with subtle statistical calculations than I am—I don’t want to give potentially bad information.

[AGD]

I was right by intuition.

Glad to her it.  It was just an example. The fact that your intuition didn't fail you in this one example is by no means proof that it will never fail you.

I got the example and I really like and agree to your postings. You should be a merit source btw.
It is hard for our brains especially when it comes to very big numbers, so your pictorial explanations might help forum users a lot.
Btw. I guess since I was driving cars a lot in my life, I know about the forces included, but people really underestimate driving speed. That's true.

[pebwindkraft]

On Unix or Linux, read() off /dev/urandom; or use whatever special nonportable APIs may be offered to obtain randomness directly from the kernel (getrandom(), a special sysctl, etc.).  On other platforms, find the equivalent.  If writing a web application, use getRandomValues() (for most any current browser) or, if feasible, the generateKey method; then, pray to whatever gods you believe in that the browser is not too stupid.

I do not trust - neither in someone else's god, nor in someone holding my private keys 

I am reading about entropy, especially in the bitcoin discussion, but not sure what is considered a good "value"  for entropy/randomness.
There is this thread from May 2017, which seems to indicate, that most modern unixoide systems have a good entropy. And of course I just checked my OSX and OpenBSD boxes, which show the expected (seemingly good) results.
How is this linked to bitcoin? Any hints?

[hatshepsut93]

1. Is this a good idea to generate random numbers with physical dice? I've heard that cheap gaming dice have poor quality of randomness, and if their sides are not a power of 2, you have to do some additional operations to remove bias when generating random bits.

2. Does quality of RNG that collects entropy becomes better with the system uptime - i.e. should I wait some time (while moving my mouse around and typing something?) before generating a new Bitcoin wallet after turning on my cold storage machine?