Is it possible to generate the same adress twice?

[Remember remember the 5th of November]

In case one does, it's finders keepers so.

Personally I am importing the blockchain into a MySQL database and will be creating a list of bitcoin addresses with a balance of X coins that have not been touched in a long time, compile that list into a single file and run my CPU Address bruteforcer on it.

With my 30k list of addresses, I am generating about 800k addresses per second(even when comparing each and everyone of these 800k to the list)(on a single core). I am not even using any binary search trees.

If I were to port this code to a GPU, it would be orders of magnitudes faster. Hey, it may take a billion years to get a single address, but I am doing for the fun.

[1714147499]

1714147499

[1714147499]

1714147499

[lunarboy]

Just to give all a complete understanding on the scale of probability.

Can anyone give an estimate as to how long it would take the ENTIRE network hashing simultaneously to crack one address with a big balance ?   

[DeathAndTaxes]

Just to give all a complete understanding on the scale of probability.

Can anyone give an estimate as to how long it would take the ENTIRE network hashing simultaneously to crack one address with a big balance ?    

Just about the time the Sun burns out, no?

Well significantly longer.

A perfect computer, that is one that operates at the thermodynamic limit in absolute zero, using all the available energy of our sun can't count to 2^256 in the next 4 billion years before our sun burns out.  Yes we are talking far future science fiction, like using all the matter in our solar system to construct a star system sized super computer and the dyson sphere around the sun to power it.

This is just counting 0, 1, 2, 3, .... 2^256.  It isn't based on any current or future (Moore's law) computing power but the thermodynamic limit which is the efficiency limit of any cryptographic system.  Per linked article below you would need to capture the entire output of a supernova to has sufficient energy to count to 2^216 so given a sufficient number of perfect computers and the ability to capture without any loss the energy output of a super nova if you found and used roughly 1 trillion super novas one could count through all possible values o to 2^256.

I think Bruce Schneier says it best

... These numbers have nothing to do with the technology of the devices; they are the maximums that thermodynamics will allow. And they strongly imply that brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.

http://www.schneier.com/blog/archives/2009/09/the_doghouse_cr.html

DISCLAIMER (as people have taken this out of context before):
ECDSA like all public key cryptographic systems rely on certain mathematical properties to remain secure.  ECDSA relies on the fact that finding a discrete logarithm of an elliptic curve element with respect to a publicly known base point is computationally infeasible.  This is known as the discrete logarithm problem.   A common misnomer is that ECDSA relies on factoring large numbers but that applies to other systems like RSA which are not used in Bitcoin.  This principal has so far remained true and as such no faster than brute force attack exists at the current time.  Likewise a brute force attack while possible is infeasible due to the energy requirements of a 256 bit keyspace.  However like all public key cryptography, it is possible that ECDSA will eventually be compromised due to a flaw in its design or underlying principal allowing faster than brute force attacks.  Depending on the severity of the compromise it *may* be possible in the future to find a private key from a public key in a reasonable amount of time/energy.    The above cite is only based on brute force attack against a 256 bit private key like what would occur by computers randomly generating keys that happen to be one which is already in use.  Of course if ECDSA becomes degraded the Bitcoin protocol could be extended to use new more secure address types and smart users would migrate their funds to more secure addresses.  In the event of such a compromise (or quantum computing attack) Bitcoin provides a secondary layer of security by making the address a hash of the public key.  The public key is not known until funds are spent.  If one does not reuse addresses there is no known public key to attack against.

[lunarboy]

^^
....and comprehension finally dawns.


HOLY SMOKE !    

[grue]

This calculation is based on Boltzmann's constant which is classical physics.  Not sure if quantum effects can theoretically do better.

"quantum physics" doesn't work that way. What you're probably talking about is quantum computers, which can solve certain problems faster than a traditional computer.

[DeathAndTaxes]

I think Bruce Schneier says it best

... These numbers have nothing to do with the technology of the devices; they are the maximums that thermodynamics will allow. And they strongly imply that brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.

http://www.schneier.com/blog/archives/2009/09/the_doghouse_cr.html

This calculation is based on Boltzmann's constant which is classical physics.  Not sure if quantum effects quantum computing can theoretically do better.

That is correct.  A quantum computing attack on ECDSA is theoretically possible but not currently available.   At the current time no true QC has sufficient qubits necessary to complete Shor's algorithm against a 256bit key.  IIRC the largest true QC has 7 quibits (see note below *).  It was used in 2011 after years of development to factor the number 21. I can't find the cite now but I remember reading a research paper indicating an optimal construction of shor's algorithm to break a 256 bit ECC key would require >3000 qubits and that excludes the additional overhead to compensate for quantum noise.  

I think Gavin once said he would be worried once QC can break 64bit keys.  At that point the Bitcoin community should be looking at post-quantum cryptography.

http://en.wikipedia.org/wiki/Post-quantum_cryptography

The Bitcoin protocol provides a defense against non brute force attacks on ECDSA (like QC and cryptographic flaws) in that the address is not the public key but a hash of the public key (see note below **).  The public key remains an unknown until coins are spent.  Shor's algorithm requires knowledge of the public key to find the private key.  If one does not reuse addresses there is no known public key for the addresses holding funds.  If you receive coins at an address you have previously spent from (address reuse) a quantum computer could (in theory) use the known public key to find the private key and transfer those coins (steal them).  

http://en.wikipedia.org/wiki/Discrete_logarithm#Algorithms
http://en.wikipedia.org/wiki/Elliptic_curve_cryptography
http://en.wikipedia.org/wiki/Shor%27s_algorithm


* There is the DWave system which is 512 qubits and it has shown speed up relative to classical computers however it does not appear to work "as expected".  The speedup was only a factor of 3,600 and while impressive it is far below what is possible using QC (in theory).  A 3,600 speedup to breaking ECDSA for example is a non-event.  It breaks the energy requirements down from 1 trillion supernovas to a mere 300 million supernovas.  This isn't to say DWave is a "scam" it does show promise in certain applications namely complex modeling just that its improvement while impressive is much less one would expect from a true quantum computer.


** It is in aspects like this I am amazed how many things Satoshi got right on the first try.  Maybe it was just luck (hash is smaller than the public key) but had the address been the actual public key (w/ version and checksum) Bitcoin would be far more vulnerable to QC attack.

[nimda]

Possible but improbable.  That can be kind of disconcerting to people but understand this same "issue" existing in all public key cryptography.  For example I could just happen to create a private key that would allow me to impersonate your bank's SSL cert.  I could just happen to create a PGP private key which unlocks someone else encrypted messages.

It is possible but so improbable as to be considered essentially zero.

https://en.wikipedia.org/wiki/Almost_surely

[AliceWonder]

You can email the salt to yourself (and others) in plaintext.   The point of the salt is to prevent an attacker for just doing an attack against all possible keys using a dictionary.  If an attacker learns your salt then he can employ a dictionary or brute force attack against your private key however at that point you are no weaker than if you used no salt.

You can also salt the salt - e.g. use the md5sum of the salt you keep in a text file. Then attacker who gets your salt has to know you do that.

[cp1]

Everyone it seems in agreement. Yes its possible but no, it's so unlikely there is no need to worry about it.

OK but wouldn't it be fairly simple to have an automatic check within all the clients and a simple prompt ..
 'this key pair already exits please try again'

Getting Deja-vu on this topic but its nice to rehash once in a while. 

It would be better if it said "Bingo!  You've found someone else's address -- transferring all their funds now"

[nimda]

Everyone it seems in agreement. Yes its possible but no, it's so unlikely there is no need to worry about it.

OK but wouldn't it be fairly simple to have an automatic check within all the clients and a simple prompt ..
 'this key pair already exits please try again'

Getting Deja-vu on this topic but its nice to rehash once in a while. 

It would be better if it said "Bingo!  You've found someone else's address -- transferring all their funds now"

And then told you, "Due to the incredibly small chance of this happening naturally, this event probably represents a fundamental flaw in the way Bitcoin addresses are generated. Sell all your coins and warn your close friends, then notify Gavin Andresen."

[raze]

Just to give all a complete understanding on the scale of probability.

Can anyone give an estimate as to how long it would take the ENTIRE network hashing simultaneously to crack one address with a big balance ?    

Just about the time the Sun burns out, no?

Well significantly longer.

A perfect computer, that is one that operates at the thermodynamic limit in absolute zero, using all the available energy of our sun can't count to 2^256 in the next 4 billion years before our sun burns out.  Yes we are talking far future science fiction, like using all the matter in our solar system to construct a star system sized super computer and the dyson sphere around the sun to power it.

This is just counting 0, 1, 2, 3, .... 2^256.  It isn't based on any current or future (Moore's law) computing power but the thermodynamic limit which is the efficiency limit of any cryptographic system.  Per linked article below you would need to capture the entire output of a supernova to has sufficient energy to count to 2^216 so given a sufficient number of perfect computers and the ability to capture without any loss the energy output of a super nova if you found and used roughly 1 trillion super novas one could count through all possible values o to 2^256.

I think Bruce Schneier says it best

... These numbers have nothing to do with the technology of the devices; they are the maximums that thermodynamics will allow. And they strongly imply that brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.

http://www.schneier.com/blog/archives/2009/09/the_doghouse_cr.html

DISCLAIMER (as people have taken this out of context before):
ECDSA like all public key cryptographic systems rely on certain mathematical properties to remain secure.  ECDSA relies on the fact that finding a discrete logarithm of an elliptic curve element with respect to a publicly known base point is computationally infeasible.  This is known as the discrete logarithm problem.   A common misnomer is that ECDSA relies on factoring large numbers but that applies to other systems like RSA which are not used in Bitcoin.  This principal has so far remained true and as such no faster than brute force attack exists at the current time.  Likewise a brute force attack while possible is infeasible due to the energy requirements of a 256 bit keyspace.  However like all public key cryptography, it is possible that ECDSA will eventually be compromised due to a flaw in its design or underlying principal allowing faster than brute force attacks.  Depending on the severity of the compromise it *may* be possible in the future to find a private key from a public key in a reasonable amount of time/energy.    The above cite is only based on brute force attack against a 256 bit private key like what would occur by computers randomly generating keys that happen to be one which is already in use.  Of course if ECDSA becomes degraded the Bitcoin protocol could be extended to use new more secure address types and smart users would migrate their funds to more secure addresses.  In the event of such a compromise (or quantum computing attack) Bitcoin provides a secondary layer of security by making the address a hash of the public key.  The public key is not known until funds are spent.  If one does not reuse addresses there is no known public key to attack against.

Post of the day award goes to D&T. I'm also a fan of Schneier's work.

[threeip]

Getting Deja-vu on this topic

"Due to the incredibly small chance of this happening naturally, this event probably represents a fundamental flaw in the way Bitcoin addresses are generated. Sell all your coins and warn your close friends, then notify Gavin Andresen."

Then you get Deja-vu again.
Then you know something has been changed.. in the Matrix.

[lunarboy]

Getting Deja-vu on this topic

"Due to the incredibly small chance of this happening naturally, this event probably represents a fundamental flaw in the way Bitcoin addresses are generated. Sell all your coins and warn your close friends, then notify Gavin Andresen."

Then you get Deja-vu again.
Then you know something has been changed.. in the Matrix.

Pop-up Black cat walks across the screen.

[AU]

No just no

[DeathAndTaxes]

No just no

Yes just yes.

The question was possible.  Yes it is very much possible.  It is however highly improbable.  The probability of such an event is so low that one should spend time worrying about more likely events such as getting struck by lightning in a desert, or getting eaten by a shark in a sushi restaurant, or winning the lottery the day an extinction level event asteroid strikes the earth.

[hayek]

If you took the entire known universe and broke it up in to even sized parts and the total number of parts was equal to the total possible addresses each "part" in the universe would consist of ~900 atoms.

I believe this is "effective" infinity as we are bound by scarcity. Not in a scarcity of addresses sense but a scarcity of time and resources available in the entire universe. If you're children's children's children's children's children's were to generate as many addresses as they possibly could in their lifetimes they would not duplicate an address.



Another good one is:

If every grain of sand on the entire Earth represented another Earth with an equal number of grains of sand it would not come close to the total number of addresses. In fact, that number would be close to 4^41. So 42 digits. Bitcoin Addresses are 256 digits

[DannyHamilton]

In fact, that number would be close to 4^41. So 42 digits.

I know, I'm pointing out facts that aren't really all that relevant to the discussion at hand, but:

4⁴¹ is approximately equal to 4.8357033 X 10²⁴

So that's 24 digits in base 10 (or 41 digits in base 4?)

Bitcoin Addresses are 256 digits

Again, I don't want to take away from your point (which seems to be something along the lines that the number of possible bitcoin addresses is so large that most humans have a difficult time comprehending just what that means).

However to be technically accurate...

Bitcoin addresses are 160 bits, which is approximately equal to 1.4615016 X 10⁴⁸

That's 48 digits in base 10, 160 digits in binary, or about 30 digits in Base58.

[hayek]

Danny I'm always learning from you.

Yeah I screwed up my conversion. Perhaps too much caffeine today.

[DannyHamilton]

Danny I'm always learning from you.

Yeah I screwed up my conversion. Perhaps too much caffeine today.

No worries.  We're all susceptible to math errors.  I just made one yesterday that cost me about $20.

[pand70]

I would be funny if someone was taking the time to pair the possibility of a collision with facts like "winning a lottery 100 times in a row".
Not just saying something flashy but actually calculating the possibilities of both events.