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%.

[rupy]

Ok, one last thing: if the wallet stores "only" the private keys, why does the wallet.dat filesize change upon every transaction to an address in it? It stores some reference to transactions there? Because you can make payments to an address in a wallet that isn't online without problems right?

[memvola]

Ok, one last thing: if the wallet stores "only" the private keys, why does the wallet.dat filesize change upon every transaction to an address in it? It stores some reference to transactions there?

Yes, it stores the transaction passively. The client is able to scan the blockchain to re-discover these transactions (the -rescan command-line option forces this), but storing them in the wallet is more convenient.

Because you can make payments to an address in a wallet that isn't online without problems right?

Of course. The private key can even be on paper or even in your head.

[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?

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%.

I understand the probability, but say you have all your savings on an address, and, god forbid, someone else "mints" an address that has the same public key, isn't that really HORRIBLE?! How would/could the system then help the real owner of these coins?

So I guess the only real hedge is to spread coins over many addresses?

I mean putting enough energy behind trying to generate an address with alot of coins on it would make sense if bitcoin value rises higher!

the public key is [0-9a-zA-Z] so its not really 2^160 right? It's 32 characters with 10+28+28 mutex no?

[memvola]

I understand the probability, but say you have all your savings on an address, and, god forbid, someone else "mints" an address that has the same public key, isn't that really HORRIBLE?! How would/could the system then help the real owner of these coins?

There are no real owners of coins. Having the only person/entity with the private key is the closest you can get to ownership with Bitcoin.

Having said that, if you think it is possible, you probably haven't grasped the improbability yet. This comes up pretty often, so you can search the forums to find very nice and funny analogies to explain the situation.

Basically, if 1 billion people began generating addresses at the rate of 1 million addresses per second, in about a century they would generate a total of 2⁸¹ addresses. 2¹⁰⁷ addresses until the death of our sun. Of course these aren't unique addresses, so you will never have all addresses at this speed. It might feel as if you could be unlucky enough to have your private key discovered in your lifetime, but you really aren't. The probability of you getting kidnapped and beaten until you reveal your password is much much higher.

So I guess the only real hedge is to spread coins over many addresses?

This is a good measure, not only because your private key might accidentally get generated (it won't), but as a general precaution. If you store money in various private keys and divide them with separate access restrictions, it will make it harder for attackers to access all your money, even through physical torture. A more sci-fi scenario is; if an address never initiated a transfer, its public key is not revealed, which makes it practically immune to quantum computing attacks that we know can be possible in the far future; so the true paranoid might want to store their savings in virgin addresses.

the public key is [0-9a-zA-Z] so its not really 2^160 right? It's 32 characters with 10+28+28 mutex no?

A public key is 256 bits. An address is a 160-bit hash of the public key, plus version and checksum. What you are describing seems to be the encoding, which can be 27-34 characters long.

[DannyHamilton]

the public key is [0-9a-zA-Z] so its not really 2^160 right? It's 32 characters with 10+28+28 mutex no?

The public key is a 32 byte (256 bit) integer.  So that part is 2²⁵⁶.

The bitcoin address on the other hand is built off of a 20 byte (160 bit) hash of the public key.

This results in 2¹⁶⁰ possible addresses (1.46 x 10⁴⁸).

Then a 1 byte version number is tacked on to the front of the address, and a 4 byte checksum is appended to the end, resulting in a 25 byte number.

This 25 byte number is then encoded with Base58Check encoding using [1-9,A-H,J-N,P-Z,a-k,m-z] (note that 0, I, O, and l are not used).

That encoding typically results in 33 or 34 characters made up of 58 different symbols.

34⁵⁸ = 6.7 x 10⁸⁸.  You'll notice that is significantly larger than 2¹⁶⁰.  This is because 5 bytes (the version and the checksum) are dependent on the 160 byte hash.  There are many combinations of [0-9,A-Z,a-z] that are not valid bitcoin addresses, leaving only 1.46 x 10⁴⁸ that any well written wallet will recognize.

[DeathAndTaxes]

I understand the probability, but say you have all your savings on an address, and, god forbid, someone else "mints" an address that has the same public key, isn't that really HORRIBLE?!

You could also die tomorrow getting eaten by a shark while struck by lightning in a desert.  The odds of that are probably higher than a 160 bit collision.  You could also buy one ticket, win the powerball lottery jackpot, next day buy a ticket win that powerball lottery jackpot, next day buy another ticket win that powerball lottery jackpot, next day buy a ticket, win that jackpot, next day buy a ticket, buy that jackpot, next day buy a ticket, win that jackpot, next day buy a ticket, win that jackpot.  The odds of doing that is more probably than generating a 160bit collision.

the public key is [0-9a-zA-Z] so its not really 2^160 right? It's 32 characters with 10+28+28 mutex no?

Well not exactly. The address isn't the public key.  The address is a checksummed hash of the public key.

So in Bitcoin you have:
* private key - 256 bit number
* public key - 512 bit ECDSA (x,y pair) -essentially a number
* public address - 200 bits (8 bit version identifier) + (160 bit hash of public key) + (32 bit checksum - to prevent sending funds to invalid addresses)

Public addresses are simply 200 bit numbers.  We put them into Base58 format to make them human readable but they are just numbers to the network.  

All three of the following numbers are the same and represent a bitcoin address, they are just in different formats.

00010966776006953D5567439E5E39F86A0D273BEED61967F6 (in hexadecimal)

0110011101110110000000000110100101010100000000000000000000000000
0110101000001101001001110000000000000000000000000000000000000000 (in binary)

16UwLL9Risc3QfPqBUvKofHmBQ7wMtjvM (in Base58 format)

The Base58 is the most human readable (and compact) but all three formats have the same value.

Someone made this awesome graphic to show the details


More details:
https://en.bitcoin.it/wiki/Technical_background_of_Bitcoin_addresses

[DannyHamilton]

. . .
* public key - 256 bit ECDSA (x,y pair) -essentially a number
. . .

Don't "compressed key" addresses just use half of that pair?  The pair together (as indicated in your graphic) is 512 bits, but in the case of a compressed key address, only one of the 2 values is represented (and therefore only 256 bits), right?

[DeathAndTaxes]

Typos typos typos.  Your right Danny.  Although the compressed key is more than just the y value (32 bytes).  It also includes a byte to indicate which side of the curve the point lies on (ECDSA curve is like a U so a single y value can represent two points).

The protocol itself isn't aware of compressed keys and to make it aware would require a hard fork.  All that potential bandwidth and storage savings wasted.  Even if a compressed key is used in the client it is converted to a full key when creating a transaction on the network. - Incorrect.

[kjj]

Typos typos typos.  Your right Danny.  I learned that even compressed keys have are more than 256 bits.  It is the x value plus a flag which allows the client to identify it as such (and know if it is positive or negative y value).  I intended to leave compressed public keys out of the discussion so I should have wrote 512 bit (corrected).

The protocol itself isn't aware of compressed keys and to make it aware would require a hard fork.  All that potential bandwidth and storage savings wasted.  Even if a compressed key is used in the client it is converted to a full key when creating a transaction on the network.

No it isn't.  We pass the pubkey as a binary blob to openssl, and openssl will validate the signature using either form.  The same private key can actually correspond to two different addresses, because the hash of the compressed pubkey is different from the hash of the uncompressed pubkey.

[DeathAndTaxes]

Thanks for the clarification on how protocol handles both key forms.

When you said "no it isn't" that didn't refer to the key size did it?  My understanding is that compressed keys are 33 bytes. 32 bytes for y-value plus another byte to indicate which "side" of the curve the point is located on.

On edit:

More info on compressed keys (including wrong answer about compressed keys being incompatible with the protocol)
http://bitcoin.stackexchange.com/questions/3059/what-is-a-compressed-bitcoin-key