How does wallet.dat work?

[rupy]

So in wallet.dat there are private keys for unlocking bitcoins sent to an address. But how does that work? What encryption algo is used?

[DannyHamilton]

. . . What encryption algo is used?

Not sure what you are asking here.

Bitcoin uses a digital signature cryptographic function (secp256k1 ECDSA) to "sign" the transaction with a private key. To be a valid signature, the private key used has to match the public key that was hashed to create the address that the bitcoins were previously spent to.

This is all done with hashes and digital signatures (types of cryptographic functions)

The only thing I can think of that is "encrypted" is the private keys in your wallet.  If you choose to encrypt your wallet, Bitcoin-Qt will use the EVP_Encrypt functions from OpenSSL to encrypt the private keys using a type of aes_256_cbc() (I think).

[DeathAndTaxes]

Correct.  I would add that the wallet encryption uses thousands of rounds of SHA-256 to convert the passphrase to the AES key.

So to OP when you say what encryption is used it is important to clarify what are you asking.

What algorithms does Bitcoin use to verify transactions? Transactions are signed by the private keys using ECDSA and verify by miners using the corresponding public keys to verify authenticity

vs

What algorithms does the client use to PROTECT the private keys?  The client uses SHA-256 (for key generation) and AES_256 to encrypt/decrypt the private key portion of the wallet using a passphrase supplied by the user.

[rupy]

Ok, I was talking about ECDSA, so in the wallet there are the few transactions with a private key to prove I own them? When do I prove that I own coins? When I spend them I gather but how?

[casascius]

Ok, I was talking about ECDSA, so in the wallet there are the few transactions with a private key to prove I own them? When do I prove that I own coins? When I spend them I gather but how?

When you spend coins, your client broadcasts a message announcing the new owner of the coins - specifically, the hash of the new owner's public key, which is what's encoded in a bitcoin address.  This message is signed with the private key on record as being the "current owner" (that's you, and that's what makes the coins yours in the first place).  The message also includes a copy of the public key, since the rest of the network may not have it (since transactions identify the new owner only by the hash).  Both of those were generated when you created the address in the first place, possibly before.

The network accepts the public key as long as its hash matches the record everybody knows about.

[DannyHamilton]

. . . so in the wallet there are the few transactions . . .

I believe the transactions are stored in the blockchain, not the wallet.dat

. . . with a private key to prove I own them?. . .

The private keys are stored in the wallet.dat

So, your client program (I assume you are using Bitcoin-Qt?) uses the information in the wallet.dat to search through the blockchain for transactions that match the known private keys.

. . . When do I prove that I own coins? When I spend them I gather but how?

Yes, you can't update the blockchain with a new transaction without first proving that you have the private keys to the previous transactions that you want to use as inputs to your new transaction.  Using digital signatures you demonstrate that you have the private key that is associated with the addresses used in the previous transactions and in doing so you assign a new address for the value to be associated with.  Other nodes and miners validate the signature and relay the transaction.  Eventually a miner includes the transaction in a block in the blockchain.

[DeathAndTaxes]

Simple version.  The wallet.dat just contains your private key*.  You sign over ownership of coins** sent to your addresses to the new owner.  The transaction records the transfer of ownership.  To prevent someone else (say me) from transferring your coins for you (to my wallet) the network verifies that the transaction is signed by the private key of your address(es).

Every one of your addresses has a corresponding private key.  The magic of ECDSA (and all public/private key encryption) is you can share the public key and keep the private key a secret.  This ensure only you can sign messages with the private key but anyone can verify those messages with the public key.   You don't actually ever send or receive coins, you ANNOUNCE to the world the ownership change.  

Kinda like the digital equivalent of:

"Attention everyone in the world,  this 1 BTC coin (see as irrevocable and absolute proof of ownership this prior announcement by [previous owner]), let it be known forever that I have transferred ownership of it to D&T, oh and btw here is a digital signature that proves me and only me, Rupy could possibly have made this announcement.  Thank you that is all, please everyone in the world retain a copy of this announcement forever."

later when I spend it:

"Attention everyone in the world, this 1 BTC coin (see as irrevocable and absolute proof of ownership this prior announcement by Ruby), let it be known forever that I have transferred ownership of it to DannyHamilton (why not), oh and btw here is a digital signature that proves me and only me D&T could possibly have made this announcement. Thank you that is all, please everyone in the world retain a copy of this forever."

* Technically it contains more but that is merely to prevent a need to recreate the wallet on each startup.  The private keys are what can't be replaced.  They are the secret part.  If you delete your wallet.dat and don't have a backup it is the lost private keys that you will be crying about.  There are no coins in your wallet, your coins are "safe" the only problem is without access to the private keys you will never be able to transfer/spend them.  You can forever view them on the blockchain if you like.

** Coins are actually an abstraction.  The network works on the concept of inputs and outputs.  All transactions (except newly minted coins) have as their input the output of a prior transaction.  When your wallet says "you have 20 BTC" what it really means is "I have done an exhaustive search of the blockchain and the the combined sum of the value of all the unpsent outputs assigned to addresses for which I have access to the private key total 20 BTC".

[DannyHamilton]

. . . this 1 BTC coin . . . let it be known forever that I have transferred ownership of it to DannyHamilton (why not) . . .

Nice.   

[rupy]

I'm thinking about transactions as atomic, so say you have 3x1BTC incoming on one address (adr1) and 2x1BTC on another (adr2) and 1x5BTC outgoing (payment), then the swarm know you have 5BTC (because they can verify the sum on addresses you have as 5?) does that mean you say "I holder of adr1 and adr2 now give ownership of 5BTC to address XXX and here is a public key to prove i have the private keys to adr1 and adr2"?

[casascius]

I'm thinking about transactions as atomic, so say you have 3x1BTC incoming on one address (adr1) and 2x1BTC on another (adr2) and 1x5BTC outgoing (payment), then the swarm know you have 5BTC (because they can verify the sum on addresses you have as 5?) does that mean you say "I holder of adr1 and adr2 now give ownership of 5BTC to address XXX and here is a public key and signature to prove i have the private keys to adr1 and adr2"?

Other than the minor correction above, you're exactly right.

Actually, one other minor detail if it matters: there will be one signature per incoming transaction you unlock, rather than per address.  So this transaction would have 5 signatures - 3 from the first key, 2 from the second.

[kjj]

I offer this in hopes that it helps someone find a way to think about bitcoin's inner workings in a way that is useful to them.

There are no addresses. 

There are no balances.

Bitcoin is a chain/mesh of transactions.  Those transactions go by many different names, sometimes "inputs" or "outputs", sometimes "vins" or "vouts", sometimes "coins".  I like to think of them as "coins", but it requires special metaphors.

Your wallet is a collection of "coins", each of which has a specific value.  To complicate things, sometimes we think of the unit that the value is expressed in as "coins" too, but try not to do that for a little while.  When you want to spend, you select a bunch of your "coins" such that their value is equal or greater than the amount you want to spend.  You then prove that you "own" those coins by signing them* , and you bundle them together and specify one or more outputs, each with a specific value.

Think of it like melting a bag of "coins" of different values and minting them into a new bag of "coins", with the network checking to make sure that you don't try to make the value of the output bag more than the value of the input bag.

Of course, these aren't real "coins", there isn't a thing being acted upon.  These are abstractions built upon abstractions.

* Technical note, typically the signature is calculated based on a subset of the entire event (the transaction), rather than just signing the input by itself.  This is because you usually care more about where the spend is going than where it came from.

[DannyHamilton]

. . .
* Technical note, typically the signature is calculated based on a subset of the entire event (the transaction), rather than just signing the input by itself.  This is because you usually care more about where the spend is going than where it came from.

That one tripped me up when I was learning how this worked.  I couldn't figure out why a peer couldn't change the address in the output before relaying the transaction.  I figured the input was signed (or rather a hash of the input), so any peer could do whatever they want with the output.  Then it was explained to me (as you have just done here) that the entire transaction is signed (or rather a hash of the entire transaction).  Changing an output would change the signature, and without the private key a peer can't generate a valid signature.  Light bulb goes on and it all makes sense.

[rupy]

But how does then the addresses work:

1) I have 1Eu6P1eRSewoqf8GZcYoBtMtXG1865Umjh, it has never received any money. How do I prove ownership of this address? Why can't somebody just claim to own this address?

2) If I receive money on this address without having bitcoin client running, will that money just magically appear when I launch the bitcoin client in the future (IE is it the ownership of the address that is stored in the wallet or the transactions/coins?)

[kjj]

But how does then the addresses work:

1) I have 1Eu6P1eRSewoqf8GZcYoBtMtXG1865Umjh, it has never received any money. How do I prove ownership of this address? Why can't somebody just claim to own this address?

2) If I receive money on this address without having bitcoin client running, will that money just magically appear when I launch the bitcoin client in the future (IE is it the ownership of the address that is stored in the wallet or the transactions/coins?)

Anyone can claim to own the address. 

But if you really have the private key for it, only you can spend coins sent to it, and only you can sign messages using that key.  Those are really the same thing.  A bitcoin transaction is really just a special message to be signed.

Yes.  The important thing is knowing the private key.  The way the client works internally isn't so important, but basically those coins are yours as soon as the transactions is confirmed.  When your client gets back online and catches up on the block chain, then it will update the balance that it shows you.

[rupy]

so basically, when you create the address there is a private key created that is stored in the wallet? how are addresses created?

[memvola]

so basically, when you create the address there is a private key created that is stored in the wallet?

Yes.

how are addresses created?

Actually, the private key is created first. It's basically just a 256-bit random number. Then the ECDSA public key corresponding to that private key is generated. This public key can be used to verify a signature. This way, you can prove that you have the private key without having to reveal it.

The public key is then hashed a couple of times using different algorithms and decorated with a version number and checksum to produce the address, which makes it easy to distinguish Bitcoin addresses (e.g. from test network addresses) and very hard to create a valid one by mistake (e.g. typo).

[kjj]

so basically, when you create the address there is a private key created that is stored in the wallet? how are addresses created?

First, you pray.  Then you pull 256 bits at random from the entropy source that you just prayed to.  These 256 bits are your private key.  You check that the private key is not in excess of the modulus of the field, which would make it insecure, if it is, you start over.  Otherwise, the private key gets encrypted (you have encryption enabled, right?) and stored in your wallet.  Then, an operation called EC point multiplication is done using that private key and a well known constant.  The result of that multiplication is a pair of 256 bit numbers (x and y), the pair together known as the public key.*  The public key is put into a special representational form and stored in the wallet.  Finally, the pubkey representation is hashed, and then hashed again.  The second hash is then encoded with a checksum (more hashes!), and the result is an address.

* side note, the y-coordinate can be reconstructed, so it isn't needed, and can be discarded, but we have to store 2 different flags.  This changes the representation, and thus the hash, meaning that a private key can have two different addresses.  One flag is a marker along with the private key, telling the software which of the two possible addresses to use, and the other flag is a parity indication, coded into the public key representation to resolve the ambiguity of the quadratic used to reconstruct y.

[rupy]

Ok, thanks! I think I get everything about bitcoin now!

But so there must be a chance in one gazillion that two private keys generate the same public key hash no?

[DannyHamilton]

Ok, thanks! I think I get everything about bitcoin now!

But so there must be a chance in one gazillion that two private keys generate the same public key hash no?

It's a lot bigger than a gazillion.  It is so unlikely that you can really consider it impossible.  A 160 bit number is a lot bigger than most people can wrap their minds around.  But yes, the only thing in bitcoin that prevents two attempts at generating an address from generating the same address is the extreme unlikelihood of it happening.

[TangibleCryptography]

Ok, thanks! I think I get everything about bitcoin now!

But so there must be a chance in one gazillion that two private keys generate the same public key hash no?

Yes the odds are 1 in 2^256 however what really matters is that the odds of two public keys producing the same address (which is a 160bit hash of the public key with other meta data like version and checksum) are 1 in 2^160.  Note even the 1 in 2^160 is a very small number and for all practical purposes it can be considered 0%.