Topic: Can we please stop saying that it is improbable to generate an inuse key? - page 2. (Read 3526 times)

i think the OP is trying to make the point that if there are
1000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000
privkeys (i know i know i have not done enough zeros.. its an example)

but a rndom generator only deals with a length of
1000000000000000000000000000000000000000000000

then everyones address would be somewhere between
1 and 1000000000000000000000000000000000000000000000

leaving the other keys above the 1000000000000000000000000000000000000000000000 never touched

"B-but it's only got 4 digits, it can't be that big!"

This ^

It *is* improbable.

Given enough time some miner will eventually solo mine a series of 1000 blocks, one-second apart.  The probability is not zero, so it'll eventually happen, right?

It is improbable to generate an inuse key. That is a fact.

Even so, my version is on the CPU and is therefore much efficient than a GPU which uses more watts. The key to this optimization is that I skip the base58 phase and use the RIPEMD160 hash and compare the bytes in a boolean expression. This way I also don't need to use PCRE ot strcmp. On my i5-4670k I do 33 million keys per second(which are compared to the list of 30k addresses) per thread.

The only downside is this method requires a list of keys in a file, they are supplied in base58 format and inside they are decoded back to their RIPEMD160 states.

Which for the purpose of this dubious scenario is like the guy with a bucket emptying the ocean laughing at the guy with a teaspoon trying to do the same thing.

In depends on what you mean by "time".  If given an infinite amount of computing power, an infinite amount of storage space and an infinite amount of time.  However under more realistic constrainsts you may never see a 160 bit collision before the heat death of the universe.  So saying "there will be collisions" especially the plural is dubious.  There may eventually be a collision but even that isn't guaranteed.

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.

Bitcoin addresses (2¹⁶⁰)
1461501637330902918203684832716283019655932542976

Earth Population
7218626512

Bitcoin addresses per person in Earth
202462564713848561306988538198010461031

Thats Two and two quintillion, four hundred sixty two quadrillion, five hundred sixty four trillion, seven hundred thirteen billion, eight hundred forty eight million, five hundred five thousand,  hundred thirty eight hundred-quintillionths

The later is only assuming a QC with sufficient qubits (~40,000) to implementing Shor's algorithm against 256 bit keys is ever possible.  The largest quantum computer which has implemented Shor's algorithm is 5 qubits.  It "cracked" the number 21 into the prime factors 7 & 3 (5 bit encryption if you want to call it that) after a mere 9 months.

Still you misunderstand that scope.   It doesn't matter how many addresses have been used in the past.  To steal funds you would need to produce a collision with a funded address.

Given a max of 2.1 quadrillion satoshis there simply can never be more than 2.1 quadrillion funded addresses.  Even if you assume 2.1 quadrillion funded addresses (dubious but good for an absolute upper bound) that puts the possibility of a preimage attack at 2^160 / ~2^50 = 2^110 which is many magnitudes beyond what is possible with brute force.

Another way to look at it is the Bitcoin network has ~30 PH/s.  Let assume all of that could be used to brute force keys instead.  Now lets also assume that it is as easy to compute and check a pubkeyhash (it isn't).  There are roughly 1 million funded PubKeyHashes.  If the entire network attempted to brute force them it would take on average 823,233 years to break a single pubkeyhash and the payoff would be a random amount of bitcoins but the average reward would be ~2.1 BTC.   The chance of a collision in a century would be 0.0121%. 

I suppose you're right. It's semantics really though.


I can't wait to get my hands onto a ASIC designed to generate keys.

On a side note, let's stop the misuse of the word "collision" please. A "collision" in an algorithm is when two different inputs give the same result.

A fail wallet client having a fail keyspace and always giving the same keys is not a collision, is just a fail

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.

By brute-forcing keys, the probability is the lowest. Anything related to a vanitygen that's not truly random, is at risk of being brute-forced as it seriously diminishes the keyspace. As time goes on, if people do not adhere do the rinse-and-don't-reuse address policy, the collision probability will increase. People are already generating lists upon lists of private keys just for the sake of generating them. As hardware and storage technology increases, its less of a monetary drain to just let a computer go to work generating Millions upon Millions of addresses every second.

The probability is non-zero, but thats also why they say its improbable not impossible.

If you make a wallet that always choose the same 3 keys then yes of course it will have collisions, but it will be faulty software. It is like making a fail bitcoin client wich crash on start and then blaming the bitcoin algorithm for that, nonsense.

I personally have over 100M private keys generated. But even 100 addresses per person is an understatement, the spec recommends never using an address twice, especially since once you sign a tx, it becomes that much easier for a QC to crack your private key.

Personally I believe it's FUD to exclaim that we WONT see collisions.

There have been a few cases where wallet implementations have resulted in extremely reduced keyspaces.

No, my point is if you are deliberately trying to cause collisions, making the hash function collide should be about 2⁹⁶ times easier. I did not say it would happen before the sun burns out.


Yes. I recall reading that merely counting to 2¹²⁸ would theoretically take more energy than is in the known Universe. Although, for a hash collision, you would only need 2⁸⁰ attempts on average.
Edit: 700Billion = 2^39.3; about the equivalent of DVD encryption (limited to 40bits by US export restrictions at the time).

Isn't it 2^160? since bitcoin address is actually a 160bit hash.

Now 2^160 is still quite large, but let's assume every person on earth uses Bitcoin, and has 100 addresses (the default of Bitcoin qt client pre-generates 100 addresses).

Now we are down to (2^160)/700B

Are you still confident that it's large enough?

Unless the algorythm is cracked, no, we will not see collisions, stop spreading FUD.

Hmm, so then we'll see collisions even sooner.