Bitcoin address exhaustion

[nmat]

This may sound stupid, but isn't it possible for someone to create a lot of bitcoin addresses and start stealing money from other people? I could make a script that keeps generating new addresses and spends any money that arrives on them... no?

[1715559978]

1715559978

[1715559978]

1715559978

[Jaccubin]

But why would anyone send BC to these adresses any more than anyone would just transfer money to a completely random bank account? I'm not sure I'm understanding what you're proposing here.

[lvt]

afaik, this is not possible.

addresses are never duplicated, that's the whole thing about bitcoin algos and p2p - period.

unless you were actually controlling a remote pc holding one of the addresses on it, there is no way in hell you'd ever see random donations/transfers

[1bitc0inplz]

You are correct, this is a theoretical attack.

Ignoring the probability or computational power behind this attack, lets assume it could be done.

Given that it could be done, if you could generate an address which collided with someone else's address you could spend any Bitcoin they had received at that address.

However, considering the address space involved here, the practicality of finding a collision is astronomical. You could spend the rest of your life generating wallet IDs on as many computers as you could find, and you'd almost 99.999% be guaranteed to never find a single collision.

[1bitc0inplz]

afaik, this is not possible.

addresses are never duplicated, that's the whole thing about bitcoin algos and p2p - period.

unless you were actually controlling a remote pc holding one of the addresses on it, there is no way in hell you'd ever see random donations/transfers

That is incorrect. There is no network validation of addresses. They are completely "random" by the node who generated them. There is a very non-0 chance that two nodes can generate the same address, and nobody would be none the wiser.

[xumi]

addresses are generated randomly, he expose the posibility of addresses colliding (a bitcoin client create a wallet that is already in use) so that wallet would update the transactions in that address and if it has some BC inside, they can be spent, spent = stolen.

I read some time ago that due to the lenght of the addresses is "almost" impossible, better said, very improbable, but not impossible.

It would be nice to kinow if there's a kind of system that avoid creating an address that is already in use.

I dont find it very hard to occur, after all the possibility of solving a block is very small, but is completely possible.

[nmat]

You are correct, this is a theoretical attack.

Ignoring the probability or computational power behind this attack, lets assume it could be done.

Given that it could be done, if you could generate an address which collided with someone else's address you could spend any Bitcoin they had received at that address.

However, considering the address space involved here, the practicality of finding a collision is astronomical. You could spend the rest of your life generating wallet IDs on as many computers as you could find, and you'd almost 99.999% be guaranteed to never find a single collision.

So, the algorithm for generating wallet id's is that much heavier than the one for mining? People have lot of computing power over here...

As far as I understand, new bitcoin addresses everyday for each new transaction so that must really increase the chance of performing this attack successfully.

[1bitc0inplz]

So, the algorithm for generating wallet id's is that much heavier than the one for mining? People have lot of computing power over here...

As far as I understand, new bitcoin addresses everyday for each new transaction so that must really increase the chance of performing this attack successfully.

The main difference is what we're looking for.

What you are talking about is looking for a needle in a hay stack, literally. You are looking for 1 (even if you say *all* the address, computationally it's still N) thing in a HUGE address space.

However, when we mine we're not looking for a hash collision. We're simply looking for a hash that happens to be numerically equally to or lower than some "arbitrary" other number.

Put in the form of an analogy, if I asked you to "find me someone who was born on March 3rd, 1957" you would have a much hard time at doing than as opposed to if I had asked you to "find me someone born after March 3rd, 1957".

[Alex Beckenham]

It would be nice to kinow if there's a kind of system that avoid creating an address that is already in use.

Since addresses can be generated offline, how do you define 'in use'?

You can only check the addresses in the blockchain, but you can't check what addresses have been generated offline.

[The_JMiner]

Gratz you spent a 100 million seconds creating a 100 million addresses.

Now lets see if anyone sends you money!
 

So you basically spent 3.5 years that you could have spent mining! Instead you spent it creating addresses...

[lvt]

afaik, this is not possible.

addresses are never duplicated, that's the whole thing about bitcoin algos and p2p - period.

unless you were actually controlling a remote pc holding one of the addresses on it, there is no way in hell you'd ever see random donations/transfers

That is incorrect. There is no network validation of addresses. They are completely "random" by the node who generated them. There is a very non-0 chance that two nodes can generate the same address, and nobody would be none the wiser.

taking this as constructive criticism, let's say your quote was the case (Could be, or may not be - I'm not saying anyone is wrong)

A good example would be the only one I can currently think of. If I (person A) were to generate a new address, and person B (in another state or country), were to already have this address, and a bitcoin transaction was made to the address, would the end result be double of what the original transaction was?

If so, I was trying to point out that bitcoin addresses take a long time to generate and hence that,
I figured it would check the network if the address was already validated or not.

[1bitc0inplz]

afaik, this is not possible.

addresses are never duplicated, that's the whole thing about bitcoin algos and p2p - period.

unless you were actually controlling a remote pc holding one of the addresses on it, there is no way in hell you'd ever see random donations/transfers

That is incorrect. There is no network validation of addresses. They are completely "random" by the node who generated them. There is a very non-0 chance that two nodes can generate the same address, and nobody would be none the wiser.

taking this as constructive criticism, let's say your quote was the case (Could be, or may not be - I'm not saying anyone is wrong)

A good example would be the only one I can currently think of. If I (person A) were to generate a new address, and person B (in another state or country), were to already have this address, and a bitcoin transaction was made to the address, would the end result be double of what the original transaction was?

If so, I was trying to point out that bitcoin addresses take a long time to generate and hence that,
I figured it would check the network if the address was already validated or not.

Sorry, I wasn't trying to be a critic... just trying to answer some questions  

It's not that the money is duplicated, but rather that two people now have access to it. Much like, if you have a joint checking account with your partner. Just because you both might have your own ATM cards, and you each go to the ATM and see an account balance of $100, that doesn't mean you EACH have $100. It's kinda a first come first serve access to that money.

The same applies here. If a collision did occur, the person who spent that money first would effectively steal it from the other person. This does not create double spending.

If a system did exist to allow Bitcoin clients to verify if an address already existed, what would stop a malicious user from ignoring this message and just preceding with their newly minted address as their own?

[nmat]

Gratz you spent a 100 million seconds creating a 100 million addresses.

Now lets see if anyone sends you money!
 

So you basically spent 3.5 years that you could have spent mining! Instead you spent it creating addresses...

Well, that's why I started the thread. Because 100 million address could mean a lot or could mean very few, depending on the address space. I was worried that the 160 bit address space would not be enough since each person creates lots of addresses. Quoting the wiki:

Since Bitcoin addresses are basically random numbers, it is possible, although extremely unlikely, for two people to independently generate the same address. This is called a collision. If this happens, then both the original owner of the address and the colliding owner could spend money sent to that address. It would not be possible for the colliding person to spend the original owner's entire wallet (or vice versa). If you were to intentionally try to make a collision, it would currently take 2^126 times longer to generate a colliding Bitcoin address than to generate a block. As long as the signing and hashing algorithms remain cryptographically strong, it will likely always be more profitable to collect generations and transaction fees than to try to create collisions.

In a few years (months?) mining will become really hard so I thought that collecting money from addresses could be worth trying.

[lvt]

true, from what I was reading, I took it as since the funds were sent, and (collected) at the same time, both parties would actually have such in their balance. It was a theory but a long way from the truth I guess o;

[cbeast]

An easy protection would be to not keep all your bitcoins on one address. Spread them out.

[nmat]

Relevant thread :
http://forum.bitcoin.org/index.php?topic=26278.0;all

Thanks. I think this pretty much ends the discussion, hehe

I believe you have a better chance of quantum tunneling a tennis ball through a wall by throwing it. At that point, I call it impossible. And it is for all intents and purposes.

[Yatta99]

I don't think that 'almost impossible' or 'virtually impossible' are high enough standards. The 'impossible' happens with quite regular frequency. Every week something 'impossible' ends up in the news: someone gets struck by lightning for the fifth time, someone wins the jackpot on a lottery for a second time, someone shoots a basket from half-court during a basketball game, etc. With enough Bitcoin clients running and generating addresses during the normal course of transactions it's just a matter of time before some monkey pounding on a keyboard comes up with "To be, or not to be". The only real protection (if you want to call it such) is to have many addresses in your wallet with all your Bitcoins spread among them. If/when an address is compromised you will potentially lose a little rather than everything.

[netrin]

There is a very non-0 chance that two nodes can generate the same address, and nobody would be none the wiser.

There is not a VERY non-0 chance.

you'd almost 99.999% be guaranteed to never find a single collision.

Nor an ALMOST.

There has NOT been one SINGLE documented crack of a conventionally generated 160 bit SHA-1 hash. It could happen (if god played dice). Perhaps someone will come up with a fantastically clever new non-brute force algorithm. Perhaps computers will compute faster than currently understood physical limits (such as infinite quantum states).

1 - (number of blocks, 135483) * (new addresses per block, 1 to 10) / (key space, 2^160) = 1 - 10^(5 or 6) / 10^49

99.9999999999 9999999999 9999999999 9999999999 9 % chance that it's not gonna happen

(give or take a 9, minus the chance of god playing dice, new published algorithm crack, or yet unknown technological innovation)

The only real protection (if you want to call it such) is to have many addresses in your wallet with all your Bitcoins spread among them. If/when an address is compromised you will potentially lose a little rather than everything.

No. You'll then have only divided a seemingly infinitely improbable chance by a tiny finite number (number of your wallet keys with value). You can remove a '9' from my estimate above. If someone can crack one hash, then they can probably crack a huge number of them. Though not putting "all your eggs in one basket" is good advice for other reasons.

EDIT: strike-outs are mine.

[netrin]

Since this type of discussion comes up very often. Perhaps it's useful to internalize the following fact and spread the knowledge far and wide in the future. Of course, I welcome verification of my assertion.

The size of the 160 bit SHA-1 key space is in the same order of magnitude as the number of atoms in the Earth (~10^50)

[Rob P.]

Whenever your bitcoin client creates a new address, it randomly creates a public/private keypair of one of the 2^160 possible addresses. 
If (and it's a HUGE if, with a VERY low probability, but it's not ZERO) you create a public/private keypair that someone else has already created, you'll have access to the coins in that address in the block chain.

Elsewhere in the forum someone was working on a program that would generate approximately 80,000 bitcoin addresses per second. 

At that rate you can create 80,000 * 31536000 (seconds/year) = 2,522,880,000,000 (2.5 Trillion) addresses a year.
However, you'd have to run that for 5.7929891129617856×10^35 years, to exhaust all of the address space. 

And of course, you'd have to have a client that could handle that many addresses, which I doubt the default client can do.  So, you'd have to come up with a way to check them all in the block chain to see if they are valid, which would slow down your rate.

It's a big number.  So, the odds of two people colliding with the same address are astronomically tiny.

You'd be better off using vanity ID creation code to try to create a specific address, at least then if/when you found it, you'd know it.