A question regarding off-line wallets...

[kodiak1120]

I'm trying to get my head around the concept of an off-line wallet and I have a lingering question or two.  

First, my understanding generally of the process is you use the script found at bitaddress.org to create both a public and private key, but you don't do this while online or on a computer that is or will be connected to the internet.  Instead, you basically create a bootable usb drive with a Linux operating system that you boot from your computer while the computer is disconnected from the internet.  Then you use the script from bitaddress.org to create the private and public keys (encrypt them if you wish) and print those keys onto paper.  This gives you a paper that contains a public address and a private key that match.  

My question is how does the blockchain know that the private key you created off-line matches the public address?  I think the answer has to do with the SHA-256 hash function and the fact that such functions are basically a one-way street, meaning anyone can verify the public address if given the private key, but not vise-versa.  So when you go to spend whatever bitcoins are sent to the newly-created public address, all the blockchain has to do is verify that your private key, when ran through the SHA-256 algorithm, produces the same string of characters as the public address.  Is this correct?

My other question is if the creation of the public address is done off-line, there is apparnetly no syncing with the blockchain so what happens if the same public address is created twice?  In other words, what happens if I randomly create a public address that's already in use?  Wouldn't my private key give me control over the bitcoins already associated with that public address?   I think the answer is that the chances of this happening are essentially impossible given the number of different combinations that can exist.  

Thanks.

[DeathAndTaxes]

It doesn't matter if it is online or offline if you create a private key which can sign for an existing address you can spend those coins.

Of course the probability is so asininely small that for all practical purposes it is ~0% (offline doesn't increase or decrease this chance).  You won't do it today, you won't do it even with a planetary sized super computer operating at the thermodynamic limit for billions of years.

This may seem "weird" but all public key cryptography works on a similar concept.  For example you in theory "could" by just mashing random keys on your keyboard create a private key which would allow you to impersonate a bank's secure website because your private key can produce the signature that a browser would verify to ensure it is at the correct webserver.   Once again the odds of doing this are so asininely small that it can be considered ~0% for all practical intents and purposes.

Likewise here is my PGP public key:
http://pgp.mit.edu/pks/lookup?op=get&search=0xC5B8C5DDCDBD1C8E

The only thing which prevents you from signing documents as me is a random number (my private key).  In theory you could "find" that private key either intentionally or by dumb luck but practically it isn't going to happen. 

TL/DR version:  2^128 is much bigger than you think.

[kodiak1120]

TL/DR version:  2^128 is much bigger than you think.

Got it... thanks.  I guess a subquestion of my prior question is would the private key always be the same if the two addresses are the same?  In other words, what if I used the bitaddress.org script to randomly generate a public address and private key, and the public address I got was the same as your public address,  would I then also get your private key or could our keys be different?

Kevin

[Cryptopher]

Public key cryptography, and encryption in general, works on entropy/information gain - which comes from thinks like cursor movements, entering keys. In more elaborate systems this can be generated from things like nuclear decay and whatnot.

Anyway, stuff gets signed using a private key - which the authorised user(s) (generally just one) have access to, and the public key (which is available to all) is used to verify who signed it. I'm not sure if collisions can occur when generating a public key - but if they can it is microscopically unlikely.

[acoindr]

OP good job  

You've almost answered your own questions correctly. Let me fill in the details a bit more. First I'd recommend using Armory for offline/cold storage. It makes the process more intuitive and probably less susceptible for anything going wrong IMO.

It's not necessary to use bitaddress.org offline with linux etc. This is recommended because you're dealing with manually generating/handling private keys. Anyone with access to this has access to all the coins. If your computer has spyware or bitaddress.org is compromised then private keys you thought were safe could actually lose all your coins. By taking the key generating Javascript offline and encapsulating it you cut down the risk of exposure. Of course if the Javascript was compromised then those extra steps wouldn't help. That's why I recommend Armory which can put everything in a context users are familiar with.

Regarding generating keys offline you're basically correct. The only thing Bitcoin checks for is that a public key it is aware of (some coins went there) is accessed with a corresponding private key. However this is done with ECDSA (here is a great video explaining it) not SHA-256 which is the hashing algorithm used to mine blocks for Bitcoin.

Last regarding the possibility of generating a private key someone else has both you and DeathAndTaxes explain it correctly.

[DeathAndTaxes]

TL/DR version:  2^128 is much bigger than you think.

Got it... thanks.  I guess a subquestion of my prior question is would the private key always be the same if the two addresses are the same?  In other words, what if I used the bitaddress.org script to randomly generate a public address and private key, and the public address I got was the same as your public address,  would I then also get your private key or could our keys be different?

Kevin

There is no guaranteed one to one relationship between private keys and public keys or between public keys and addresses (hashes).  As long as a private key can properly sign the transaction it is "valid" even if different.

So in theory you could have two private keys a & b which both produce the same public key K.  You could also have a set of keys (a & A) and (b & B) which when hashed produce the same address.  Both of those are forms of collision.

Public key cryptography is based on probability.  We can never say "it can't happen" we can simply say "the odds of it happening are so small that an attack would be infeasible".

[DeathAndTaxes]

However this is done with ECDSA (here is a great video explaining it) not SHA-256 which is the hashing algorithm used to mine blocks for Bitcoin.

Well Bitcoin is "complicated" so this isn't exactly correct.  

Most payments on the Bitcoin network are "PayToPubKeyHash" so the network is unaware of what the PubKey is, it only knows the hash of the pubkey being paid received an output.  The sender's client takes the address and reverses it to the PubKeyHash.  The PubKeyHash is actually what goes in the output of the tx.   Until that output is spent the network doesn't know what the correct pubkey is.

So to validate a spend the network needs to validate three things:
a) that the transaction is signed by the private key which corresponds to the public key (signature is valid).
b) that the PubKey when hashed (SHA-256) produces the PubKeyHash in the output of the prior tx (this pubkey corresponds to the address paid).
c) that this output has not already been spent (it is not a double spend).

An example might help.  Lets take this random tx:
https://blockchain.info/tx/83d51f7c87f275867288958d4f01afbde346370dedd3723cfe1c89ef3ba94012

Now to make it "simple" for end users Blockchain.info displays the Bitcoin address (i.e. 0.51 BTC was transferred to 162r6LJBJPhFQ3A9DjTKiww9sahzYWi1sV).  However the actual transaction doesn't include the address.  It includes the PubKeyHash.  The sender's client took the address 162r6LJBJPhFQ3A9DjTKiww9sahzYWi1sV and reversed it back to the pubkeyhash 373206576366c5c4cbd43e0e127262ce57bfe19d

If you look at the bottom of the page (you may need to enable showing scripts) you will see this:

OP_DUP OP_HASH160 373206576366c5c4cbd43e0e127262ce57bfe19d OP_EQUALVERIFY OP_CHECKSIG

In crude simplification it is saying this output (0.51 BTC) is locked and can only be spent by a tx signed by a private key which corresponds to a public key, that when hashed (SHA-256 & RIPEMD-160) produces this exact hash 373206576366c5c4cbd43e0e127262ce57bfe19d .  The Bitcoin network has no idea what pubkey hashes to that value (because hashes are one way functions) but it will instantly know it when it sees it.

If you attempted to spend this output with an incorrect pubkey which you could complete check "a" above, when your pubkey was hashed it would produce a different output.  Say it produced 966ca2c8a091088b8129ee3b053c51d799261eac .  Since 966ca2c8a091088b8129ee3b053c51d799261eac does NOT EQUAL 373206576366c5c4cbd43e0e127262ce57bfe19d the transaction is invalid (doesn't validate rule "b" above) and all nodes simply simply discard the transaction.

[acoindr]

However this is done with ECDSA (here is a great video explaining it) not SHA-256 which is the hashing algorithm used to mine blocks for Bitcoin.

Well Bitcoin is "complicated" so this isn't exactly correct. 

Most payments on the Bitcoin network are "PayToPubKeyHash" so the network is unaware of what the PubKey is, it only knows the HASH of the pubkey being paid received an output.

So to validate a spend the network needs to validate three things:
a) that the transaction is signed by the private key which corresponds to the public key (signature is valid).
b) that the PubKey when hashed (SHA-256) produces the PubKeyHash in the output of the prior tx (this pubkey corresponds to the address paid).
c) that this output has not already been spent (it is not a double spend).

As usual thanks for the detailed clarification