Can we please stop saying that it is improbable to generate an inuse key?

DeathAndTaxes

donator

Activity: 1218

Merit: 1079

Gerald Davis

Quote from: taturii on March 11, 2014, 07:51:24 PM

To make myself clear I've done the calculation of the acumulative probability of a collision as the addresses are generated. This probability increases with the square of the number of generated addrsses. If we consider the most restrictive case: the 160 bit space of the public key hash, a 1% probabiliy of bitcoin addresses collision will be reached when 1.2x10^23 bitcoin addresses are generated. This means that a million machines generating 30 million addresses/second each would need a thousand years to reach a 1% probability of a single collision.

Of course even that overstates the scenario in the OP which is a "inuse key". Given the size of the key space in the highly improbable event of a collision it is very likely between two unfunded addresses created by the same mass creating entity.

taturii

member

Activity: 96

Merit: 10

To make myself clear I've done the calculation of the acumulative probability of a collision as the addresses are generated. This probability increases with the square of the number of generated addrsses. If we consider the most restrictive case: the 160 bit space of the public key hash, a 1% probabiliy of bitcoin addresses collision will be reached when 1.2x10^23 bitcoin addresses are generated. This means that a million machines generating 30 million addresses/second each would need a thousand years to reach a 1% probability of a single collision.

lnternet

sr. member

Activity: 299

Merit: 253

It's 50:50. Either you generate an address that's already in use, or you don't.

Lauda

legendary

Activity: 2674

Merit: 2965

Terminated.

Quote from: Beliathon on March 11, 2014, 03:22:27 PM

Or of being struck by lightning in the same spot 10,000 times in a row for seven weeks straight. And surviving to tell the tale.

Can we stop saying that it's improbable that this will happen? Cheesy

Beliathon

hero member

Activity: 784

Merit: 1000

https://youtu.be/PZm8TTLR2NU

Quote from: freequant on March 11, 2014, 02:13:35 PM

Quote from: mustyoshi on March 10, 2014, 11:45:06 AM

Because I'm sure we're all aware that due to the nature of random number generators, and implementations, the more widespread the adoption of Bitcoin, the more likely it is that we will see key collisions.

Are we even sure that ECDSA even has an unbiased distribution?

True, one should always speak in relative terms. You have as many chances of having a collision as you have chances of being killed by a 22-carat pure gold meteorite at the time you generate your key.

Or of being struck by lightning in the same spot 10,000 times in a row for seven weeks straight. And surviving to tell the tale.

freequant

hero member

Activity: 770

Merit: 500

Quote from: mustyoshi on March 10, 2014, 11:45:06 AM

Because I'm sure we're all aware that due to the nature of random number generators, and implementations, the more widespread the adoption of Bitcoin, the more likely it is that we will see key collisions.

Are we even sure that ECDSA even has an unbiased distribution?

True, one should always speak in relative terms. You have as many chances of having a collision as you have chances of being killed by a 22-carat pure gold meteorite at the time you generate your key.

DeathAndTaxes

donator

Activity: 1218

Merit: 1079

Gerald Davis

Quote from: Ekaros on March 11, 2014, 01:27:42 PM

How many of us have a way to generate secure(private) random data or even sufficiently random seeds... And I'm using random here for not pseudo-random that is seeded and then algorithmically generated...

Roll a bunch of dice? Flip a bunch of coins? It may not be particularly useful for random wallets where a new random private value is needed for each private key however it would be fairly easy to do for a deterministic wallet.

bountygiver

member

Activity: 100

Merit: 10

If you did generated an in use wallet private key.
You just hit the world's lowest probability to win jackpot and you deserve to keep the money. :p
It's easier to get struck by lightning 10 days in a row than generating an in use wallet key.
http://what-if.xkcd.com/2/
Still easier than guessing all SAT questions right though.

Ekaros

hero member

Activity: 728

Merit: 500

Quote from: HeliKopterBen on March 11, 2014, 01:22:12 PM

If you actually do generate a duplicate key, I would be much more concerned about a flaw in the software used to generate the key. Scrap that program and use a different method to generate keys.

How many of us have a way to generate secure(private) random data or even sufficiently random seeds... And I'm using random here for not pseudo-random that is seeded and then algorithmically generated...

HeliKopterBen

hero member

Activity: 622

Merit: 500

If you actually do generate a duplicate key, I would be much more concerned about a flaw in the software used to generate the key. Scrap that program and use a different method to generate keys.

Ekaros

hero member

Activity: 728

Merit: 500

I think vector of attacking a the RNG is much more interesting...

That is probable attack vector if you know the implementation and hardware. I don't think many use truly random generation in key generation... At current levels of power and computing this isn't feasible, but it might be at some point...

Skoupi

sr. member

Activity: 252

Merit: 250

Skoupi the Great

Quote from: retrend on March 10, 2014, 11:51:49 AM

Facts and maths are great, but you never know do you!

That's why I've had my vanitygen running on the satoshi wallets since 2011.

Dat genius

BadBear

legendary

Activity: 1652

Merit: 1128

You should be much more worried about being hit by an asteroid.

Lauda

legendary

Activity: 2674

Merit: 2965

Terminated.

People still realize how wide the spectrum is for a collision. Therefore we must use words like improbable.
Let me steal something: Now ←-------------- Very Soon -------- Soon -------- Soon-ish ---------------→ End of Time
Now, it's possible that one collision might Soon-ish.

Quote from: RodeoX on March 11, 2014, 12:53:12 PM

The chances of a treasure chest in your yard from a privateer must be many times greater than an encryption collision. So relax, if your key is generated by another peer you can just start looking for the treasure.

Good one, mate.

Beliathon

hero member

Activity: 784

Merit: 1000

https://youtu.be/PZm8TTLR2NU

There are more possible private keys than there are grains of sand on Earth.

Is a collision possible? Certainly.

Is it going to happen in your lifetime? Not a chance.

Quote from: RodeoX on March 11, 2014, 12:53:12 PM

The chances of a treasure chest in your yard from a privateer must be many times greater than an encryption collision. So relax, if your key is generated by another peer you can just start looking for the treasure.

I think I'm in love with you.

RodeoX

legendary

Activity: 3066

Merit: 1147

The revolution will be monetized!

I don't think any of us have to worry. This can be mitigated by the much greater probability that there is pirate gold buried in your backyard. The chances of a treasure chest in your yard from a privateer must be many times greater than an encryption collision. So relax, if your key is generated by another peer you can just start looking for the treasure.

franky1

legendary

Activity: 4410

Merit: 4766

do you know the probability of life being created on any planet in the universe.
now
multiply that by the probability of that life being more then just a 1 celled organism
multiply that by the probability of that life having different abilities, such as swimming, flying walking
multiply that by the probability of that life gaining intelligence to communicate with each other (like birds)
multiply that by the probability of that life gaining intelligence to communicate with each other to such an extent that they can work together to do things.
multiply that by the probability of that life gaining intelligence to communicate with each to learn how to make objects like axes and clubs(Neanderthals)
multiply that by the probability of that life gaining intelligence to develop even further to then make computers to automate tasks

now you probably have a very large number, which is right.. we are an improbable number, that many things had to combine in the right way for it to happen.

... yet 7 billion of us all have the same ability to walk talk and build.

,, nothings impossible, just improbable

Peter R

legendary

Activity: 1162

Merit: 1007

Quote from: btc_jumpnrl on March 10, 2014, 12:29:05 PM

In time there will be collisions because the probability is not 0. However, not only do you have to match an in-use key, that key also has to carry a balance.

I don't think people realize how much is "possible" if you only include P=0 events as impossible.

For example, the laws of physics are reversible. Video record someone "breaking" the triangular group of pool balls, as the balls scatter into an unorganized state. Now play this recording backwards and watch the balls all converge to the organized triangle, popping the cue ball back against the player's cue. Calculate the physics of every collision for the "backwards event" and you'll see that no laws of physics were violated. The "backwards event" is possible.

But you won't be able to make it happen!!

For any event that can happen (e.g., cracking an egg), the backwards event can also happen with some probability (uncracking an egg). It is just so vastly improbable that physicists assume it will never happen and call this the "Second Law of Thermodynamics." But it's not a law at all--it's just a bold statement that extremely unlikely events do not actually happen.

taturii

member

Activity: 96

Merit: 10

Quote from: Remember remember the 5th of November on March 10, 2014, 12:35:50 PM

Quote from: retrend on March 10, 2014, 11:51:49 AM

Facts and maths are great, but you never know do you!

That's why I've had my vanitygen running on the satoshi wallets since 2011.

Lol @ vanitygen. I've written a much optimized version. With 30k addresses, it generates AND compares with 33 million keys per second on the CPU. Vanitygen is much slower.

2^256 is approx. 10^77, the age of our universe is 4x10^17 s approx. Even if you had a trillion machines (10^12) generating 100 million addresses per second since the big bang you would cover the 0.00000000000000000000000000000000000000001% of the 256 bit configuration space. It is more likely that a frappuccino pass through Mark Karperles by tunnel effect.

Edit: if we only consider the 160-bit space corresponding to the public key hash. The same trillion machines working since the Big Bang would only cover the 0.000000000001%, so it can be safely said that generating used keys is improbable.

whtchocla7e

full member

Activity: 392

Merit: 116

Worlds Simplest Cryptocurrency Wallet

Quote from: gadman2 on March 10, 2014, 11:48:36 AM

I don't think you fully understand how large 2^256 is:

I don't think you fully understand how insignificant this is to my algorithm.
Oh boy... Cheesy

Topic: Can we please stop saying that it is improbable to generate an inuse key? (Read 3574 times)