Bitcoin Forum

I've discussed this enough on IRC that I thought I ought to put it someplace more lasting.

Bitcoin really ought to offer and default to using deterministic wallets.   The additional security of the current pre-generated ones is fairly small considering how most people use bitcoin and the liability of harm due to insufficient backups and increased pressure to keep a single wallet online is enormous.

What is a deterministic wallet?  It's a wallet which you can backup once and it stays backed up forever because all future addresses are determined in advance. It can also be stripped down to a very small size which could be easily backed up on paper (e.g. with a QR code). This is in contrast to the current non-determinstic wallets where the keys are random but are precomputed ahead so that you're safe only if you backup at least every 100 get addresses or sends, and which grow large and harder to backup on paper over time.

I've found the backup behavior of the current wallets fairly difficulty to get even moderately technical people to understand. The current system provides enough safety to encourage complacency but not enough to make complacency acceptable.  The positive side of a non-determistic wallet is that it becomes "unstolen" over time but people are frequently reusing addresses and attackers will not act slowly regardless.

There are two types of deterministic wallet I'd like to discuss. I'll call them type-1 and type-2.

Type-1 is the most obvious kind:

The wallet stores a large random seed  S (which can be encrypted if the user uses wallet encryption)

Privatekey(type,n) is then simply set to H(n|S|type)  where H is an acceptable secure hash function and type can be set to different values for change addresses vs displayed addresses (so this distinction is preserved even if new wallet metadata is lost).

The system would generate some (maybe 1000 of each type) addresses ahead of the furthest it has observed on the network but only bother to store the addresses. The keys can be regenerated as needed.



Type-2 is a bit less obvious and understanding it requires you to know about a property of ECC keys, roughly:

A_public_key = A_private_key*point

Which means you can do:

B_public_key = A_public_key+B_secret*point
and have a new key which has a private key:
B_private_key = A_private_key+B_secret

So a type2 wallet stores:
Master_private_key
A large Random_seed S.

and keys are given by

Privatekey(type,n) = Master_private_key + H(n|S|type)

which works just like a type-1, the advantage of the type-2 is that you can separately secure the Master_private_key, but still generate new addresses with
Publickey(type,n) = Master_public_key + H(n|S|type)*point

This means that a e-commerce site could have the front end webserver with access to the public key and S, and someone who hacked the server could violate the confidentiality of the addresses in use (because he could enumerate all past and future addresses based on an infrequently changed public key) but couldn't actually steal any of they money sent to the addresses because he would have no access to the private keys.

This could also be used to allow getaddress to work in the client without having to provide a key (access to the TXN data in the wallet means that access to the wallet, even with private key encryption, screws your confidentiality)  which would avoid the problem of backups being endangered due to address depletion from hitting getaddress a lot between entering in the key.

The purpose is clear and definitely appealing.

Type-2 might indeed be a good implementation, but I don't think I understand Type-1.
You would use H(n|S|type) to seed a keypair generation? Isn't the data too small for that purpose?
Or H would not be the usual kind of hash function, maybe a symmetric cypher?

ECC != RSA. You only need as much data is in a private key to create one.

I like this idea.

Will

Definately worth of inclusion.
+1

"in general" session-based components/"smoking crypto" in crypto-systems are nice to strengthen them w/o overhead increase and used by military from WWII era.
so, IMO, its[impact] worth code grow.

I like this idea. A lot. I'm not a cryptologist but I can't think of any downside to this other than one possible (if unlikely) one: what if generating 1000 addresses past the last one seen in the chain isn't enough? After all, a user can generate then discard an arbitrary number of addresses for use, but the code as described would only look for the first 1000 addresses past the last one seen (I assume it would initially look for any of the first 1000 addresses.) But then even this could be handled by a "look for more of my addresses" button that looks for the next 1000 addresses.

Lack of backwards-compatibilty of the new wallets might be an issue, but surely not a significant one (especially if the clients using deterministic wallets would still be able to read and continue growing older wallets.)

So, yeah, no obvious downside that I can see. Who do I pay to get this into a client?

Just a small question. Wouldn't this make it easier for an unauthorized individual to make a copy of the wallet and then use it at an arbitrary date in the future to access and steal any coins in it?

Yep. That is the compromise.  The current wallets unsteal themselves.

My arguments:
(0) In spite of recent concerns, I think that loss is a greater risk for most users than theft.
(1) People frequently reuse addresses today, this eliminates the unstealing advantage.
[And, in fact, someone on IRC was just asking about changing the client to send change back to the original address in order to make backups more effective]
(2) Encryption makes theft less likely than it has been
(3) Thieves know about the unstealing property and will already act fast enough if coin is available.  If you're about to receive a lot of new coin you could start a new deterministic wallet. Also after compromising your machine once the thieves will likely leave backdoors in any-case.

If the interface allowed you to have multiple deterministic wallets at once (or just multiple key-heads in a single wallet) you could periodically trigger the creation of a new one in order to get the forward privacy, and you could do this in time with your backup schedule so you're not left surprised by a backup that failed to grab all your addresses.

+1

sounds like a good idea, it should be an option (truly paranoid people will probably disable it) but I have no problem with it being on by default

+1

I think this is a great idea. Indeed I've suggested it myself several times, here and in the github threads. I like the idea of having minimal sized keys (none of the transaction history) in the wallet. Further, the wallet should 'optionally' cycle through the pre-generated keys. A user should be able to have a wallet with a single key. In fact, I would prefer a wallet as simply a directory (or plain text file) containing individual keys.

In my own use case, I create new wallets often. Deterministic wallets would simplify my backup use cases and make me a lot less paranoid. As it is, I feel the wallet is far too much of a black box. Predictability will go a long way to help bitcoins gain traction.

The idea of a master key is very good.
It is already used by programs such passwordmaker (open source) which i use with great satisfaction.
Anyway i think that periodically is necessary to create a new set of keys, that is a new wallet to which transfer all the funds, discarding the old wallet: we can never be sure if a certain wallet is compromised or not.
This operation, in my opinion should be executed before every backup and in case we use a master key we should generate a new one.

Is it possible to make the pubkeys separately deterministic from the private keys, and have multiple chains of them? My thought is that this would be nice to allow receive-only bitcoinds for services-- they can call getnewaddress to get a unique destination address, and listtransactions can still show what they received, but they don't have the private keys to send the funds. The other servers could have the "root keys" needed to track all the other servers' transactions, so listtransations on any server would show the data for all the servers. Finally, only the super-secure wallet would have the data needed to generate the private keys and actually spend the funds.

I presume multiple chains is merely a simple matter of implementation, but I'm not sure whether deterministic pubkeys matching privkeys is possible?

This would be cool. I'm assuming given two known public keys for an individual the relationship cannot be reverse engineered?
If so that would not be a good thing.

Am I right that if use seed encryption, then the same  large random seed  S can be used by backup many wallets simultaneosly? One wallet for each password.

Not a cryptographer, but I like this idea.  In fact, this is how I had assumed Bitcoin was implemented before I read the technical information.  A lot of important web services will need this feature to function effectively and securely.

One of the advantages of the deterministic wallet is that they can be backed up offline and any copy is as good as any other no matter how old. One of the reasons we want to do this is to protect our bitcoins for posterity, or at least so we can sleep well at night.

So it seems just as important to me to be able to secure a wallet 100% offline. I should be able to send a transaction without ever exposing my wallet to the network. It should be possible to create a 'send file'. In other words, I should be able to use my offline deterministic wallet to sign a transaction, then separately (and perhaps physically) take the transaction to another machine that is on the network and execute the transaction without the wallet.

We discussed that here: http://forum.bitcoin.org/index.php?topic=19080.msg263715#msg263715

Excuse me if I'm being a noob, but as I understand this system, it's basically generating many keys in a deterministic way from a single backed-up seed. Doesn't this make it possible for anyone with multiple public keys generated from the same seed to do some sort of correlation attack and discover the seed?

Again, I'm not a cryptographer and could be way off the mark here. I think it's a fantastic idea, if it is indeed secure.

It should be hard.  The more info you provide, the easier it gets.

The biggest weakness is likely the initial password.  If that is complex enough, then it should be OK.

Aside from the OP's deterministic minimums based on seeds, I would like to hope the current rand seed is based on cumulative data, the time, mouse and keyboard, threads, etc. I can't find the source but there are two headers files of interest: src/key.h and src/cryptopp/cryptlib.h the former making reference to EC_KEY_generate_key which might be related to the OpenSSL implementation: http://linux.die.net/man/3/ecdsa

Just to confirm my understanding.

Capital letter = point (used for public keys)
Lower letter = integer (used for private keys)

a = master private
A = master public

b = generated private
B = generated public

G = generation point (constant for curve)

v(n, t, s) = hash function
s = random seed
n = transaction/key id
t = type id

The standard rule is

A = a*G

We can generate a new private key using

b = a + v(n, t, s)

The corresponding public key is

B = b*G = (a+v)*G = a*G + v(n, t, s)*G

However, a*G is the master public key

B = A + v(n, t, s)*G

So, all of the public keys can be computed with just the master public key and S. 

n and t are assumed to be pretty small numbers.

The private keys are

b = a + v(n, t, s)

They need a (the master private key) to be generated, as well as all the other values.

As long as a and s are protected, the user can never be unable to spend his coins and as long as a is kept secret, nobody else can spend his coins.

I wanted to share some thoughts about how Webcoin is going to handle DWs. I'll use the same symbols as TierNolan.

First of all, I don't see the need for a seed. Since the seed has to be stored with the private key anyway, you might as well regard it as part of the private key.

Next, the master private key should have a full 256-bits of entropy. So we use a random number 0 < a < 2²⁵⁶. Yes, it's a pain to type. In practice you'd normally use more convenient ways to transfer DWs, such as USB sticks, QR codes, etc.

(However, if your house just burnt down and you lost every backup but the printed hardcopy at your safety deposit box, I don't think having to type a very long password is going to concern you too much.)

Here is an example of a 256-bit number using base58 encoding:

"6QPCJCRhPSVoKL4hhLoqRuBEk4VYzAFMAC1GwQ7JbSR4"

In reality we'll also add a checksum and a version byte, similar to a Bitcoin address.

In our version, there is no seed, so we've been working with v(t, n) instead of v(n, t, s).

t ... type is included only for future use. Currently it is a zero-length string, i.e. it is omitted.
n ... serial is a 64 bit unsigned integer (LE).

So a new keypair b, B is generated as:

b = a + SHA256(A t n)
B = A + SHA256(A t n)*G

A is an ECPoint encoded using standard non-compressed form (0x04 x y)

To generate a new public key for the wallet, you need to know A, t and the next serial number to use.
To spend the coins on any of the addresses, you need to know a, t and the serial number.

During normal use, we assume that we have access to a metadata storage system. The metadata storage is retrievable using an access key SHA256(A "access"). It's contents are unencrypted, symmetrically encrypted or asymmetrically encrypted depending on the application. For example, a merchant server whose only job is generating addresses would encrypt metadata for those transactions using a public key and the wallet would retrieve it using the corresponding private key. That way, if the merchant server is compromised, privacy for previous transactions is still guaranteed.

If the metadata is lost for any reason, the user can use a recovery tool to get their coins back. The recovery tool needs a full database of unspent outputs in the block chain and will simply generate public keys using sequential serial numbers using the method above. Whenever it finds coins it will add an entry to a new metadata array.

Note: Using t will make coin recovery more difficult, because the recovery tool will have to a) know all values for t and b) separately scan them all. That's why we're more interested in keeping t an empty string for all normal use cases and using the metadata to synchronize what the next available serial number is.

The maximum number of addresses for one wallet is 2⁶⁴ or 18,446,744,073,709,551,616 (for each t).


Correct. I want to add one more: As long as the master public key A is secret, nobody can break the privacy of the other addresses.

Nice! We need this everywhere.
Wallet's private data is 1 Random number, all the rest can be derived from it.

Am I correct in thinking that if you keep A a secret between you and a friend, and agree to use some agreed upon sequence of serial numbers (could this just be trivial and the same for everyone?), that they could have access to an infinite number of your public keys that can't be associated by an outsider?  Edit: lol I think you just said this in the last sentence.

If so, then it seems like it could enable people to interface in the client with a contacts list instead of ugly addresses, but without having to reuse them or manually request new ones all the time.

I guess one major problem would be losing the master private key, and having people continue to send to addresses derived from the associated public key.

This could be mitigated by having your contact instead for each transaction get the master public key from an (untrusted) online storage server who stores it encrypted to your private key and your contact's public key, and check that it hasn't changed.  That way if you lose your wallet, you can stop everyone from sending to it in one step by deleting the master public keys from your storage server, and restart it again by uploading new ones for each of your contacts, without having to notify them, since their client can just start the agreed upon serial number sequence anew if they notice that the master public key has been changed.

Edit: Damn, I read your post two days ago, and forgot to re-read it before responding.  I apologize for basically restating what you did.

You've missed a whole use case here:

Say I want to run a webserver that accepts paymets. It needs to be able to generate addresses, but if it gets hacked, I don't want the hacker to be able to spend any of the incoming money.

By splitting the master private key and the seed used to generate the addresses, a RX only wallet can generate unlimited new addresses without having the ability to spend or any required communication with a separate secure wallet that can spend.  An attacker who stole the data on the webserver could only deanonymize payments.

Thats why I proposed it with a separate seed. :)

Perhaps not important for all uses, but pretty useful for this ecommerce one.

Actually, my post specifically mentions this use case:



You don't need a seed to generate addresses securely. Knowledge of A is enough to generate addresses and you don't need to have the master private key at all.

The only problem is that if the hacker has A, he knows all your addresses, so while he can't spend your money, he can see all your blockchain activity. If you extend your seed concept a bit you could use a changing seed, so that an attack would only compromise the current seed.

Going one step further, I've recently been thinking about using a hashing chain. I.e. the hashes no longer depend on A, but instead depend on the previous hash plus the serial number. Then you make the server forget each hash as soon as it's no longer needed. The first hash would be derived beforehand from the master private key in some fashion and is then part of the deployment package to the webserver. That way you can still generate all private and public keys from the master key (full determinism), but a hacker gaining access to the merchant's webserver would only be able to spy on future transactions, not past ones.

Sorry, — I shouldn't post at dark-am when I should be sleeping. The mixed case threw me, I saw that a was the initial private key and thought you were saying you were using it in the hash and I stopped reading. :( Sorry.

I'd need to see a more concrete version of the chain version. The simplest implementation with just H(prior-key|type|serialnumber) would be insecure because the serial number would not have enough entropy. e.g. I'd generate two addresses keys on your site, getting sequential serial numbers, then I'd send money to both and wait for you to spend it and disclose the public keys in the process,  then I'd search the space of likely serial numbers such that one address leads to the next.  Then I can generate all future public addresses.

In ten seconds I see a way to address that, but there may be a better one.

It seemed to me that the lack of cheap random access was a bit of a liability, but if the chaining variable is simply the prior key or address which you'd need to cache in any case to identify transactions, then this would be pretty good.

Good point, I should have been more specific. So here is the chain variation in detail.

Let s_n be the second part of the private key which the merchant's webserver generates.

The private and public keys are therefore:

b_n = a + s_n
B_n = A + s_n*G

The first hash s₀ is generated by the wallet as follows:

s₀ = SHA256(a i C)

i ... A 64-bit integer (LE) that starts at 0 and is incremented if the same wallet is used for more than one chain.
C ... Some constant, e.g. "BITCOIN_CHAINHASHSEED_gZ5hA5S7237RoJ" - this is the same globally for everybody.

The merchant then takes s₀, i and A and inputs them as settings on his webserver. The server initializes the transaction serial number n as 0. It is now ready to accept orders.

A user wants to do an order and pay in Bitcoins. The merchant server now runs through the following steps:

1. Increment n.

2. Generate new s_n:

s_n = SHA256(s_n-1 n C)

n ... The current serial number as a 64-bit integer (LE).
C ... Another constant, e.g. "BITCOIN_CHAINHASH_2bIyLHNXlHe77u" - this is the same globally for everybody.

3. Derive the public key B_n:

B_n = A + s_n*G

4. Create, output and store the Bitcoin address corresponding to B_n.

5. Securely delete s_n-1.

Note that storing the address in step 4 depends heavily on the specific use case. Here are a few examples:

(A) The server stores the address until the payment arrives and then sends the details of the order via email to the merchant at which point it deletes its own stored information about the order.

(B) The server doesn't store the address in plain text, but instead encrypts it with a public key and stores it like that. Every day the orders are downloaded, decrypted and processed on an offline system.

(C) The server stores the address until the payment arrives, then enables the user's account to access the digital content he/she has purchased. After that the server encrypts the address and other information related to the transaction with a public key and stores it for archival.

Implementation-wise we would probably wrap the chainhash stuff in a library that takes A as a configuration value and s₀ and n as initialization values and just spits out new addresses on demand. It would also provide utility functions to write data to the metadata storage like setDescription(chainSerial, transactionSerial, description). This information could be submitted to the wallet metadata using asymmetric encryption and later be retrieved by the wallet software and displayed in the list of transactions - similar to Bitcoin's address book feature.


Hmm, I don't think that attack is possible - or I haven't understood it correctly. My chain consists of private information only. Having the public key and the serial number would not enable you to predict the next address. Curiously, even breaking ECC and finding out any number of b_n wouldn't give you access to s_n, because you'd still only have sums a + s_n with no way to solve for a.

More realistically, breaking into the server you could compromise the current s_n and the current serial number n, which would tell you how many transactions have taken place as well as predict any future addresses - both with respect to this specific chain. It would not allow you, however, to find out any of the previous addresses unless that information is still stored on the server in some other fashion.

Caveat: The chain serial i increases the dimensionality of the address space. If all metadata of the wallet is lost and we want to recover our money based on only the private master key a, we have to in theory try every n for every i. In practice, the user will likely have a small number of chains per wallet and/or know roughly how many he/she has. So the search would be limited to very small values for i. Given that a total loss of metadata is a worst case scenario and other types of backup are likely being used as well, a certain amount of computational work for the recovery procedure seems acceptable.

With Webcoin specifically we hope to eventually store the encrypted metadata in a DHT. At that point the deterministic wallet concept serves two goals: (1) Reducing the amount of data that needs to be stored (a serial number like i and n could be stored as a var_int, 1 to 9 bytes, compared to a private key (32 bytes) or even a public key (65 bytes)) and (2) Providing a "last resort" recovery mechanism if all else fails - namely by scanning for unspent outputs using the private master key.

Agreed very much. I was quite surprised to discover this feature after muddling through a lot of very geeky documentation. People can't be expected to comprehend this sort of quirks.

I just looked at OP but be aware when designing a scheme like this you must be very careful to use the correct cryptographic primitive.

The primitive you are looking for here is a http://en.wikipedia.org/wiki/Pseudorandom_function_family.
A http://en.wikipedia.org/wiki/Cryptographic_hash_function is NOT the same thing.  In particular, it is not true that given a hash function H, taking family F(K)(X) = H(K | X) will yield a PRF (perhaps, for a particular hash function, it will yield something noone knows how to break, but its security is not provable assuming the security of the hash function).

PRFs are mainly used to construct other things and so may be unknown to you.  You likely do know something very similar, the "PRP" or Pseudorandom Permutation, which is like a PRF but which is indisinguishable from a random permutation by bounded adversaries (note the two are basically the same to an adversary, since they could never distinguish a random function from a random permutation anyway, as querying a random function on a reasonable number of places will never show two values mapping to the same).  PRPs are what applied crypto people call "Block ciphers".  So you can use a block cipher, e.g., AES, to do what you are trying to do.   But do NOT use a hash function, that is not what it is for.

Again I cannot stress enough how important it is that correct crypto primitives are used for their intended purposes.

So instead of using a hash we should be using a block cipher?

I presume that the difference between the two with the most practical impact is the presence of collisions in the former and the absence thereof in the latter.

I'm not really calling in to question the validity of what you say but, to make your point more obvious, could you give a realistic example of a situation in which using a hash function instead of a pseudorandom function gives noticable problems?

ByteCoin

I'm no cryptographer, but hashcoin said "it will yield something noone knows how to break, but its security is not provable assuming the security of the hash function". So the problem isn't that there's a known weakness, but that it's not provably secure, as PRF is, assuming the security of the function.

Yep, you're correct. I'll update my posts to use SHA-256 with HMAC, which is used as a PRF in IPSec, TLS, DKSPP, etc.

No. Because it's the secret keys that are correlated and an attacker would only have the public keys.

Even if he did have some secret keys, it wouldn't matter. This attack would be possible in theory but impossible in practice because the scheme is specifically designed to make it impractical. (It's not particularly hard to do that. Both schemes proposed use well-known methods to prevent this even if an attacker had some private keys somehow.)

Of course, if the seed gets out, all future keys are compromised.

This is a fascinating thread, and although the maths often fly over my head, I'm earnestly trying to keep up. Please correct me if I have been derailed from the very beginning, the goal is to base an entire infinitely expandable wallet on a single seed. While subsequent data (generated keys, transaction references, etc) could be stored with a wallet, all that is critically necessary to back up is this (what?) 100 byte seed. Everything else can be regenerated ad nauseum.

If this mechanism is being seriously considered, someone needs to make sure it's not encumbered by a patent. I remember when I first heard the notion of a "family of public keys" such that a single private key would allow deriving the corresponding family of private keys, I seem to recall it being patented. That was at least three years ago, I think, so it may not even be covered any more.

FWIW, I may be filing a patent on this, so I'll report back if I find anything problematic.

If I do so, I will be offering it under terms no more restrictive than the Xiph.Org patent license: https://datatracker.ietf.org/ipr/1524/  (e.g. a free license to anyone who doesn't conduct patent litigation against bitcoin users)
 

I'm curious, are you allowed to file a patent AFTER discussing it in a public forum? I was informed, perhaps wrongly, that if I had intentions of patenting something, prior to actual filing I should never disclose it in public or discuss it without making clear it is confidential, otherwise it would render the idea inadmissable.

It depends on the country, in the US you have 1 year to file after demonstrating your invention in public.

I like that this idea makes it more convenient to back up your wallet addresses, lessening chance of losing bitcoins through hard drive failure/fire/whatnot, but the proposed solution creates an unacceptable trade-off in that it's too easy for an attacker to compromise all future transactions.  If the attacker has access to a wallet just once, they can clear out the victims wallet at any future time, and at a time of their choosing when they believe they will get maximum value out of the wallet.  And when the attacker chooses to act, the victim will never know what hit them, or when the wallet was compromised - it could have been months or years in the past.  This seems scary to me, and would keep me from using the same wallet over a period of years.  Regularly creating new wallets rather defeats the purpose of the idea of a deterministic wallet that doesn't need multiple back-ups.

How about a middle ground: the client could pre-generate the next, say, 100 addresses, and then whenever a backup is performed, these pre-generated future addresses are also saved.  "New" addresses are actually being pulled from this pool of pre-generated addresses.  Enough addresses should be generated to cover, say, a month's worth of transactions, the maximum supported time between wallet backups (yes, some people only back up monthly).  Pre-generated addresses that were unused for a month would be discarded.  Exact number of pre-generated addresses would be set in Preferences page.

With this scheme, even if a hard drive fails right after receiving a transaction using a "new" (but actually pre-generated) address, the transaction address used would have already been backed up in the past month.  It would be kind of like the new video cameras that are always recording, overwriting their cache constantly, and when you press the button _after_ the action has happened, the previous 10 seconds of video in the cache is saved to memory. 

An attacker that compromises the wallet with pre-generated addresses would then want to act within a month since they could not compromise all future transactions as with the deterministic wallet.  This tighter coupling between the time of compromise and the wallet being emptied is a Good Thing for post-hoc failure analysis.  And if you transfer all of your coins to a "new" address, you can be guaranteed that your wallet is secure, even if someone finds, say, an old backup you forgot about and threw out in the trash.

This scheme also avoids the potential cryptographic problems of creating a seed address that might, just might, have a cryptographic vulnerability. Using a set of pre-generated addresses avoids this issue by using future randomness in generating future keys.

Finally, philosophically, I think wallets need to be living entities, and an immortal wallet is not a good idea.  I can't concisely explain the reasons why this is best besides the above example about the backup found in the trash.  There's a reason the PGP key system is designed to allow keys to expire, and all good security systems require occasional password changes.

It already does.

Even after a PGP key has expired, you can simply edit it to extend the expiration date. Passwords on deterministic wallets can be changed like any other.

Doh, it's like I read https://en.bitcoin.it/wiki/Securing_your_wallet many moons ago, forgot it, then wrote it back out again, thinking I was being original.  Squishy data storage (brains) aren't very good. http://www.htmlhelpcentral.com/messageboard/showthread.php?13363-Mind-Control-Magic-and-the-Value-of-Branding-Online

I am wondering the same thing: if the wallet is deterministic and you publish several public keys shouldn't it be possible to calculate the original private key? Especially regarding merchants, restaurants and such who most likely will publish a lot of keys. The more keys published the easier it should get to find the private key!

Or am I missing something?

As it is currently not (in realistic time) possible to get a private key to a public address, you are likely also not able to determine how these private keys might be linked together.

No, you are correct. But it doesn't matter. Here "easier" means that if you dedicated every computer on the planet to breaking a key, it might take a few dozen centuries rather than a few hundred centuries. In fact, the system is so strong, even if you released the master public key, allowing an attacker to generate as many related public keys as he wanted, it would still be impossible (for practical purposes) for him to compromise a single private key. (In fact, this scheme was originally developed with the idea of using it exactly that way.)

This is the interesting thing about public key cryptography. Attacks are always possible. Every conceivable compromise is doable in principle. So you can't just check if an attack is theoretically possible, you have to ask if it is practical.

I'd like to direct you to a  proposal  (https://bitcointalk.org/index.php?topic=39181.msg478907#msg478907) which could be seen as implementing a type 2 deterministic wallet on funder's clients. The hash function in this case is choosing the x coordinate of an elliptic curve multiply in a similar fashion to ECDSA.

I believe that this would satisfy the goals of a deterministic wallet and have a number of other fairly obvious beneficial effects.

ByteCoin

can someone explain this to me?

If someone steals your wallet, they get all your old addresses and the next 100, but no more.  When you start using addresses, the key pool keeps getting refilled with random addresses based on the random number generator on your computer.  The attacker will generate different (and thus useless) addresses.   Therefore, if someone steals your wallet, it "unsteals" itself after you go through 100 addresses.

Since the point of deterministic wallets is to produce the same sequences of addresses every time, the attacker will always generate the exact same addresses until the end of time.  They have permanently stolen your wallet, and could wait years before executing an attack, if they knew you were going to keep using it.

However, I'm of the opinion that this is basically irrelevant.  The severity of attacks on both types are not much different, and many cases they are the same -- because if the attacker has access to your system to steal it, they can install a process to continue stealing your wallet.  I firmly believe that users' not having sufficient backups is a tremendously more significant risk to their wallets.  As such, deterministic wallets are superior since they only require one backup at time of creation.

I agree. If an attacker has access to your system and you don't notice it, he can continue to download new copies of the wallet and if you do notice it, you can generate a new wallet and transfer your money over. So the ability of current wallets to unsteal themselves only applies if:

• The attacker waits rather than stealing your wallet's current contents.
• You unknowingly/accidentally fix the hole he/she used to break into your computer.
• You use up ~100 addresses before the attacker notices he/she no longer has access to your machine.

In high-security scenarios, a better alternative than a set of pregenerated addresses would be to simply create entirely new wallets from time to time. Whether these are deterministic or not makes no difference at that point.

At the same time for normal users a deterministic wallet makes it much easier to protect against a whole range of data loss scenarios. It's much easier to have secure, long-term backups if you don't have to constantly update the backed-up data. As long as it is implemented well, it should be just as secure against theft and much more secure against loss.

so this paper backup i generated from Armory consists of a Root Key and a Chain Code.  is the Root Key the same as the Master Private Key discussed here earlier?  whats the Chain Code and where is the Seed?

The "root key" is a Bitcoin address that serves as the "root node" of the deterministic wallet.  All other addresses are based on it.  The chaincode is another 32-byte number that helps you get from PrivKey(i) to PrivKey(i+1) or PubKey(i) to PubKey(i+1).    In order to have "type 2" deterministic wallets, you will need to be multiply the priv/pub keys by a number... so the chaincode is used to create that number.

As described by gmaxwell, you could easily use lots of different chaincodes to create different address "branches".  Right now, in Armory, there is only one chaincode per wallet.  But you could could add multiple chaincodes to create multiple "branches" that would then appear unrelated -- i.e. you could give someone a watching-only wallet with the first chaincode, another person with a different chaincode but same root public key -- they'll generate two completely different address chains even though they both have the same root public key.  You can generate all private keys in both, but the two people will not be able to generate or even recognize addresses on the other branch.

what does the QR code represent?

The QR code is the exact same data, but in a QR code.  The primary goal was that you could use the paper backup as both a backup, and a means to transfer a wallet to your smartphone, just by scanning it (there are currently no Bitcoin apps that leverage my wallet format, but I'm getting help to work on one, now).  But it would also be useful if you have a webcam setup for scanning QR codes -- it'll pick up the exact same letters as shown on the page, and you can just copy the text into the "paper backup import" dialog.

For anyone in this thread who has no idea what I'm talking about, the paper backup looks like this:

http://dl.dropbox.com/u/1139081/BitcoinShare/Screenshots/dlgPaperBackup.png

so how do u get priv/pub keypairs out of the root key/Bitcoin address?

I picked a sub-optimal construction, and wished I had talked to gmaxwell and sipa before I commmitted myself to it, because I like theirs better.  However, there's nothing wrong with what I did, it's just that it can be a little slow, and theirs has some nice properties (like random access).  I will be adding support for their method in Armory and deprecating mine (eventually).  Until then, here is both algorithms:

Let the root address be considered keyIndex=0, C be the chaincode, and O be the order of the elliptic curve group:

Mine:
M = doubleSHA256(PublicKey(i)) XOR C
PrivKey(i+1) = (PrivKey(i) * M) mod O


gmaxwell and sipa use HMAC construction; || represents concatenation
PrivKey(n) = SHA256( C || SHA256(C || PubKey(0) || n) )

I'm interested in deterministic wallets especially how to generate pools of addresses
with the parameter range from-to
I want to have addresses generated on the server side (and not saving the private keys there), offering users unique addresses (tipping jar/donations, sales, etc) while not exposing the public keys to any network.
I found bitaddress script has some limited support for deterministic wallets but I can't use it effectively yet.

Mila,

Look at Armory (https://bitcointalk.org/index.php?topic=56424).  It provides exactly what you describe:  keep the full wallet somewhere else (maybe not even touching the internet), create a watching-only copy of it (no private keys), and use that on your website to distribute addresses.  There is no JSON-RPC interface to it (yet!), but I could help you produce a straightforward script along the lines of "getAnotherAddress.py" that will read your watching-only wallet fie, and return the next unused address.

If you want more information, see the presentation on my webpage:  Using Offline Wallets in Armory (http://bitcoinarmory.com/index.php/using-offline-wallets-in-armory).  That doesn't show you exactly what to press, but it explains how the process works.  Please PM me if you want help setting it up :)

This is one of the reasons I created watching-only wallets -- risk-free webservers.  I hope you get some benefit out of it!

Good work eto.  I think deterministic wallets should be considered for the reference implementation as well.

Actually, they are.  Sipa has a test branch implementing the deterministic wallets I described above (the HMAC version)... though it will probably a little while before it gets fully tested and merged.   Once that happens, I will add support to Armory for it.

I like the visual appeal of Armory. The general design, the logo, the name.

I'd like to add to this thread the simple explanation why the crypto behind deterministic wallets is sound, i.e. why it's safe to assume that an attacker who only looks at public data (that's sent over the bitcoin network and stored in the blockchain) doesn't have an advantage if the participants use deterministic wallets instead of the regular random-independent wallets. As discussed here, obviously if an attacker obtains the master private key and random seed then he can generate new keys, unlike the case of random-independent wallets, but the focus here is about an attack without access to the secret data.

Since with type-2 deterministic wallet the public keys are generated independently of the master private key, using key homomorphism, it's enough to say why signing transactions with pseudorandom private keys and revealing the signatures is safe from related-key attacks. The only assumption needed is that PRFs (pseudorandom functions) exist, which is a more conservative assumption than PKE exists. In other words it should be safer to assume that sha256 is pseudorandom than that elliptic curves give public-key encryption, though admittedly elliptic curves are used in bitcoin just for digital signatures and not PKE.

So assuming that the hash function h(x)=hash(type|seed|x) is a PRF, a PPT (probabilistic poly time) adversary who's given r_i=h(i) for i=1,2,...,n=poly(security parameter) cannot distinguish them from R_i that are truly random. Now suppose (sk_i,pk_i)=keygen(r_i) and the signatures sgn_i=sign_sk_i(msg_i) are published along with the msg_i, and a PPT adversary A1 can create a signature sgn' for a new msg' so that verify_pk_j(msg',sgn') is true for some j<=n with a non-negligible advantage compared to the case where the keys were generated with keygen(R_i) randomly. This means that there exists another PPT adversary A2 who can distinguish between pseudorandom r_i=h(i) and random R_i sequences with non-negligible probability, simply by taking his input sequence t_i and creating (sk_i,pk_i)=keygen(t_i) and signing sgn_i=sign_sk_i(msg_i), and then simulating A1 by giving it the msg_i and sgn_i signatures and testing whether A1 successfully signs some new msg''. Therefore A2 is a PPT distinguisher and the hash function isn't a PRF, QED by contradiction.

In more simple words, this proof just says that for any efficient computation that you do on peudorandom input, the output of this computation is computationally indistinguishable from that output that you'd get in case you did the computation on truly random data. In this particular case it might seem to be a little confusing because the attacker A1 isn't supposed to be able to efficiently compute a signature for a new message. So it's a proof by contradiction, saying that if such a miraculous A1 actually existed, then we could use it to distinguish between pseudorandom input and random input. Our entire computation is efficient, because the keygen algorithm and the signing algorithm (when we now the secret keys) and the verification algorithm are efficient.

That was a generic argument why pseudorandom keys are safe from related-key attacks, it has nothing to do with bitcoin wallets. However, in the context of bitcoin the optimal behavior of signing only once with each key is also true for deterministic wallets, meaning that an adversary has less than 10 minutes on average to try to attack, under the (even more conservative) assumption that the address hash is a one-way function.

So the bottom line is this: let's say that you have a 10 megabytes file f1 that contains truly random data, and another file f2 that was created by taking 256 truly random bits as a seed and creating the 10 megabytes file f2=(sha256(seed|1),sha256(seed|2),sha256(seed|3),...). If you agree that it's infeasible to tell which file is f1 and which is f2, then a deterministic wallet is right for you. If you disagree, then stick with a random-independent wallet. If you're unsure, then go with a deterministic wallet, it's cryptographically sound and it's much safer/easier in terms of backups.

The clients that offer type-2 deterministic wallets (like electrum and armory) should advise their users that sharing any private key from the derived chain (not the master private key, of course) MUST be avoided. Such a sharing of a private key could happen for example by funding your MtGox account with the "Redeem private key" option.

Recall the suggested computation of the key chains was this:
where S is a random seed.

The use scenario is that a "hot" machine (connected to the internet and potentially vulnerable) generates a chain of public keys, and for that purpose stores Master_public_key as well as S. In a reasonable threat model both values become available to an attacker because the "hot" machine is vulnerable. Since the serial numbers n and the type can be guessed, a single leaked private key will leak Master_private_key as well by a simple substraction in the finite field underlying secp256k1.

Conclusion: Users should be advised that ANY private key from the generated key chain is to be secured with the same security level as the master private key.

This seems to affect not only the implementation of deterministic wallets in electrum and armory but also the hierarchical deterministic wallets suggested in BIP 032:


Suppose the "hot" machine of some main business wants to be able to automatically generate extended public keys (Kn,cn). It needs to store (Kpar,cpar) to do that. Suppose it computes the corresponding extended secret key (kn,cn) on a "cold" machine and hands it to the business' subbranch numbered n, so that the subbranch can work independently. Now, if the information (Kpar,cpar) stored on the main business' "hot" machine leaks then the subbranch can obtatin the main business master private key kpar by these computations:

• I = HMAC-SHA512(Key=cpar, Data=Kpar || n)
• Split I into two 32-byte sequences, IL and IR
• kpar = IL^(-1)*kn (arithmetic in the finite field underlying secp256k1)

Conclusion: In a scenario where derived secret keys are handed over to subbranches, the derived public keys MUST not be generated on the fly on "hot" machines. Instead, even Kpar must be stored "cold". To some extend this contradicts the original idea of hierarchical deterministic wallets.

thanks for the advice.
I added the following warning to Electrum: https://github.com/spesmilo/electrum/commit/ad3be71ed7178881d8c0706588dfb3b3d573691d

(it is displayed before the password is requested)

Thanks for noticing this. I must admit that I never considered this scenario.

https://en.bitcoin.it/w/images/en/3/36/BIP32-derivation.png

I'm trying to understand the full implications of accidentally revealing a individual private key.

Suppose I gave Mt Gox the extended public key m/0/0. They would then be able to generate m/0/0/0...k themselves in order to send each future BTC withdrawal to a unique address without further interaction from me.

If I accidentally reveal private key m/0/1/42 this means they can generate all private keys in the m/0/1/0...k series as well.

What does that mean for other branches like m/1, m/2, etc?

In general, deterministic wallets (a) make life easier while (b) increasing the security threat (e.g. decreasing overall security).  Before, if one private key was compromised, others were safe.  Now, the picture is not so clear.

And if the seed is compromised, all keys are thus compromised.

If all private keys are covered by the same master key, then the security situation is largely unchanged, and the threat model focuses on protecting the seed (rather than a wallet full of keys).

However, private keys are not necessarily all tied together.

It seems like it should be possible to compartmentalize the risk. Accidentally revealing one private key will compromise the entire branch but it should be possible to limit the damage to that branch without affecting others.

+1 for type-2 deterministic wallets

As currently proposed, if you have the master public key you can, in principle, iterate over the serial number to generate all possible addresses. However, there is no hard upper bound on the serial number, or the sizes of any gaps in the sequence of used addresses. Would it be possible to include some identifying information--in particular, the serial number--in the address itself, so that one could easily check whether a given address matches a known master public key without scanning through all possible serial numbers? Or is the address format too inflexible for that?

The difference in security model between deterministic and non-deterministic wallets is really quite tiny in practice.  There's very few situations where that difference is the results in devastating compromise with a deterministic wallet, that wouldn't also be devastating to a randomized wallet.  And then that is compounded by the fact that there's very few situations where an attacker would get one private key but not the others:  they usually get nothing, or they get everything.  In terms of users revealing private keys from their wallet -- that is a practice that just shouldn't happen.  If they are doing that, then yes, the deterministic wallet is less safe, but the user is exercising poor judgment and likely to compromise themselves other ways (they should be educated about this).

The reason why the security difference is effectively small between a compromise of either system, is because existing Bitcoin-Qt wallet behavior of pregenerating a pool of 100 addresses actually makes the two very similar.  Sure, the Bitcoin-Qt wallet "unsteals" itself after some amount of time, but that time may be very far in the future when the user actually gets through those 100 and starts generating more.  Most of the coin-stealing will occur with the coins already available in the wallet, since there's no guarantee that coins will be added or removed from the wallet in the future to risk losing them if the user spends them.  Perhaps if the attacker knows some information about the user and knows they will be receiving coins in 3 months from now and want to wait for that to occur then the randomized wallet is preferred (for the user)... but then that is effectively a targeted attack, which is expected to be much more difficult to deal with, anyway.

In reality, the biggest risk to the average user is not time-staggered wallet theft, but loss of coins from HDD loss or wallet corruption.  The ability to make a single backup, ever, far outweighs so many other risks faced by regular users.  That's not to say the randomized key model is inferior for all use cases, but the default very clearly should be deterministic one (let knowledgeable users who understand the various factors make the decision to change from the default).

I'm still not sure about the answer to my original question. As BIP34 is currently written, if an attacker knows the chain code associated with m/0/0 and knows one of the private keys in the series m/0/0/0...k series can also he recover the private key of any other branch in the tree, or does m/1, m/2, etc use a different chain code that can't be derived from the m/0 chain code alone?

If the attacker a single private key and the same key's chaincode, m/i/j/k, he can only determine m/i/j/k/X.  You can't reverse the chain or get to other chains, or even determine "brothers" in the same chain.  You can only traverse down a separate chain specific to that key (which is not ever used in BIP 32 wallets, by default)

So what is this about?

I understood this to mean if the attacker knows the extended public key (which includes the chain code) of a node, and any one of the associated private keys, then the attacker can also recover all the sibling private keys. Is this not correct?

Correct. It is the chaincode that you gave away which determines (or limits) the "damage" that a leaked private key does. If you give away the chaincode of m/0/0 to someone then that person knows how all private keys below m/0/0 are linked to the private key of m/0/0. Consequently, if any private key below m/0/0 leaks to that person, say of m/0/0/42, then that person can compute the private key of m/0/0 and from that the private key of all m/0/0/x.. in the branch of m/0/0 including siblings of m/0/0/42. However, assuming you didn't give away other chaincodes, that person cannot compute the private key of m/0 or m/0/1.

I don't think that type-2 deterministic wallets should be the default in any client, because users have to think and care about what they export from their wallets (chaincodes, extended pubkeys, private keys) and how they secure the exported data. Type-1 deterministic wallets seem to be a more suitable default. If type-2 wallets were default then the average user should not be given the opportunity to export chaincodes. So there should be no "extended pubkeys" ("pub" suggesting that they can be exported) but only "extended privkeys".

As far as key hierarchies go, do we have any significant application for it yet? I would really like to be convinced that we absolutely need them.

I think that there's some confusion here, type-2 should always be more secure than type-1, for any kind of user.

With type-1, the secret seed derives the actual privkeys, therefore if the secret seed is compromised then all of your privkeys leak.

With type-2, if the hash derivation function includes the secret seed as one of the concatenated inputs (as in the OP of this thread), then the secret seed in itself can only derive pubkeys, and unless the attacker also gains access to the additional (master) privkey secret, all your privkeys are still provably secure.

The disadvantage of having the secret seed as one of the concatenated inputs of the derivation function is that the 3rd-party couldn't generate new pubkeys on its own, without knowing the secret seed. But the other advantages of type-2 still hold, namely that the owner of the wallet can generate new pubkeys without accessing (decrypting) his privkeys, and that for backup purposes you only need to store your master privkey and secret seed (this is an advantage over the regular random-independent wallet, not over type-1 wallet).

If BIP 0032 doesn't include an option to have a secret as one of the inputs of the hash derivation function, then I think that this kind of mode should be added to BIP 0032. This could even be the default, if we're worried about scenarios where users aren't careful and compromise a branch in their key hierarchy. We might wish to give users the option to have different secret seeds for particular branches in the key hierarchy, and store all these seeds in the wallet file (and warn the user that he needs to backup his wallet when he creates a new seed).

Agree.


"the secret seed in itself can only derive pubkeys" should be "the secret seed in itself can only derive relations (in the sense of differences) between pubkeys and relations between privkeys".
"unless the attacker also gains access to the additional (master) privkey secret" should be "unless the attacker also gains access to a privkey (master or derived)".


Depends on how you see it. If I want to generate new pubkeys without accessing my privkeys it means that, securitywise, I want to treat my secret seed differently (i.e. less secure) than my privkeys. To me this is the same as having a 3rd party generate them (and having access to my secret seed).


This mode could be a "self-seeded" mode, where the chaincode is not inherited from some parent key but is a hash of the privkey. Then it suffices to backup the privkey alone. And yes, this should probably be the default, and an inherited chaincode should not only be used on explicit request.


Maybe two seeds are enough, one inherited, one self-seed (=hash of privkey).

I listed one in an earlier post. If I'm going to buy Bitcoins on an exchange I'd like to be able to give the exchange an extended public key so that they can automatically generate new withdrawal addresses without further interaction. Similar I'd like the exchange to give me an extended public key so that my HD-aware client can automatically generate the next unique deposit address every time I want to add Bitcoins to my account.

If Wikileaks wants to receive donations without allowing a third party to monitor how much they have received or who the donors are they could use an BIP32 HD wallet. Every visitor who requests a donation address gets an extended public key instead of a regular public key, so now the donor can generate his own unique donation addresses without needing to visit the Wikileaks web page every time.

Clients that understand HD wallets could be configured to store a counter in the address book entry of each extended public key and to by default automatically send to a unique address when that entry is selected by the user.

I feel confused.

For deterministic wallets allowing generation of public keys without private keys, the chain code must be included in the watch-only wallet. Therefore, the chain code have to be kept online. In the following discussion, I assume the chain code(s) are known to the public.

In Armory, if someone knows the private key of sequence number x, he will be able to determine all private keys with sequence number > x, but not for those sequence number <x. This is guaranteed by the EC algorithm.

Here are my questions for BIP32:

Assuming all chain codes are known, if private key m/i/j is known, :

1. are every private keys under m/i/j known? (I think the answer is yes)

2. are every private keys under m/i/j+1 known? (The answer should be yes if it followed the Armory model)

3. are every private keys under m/i/j-1 known? (The answer should be no if it followed the Armory model)

4. are every private keys under m/i known?

5. are every private keys under m/i+1 known?

6. are every private keys under m/i-1 known?

7. is the m known?

Answer is yes to all of them.
(Assuming that all pubkeys are also known, not only chaincodes, so in fact all extended pubkeys are known. I thought this is what you meant to ask.)

Sorry, I mean private keys, not public keys

Another use case for key hierarchies is shopping sites. When I create an account on Bitmit they should assign me an extended public key that my client saves in order to create all future payment addresses. This provides two advantages:

Security: As long as one does not go undetected during the initial account setup, a MITM attack can not redirect payments to the attacker's addresses since my client already knows where to send payments.

Anonymity: To the extent possible I don't want to use outputs from different addresses as inputs in a single transaction. If I need to pay Bitmit 10 BTC but all I have are two 6 BTC outputs on different addresses I can use two transactions to complete the sale by sending 6 BTC to address k and 4 BTC to address k+1. Now it will be more difficult for a third party to examine the blockchain and determine that the same individual controls both addresses.

We only need a key hierarchy as in BIP32 (chaincodes on >=two levels) if we are required to derive 2nd-level chaincodes from 1st-level chaincodes because, for some reason, it is infeasible to derive 2nd-level chaincodes from 1st-level privkeys. To make it clear that we do, let's add this to your example:

• your withdrawals shall all go to savings addresses for which you will not want to access the privkey (1st-level) for a certain time frame (say years)
• within that timeframe you expect to sign up with different exchanges, each of which you want to equip with its own pubkey and chaincode (2nd-level)
  

Now a BIP32 specific question:
Why are the child chaincodes derived from both the parent pubkey and the parent chaincode rather than just from the parent chaincode alone? What about this derivation:
K_n:=H(c_par||n)*K_par
c_n:=H(H(c_par||n))
where H is some cryptographic hash. Looks easier to me and doesn't require 512 bit digests. Am I missing some point?

I would imagine this is the case for any website that needs the ability to generate new 2nd-level codes on the fly, since you wouldn't want to put the private keys on a public-facing server, such as if a public donation page handed out unique extended public keys for improved anonymity.

What do you gain by not using all available data? I consider using one 512-bit hash much more elegant than doing several 256-bit hashes.

If you're not interested in using any of the features of the type-2 derivation, consider the extended public key the same way you'd consider a private key. It is not observable by the network, so if you don't reveal it, it is yours alone. This essentially turns the scheme in a type-1 derivation (you derive extended privkey from extended privkey).

Ok, this is going to be rather vague and it remains to be discussed if you gain anything. But I'll try to make some points.

It's more modular to have a derivation of chaincodes alone. The derivation is basically a "hierarchical" pseudo random number generator. It takes a 256bit seed (the master chaincode) and produces a tree of random 256bit numbers (the derived chaincodes). This may have other uses. Such a hierarchical PRNG can be abstracted from this particular application. Why deal with pairs of a number and a curve point if you can just deal with numbers? We would get three trees of privkeys, pubkeys and random numbers, respectively. The first two trees are obtained by multiplying their root with the third tree, from the top down. I find this easier to comprehend than one tree of privkeys and one tree of pairs.

I think of a pubkey as something that can always be made public. A chaincode you may want to keep secret under certain circumstances. Philosophically, its counter-intuitive to combine them into a pair, if they may get separated upon export anyway.

Not sure if there are applications, but maybe someone wants use the same keypair with more than one chaincode. Then it seems natural to separate them. What about using the same chaincode tree with more than one master keypair? If chaincodes are to be kept secret then pushing the chaincodes to all sub-level entities becomes an issue (=non-trivial work). Suppose the root entity wants to update its keypair. Having them separated there is no need to re-distribute chaincodes. Just publish the new master pubkey and the entities on sub-levels can recursively update their pubkeys (level by level).

SHA256 is already used. Re-using it instead of SHA512 is one less primitive and less code to rely on.

I agree there it's certainly neat to see the chain code derivation as separate, but without clear use case, I think it just complicates matters - both for implementations and for humans who need to learn how it works.

The current proposal has the advantage that keys always (assuming no collisions) come in triples: (privkey, pubkey, chaincode), so you only need a single identifier per key. Separating the chain code means that you need two identifiers, and both can be combined arbitrarily.

I don't really see what you mean by "to combine them into a pair, if they may get separated upon export anyway" - there's just an extended private key and an extended public key. If you never export an extended public key, the whole scheme works as a type-1 derivation. Sure, for actual leaf nodes the extended part isn't used, but as the chain code never gets revealed to the network, this shouldn't harm.

This is a use-case that isn't captured in BIP 0032 and I think should be.

The "main" way we associate addresses with a single identity is when those addresses are used as multiple inputs in a transaction.  We certainly could form separate transactions while using a single input for each but if all those transactions are being sent to the same address at roughly the same time, the assumption could still be made that those addresses were all associated with a single identity.

With BIP 0032, the client could instead generate multiple transactions to unique derived public addresses.  This would go a significant way towards removing this particular information leak.

I understand that anonymity is a concern for quite a few users or transaction types, but that comes at a cost to the system since all solutions that try to avoid recombining inputs imply that coins will be fragmented to exponentially growing key set. That might not be a problem for the individual but is already a significant and growing issue for miner (and transaction validating clients) since lookups for unspent output have to work on an ever (and exponentially) increasing set.

What about bargaining the interest for anonymity of the individual with that of the system by requiring that minimal transaction fee increases with growing imbalance of number of inputs and outputs ? That is: miner would accept transactions that aggregate inputs at lower fee and ask for proportionally higher fee if number of outputs exceeds that of the inputs?


 

hackjealousys use case is indeed one we were considering during the design of the payment protocol (ie, we already thought of this and would like to support it in future, at least in some wallets).

Performance of the core node has improved dramatically lately. I think it's worth using some of that for better privacy. It doesn't mean "never combine addresses" it just means wallets should try and impose an upper bound on the size of coins in its wallet. If I buy a Mars bar with a $100 bill, well, the cashier knows I have some money, but this is hardly a privacy leak worth worrying about. If I were to buy a Mars bar with a $100,000 bill (imagine it exists), that's a very severe privacy leak. So trying to ensure I get paid with outputs that don't exceed 10 BTC or so might make sense, so the size of change outputs can be limited.

With paper currency there isn't a permanent public record of every bill you've ever owned.

The severity of an information leak here has nothing to do with the amounts being spent. Combining outputs makes connections which make it easier to identify spending.

While I understand your concern for privacy, this should be an option and not default, since a cost to the system.
Merchants may actually opt for re-using the same account frequently to have simpler audit.

Is this hypothetical merchant who is reusing a single receiving address doing all his accounting on an abacus?

If you want people to be able to pay using several transactions/outputs to you (a good thing to do, imho), you should give them multiple addresses/outputscripts. The payment protocol that is being developed supports this, and this is the right way to implement that. Whether you generate those addresses from a single BIP32 chain, or randomly generate them all is of no concern.

Well technically the payment protocol just gives outputs and allows users to submit multiple transactions in payment. It doesn't tell the wallet whether it actually should craft multiple transactions. Right now the spec leaves that open. A future extension may make sense whereby you can provide each output with a transaction index, to tell wallets which outputs to assign to which transactions.

It is how the world outside Bitcoin works. Companies use a limited number of accounts to reduce audit effort. This is an other use case, probably not yours, but that does not mean it is wrong.

What is an "account", if not an arbitrary grouping of transactions?

What happens if you call an extended public key (defined in BIP32) as an "account"? The extended public key is a single unique identifier so there's no reason not to consider the root address and all its children to be a single "account". That it can be subdivided into a hierarchy is just an implementation detail.

Yes, an account is just a grouping of transactions. The only grouping currently commonly implemented is by address.

Assuming BIP32 is implemented, then the audit would have to include every address for which public key derivable from the extended public key.

But, how would an auditor tell if he/she has to check transactions only for the n-th key but not check if there are any key n+1 or even key n + m?

I. Pubkey and chaincode serve different purposes and their handling requires different security measures: the pubkey is simply a pubkey and can be publicised, the chaincode protects the anonymity of all derived keys and is (usually) kept secret. I would expect that they often do get separated. Someone may want to post the pubkey on a website or hand it out to other people, but would probably not do that with the chaincode. So he will "export" only the pubkey from his bitcoin client, not the chaincode. Or, conversely, if he decides his watching-only bitcoin client is too vulnerable, he will "delete" the chaincode from the wallet.
That's what I meant with "they may get separated", and questioned whether they should be considered a pair (extended pubkey) in the first place. This is just a remark and, as you say, "without a use case", not yet a reason to change anything. However, the matter becomes more serious if you start out with your key triple and derive a key triple for an agent of yours. Then you have to secure your chaincode from your agent just as well as your privkey (otherwise the agent can recover your privkey from your chaincode as his privkey). So you will keep your extended privkey secure, but you certainly want to erase the chaincode from the extended pubkey that maybe stored in a vulnerable place.

So after all I think it depends on the use case whether the chaincode is stored along with the privkey or with the pubkey. Creating extended pubkeys first and then erasing half of it is not very elegant. Maybe the three things should be separate from the beginning?

II. The point I made about "updating pubkeys along the entire tree" can be backed up by a use case, I think. My use case is a bit biased, because I am thinking of pubkeys not only as payment addresses, but also as identities or pseudonyms. I am also assuming that every node in the key tree represents a separate entity, and that entities do not trust their children. Let's think of the nodes as branches and sub-branches or agents of some company, where each node is establishing it's identity via the pubkey.

So the use case is this: Each entity (=node) wants to be in control of all derived entities, i.e. wants to be able to derive their keypairs, that's why a hierarchical scheme is used. We want anonymity, i.e. derived pubkeys cannot be linked to it's own pubkey, that's why chaincodes are used. When a sub-entity is created we tell the sub-entity its pubkey and chaincode (=extended pubkey). "Telling" in practice means to send it in encrypted form. Each entity will then separate it's chaincode from the pubkey: the pubkey is public because it is the identity and the chaincode is secured. Now suppose the root decides to update its pubkey, or to establish a second pubkey besides the first one. With extended pubkeys we have to redo all the work, i.e. we need an encrypted communication from each entity to each of its children. But with pubkeys and chaincodes in independent trees it is easier: each entity publishes its new pubkey, the children see it and compute their own new pubkey. Note that this "advantage" applies only to the derived pubkeys, the derived privkeys still require the encrypted communication.

I admit this use case is quite abstract. I'm still mentioning it here, maybe someone can make more sense of it?!

 

Part of what I wrote above is nonsense I think, regarding the supposed "disadvantage", because I don't really see a practical use case where some 3rd-party should generate new pubkeys for someone elses wallet. So please disregard that. Also, I didn't understand why you consider what you said to be type-1, but nevermind.

My basic concern was that if somehow one privkey leaks, then the attacker could also steal your other privkeys, unlike the case with the currently used random-independent wallets (unless the attacker doesn't know the secret seed that's used for deriving the deterministic keys). I see that you also added a remark regarding this on December 20 in the wiki (link (https://en.bitcoin.it/wiki/BIP_0032#Security)), and now that I've read and understood BIP32 I see why that remark is true.

I see in BIP32 that the secret seed is indeed used in the derivations, i.e. by using the chaincodes, though perhaps there isn't enough emphasis there that we should regard the chaincodes as secrets. Specifically, BIP32 doesn't explicitly say which data of the wallet should be encrypted, and one straightforward way to handle the above concern is to have two (optional) passwords for the HD wallet, one major password that encrypts all the privkeys, and another minor password that encrypts all the chaincodes. When the user wishes to spend his coins, he has to provide his major password. When the user needs to create new pubkey addresses, he has to provide his minor password (if he opted to have one). It'd be reasonable for users to select a weak minor password that they can type quickly, and also as written in the wiki the client can keep a pool of N look-ahead keys cached, so having the minor password wouldn't be too burdensome. Do you think that allowing two passwords is a good idea?

BTW, I noticed that in BIP32 (unlike in the OP) the derived pseudorandom number multiplies the privkey, instead of being added to the privkey. Is it just to have more efficient calculation than K_par+G*I_L for the pubkey? This method also permutes over the entire space, so it should be just as good?
And why does the serialized format stores the fingerprint of the parent?

Actually there are very good reasons for that to happen.  Two examples:

1) Payment processing.  A processor company could maintain the webpage and infrastructure but generate addresses ad-hoc from your chain-code.  The benefit is that you (as a merchant) don't have to wait. the funds hit your wallet and don't go through the payment processors. I think there is already ones that do this actually.

2) Website.  Your '3rd party' in this case would be your webserver; however it wouldn't hold any public keys so it is really the same thing as #1, you just happen to own both.  Because the webserver can generate keys ad infinitum you don't have to worry about running out or having it get compromised and your private keys out.

3-Bonus) Games & Public Affairs - Lets say bitlotto wanted to make all the payment addresses for the future available, he could publish the public details of the chain for anyone who cared and then you would know what payment address would be XYZ.  This is a fluff example really, but the point is once the tool is there then people will find creative uses for it.

Well then, if there are practical use cases where you should want to give some 3rd-party (that you don't trust) the ability to create new pubkey addresses for your wallet, then it can be done with BIP32 by giving the 3rd-party the relevant chaincode.
However, if that 3rd-party manages to obtain a single privkey of yours, then all your other privkeys will also leak.

So if we can reasonably expect that such use cases will be common in the future, then maybe the BIP32 design gives users too much of an opportunity to shoot themselves in the foot? Instead, if the derivation function would be one-way (like in Armory), then only the branch starting with the chaincode that you gave the 3rd-party could be compromised. Maybe there could be two wallet modes, one less secure mode that derives keys in a reversible way (when the chaincode is known) as in the current BIP32 design, and another more secure mode that derives keys via OWF? Maybe you should be able to use the different modes in different branches of your wallet file?

I would personally very much like to limit the number of variations we need to consider. You are right that there are security risks when a user can obtain a parent extended public key, and a child secret key, but I do not see a way to avoid this, except by dropping the ability to do public derivation. However, when client software does not expose a chain code ever, the whole sceme is effectively type-1, in the sens that it derives private data from private data (and knowing the public key gives you 0 information about the child key); it's a weirdly complicated randomization function, but it still is one.

Now for the encryption case: I envisioned chain codes as not being encrypted, as that prevents the wallet from functioning without decryption whatsoever (as opposed to just decrypting private keys when needing to do a spend). This does mean that if someone who got a child private key from you is able to steal a parent chain code, you are fucked. My only answer to this right now, is that giving someone a private key already implies a degree of trust (you're sharing private keys, so you're sharing the ability to spend the same coins). However, if you trust them enough not to steal your wallet, why not trust them with the keys in the first place.

Regarding using addition instead of multiplication: we switched to multiplication at some point, but I can't remember why - the only thing it adds is removing the ability to compute I_L from a parent and a child pubkey, which doesn't seem to gain you anything.

That appears to be false, see post #56 and this post.


Right, the post above by jl2012 confused me. There seems to be an inherent contradiction between key homomorphism and leakage of the ancestor privkeys, in the sense that if some privkey k_i is compromised (and all the chaincodes and pubkeys of the wallet are public) then we have that I_L=HMAC(c_par, K_par||i) is known, and we can solve I_L * x = k_i (mod n) and obtain the privkey x=k_par

Maybe another signatures scheme (instead of elliptic curves) could allow both key homomorphism and one-way derivation (in the sense that k_i wouldn't reveal k_par), I don't know. But we're not planning to move away from ECC anytime soon, certainly not just for deterministic wallets, so in practice it wouldn't matter. So far the only thing that I can think of is the straightforward option of allowing the user to encrypt the chaincodes (maybe with a "minor" password as I mentioned above) if he wishes to be less exposed to security risks.


I'm still not exactly sure what you mean by "client software does not expose a chain code ever". Suppose for example that the user stores his wallet.dat file on the cloud (e.g. dropbox), if the chaincodes aren't encrypted then they are exposed, no? So the user assumed that he's safe to store the wallet on the cloud because the privkeys are encrypted, but if a single privkey leaks somehow then all his other privkeys also leak, which isn't the case with the regular random-independent wallets.


With the additive variant, don't you get I_L*G from parent and a child pubkeys, rather than I_L itself? I'm still not sure what are the advantages of the multiplicative variant.


Given the (supposedly) practical use cases that ErebusBat mentioned, I urge you to get more peer reviews regarding these security concerns where we might allow users to shoot themselves in the foot more easily, before you deploy BIP 32 in the official client.

An alternative might be to change the scheme so that the main trunk of a deterministic wallet does not have the homomorphism, only further branches from that do.  This would greatly confine the leakage there, and also make it more intuitive: leaking the private key for any "subaccount" (or whatever you want to call it) leaks that subaccount.  This may be a way to get both properties.

But the homomorphism is really important and enables many valuable use-cases. Right now the need to have private keys online to accept payments is actively getting people robbed. The need to have static addresses for donations and reoccurring payments is actively and materially compromising privacy.   The reversible privkey leaks are only applicable to a subset of cases where people would otherwise be robbed completely.

I like this idea. And in fact, with this idea of yours we can still preserve the important property where your initial wallet.dat backup can always restore all your future privkeys, including privkeys that belong to a "non-homomorphic" subaccount that you created after your initial backup: instead of doing HMAC-SHA512(key="Bitcoin seed", msg=S) to derive the master privkey and master chaincode as BIP32 specifies, we can do HMAC-SHA512(key="seed #i", msg=S) to derive master privkey&chaincode for each subaccount #i, and since the random seed S is stored encrypted and SHA2 is a one-way function, this is secure in the sense that leakage in subaccount #i_0 doesn't compromise any subaccount #j for j!=i_0 (the user will need to provide his wallet password when he wishes to create a new subaccount, which is fine).


Yes, I wholeheartedly agree that type-2 derivation is really great and that its benefits vastly outweigh the potential risks.
All that I'm trying to get across is that wherever we can make design decisions that minimize the possibilities of users shooting themselves in the foot, it's a good thing to do it, instead of assuming that the users will be prudent and then telling some user who lost his coins that he had to read the "fine print" on the risks that key homomorphism.

I was looking at bitaddress.org 's brain wallet feature. It takes in a passphrase and generates a private key/public address.

Could the same algorithm be used to create a whole series. If the passphrase as "Bla Bla" could you make the seed to create the next address "Bla Bla1" and then do "Bla Bla2".... to create an infinite series of addresses?

Is there any flaw that anyone sees in using the algorithm in bitaddress to do this (if not I might submit a patch to add this feature).

Does Armory use the same passphrase->seed algorithm that bitaddress does (are they compatible)? Is there a reason?

Also, has anyone figured out a method to take some seed that can just generate public addresses on an exposed merchant server that would have a private seed on a secure machine that could generate the corresponding private keys? Does anyone have any code in any language to do this?

That's exactly what Armory does.  See the Offline wallet tutorial (https://bitcoinarmory.com/using-offline-wallets-in-armory/).  All private keys are on computer that never touches the internet.  Watching-only wallet on online computer only contains public keys.  Both wallets are really the same wallet, generate the exact same semi-infinite sequence of addresses, but anyone getting ahold of the watching-only wallet cannot take the funds.

You may use bits of proof's BIP32 implementation in:

https://github.com/bitsofproof/supernode/blob/master/api/src/main/java/com/bitsofproof/supernode/api/DefaultKeyGenerator.java

that re-generates the exact same key with a given sequence number from extended private or only the extended public key.
It also supports key hierarchies, so you may use key co-ordinates of any dimension.

You see an example use of the public and private key generator in the unit test below:

https://github.com/bitsofproof/supernode/blob/master/api/src/test/java/com/bitsofproof/supernode/api/KeyGeneratorTest.java

Hello all,

I've made some changes to BIP32 to deal with the issue of revealing a master key by exposing both public parent and private child. The change is important (the child key derivation function changes), but it's maximally compatible with the previous version. In short, it means you can now select whether you want "public derivation" (the older, type-2 style) or "secret derivation" (safer, type-1) in each step, and the default wallet structure uses secret derivation for deriving account keys from the master key. This means that a leak of a secret account key (or below) cannot result in revealing the master secret.

As I don't like encumbering the key derivation with information about wallet structures, the derivation type is not hardcoded but can be selected at each stage individually.

Any comments from iddo, or other people?

The additive version would be faster because the "fast exponentiation" algorithm that computes I_L*G can use pre-computed values of x*G for small x. I believe OpenSSL does something like that.

Not saying that speed should be of any concern here, though..

Seeing that some interna of BIP 32 are being re-discussed, I would like to bump this comment of mine from several month ago. Sorry for repeating myself, but I thought that new applications or use cases, and therefore new opinions, might have come up in the meantime. This question/suggestion is about the "public derivation". Instead of
why don't we use
the difference being that ci depends only on cpar and i (as before) but not on Kpar anymore.

[EDIT] Correction. I meant that the entire I does not depend on Kpar:
[/EDIT]

The advantage that I see with having ci independent of Kpar is that it opens up the possibility of updating all extended pubkeys in the tree (by updating the root extended pubkey) without touching the chaincodes.

Consider a hierarchy of servers where each server holds the extended pubkey corresponding to its position in the hierarchy. Note what is required when a server B receives his extended pubkey from the higher level server A. In the communication between A and B the pubkey-part of B's extended pubkey has to be authenticated (if B uses the wrong pubkey, money sent to it will be lost) whereas the chaincode-part has to be encrypted (by default chaincodes are to kept secret). In an update throughout the whole tree we could spare us the encryption part of that communication (if ci was indepent of Kpar) because the chaincodes remain unchanged.

Countering the above cited comment: what do we gain by having ci depend on Kpar?

I really don't like the complexity of maintaining essentially two independent sets of information. It means software has to deal with any combination, and tree nodes need identifiers for both the key and chaincode part.

In addition, keys and chaincodes are cheap - just 32 bytes. I don't really see the benefit of being able to keep one identical while updating the other.

Perhaps there are specific use cases, but you'll have to be more concrete to convince me about that. Right now, I think it just complicates reasoning and implementation.

You don't need to maintain two independent sets of information. With this last post I didn't mean to go as far as I meant to go in my post from december (where I actually did suggest to separate them in two independent sets). In fact all the infrastructure for extended pubkeys can stay as it is. This is just a slight modification to the derivation function (removing the parameter Kpar from some input) and leaves everything else untouched. In particular, the infrastructure handling extended pubkeys is untouched. The "updating" feature doesn't need to be implemented, it's nothing more than a future option for if a use case comes up.


It doesn't complicate implementation because I consider it a trivial change. It doesn't complicate reasoning because the user won't even notice this change. Nothing of what we explain to end users of BIP32 needs to be altered.

My question is: do we lose anything substantial by giving up dependency of ci on Kpar? Securitywise, anonymitywise, etc?

If not then I would vote for leaving that door open.


While probably infrequent, updating won't be an uncommon scenario. The benefit that I pointed out (and the only one I see at the moment) is that we spare us an encryption-requirement when passing around the updates (there is still an authentication-requirement).

I don't mean implementation of the key derivation code - that's a trivial change indeed. I mean wallet maintenance code that deals with importing keys, detecting parent-child relations between imported nodes, backups and recovery, creating new nodes when used ones are found on the network, .... It just seems so much easier to me when key/pubkey/chaincode are part of an immutable whole, identified using just their address.

Maybe I'm overlooking something and should read the code.. but how does modifying an inner function keep you from treating key/pubkey/chaincode as an immutable whole? I agree that they should be treated as such. When you mention import, detection, backup, recovery, etc. do you mean these are just too many places that require modification, or they are each substantially more involved than the derivation code?

None of that code has been written. I just mean that not being able to assume "if the address is the same, key/chaincode/pubkey are the same" complicates things, both for implementations that need to be aware of things like "someone is importing a tree node, we already have the address, but the chaincode was updated, however old children derived from still use the old chaincode... what if one of those old nodes gets used on the network, do we create a new one using the old or using the new chaincode". I'm not sure about you, but it makes it terribly complicated for me to think about even what the correct behaviour would need to be, in many edge cases.

Your use case doesn't convince me to add that complication, both for those who need to implement it, and those who are going to use it.

I suggest to set and serialize maximum i for each extended key. Such serialized string would define the wallet keys without the need of a regular backup until maximum number of keys not exceeded.
It would also facilitate audit since the set of possible descendants of a key would be of a practicable size. Also the bloom filter could be precomputed for SPVs including all possible addresses derivable.

I'm not convinced. Part of the point is to be able to generate more keys on the fly as needed, without all of them being known in advance, or even be known how many there are.

Well, ok, see the problem with updating chaincodes. But luckily I intended to update only pubkeys, not chaincodes, mainly because I don't see a point in updating chaincodes. If you prohibit updating chaincodes then you have the nice side consequence that your bijection between addresses and triples (key/chaincode/pubkey) is maintained.

Think of an update as importing a completely new (key/chaincode/pubkey)=address. The coincidence that there are two such triples with the same chaincode should be irrelevant for the implementation. I don't expect "update" to be implemented in mainline nor even to be mentioned in BIP32. If someone ever wants to implement "updates" it can be done with an external script that makes RPCs to import the new extended pubkey. It seems to me that the problems you describe are the problems of that person who decides to implement updates in the future, not the problems of implementing BIP32 now (without "updates"). 

There are use cases where knowing all possible keys (or addresses) in advance is an advantage. I mentioned two: audit and bloom filter computation. The limit could be optional with default 2^31 as is by the definition.

Very nice, I like your BIP32 modifications with type-1/type-2 derivation according to the highest bit of the index. it could give flexibility with scenarios that ErebusBat mentioned, something like person A giving person B that he trusts the ability to derive a branch (with privkeys) in his wallet, and then person B wishes to give an untrusted person C the ability to derive pubkeys in a sub-branch, so to enhance security he can break the homomophism link by doing type-1 derivation (person B couldn't have done the type-1 derivation if it was only possible at depth=1 of the "subaccounts", because he's not trustworthy enough to have access to that depth, and besides keeping the layout of extending the particular branch instead of starting a new subaccount could be useful for accounting and so on). Probably there would be more interesting use cases than this one, that I haven't thought of.

I suppose that with this updated BIP32, some of the complexity will be transferred to the people who should do GUI design for wallet layouts :)

As discussed, it's important to do the secret type-1 derivation from the master node (depth 0) to the subaccounts (depth 1), since if the master node leaks then the entire wallet leaks. So the derivation from depth 0 to depth 1 should be type-1 by default, and maybe if you wish to be extra safe (about preventing people from shooting themselves in the foot) then you should specify that type-2 derivation from depth 0 to depth 1 isn't allowed according to the BIP32 standard, and enforce that in the Satoshi client. BTW, with the updated BIP32, I guess that there's no need to save the initial entropy S in wallet.dat ?

I'm not sure that I understood your use case, could you please explain the exact scenario more clearly? if you had an ancestor chaincode and pubkey, then you can derive the descendant chaincode and there's no necessity to encrypt and send it to you, and if you don't have any ancestor chaincode then an encrypted chaincode must be sent to you, no?

Maybe we do gain some security by having ci depend on Kpar, because commonly just the hashed address of Kpar is published (until the coins get spent).

Huh? Why would regular backups be needed? The major advantage of deterministic wallets is that backups aren't needed (see here (http://bitcoinstats.com/irc/bitcoin-dev/logs/2013/04/03#l6858480)).

I'm still hoping to hear some explanation on why the multiplicative variant is advantageous.
It seems to me that it makes sense to re-consider this issue before BIP32 is finalized.

Can someone precisely specify the additive variant of the CKD function?  I'm fairly certain I know, but I don't want to end up missing a detail and evaluating something else.

It's described by gmaxwell in the OP of this thread.
As currently in BIP32 you would still have I=HMAC-SHA512(Key=c_par, Data=K_par || i)
And then:
k_i=k_par+I_L
K_i=K_par+G*I_L
c_i=I_R

We actually just had a discussion about this, and I'm in favor of changing this. The proposal would be:

• k_i = k_par + I_L
• K_i = K_par + I_L*G

I've been holding back on changing this, as speed wasn't a priority really. However, it is a lot easier to do the required operations for public derivation in constant time, than for the multiplicative case, which means it's easier to secure against timing attacks (and we are, very intensively, dealing with private material here). Also, it means you only need almost the same primitives as needed for ECDSA in the first place.

It is not less secure, as you still need to solve the ECDLP to find I_L from I_L*G (=the public key, which is exposed). Assuming a weaker version of the scheme, where it's just K_i = K_par + (i*c_par)*G, and assuming there is a transaction with inputs corresponding to i values i1 and i1+1, and a transaction with values i2 and i2+1, an attacker could detect these were created by someone using the same chain code twice. This would not be possible in the multiplicative version, and also not in the real scheme where the 'tweak' I_L is computed using an HMAC.

Anyone objects to changing this?

Thanks for that.   Just for myself, I copied it below, adding sub tags for subscripts, and bolding EC points (but not scalars)

As currently in BIP32 you would still have I=HMAC-SHA512(Key=c_par, Data=K_par || i)
And then:

k_i=k_par+I_L
K_i=K_par+G*I_L
c_i=I_R


Pieter: what's the difference between what you just posted and what iddo posted?

Also, aren't timing attacks supposed to already be "covered" if you are using a vetted implementation?  I'm not opposed to making it easier to implement, but I thought that was part of the reason to use, say, OpenSSL, because they already diligently covered a bunch of these side-channel concerns.

Nothing, timing coincidence.


OpenSSL's ECDSA_sign probably guarantees this (I haven't verified), but as generic EC multiplication isn't required by ECDSA_sign (only by ECDSA_verify), it's not guaranteed to have a constant-time version (and a variant-time one is certainly faster).

Assume you lost your wallet storing the unspent transactions, but you have the root key for the BIP32 generator from a cold store. Theoretically nothing is lost since you can scan the block chain for all outputs that can be spent with descendants of the root key, but practically you are not able to do this if you do not know what sequences were used.

Therefore you either have to backup the sequences used or simpler set a limit to them in beforehand that is a practicable magnitude for a scan.

As Pieter mentioned in the link that I gave you, it should be very practical to scan in mostly all cases of wallet layouts, the branching factor and depth are quite tiny.

Can you specify what information your are assuming your attacker has? Does he know c_par and is just scanning all pubkeys he gets to see for a difference of c_par*G? Or how does his "detection" work?

Can you specify what information your are assuming your attacker has? Does he know c_par and is just scanning all pubkeys he gets to see for a difference of c_par*G? Or how does his "detection" work?
[/quote]

Sure. I assume the attacker can only observe the blockchain. For any transaction with multiple inputs, he subtracts the pubkeys used in any pair of inputs. If he finds two transactions that result in the same difference, they are very likely keys that are generated from the same extended parent (the difference would be (i-i')*c_par*G. Note that he can't find c_par or i or i' itself, just a likelyhood that c_par is the same. Also note that this doesn't work in the real scheme as not i*c_par but HMAC-SHA512(key=c_par, msg=K_par || i) is used, which guarantees no tweak will be reused.

This was just a thought experiment to see how much we'd have to weaken the construction before the add-vs-multiply makes any difference.

How does the corresponding weaker multiplicative scheme look like that you are comparing it with?
If K_i = (i*c_par)*K_par then you get the same phenomenon, right? The difference would be (i-i')*c_par*K_par, which is recognizable if (K_par,c_par) is reused. Seems to me that additive vs multiplicative derivation is not the point. Instead it's about how i and c_par are combined. Using c_par^i instead of i*c_par looks different at first sight.

Why does constant time public derivation give security against timing attacks? Isn't it the case that public derivation doesn't use the privkeys, and therefore cannot leak privkeys? Maybe you meant security against leakage of just the chaincodes? I probably simply misunderstood what you're saying there, so it'd be helpful if you explain where exactly we need protection from timing attacks.

Yes, obviously with a variant that uses K_i=K_par+(i*c_par)*G you could detect c_par*G from the sub-branch with i1,i1+2 compared to the sub-branch with i2,i2+1, and maybe you could do much worse stuff as well. The OP also uses the safe version with hash(seed|i) to derive the next values. You can see that the formal proof in post #62 fails for K_i=K_par+(i*c_par)*G because we wouldn't claim that the r_i that's used for (sk_i,pk_i)=keygen(r_i) is pseudorandom. As you mentioned in post #103, if the attacker learns I_L then it doesn't seem like such a big deal, and as mentioned here the attacker needs to solve ECDLP to learn even just I_L, so the additive variant appears to be provably secure, as far as I can see. But of course it wouldn't hurt to show the finalized BIP32 to some elliptic curves crypto experts and ask for more peer review, before including it in the Satoshi client.

Scenario is this: Server A is holding (K_par,c_par). Server B is being set-up in a different location and is supposed to hold (K_i,c_i). All chaincodes are to be kept secret by the servers holding them, i.e. c_par shall only be known to A (not B) and c_i shall only be known to A and B (no third party). It is irrelevant here who knows K_par and K_i. So B does not derive anything itself. Instead, A does the derivation of (K_i,c_i) and sends the result to B. Of course, the communication of A to B must be authenticated. The point is that on top of that at least c_i must (in the general case) be sent in encrypted form.

I am having problems answering you other questions because I'm not sure what exactly the word "you" refers to.

The assumption there is that if a key with a sequence number is not on the block chain, then higher sequences were not used, right?

I think that would not hold. A shop usually offers unique addresses to receive payment for individual orders. Some orders never get paid, therefore their key will not be present in the block chain, however keys with higher sequence number might be. A reconstruction of the wallet would fail at such a gap.

I don't think storing the maximal branching inside the serialized format is the right way to go. That doesn't mean wallets can't keep such information separately, but the problem is that you'll always hit more cases that aren't covered. Will you have separate limits of public and private derivation? Will you limit the number of levels below a node? The specific branching factors of all of these nodes? What if someone wants to use a non-standard more complex structure? Inherently, how the tree structure is used as a wallet, and how keys are picked in it, depends on implementation anyway.

For example, say you do this, and limit only at the direct level what the largest index of a subnode is. You're giving out addresses to pay to, a unique one for each invoice. Some are never paid, so you end up with gaps. At some point, you reach the maximal index. What now? Will you switch to a new account? Create an extra tree level? Tell the user to create a new backup? All those problems occur are exactly the same for the case where you didn't know the maximum index, but did have a maximal gap. When it gets exceeded, tell the user his gap is now larger and he needs a new backup.

I say this is all implementation specific, and doesn't belong in the serialization.

I was wrong about this, as the problem of key exposure doesn't really exist for public key derivation, where these operations are required. It doesn't hold for chaincodes either, as these aren't tweaked.

This makes me wonder whether it's still worth changing, though the implementation complexity argument still holds.

You're right. Even here, addition doesn't really change anything.

I thought the advantage of this proposal would be to have a wallet that is able to provide

1. a high number of keys to support privacy
2. does not require regular backup, at least to avoid key loss.

If serialization format (that is the ultimate backup) fails to deliver enough information to recreate all keys that might have output in a practical time span, then it fails the second goal.

If you would add a maximum sequence to the serialization of the extended key then backups would only be needed if a new extended child key is created (sub account), or if the maximum is exhausted and need to be increased to retain the same privacy level.

The client could also warn of loss of privacy and re-use already used keys if hitting the maximum sequence of already known keys, until the user increases the maximum and creates a backup.

Right, good point.

I still believe that for the default wallet layout (subaccounts at level 1 and linear path for each subaccount) and for other non-pathological layouts, you could let your computer run for a couple of hours and retrieve all your privkeys, because the depths of the branches (including branches that have keys that were never active on the blockchain) would be quite small.

I'd say that if the user chooses a peculiar wallet layout, then it's up to him to consider whether future backups might be important.

Furthermore, the client software could let you do "public-insensitive" backup that contains just your wallet layout (just the indices i, or the indices i and the pubkeys) which doesn't contain any sensitive info (chaincodes and privkeys), so you could backup just the layout from time to time, if you wish to be extra safe.

I guess a couple of hours will not cut it. Even if you have an UTXO indexed by keys (that is not even the case for the Satoshi client), it is still prohibitive to scan 2^32 possible generated keys. I believe that you either store what much smaller subset was potentially used, or you can not practically reconstruct the set of keys used, which defeats a purpose of the proposal, that is not to have the need of regular backups.

I expect additive and multiplicative derivation to be equivalent in all "theoretical" aspects of security and anonymity. By "theoretical" I mean disregarding timing attacks, complexity, etc.

I've seen people (not only newbies) confuse the discrete log problem with computing n-th roots. The latter problem is easy: from n*K and n you can compute K. This kind of confusion may lead people to wrongly assume that it was impossible to infer K_par from c_i*K_par and c_i, and they would take this as some sort of "anonymity feature" of multiplicative derivation. With additive derivation everybody can see immediately that K_par can be inferred from K_par + c_i*G and c_i.

This would be an argument for additive derivation: it can fool less users, or its properties (and non-properties) are easier to explain.

So in this scenario, why wouldn't you need to send c_i in encrypted form with your proposal?

My purpose for BIP32 was indeed to make using many keys viable, and not needing frequent backup. That means backups must protect you against loss of coins. It doesn't mean it should be trivial to restore from  a backup, or to reduce your wallet to the blockchain.

When recovering from a backup, use some lookahead like 100 or 1000 keys when scanning (depending on the purpose). If a gap larger than the lookahead is used, I'm sure you'll notice transactions/money is missing after some date. Just retry with a larger lookahead and you're fine. Also note that a large lookahead is only necessary for external subaccounts (so not for change addresses, as you don't expect gaps there at all).

Alternatively, an automatic and low-privacy-risky backup with just the maximal indexes can be used as well, as like iddo suggests. I'm not sure that's necessary in practice though.

The reason I don't like putting a maximum index in the serialized form is because that doesn't tell you what to do when you run out of indices.

I don't think that c_par^i would give you pseudorandom keypairs. These thought experiments didn't explicitly specify how to derive c_i from c_par, but it appears that you would be claiming that the sequence ((c_{i-1})^i for consecutive i=1,2,3,... is indistinguishable from random data, which isn't true. If we cannot argue that the sequence is pseudorandom, then we cannot prove that we're secure against related-key attacks. So the bottom line is that we'd have to stick with HMAC-SHA2 anyway...

Where does the 2^32 figure come from? I thought that we're talking about a user who has a backup of the master node, and he just needs to scan his subaccount (depth 1) branches to a reasonable depth (say 10000 or 100000 or 1000000 payment addresses in each subaccount, assuming that the user didn't have more than 1 million customers). Why would such a task take 2^32 time?

The proposal does not require consecutive generation of the keys but defines a 32 bit integer as index.


An answer could be: re-use keys. This reduces privacy, but it does not have to be without prior warning: e.g. the client could warn if 90% of key interval is used that the interval should be increased and wallet backup created to avoid reduced privacy as pool exhausted.

I see that the look ahead scan you describe would also practically work (provided increasing not random indices are used), but like the maximum better because it supports the use case of an audit as the serialized key would provide the set of potentially used keys without heuristics involving the block chain content.

Sure, but I was talking about the default wallet layout, with consecutive indices (1,2,3,...) for each subaccount.
And I believe that other layouts that users might choose to use would be just as easy to scan.

Keys generated within a single sub account might also use any random index.

In the scenario itself you always need to send c_i, and if you send c_i then it has to be encrypted. I am assuming that the scenario above has been completed and, at a later time, A wants to establish a second tree of pubkeys (for a different purpose, or update). First of all, I made a mistake in my proposal. It should be
so neither of IL,ci=IR depends on Kpar. Let's assume multiplicative derivation, i.e. K_i=I_L*K_par.
In the above scenario I forgot to say that B knows "his" I_L, i.e. the I_L for which K_i=I_L*K_par. This implies that B knows K_par (before, I said this was irrelevant - its not). In fact, I assume K_par is allowed to be public. With this proposal, A creates a new K'_par and sends it to B, and B computes K'_i=I_L*K'_par, re-using his I_L. We do not need an encryption simply because c_i is not re-transmitted, only K'_par is. And I argue that K'_par does not need to be encrypted.

The time point a key was created would (if serialized) also greatly aid the reconstruction of the wallet since it would reduce the scan to blocks after that time point.

Maybe this was too fast. If we re-use multipliers with different pubkeys there seems to be a difference. Consider
vs
Assume all these pubkeys appear on the blockchain. By computing all differences of all pairs of pubkeys on the blockchain an attacker who does not know I_L can link the pair (K_i,K'_i) to (K_par,K'_par) in the second scheme because K_i-K'_i=K_par-K'_par, but not in the first scheme where K_i-K'_i=I_L*(K_par-K'_par).

That's just complicating things for yourself, but yes, you can.

grau, I think the part you are missing is that there is a "convention" tied in with BIP 32.  You could do arbitrary things with BIP 32, and use key gaps of 1,000,000 keys, or use arbitrary 32-byte strings for your child indices, or go deeper than three levels.

But a "standard" implementation of BIP 32 will not do that.  BIP 32 specifies a set of tools that let you do all these arbitrarily complex things, but also describes a convention that avoids the problems you are talking about.  Don't skip wallets, don't use arbitrary 32-byte IDs, don't go past level 3.  If you violate any of these things, you won't be compatible with other implementations of BIP 32, and you'll be forced to address all the problems you are bringing up.  

Look at BIP 32 as a flexible, extensible language for addresses tress and also a prescription for using that is generally accepted.  By generally accepted, I mean that if you follow this prescription, you should be able to import your root private key into Armory, Bitcoin-Qt, Electrum, Multibit, etc, and it will work.  

EDIT: But the simplicity and flexibility of the design allows for us to expand into more complicated things, later, or for devs to do their own "proprietary" deviation of this prescription, and not have to come up with a whole new deterministic wallet algorithm (if they don't mind being incompatible with other apps). 

I think the proposal misses to make these conventions explicit, and I tried to point out what problems this imposes. In fact I would want to go further, not calling them conventions but be explicit part of the "standard".

The suggestions I made would put further limits on how the proposal is used for the sake of better scan performance and simpler backup procedures.

This does strike me as heading towards "over-engineering" - I think the simpler it can be kept the better.

Great designs *allow* for extension but don't try and be everything to everyone all at once.

I don't want to specify how wallet software should work.

OK, you do not want to specify but expect that they follow conventions.
I give up arguing for being explicit, and will also follow those conventions just as if they were specified.

Please don't - we really need to work together to get the conventions and specifications at least "singing from the same hymn book".

(maybe "guidelines" to go along with the specifications?)

If you have a reason to deviate, do so. If you don't have a reason to deviate, don't.

I'm just saying that applications and their expectations will differ, and it is unreasonable that they will all behave in the same way to the smallest detail. And that's just fine.

I feel that how different applications deal with backups and recovery is such a detail. Perhaps it makes sense to add a section with recommendations about this, but I can't expect everyone to follow them. An application may just start with a new seed after a time and tell the user to make a new backup. It may keep track of the necessary gap to do a scanning recovery, and warn the user when some maximal configured gap is exceeded. It may rely on a local fast-accessible indexed UTXO to search a huge amount of addresses. It may automatically backup the highest used indexes to dropbox. I don't think we know the best practices here, so I don't see a reason to fix them.

No worries. I am willing to comply with what is written into the proposal. I tried to include more, if not applicable for the spec, then lets add a recommendations section enumerating, that:

1. use consecutive indexes at generation
2. record highest generated index per level
3. do not use more than 3 levels
4. record time point an extend key (level) was created

Any other?

I actually implemented the spec as close as it can get here: (not yet merged to main of bits of proof):

https://github.com/bitsofproof/supernode/blob/lean/api/src/main/java/com/bitsofproof/supernode/api/ExtendedKey.java (https://github.com/bitsofproof/supernode/blob/lean/api/src/main/java/com/bitsofproof/supernode/api/ExtendedKey.java)

And here are the unit test cases

https://github.com/bitsofproof/supernode/blob/lean/api/src/test/resources/ExtendedKey.json (https://github.com/bitsofproof/supernode/blob/lean/api/src/test/resources/ExtendedKey.json)

of serialization both production and test, using two hierarchy levels and indices 0x80000000, 0x80000001, 0, 1

What do you mean by "A creates a new K'_par and sends it to B" ?
Do you mean that A uses c_parpar to compute HMAC-SHA512(c_parpar,i') to get I_L' and I_R' and derive K'_par from I_L' ? If so, B wouldn't have I_L' and I_R', so the encrypted I_R' has to be sent to B ? If I misunderstood then please try to explain it a bit more clearly?
Also, what you're describing isn't exactly a "use case", could you please elaborate on the practical objective that we'd achieve here?

It doesn't matter how K'_par is created by A, whether deterministically or not. The point is that B reuses the same I_L (or I'_L=I_L) to derive K'_i as he did to derive K_i.

This isn't exactly a use case, true. It is just something that is possible if I is independent of K_par. I still have to see an argument why I should depend on K_par. There may well be some arguments but I haven't seen any yet.

If you want a use case: A has (Kpar,cpar) and publishes Kpar. B instantiates itself and contacts A: "I want to be your sales agent". A increments i for the new agent, computes I = HMAC-SHA512(cpar,i), sends I to B (encrypted and authenticated communication). Now B is fully instantiated. B considers I as his random "name" that A has chosen for him. A has a table of number-name pairs (i,I). This table can be fully reconstructed from cpar. B can derive his public key K_i that he will work with by himself, from his "name" I and the public Kpar. Later in time A may come up with a new line of business, which required separate accounting. That's when A creates a new K'par (deterministally or not, as he choses). A publishes K'par. But A doesn't want to create new "names" for his sales agents. The sales agents that choose to participate in the new business line can start right away without further communication with A. They just derive their K'i from K'par and their name I.

Well, one argument why we should depend on K_par is that with the updated BIP32 we allow either type-1
 or type-2 derivation from the current node.
With your proposal we will have a tree of hashchains c_i=hash(c_par,i) where you derive deterministically the keypair (k_i,K_i) from each c_i (BTW I'm not sure why you'd want to split I to I_L and I_R instead of having single 256-bits I that's used both for deriving the current keypair and the next chaincode), so indeed it gives the benefit over the OP because you can share some c_i in the middle of the hashchain with another person.
But if you unlink the chaincodes and from the keys, then you canot disallow type-2 derivation when the input to the CKD is just the pseudorandom hash value c_i, meaning that logically k_i=CKD(k_par,c_i), unless you could tag c_i somehow, or enforce the derivation type via CKD(k_par,c_par,i) as BIP32 does now, but then the property that the chaincodes and keys are unlinked becomes problematic.
In general, if the chaincodes and keys are unlinked then you could prepare an entire wallet layout starting from a master chaincode without any keys, and then for each master privkey that you plug in you would get different keys in the tree. I'm not so sure whether having the ability to do such things is a good idea.


I still don't see how exactly it could be that "A creates a new K'par" and follow the same old hashchain of chaincodes with the new K'par, since if we use (say) the multiplicative variant then there's a correspondence between the keys and chaincodes, so the chaincode that created Kpar doesn't create K'par, and if K'par is created with a different chaincode then the subsequent hashchain would also be different. I think that your proposal is simply missing the relevant details on how wallet structures can be created. If you fully specify what exactly is allowed to be created in wallet.dat, and then show how your practical use case applies, then it'd be easier for us to consider your ideas.

He wants to generate a k_par/K_par indepedently from BIP32 derivation, and "inject" it into an existing key tree, updating the keys that are derived from it, while retaining the chain codes (I think).

I'm not convinced about the use case, and IMHO allowing this overwriting of keys makes things harder to reason about. We're not explicitly depending on chain codes to be unique across keys, as far as I can tell though.

I see, though maybe he wishes to inject the new keypair as a parallel path that would co-exist in the wallet, instead of overwriting the old keypair, meaning that all the previous keys will still be retained. In other words, we can regard this injection as creating a fresh master privkey somewhere in the middle of the tree structure (which implies that we now must backup the wallet), and use the old chaincodes with this fresh master privkey too.

People are already loosing thousands of dollars by just getting their private key compromised do you really want people to be loosing tens of thousands by getting their deterministic wallet compromised? You must consider the nature of humans when introducing such technologies, even Bitcoin itself is perhaps already too chaostic and unpredictable for most people.

thanke, the only reason to unlink the chaincodes from the keys is to avoid the secure communication needed for sending another chaincode in the use case that you described, or do you have other use cases as well? If that's the only reason then it isn't much, as chaincode leakage without privkey leakage gives nothing to the attacker (e.g. you even said in post #76 that if chaincode is given to 3rd-party to generate new pubkeys then you don't regard the chaincode as sensitive data), and we opted to deal with possible leakage of privkeys by allowing type-1 derivation to break the homomorphism link. Anyhow, establishing secure communication to send a new chaincode in your use case isn't such a big deal, unless you demonstrate how to wrap this use case in some system that requires intensive use of re-transmiting encrypted chaincodes, or something else along these lines?

Another issue that's external to BIP32, but related to users shooting themselves in the foot, is how the initial entropy S can be created. Obviously, by default it's very important that S would be created from random bits, but we should consider whether to also allow users to input a string/passphrase and derive the master node from it. That implies that the user could restore his entire HD wallet via a passphrase, and advanced users could choose for example scrypt(passphrase, #iterations) as input for deriving the master node. Maybe this should be an advanced option that's hidden by default (maybe you'd even have to patch and recompile the client for it), otherwise attackers could attempt dictionary attacks and steal coins. However, if the Satoshi client won't allow this option at all then it's likely that sooner or later someone else will create a modified version of the client (similarly to the version without mandatory transaction fees) and call it "HD Brainwallet 2.0" or something, so I think that it's a good idea to consider what's the safest way to include this option in the Satoshi client. Maybe the best way is a hidden option that can be activated via a command-line argument, where the user may input a string of minimum #chars (for example 64 hex chars is the output size of sha256sum), which means that this way different users will choose different hashing algorithms (instead of using a single algorithm that the client would provide), so the attackers' task will be more difficult. Note that using the AES wallet encryption passphrase as the passphrase for deriving the master node should be highly discouraged, because attackers don't need to have access to the wallet.dat file in order to do dictionary attacks on HD wallet passphrases.

@iddo: have a look at https://bitcointalk.org/index.php?topic=102349.0

people are already losing a lot of bitcoins through the misunderstanding of Change addresses, so it's a balance that has to be struck here.  I think a good solution would make it hard for people (even non-computer literate people) to lose any bitcoins by a combination of deterministic keys (to prevent loss due to change address mistakes) and mandatory secure passphrases/better UI to secure wallets.

Will

Yes, exactly. The term "update" was confusing, as I didn't mean to overwrite anything. Instead, new extended keypairs (or keytriples) are to be created at all nodes. This is why details about wallet structures should not matter. As I said in #120, how to import a new extended keypair (that coincidentally shares its chaincode with an existing extended keypair) should be left out of BIP32 and its initial implementation. 

I intended to take a fresh master pubkey only at the root of the tree, but of course you can do this at any node because every node is itself a root. Whether a new backup is required depends on how the fresh master pubkey is created, something I didn't specify.


I don't understand.


Yes, a single I would suffice.


Isn't this just a notational problem in BIP32 where CKD is said to be a function of (kpar,cpar,i) while kpar is not required if the highest bit of i is 0? I'll say more about type-1 derivation in another post..


This is what we should discuss. I argue that its not a bad idea, so we should pave the way for it (not implement it).


In fact, if A publishes his new K'_par on a bulletin board then no direct communication between A and B is required at all. So maybe the advantage is better phrased like this: There is one piece of information (K'_par) required for all children B_i (agents) of A, not an individual piece (c_i,K_i) for each of them. (This is of course after initially each B_i has once received its individual c_i.) You can argue that each B_i could just be told to switch to a new subkey of his, say from K_i/1 to K_i/2, when a new business line requires separate accounting. But K_i/1 and K_i/2 have the same root owner. So this scenario would be for when a new root owner is established. Hollywood-style: mafia boss A gets "replaced" by mafia boss A', all his "agents" start working for A' without ever meeting him. Maybe you were right saying "I'm not so sure whether having the ability to do such things is a good idea."  ;)


It may not be much but we can get it for free.

Nice. If I understand the proposal correctly, a particular seed that the user chooses all by himself would have a low probability to work in this scheme, so the computer will try to generate dictionary-style seeds for the user, and after less than 256 attempts on average a suitable seed will be found, and it'd have the nice checksum and variable-strength properties. BTW, if you're not convinced that scrypt is a good idea here, see casascius' 10 BTC 4 U 2 STEAL (https://bitcointalk.org/index.php?topic=128699.0) thread.

With regard to seeds for HD wallets (and elsewhere), obviously if the computer alone just generates the dictionary-style seeds then it will be a total disaster, because the attackers will also let the computer generate these seeds and thereby steal brainwallets. So the option in the Satoshi client should let the user input his my_very_long_and_secure_passphrase, and then concatenate the dictionary-style attempts to create the resulting checksum/varstrength seed. This means that the user will have to memorize the my_very_long_and_secure_passphrase+dictionary_style_postfix string if he wishes to restore his HD brainwallet from memory. This option will also take care of my previous suggestion to allow 'security through obscurity' by letting advanced users create the seed by running their secret hashing algorithm, for example scrypt(md5(md5(passphrase)), #9876 iterations) or whatever, because they could use their hashed output as the my_very_long_and_secure_passphrase input for this scheme.

I suppose that by default the Satoshi client should just create a new HD wallet (without asking the user anything) from truly random entropy, and then advise the user to encrypt and backup the wallet.dat file. I recommend that the option to create an HD brainwallet should be enabled only via an obscure command-line argument, to minimize the probability of users shooting themselves in the foot.

About the two derivation types: We don't really need two cases of derivation in CKD. We can use the first one (the public one) for both. Whether your derivation is secret or public depends entirely on what you do with cpar. Keep cpar secret (tie it with kpar) and your derivation is secret, make cpar public (tie it with Kpar) and your derivation is public. This matter can be left out of CKD and can be handled by the wallet.

Of course, strictly speaking you don't need chaincodes for secret derivation, they could be derived directly from kpar with something like ki=HMAC(kpar,i).

What about this: At the root node we have to initialize cpar somehow. The current spec says that kpar and cpar at the root node are both initialized simultaneously from the same seed S. Redefine the initialization of cpar to


kpar is still initialized from the seed S, but cpar is now a function of kpar. Then define CKD(Kpar,cpar,i) like this:

(Obviously, k_i = I*kpar.)

Given (k,K,c) and i, the wallet calls CKD(K,c,i) if the highest bit of i is 0, which is the "public" variant because it doesn't require k, and CKD(K,H(k),i) if the highest bit of i is 1, which is the "secret" variant because it requires k. Doesn't this look cleaner than what we have now?
Note that the "secret" variant doesn't use the c from the triple (k,K,c).

In a sense at each node we get to choose whether to use the chaincode that was given to the node from above (call it the "external" chaincode) or the "self-seeded" chaincode. The root node obviously has to be self-seeded and carries no external chaincode. Any conventional keypair can be a root, as any conventional keypair can be self-seeded. An extended keypair is a conventional one plus an external chaincode.
External chaincodes are thought of as being tied to the pubkey and are therefore used for public derivation. Self-seeded chaincodes are derived directly from the private key and are therefore used for secret derivation. Self-seeded chaincodes are not explicitly stored (so they cannot leak), they are recomputed from the private key when needed.

BTW, if the "secret" variant is the default then it should correspond to 0 as the highest bit of i.

[EDIT] After a small change to the above the root extended key (k,K,c) now is consistent with the other nodes. The root looks like it is derived from the base point with I=k, but with an unknown i and with an unknown chaincode associated with the base point.
[/EDIT]

thanke, let's see if I understand correctly the outlining dependencies when we compare BIP32 with your latest proposal:

BIP32 type-2 derivation:

BIP32 type-1 derivation:

Your proposed type-2 derivation:

Your proposed type-1 derivation:

As we discussed in post #75 and #76, I don't like your type-1 derivation here because it doesn't depend on the additional secret chaincode (a.k.a. seed), which means that if one particular privkey leaks while the rightful owner of that privkey derived child keys via type-1, then the attacker will also know the entire sub-tree that's rooted at that particular privkey.
If you change your proposal so that type-1 derivation also depends on c_par, then the type-1 derivation will become similar to BIP32, and we will be left with considering why your type-2 derivation is supposed to be superior to BIP32 in that case.
That's probably not the only issue that should be examined, just the issue that I noticed first.

Nice overview about the dependencies. thanks.

A general question: do we expect that intermediate nodes actually use their privkey, which at the same time is the base for their children's privkey, on the blockchain? Or will only the leafs' privkeys get used on the blockchain?



From you posts (including #75/76) I understand that you want each node to have a privkey and a seed (for child derivation) and they should be independent in the sense that if one leaks then not necessarily the other. For instance, you want that the owner can derive children from the seed without accessing (decrypting) the privkey. Possibly you also want it the other way around, to be able to access the privkey without decrypting the seed. So what you really want is two independent seeds at each node (one of them is the node's own privkey, lets also call also it a "seed" here). This is trivially done with my proposal for type-1. Simply interpret the k's as seeds instead of privkey (they are the same thing, just different "purposes"). A node that owns k takes HMAC(k,0) for his own privkey and HMAC(k,1) for his seed to derive his children from. Then seed and privkey are independent, at least on "their" level (without knowing k). The node can store only k; or the node can erase k after it stored privkey and seed independently according to the node's security model; or the node may never have learned k because the parent node transmitted only privkey and seed but not k.

Think of this as a tree where at each node something (the node's own privkey) branches "off to the side" and the information "branching off" is not required to go deeper down. Of course, it's still a tree. Another picture is that each node spans two levels and actually consists of a subtree a 3-node subtree  /\ where one branch ends (is a leaf) and the other possibly extends down deeper.

What this boils down to is a hierarchical PRNG of seeds. BTW, such a cryptographic structure can nicely unify type-1 and type-2 derivation because they can both directly build on it, according to the above proposals. In type-1 privkeys are actually privkeys, in type-2 privkeys are multipliers to the parents pubkey. This would leave us with only one cryptographic structure to define and reason about.

thanke: the two properties that we were discussing are:

(1) deriving the chaincodes independently of the keys (in order to achieve the minor benefitial property in your use case), so for example you could replace the privkey in the master (root) node and still retain your old wallet layout with all your old chaincodes intact, just with new keys. Do you now agree with me that your proposal doesn't achieve this property when you also support type-1 derivation? Or do you still claim that with your scheme you can replace only the master key and retain the same exact tree structure with all the old chaincodes intact? You continue to tweak your proposal, which is good, but it makes it a little difficult for me to see what exactly your latest proposal achieves, especially in terms of practical use cases. If you agree with me regarding this property, then wouldn't you also agree that BIP32 is better simply because BIP32 uses all the available entropy and you use only some of the available entropy? Isn't it true that your type-1 derivation is essentially the same as the type-1 derivation in BIP32?

(2) whether leakage of one particular privkey (e.g. the attacker received one pubkey and managed to break it and discover the corresponding privkey) implies that the entire sub-tree rooted at this privkey also leaks, or the attacker must also obtain some private seed/chaincode to derive the sub-tree. With BIP32 you'd need the pubkey and chaincode to do type-2 derivations and compute all the pubkeys/chaincodes in the sub-tree, and you'd need the privkey and chaincode to derive the entire sub-tree. What is your claim regarding this property?

Maybe you should start a new page on the wiki and decribe your scheme with full details there?


Yes, the privkeys of intermediate nodes are also used. See for example the picture with default wallet layout in the BIP32 wiki page, where the subaccounts at depth 1 get extended as unbounded linear paths.

Ok, let's go through this step by step. In #112 I proposed the modification to BIP32 that you are discussing here under (1), which consisted of removing the dependence of ci on Kpar, and said:
At that point I was not even aware that type-I derivation was already concretely specified in BIP32. So my first proposal (from #112, not the later "tweaked" versions) should be read as modifying only the public derivation in CKD of BIP32, and leaving the secret derivation. Now how do you mean this question:
Are you asking if I agree with

a) the modification of the public derivation is inconsistent with the secret derivation, so it's not possible to have them both?

or

b) a similar modification achieving a similar property is not possible for the secret derivation?

I guess that (a) is similar to what I'm asking, it's not about post #112, it refers to the issues raised in post #168 in response to post #167.
I was trying to understand your latest proposal better by asking specific well-defined questions, the question was whether your scheme allows replacing just the master privkey and retain the entire wallet tree structure, so that all the old chaincodes remain intact, while supporting both type-1 and type-2 derivations? The answer to this question was "yes" with a scheme that supports only type-2 derivation.

I recommended that you write your full scheme in the wiki, because it's easier to make tweaks there than in forum posts.

The answer is "yes" again, I think. Simply use (IL,IR) := HMAC(cpar,i) as proposed in #167 for both types of derivation and proceed as in BIP 32 (ki = I_L*kpar). It doesn't give any new property for the secret derivation as it does for the public one, but it doesn't break secret derivation either.

Entropy above 256 bit should be irrelevant for deriving keys which are 256 bit. The seed for master node is 256 bit anyway, so even in BIP 32 the entropy of the whole (IL,IR) cannot exceed that.


You mean the one of #180?


If I start a wiki page then it would be about a new scheme written from scratch, not about small modifications to BIP 32. This would take me a while to think through, possibly till after the conference.

Yes, if you remove dependencies then an attacker needs less if something leaks. That's unavoidable. It's not clear though whether it matters or not. We need a rigorous definition of the properties that we use to evaluate/analyze/compare the different specs/proposals. Defining these properties is probably more important right now than new specs, and would be the first thing I put on a new wiki page.

I don't see how the answer is "yes" if the property that we are trying to obtain with type-1 derivation is: assuming that all the chaincodes of the wallet are public, and the privkey k_i leaks, the attacker still cannot find the privkey k_par
This property holds for BIP32 type-1 derivation, but if you suggest here that c_i=hash(c_par,i) and k_i=f(c_i)*k_par then the attacker can solve k_i=f(c_i)*x and discover x=k_par (which he cannot do with BIP32, that's the whole point behind supporting type-1 derivation, see the discussion starting at post #104).
If the answer is "no", then I'm not sure whether your use case still applies.

Correct, but why exactly are we trying to obtain this property with type-1 derivation? In BIP 32 type-1 the chaincode cpar is completely useless without kpar (unlike in type-2) so why would you assume that the chaincode is public? Just keep it together with the privkey. I see now, you probably want both types of derivation to be possible at each node, and the problem is then that we use the same chaincode for both types, so you cannot make it public for type-2 and keep it secret for type-1 at the same time. So you would need to carry two chaincodes, one for each derivation type (one of the chaincodes can replace the privkey as in #180, so it would still be a pair, not a triple). To summarize: yes, the proposal from #167 doesn't work well in "mixed" trees where both types of derivation occur. Wanting that property in mixed trees requires an additional tweak to type-1 derivation.


Without additional tweaks, "injecting" a new master keypair would only work for all-type-2 trees. Not very nice. Strictly speaking my use case "scenario" was all-type-2 though.

Another general question: do we have any use cases for mixed trees? Should we even allow them?

The reason is security, when only type-2 is used we get that leakage of any one privkey somewhere in the wallet tree structure implies that all the other privkeys of the wallet also leak, see posts #105, #106, #122

But if it's a pair then property (2) of post #181 fails.

thanke: regarding your scheme and use case where the chaincodes and keys are unlinked, we should have noticed that if c_i=hash(c_par,i) and K_i=c_i*K_par then anyone could take the pubkeys K_par,K_i and solve x*K_par=K_i to discover the supposedly secret chaincode x=c_i, meaning that all the chaincodes would leak trivially. Though it's not an irreconcilable issue, simply take any OWF hash2 and derive the child key via K_i=hash2(c_i)*K_par, just note that the added complexity of hash2 cannot be avoided.
Obviously BIP32 was also designed to prevent this issue, and when discussing the additive variant with Pieter we considered the closely related issue of whether the leakage of I_L*G could be exploited (the answer appears to be "no" even if I_L itself leaks).

IMHO having type-1 subaccounts in BIP32 is a great feature that enhances the security of average users, but I'm still a little worried about users who will store the wallet file on the cloud (e.g. dropbox) with all the chaincodes exposed. One possible remedy (external to BIP32) is to encourage users to do the right thing by offering a GUI menu option that backups the entire wallet with deniable encryption, and recommend to the user to put only this kind of backup in public places. This can be implemented by creating a designated subaccount at depth 1 for this purpose, e.g. with index 0, and encrypting the secondary wallet with decoy passphrase by having this subaccount as its root node. Another way to select the fake root is by traversing the wallet tree structure via random walk until we reach a subtree that holds less coins than some threshold, but then we might need to somehow tag this subtree's root node in the real wallet, otherwise many more coins could be transferred to this subtree in the future.

This is even nicer than I first realized, because the GUI can let the user choose a minimal desired strength, and it'd work by dismissing all seed attempts that fall below the desired strength. So for example if the user chooses minimal strength of 15 leading 0 bits, then it will defeat attackers who only try to brute-force seeds that have up to 14 leading 0 bits.

Maybe the client should benchmark the CPU (GPU?) speed to derive the maximal cutoff strength and minimal recommended strength, and allow the user to override the minimal/maximal strengths if he wishes to obtain greater security.

I guess that the dictionary shouldn't be hardcoded, so users could plug in different dictionaries instead of the default dictionary, which would give security through obscurity (e.g. dictionaries in different languages).

BTW these self-descriptive strengthened keys should probably also be used with the AES wallet encryption that we have now, not just for HD brainwallets. Though maybe the client should have an hidden option to disable it (i.e. both when encrypting and when decrypting the wallet), to be backward compatible with previously encrypted wallets, and for (advanced? dumb?) users who don't want to memorize the dictionary postfix.

No, solving K_i=x*K_par for x is the discrete log problem.


There may be a different reason why you would want to use a "double-hash". The property of anonymity of children has been discussed: we want that a child cannot be linked to it's parent. In the strongest form: given two parents and a child of each of them, an attacker cannot determine the correspondence any better than guessing.

A property that (seemingly) hasn't been discussed is the provability of the link. You want to be able to prove that a given child belongs to a give parent, without de-anonymizing the other children (the siblings), i.e. without revealing the chaincode. In current BIP 32 this can be done by revealing I_L. As you note, I_L is already a "second hash".

What's your assumption here? That a user stores his full wallet in the cloud, including privkeys, in encrypted form? Is the worry just about deniability?

Oops, you're right, apologies.
And it will still be DLP even if you use the additive variant: K_i=K_par+G*c_i

As Pieter said in post #103, the encrypted wallet.dat should only encrypt the privkeys. We currently advise users to add another layer of symmetric encryption (e.g. with GPG or 7zip) before storing the wallet on the cloud, because of privacy concerns (otherwise your total wallet balance and addresses will be exposed). Still for example after the wallet non-encryption bug was discovered (CVE-2011-4447), IIRC there were claims of stolen coins from wallet.dat files that were stored on dropbox (possibly by dropbox administrators), etc., meaning that users do store wallet.dat files in public places, without the advised extra layer of encryption.

My suggestion is to have deniable encryption in order to incentivize users to be prudent, by offering them a desirable feature which would be built into the client.

I didn't understand. If we agree that f_K(x)=x*K is a one-way function (where K is an elliptic curve point), then why would the extra hash be helpful in this regard?

BIP 32 is doing this just fine, no extra hash required because x is already a hash of the chaincode:
HMAC(cpar,i). This was just a thought experiment. If x was cpar+i for instance then we couldn't prove the link by revealing cpar+i without revealing cpar and de-anonymizing all siblings. If x was cpar+i you could still come up with a zero-knowledge proof that you know x. If anyone knows x with K'=x*K then we can be convinced that K' was derived from K. Again, just thought experiments.

Yes obviously c_par+i is terrible, not only because revealing/leakage of c_i implies leakage of its parent c_par, but also simply because the privkeys wouldn't be pseudorandom, so we could attack such a scheme by knowing just the public signatures (transactions).

But HMAC(cpar,i) isn't BIP32, it's your scheme where the keys and chaincodes are unlinked. With BIP32, even if you discover from K_par,K_i the x that solves K_i=x*K_par you still haven't obtained the chaincode, only I_L. With your scheme, if you discover x then you do obtain the chaincode, but since discovering x is ECDLP, we're still safe.


Right, BIP32 allows us to have this property.
So you're saying that if we wish to get this property with your scheme, we will have to use the extra hash i.e. K_i=hash2(c_i)*K_par, to prove that a child belongs to a parent by revealing hash2(c_i) ?
I'm not sure what the use case would be, and maybe the usefulness is only in terms of efficiency (instead of signing messages with k_par and k_i to prove that you own K_par and K_i) ?

Yes, if we did c_i=HMAC(cpar,i) then it would be advisable to do K_i=H(c_i)*Kpar instead of K_i=c_i*Kpar. "Proving the link" between K_par and K_i is a different thing (and might have a different purpose) than proving ownership of either of the privkeys. It proves that Kpar and K_i have the same owner, not that we are the owner. It's a feature (don't know a use case yet) that you don't need the privkeys for that. As you said, the required information is H(c_i) resp. I_L.

I am not convinced that we need a public derivation after a secret one. You are citing #122 for a use case:


"Giving B the ability to derive a branch [by himself, on the fly] with privkeys" with type-2 is equivalent to handing A's privkey to B. Trusting someone should never go as far as handing over one's own privkey. That's not necessary either. Your case should be handled with type-1, giving B one derived privkey from which he can further derive whatever he wants. Seems to me an all-type-1 scenario, not a mixed one.

After all, I'm not convinced that the two derivation types should be mixed in one tree. It complicates the matter of backup and encryption of chaincodes vs export of privkeys that you brought up in recent posts. Why not separate them:

1.) Do secret derivation from any privkey without a separate chaincode, i.e. with implicit chaincode like in ki=HMAC(H(kpar),i). Then the hierarchy is trivially possible without extended keys, without keeping track of chaincodes, etc. Secret derivation doesn't need to be part of BIP 32, whose focus is _hierarchical_ derivation, because the hierarchical property is trivial here.

2.) Do public derivation as before.

If you still want to mix them, and probably type-2 after type-1 is the only order that you need, then you can still turn a privkey into an extended one by self-seeding it: kpar -> (kpar,cpar=H(kpar)) and starting your type-2 derivation from there.

Any use case that is not covered?

About encryption of chaincodes (in type-2):
Since chaincodes are generally stored unencrypted, can the wallet tag each key that was type-2-derived and forbid export of its privkey?

There can be reasonable scenarios where A and B know each other well, so A would trust B with a subtree that they'd both share. Also, another use case can be when A and B are the same person, i.e. we have only one person A who wishes to consider his full HD wallet as cold storage (savings account), but wishes to have a subtree of that wallet as hot storage (checking account), so he can transact with the hot storage privkeys as they'd be on his online machine. For example, MtGox claims to have 90%-95% of their bitcoins in cold storage. So for this use case, you will derive a child node via type-1 and treat that child as hot storage, meaning that leakage of any privkeys in your "hot storage wallet" won't affect your "cold storage wallet". Additionally, it'd be a nice feature if the client allows you to export a subtree as a new wallet.dat file, so that your hot wallet wouldn't reveal that it's connected to the full cold wallet.


Huh? Isn't that exactly the scenario that's discussed in post #122 ? And I tried to explain in post #122 why it can be useful that we don't confine ourselves to a wallet layout that allows type-1 derivations only from the (depth 0) master node to the (depth 1) subaccounts.

BTW, another reason not to confine the wallet layout is plausible deniability, meaning that when you reveal your decoy subwallet that you created via deniable encryption, it can have the same structure as the full wallet, i.e. the decoy wallet will have type-1 subaccounts of its own.


As mentioned, I don't like this idea because it violates property (2) of post #181, which would mean that if one particular privkey leaks then its entire subtree immediately leaks as well. This would make one aspect of HD wallets significantly less secure than the currently used random-independent wallets.

There is no type-2 derivation needed at all here, is there? Or you mean to divide your hot storage into hot stored privkeys and even hotter watch only wallets?

Do you agree that type-1 after type-2 is meaningless? I understand type-2 after type-1 will occur because type-1 usually happens from depth 0 to depth 1.



That we don't confine? You wrote in #122:



Ok, got that.

There is. The default should always be type-2, since this way the user can have the client generate new receiving addresses (hashed pubkeys) for him, without decrypting his wallet in order to access his privkeys, and that's a safer behavior because users should access their privkeys only when it is absolutely needed. An important special case of receiving addresses is the addresses where the coin change goes to (see the internal keychain of BIP32).
Also, in the scenario of post #122 there's person C who is only allowed to generate pubkeys via type-2 in the subtree, for purposes like the ones described by ErebusBat in post #101


No, I don't. The idea of the "subaccounts" wallet layout is that it would be nice for users to have separate subtrees of unrelated operations. For example, one subaccount for personal finances and one subaccount for business expenditures/revenues. Now suppose that your "personal finances" subaccount becomes highly valuable because you received some large BTC payments there, and therefore you would like to separate this subaccount further, into hot storage and cold storage parts. You can do that via type-1 after type-2, so IMHO it's not meaningless. Of course, you could just start a whole new subaccount at depth 1 for that hot storage subtree that you wanted, but you would miss out on the potential "hierarchical" possibilities which some people could find useful in the way that they like to organize things. Moreover, for doing type-1 derivation at a node somewhere deep in the tree structure you only need to access the privkey of that particular node, rather than the privkey of the master node at depth 0, so this might be more secure (though not necessarily).
Another reason for type-1 after type-2 is the example with persons A,B,C in post #122
And maybe another reason is decoy subwallet for deniable encryption that starts at a node that's deeper than depth 1


Yes, the confined version refers to posts #105 and #106, and the fully unconfined version is what BIP32 allows now. It's true that in post #122 I suggested to confine the current BIP32 a little bit by only allowing type-1 derivations from depth 0 to depth 1, so that (alternative) clients who state that they support BIP32 will have to disallow their users to shoot themselves in the foot. I think that we all agree that the Satoshi client should have type-1 from depth 0 to depth 1 by default, but perhaps we don't agree on whether type-2 from depth 0 to depth 1 should be strictly forbidden or not.

Hey iddo & thanke,

I love how thoroughly you've been discussing this, though I must admit I haven't read the through entire discussion.

I've updated the specification to use addition instead of multiplication, but now I'd like to make the BIP32 specification final soon.

So my questions are:

• Is there a use case to allow updating keys without updating chain codes, that's worth breaking the current spec for?
• Is there a reason to disallow secret derivation after public derivation?

If not, I'd like the current version to be final.

Grau: The thread has progressed quite a bit since your comment, but I agree it makes sense to have a set of "guidelines for wallet behaviour" that will make working with these wallets easier, though in no way required.

Hello Pieter,


The supposed use case is described in post #167,#172,#176 (edit: to be self-contained here, the use case is that A gives B some pubkey and the corresponding chaincode so that B could derive the subsequent pubkeys via type-2, then A creates a new keypair and gives the new pubkey to B, to be used with the same old chaincode, therefore there's no need to send a new chaincode via eavesdropping-resistant communication, but the communication still has to be authenticated otherwise anyone could impersonate A). I personally don't think that this use case resembles something that would arise frequently in practice, but even if thanke or anyone disagrees with my assessment, the following two issues remain: (1) we can support pretty much the same exact use case with BIP32, just with one extra session of secure communication between the two parties, in which a new chaincode is sent, and (2) so far we haven't come up with a way to achieve thanke's goal without losing other properties that are more desirable (except maybe if we bloat the wallet with two separate chaincodes for each key), namely type-1/type-2 mixing and the necessity to know the chaincode in addition to the privkey in order to derive its subtree.

It seems to me that the issues that thanke raised proved to be be a good sanity check that shows that the BIP32 design is good. Maybe thanke could improve on his ideas, but even if he does, the use case seems rather insignificant as far as I can see, and I believe that it's more important to finalize BIP32 as soon as possible.


IMHO absolutely not, because I see practical use cases for doing it (posts #122, #203, #205), and I don't see any reason to disallow it.


Few last things before you finalize BIP32: If I understand correctly, the length extension attack on SHA2 is irrelevant here, because of the HMAC ? It could be an interesting idea to replace SHA2 with SHA3 anyway, depending on who you believe (link (https://bitcointalk.org/index.php?topic=145343.msg1545309#msg1545309)). And regarding the initial seed, I suppose that you could specify that the maximal entropy that makes sense is 512 bits.

Wouldn't it just be simpler to add the base point incrementally? Why not just start out with a private and public key, store the private one securely, then just keep on adding the base point to the public key to get new addresses.

Are you suggesting k_i=k_par+1, K_i=K_par+G ?
Then the keygen isn't pseudorandom (post #62), if one privkey leaks then the entire wallet immediately leaks too, and there's no hierarchical derivation.

Ah. I see. Nevermind what I said.

A few remarks before finalization, taking into account and drawing from the long discussion with iddo:

1. Can we reserve more than one bit of the number i for different kind of derivations, not only the highest bit? This would allow addition other kinds of derivations or tweaks of existing ones in the future.

2. Additive vs multiplicative: I don't know what your status is regarding constant-time implementations. But unless timing attacks discredit the multiplicative variant, I would stay with it because of the issue raised in #155. Note that #155 is a non-issue as long as you can guarantee that no I_L is ever reused. If you can't guarantee that, in particular if you wanted to allow the re-use of chaincodes, then multiplicative would be mandatory.

3. I am having an issue with the type-1 derivation. In current BIP 32 both types of derivation first produce an I_L in their own way and then set k_i := I_L * k_par (or + instead of *). For type-1 I_L depends on k_par. Isn't it cleaner for type-1 if k_i is the direct output of a HMAC? Why the additional multiplication with k_par? This is unnecessarily complicated compared to setting (k_i,c_i) := HMAC(kpar,cpar,i). iddo phrased the desired property for type-1: "assuming that all the chaincodes of the wallet are public, and the privkey k_i leaks, the attacker still cannot find the privkey k_par". It is counter-intuitive to this property that a number I_L with k_i = I_L * k_par is even computed. Besides k_i and k_par, I_L is one more (unnecessary) thing that an implementation has to prevent from being swapped out to disk.

4. A further suggestion for type-1 on top of 3.: (k_i,c_i) := HMAC(S,i) where S := HMAC(kpar,cpar). This achieves that k_i=func(kpar,cpar,i) as before. Plus it has the following properties:
- storing S there is no need to decrypt kpar when deriving children (the new advantage of this)
- children cannot be derived from kpar alone (iddo insisted on this property)
- children cannot be derived from cpar alone (we assume cpar is stored unencrypted)
Storing S is of course optional. The common (default) use would be just to recompute it each time.

5. It is certainly possible to do everything with HMAC-SHA256 alone. For instance, if you need two values like (I_L,I_R) you can do I_L=HMAC(secret,0) and I_L=HMAC(secret,1). The question is, does it reduce dependencies of the code, code review, etc. to be worthwhile? Or does it matter here that SHA256 has by now become the best-tested hash function in the world?     

6. BIP 32 should, for each derivation type, explicitly list all properties that it claims to achieve. So that wallet implementers can rely on these properties instead of digging into the details of the definitions. 

7. I understand that it is not the concern of BIP 32 to specify how clients handle extended pubkeys. However, since this is important for security there should be some guidelines, possibly in a separate document. For example, I am thinking of an "export bit" for extended keys. A type-2 derived extended key would get this bit set for lifetime, and it would prohibit the export of its privkey.


Let me elaborate on this use case. Think of many B's, for example A is a telcom corp and the B's are millions of dealers in every village on the planet. Each B knows its I_L which is considered as B's random name, issued by A, used to identify B. Now if A publishing a (signed) new root pubkey, this is a single, identical piece of information required by all B's. No individual piece of information is required to be exchanged with each B. The scenario is mainly intended for when the new root pubkey is completely unrelated to the old root pubkey, for example if a new owner takes over A. Think of A's root pubkey being published in a certificate of some PKI. Then each B can download it from keyservers. Regardless of encryption, this is a significantly different kind of communication than of each node in the tree getting updated from its parent.

After all, I am still in favor of type-2 in the form of (I_L,I_R) := HMAC(c_par,i), k_i := I_L*k_par, c_i := I_R. The two reasons are: 1) it allows something new without breaking anything old, 2) it simplifies the definition.


I think iddo is right. Secret derivation after public derivation allows a wallet implementation to be absolutely strict about the export bit. Because if the user desires to export the privkey of a type-2 derived extended key, then the wallet would just do a secret derivation and export the privkey of the result of that.

That could indeed be nice, but still it's probably not a big deal if A also creates a new root chaincode and sends it to all the B's, especially if this root replacement would typically be a one-time important event, as opposed to frequent events. Also, if A and the B's knew in advance that they would need to support this kind of secure communication, then they can use something like attribute based encryption (http://en.wikipedia.org/wiki/Attribute_based_encryption), and thereby have a solution which is completely external to BIP32 and achieves the same properties that you seek, and it's also more flexible because it could be used by A and the B's to exchange other kinds of data instead of just the chaincode.

And I'm not so sure that the properties that you seek come without risks: it appears that in the scenario that you described the stakes are raised, in the sense that if an attacker succeeds in forging A's signature for the root pubkey, then the attacker can cause huge damage with just one forged signature.


Doesn't it break type-1 derivations?

Edit: OK, after looking at your (3) and (4) above, I see that you don't break type-1 derivation, you just break the property that'd have the same old chaincodes after replacing the root keypair, because the type-1 derivations will result in new chaincodes.

Edit2: You're hiding the output size of the HMAC there, it should be 512 bits, and if c_i=I_R is 256 bits then you feed less than optimal entropy into the hash function, so the lengths don't work as well as they could. Please write your proposed type-2 HMAC derivation more clearly?

Edit3: I mentioned in post #123 that we possibly do gain more security when the chaincodes also depend on the pubkeys, because usually just the hashed address of a pubkey is publicly known (until the coins get spent). Do you disagree?

I haven't noticed post #155, it's difficult to keep track of all the posts in this long thread:)

Suppose that's I'm a user of BIP32 and I wish to re-use some I_L, how could I do it?
It appears that this concern is with regard to a non-issue, because we cannot reuse I_L with BIP32 ? And even if we could, we'd only lose privacy, not security.
I'm not sure whether the speedup that we obtain with the additive variant is significant. If it is, then I guess that it's better to implement the faster version, especially for heavy users such as online wallet servers, e.g. the MtGox wallet. Maybe it'd also be helpful for smartphones etc.
About side-channel attacks, I don't think that there's any significant difference between I_L*k_par and I_L+k_par ?

Right  ;), so why again was this:


Of course, type-1 would be left at (I_L,I_R) := func(cpar,kpar,i).


True, it's a non-issue with BIP32 as it stands, as long as nobody tries to re-use I_L by some non-spec behaviour.
It seems the decisive argument between additive and multiplicative is protection against timing-attacks, probably Pieter can comment on that. If both can be implemented in constant time I would go with multiplicative.

Apologies, please see my edited post there.


If some hacker tries to re-use I_L because of some peculiar reason, and loses privacy (not security) as a result, I could live with that...
I don't think that there could be any timing attacks if the privkey derivation is just I_L*k_par or I_L+k_par, Pieter already commented on timing attacks in post #140

Yes, it seems better to do k_i=I_L instead of k_i=k_par+I_L (mod n)


On the one hand you say that it's advantageous only if we store S, and on the other hand you recommend to recompute S each time?
Basically if we always store S then it means that when we derive a new privkey then only the child privkey (not the parent privkey) will be in memory? But the user will still need to provide his AES passphrase to encrypt the child privkey, so I don't think that we gain much with this idea?


If you have an actual reason to doubt SHA512 then I think that resorting to SHA256 shouldn't help you sleep better at nights.

This was intentional, it should be trivial to fill in the corrent sizes once everything else is settled.


If Kpar is used as a parent then it will be a rather "static" object, so that Kpar will likely be used for spending during the lifetime of c_i. Plus when you compute a derived key you would need the pubkey and the chaincode at the same time anyway. Besides that, I disagree based on the general picture: pubkey=public, chaincode=anonymity, privkey=funds, which I like and find easy to sell and easy to argue about.

But your concern reveals a weakness in our general concept. That's also why I once asked if intermediate keys are to be used on the blockchain at all. Because re-using pubkeys on the blockchain is generally not encouraged. Intermediate nodes can avoid that by reserving one child key branch (i=0) for themselves and using that instead of their "own" key.


Correct, that's why I wouldn't bother with storing S in the reference implementation. We also don't want to complicate extended keys further, their structure shall remain unchanged, they are just pairs.
Storing S is more of an option for an advanced user, who wants to store S on a different machine than k_par for some reason, and encrypts the k_i with a different key than he encrypts k_par with. As a result of this, parent and child funds are completely separated, whereas before parent funds required a subset (kpar) of the information needed for child funds (kpar and cpar).


True. What about reducing code dependencies? Is that irrelevant?

My only point was that usually hash(pubkey)=public rather than pubkey=public, so if for example the attacker somehow obtained the privkey k_5 and the chaincode c_1 but only knows the corresponding hash(K_1) then with your scheme he can derive c_2,c_3,c_4,c_5 and then derive the entire subtree of k_5, while with BIP32 he couldn't do it unless the coins of K_1 get spent and K_1 is revealed on the blockchain. Similarly with regard to privacy concerns, if the attacker obtained just c_1 then he could derive c_2,c_3,...,c_i until reaching two consecutive pubkeys that were revealed on the blockchain, which he would detect by testing G*f(c_i)+K_i==K_{i+1}, and therefore know the subtree of all future pubkeys from here (as opposed to BIP32 where the attacker only has c_1 and hash(K_1) and therefore cannot do anything because he cannot derive any other chaincodes).

With chaincode=anonymity I think that you meant that "leakage of a chaincode"=="loss of anonymity", not that the chaincodes themselves contribute to anonymity? The purpose of the chaincodes is hierarchical derivations, in particular the ability to delegate/share a subtree with another person, and perhaps greater security when we only need to access the relevant chaincode instead of the master seed. Are there other purposes that I'm missing?


Which concern?
I failed to understand how using only the keys of leaf nodes is related to not re-using keys on the blockchain. The key gets re-used when you receive more than one payment to the same receiving address, how is that related to the hierarchical layout of the wallet?

Yes, I understood your point. My point is that K_1 is so static (valid for the lifetime of the tree rooted at K_1) that it will get revealed on the blockchain rather soon. To avoid your attack the user would have to empty the whole subtree rooted at K_1 before ever using spending from K_1. That is not realistic.


Yes, agree, these are the purposes.



Your concern about a privacy loss if cpar leaks and Kpar has been used for spending.

It is generally discouraged to receive more than one payment to the same address. One reason is anonymity (not only the receiver's, also the payer's anonymity), the other reason is that if you have two outputs to the same address, you're unlikely to spend them both at the same time, so the public key will be revealed before you get to spend the second output. I am saying that this general guideline is not compatible with using intermediate tree nodes for receiving, because an intermediate node is too "static" (it roots a subtree which probably has a significant lifetime). Only leafs are suitable "one-time objects".

If I'm guessing correctly, the reason that BIP32 specifies that for I_L>=n that resulting keypair is invalid is because we would like to have the privkey chosen uniformly at random from the valid range, so if we take I_L modulo n then the smaller privkey values will have a little bit higher probability?

Edit: instead of specifying that k_i is invalid, we could specify for example k_i=SHA256(I_L) in this case (and invoke SHA256 again if k_i is still invalid, and so on), so that we couldn't have forced gaps in the indices of the HD wallet? But if the probability is less than 1/2^127 then specifying that i is invalid is also fine.

I still agree with thanke that for type-1 derivation it makes slightly more sense to have k_i=I_L and specify that k_i is invalid if I_L=0 or I_L>=n, rather than to have k_i=k_par+I_L (mod n) and specify that k_i is invalid if I_L>=n. Note that the OP of this thread also specifies for type-1 that "Privatekey(type,n) is then simply set to H(n|S|type)". With k_i=I_L we could still treat d=k_i-k_par as the difference, so d*G+K_par is the corresponding pubkey, in case this d in needed for compatibility with type-2 in some possible context.

Since n =  2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1 the case I_L >= n occurs in one out of 2^224 times...

I think that that's the order of the field F_p, not n=order(G)

True, the order of G is 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
so roughly one out of 2^128 times

I don't really see the problem here. The default HD wallet layout that probably most users will have is just one or more subaccounts where the subaccount is an unbounded linear path, meaning that it'd be similar to the current random-independent wallet in the sense that the user would just keep generating new receiving addresses as needed, except that your initial backup of the root node is enough to restore all the subsequent privkeys, and greater security / less hassle because there's no need to access the encrypted privkeys in order to generate new receiving addresses (plus the other possible benefits like type-2 pubkey delegation and brainwallet passphrase).

One tiny correction: k_i=n is valid according to https://en.bitcoin.it/wiki/Private_key, so if type-1 is k_i=I_L then k_i is invalid when I_L=0 or I_L>n
Alternatively, type-1 could be k_i=1+I_L, and it'd be invalid when k_i>n
Or maybe we should stick with the current k_i=k_par+I_L (mod n), any of these 3 possibilities would be OK.

The reason for specifying that I_L >= n isn't allowed is indeed to guarantee uniformity. However, as this has such a ridiculously small chance to ever occur, I don't want whatever rule is used to deal with it to be complex to implement.

Also, the reason for using the same construction (k_i = k_par + I_L) for type-1, is to 1) make the code to implement it more uniform 2) not give a performance advantage to type-1. I agree that strictly from a security point of view k_i = I_L is just as good.

OK, great, please let me just mention that IMHO you should finalize BIP32 as it is now. In the time period from when BIP32 is final until it's ready to be rolled out in the Satoshi client, maybe we should solicit more peer review by other crypto specialists, just to be extra safe before this major change.

Regarding thanke's alternative scheme, I'd say that it could have some drawbacks (possibly less security/privacy, using less than optimal entropy), and its use case isn't too convincing (and doesn't support type-1 derivations that already existed in the subtree, so we'd need to be careful not to cause mix-ups).

There are still pending issues that are external to BIP32 itself, and as you mentioned it'd be good to have recommended guidelines.
I'll summarize here several external issues that seemed important to me:
1) exporting some intermediate node as the root node of a new HD wallet. One use case for this is the hot storage / cold storage issue, where we use type-1 at some relevant place of the tree structure to derive a new keypair whose subtree would be considered hot storage, and exporting this new keypair as a root of a secondary HD wallet file so that its AES passphrase will decrypt only the hot storage privkeys. In this scenario it could be nice that the secure cold storage wallet also gives access to the hot storage part.
2) incentivize users to keep their chaincodes private, I recommended to have a deniable encryption feature in this context.
3) HD brainwallet passphrase derivation via self-descriptive strengthened keying. BTW if you agree that scrypt makes sense for password derivation, this also implies that you wouldn't need to mess with OpenCL code in the Satoshi client (because we'd minimize the GPU advantage anyway). I asked Colin Percival about his recommended scrypt parameters for password derivation and he said r=8, p=1: http://bitbin.it/E68HeKkM

I found an argument why the multiplier I_L in K_i := I_L *Kpar (or k_i := I_L*G + Kpar) should depend on Kpar.

Recall: In BIP 32 we have (IL,IR) = func(cpar,Kpar,i) whereas I previously had suggested (IL,IR) = func(cpar,i).

The argument is about the provability of the link between Kpar and K_i. There are three things that one might want to prove:
1. Kpar and Ki have the same owner
2. Ki was derived from Kpar (and not some other parent)
3. Kpar existed before Ki

Revealing I_L clearly proves 1. So let's discuss the other two properties.
Case IL=func(cpar,i): Given Ki we can choose arbitrary cpar and i, compute I_L:=func(cpar,i), compute Kpar with Ki=I_L*Kpar. So we can trivially come up with infinitely many plausible parents Kpar.
Case IL=func(cpar,Kpar,i): The above is not possible anymore, at least if Kpar is properly hashed in func. If we know Kpar we can check that it is a parent, otherwise we cannot come up with any plausible parent at all. So we can prove 2. and 3. after all.

For this to be useful, as we might not want to reveal cpar, we would define:
I_L := func(func(cpar,i),Kpar)
and reveal func(cpar,i) as proof of the link. So I actually suggest (for type-2):

However, this is not yet an argument why c_i should be func(cpar,Kpar,i) instead of func(cpar,i).

About type-2.

Here is a strong argument that re-using chaincodes across different pubkeys makes sense. The argument is multisigs. We can have a multisig address as "parent", which contains several pubkeys, and still a unique chaincode for it, ie. one chaincode for all the pubkeys that appear in the multisig. If I understand Pieter correctly, his concern was to keep the wallet organized around addresses, which serve as the key to a table in which we store the values "pubkey", "privkey", "chaincode" associated to the address. "Extended" multisig addresses can be totally consistent with that: several pubkeys are stored under a multisig address, still only one chaincode. To get a derived multisig address, CKD is applied to each pubkey, each time with the same chaincode.

If you consider hierarchies of multisig addresses this turns into an argument why c_i should not depend on Kpar. Because if the parent is a multisig address, which of the pubkeys should c_i depend on? I say let c_i not depend on any of them. Then you can split your pubkeys across several machines and still derive arbitrary many levels on each machine, even if not all pubkeys of the multisig address are present on the machine. It all seems to fit very natural with how addresses are currently stored and handled.

Summarizing this and my previous post, the suggestion for type-2 (additive version) is:

I imagined constructing multisig addresses of a set of (potentially completely independent) BIP32 chains, using equal indices in each, in lockstep.

In my opinion, BIP32 is mostly about generating sequences of keys, which can either be used directly as pay-to-pubkeyhash addresses, or combined using multisig into a P2SH address. Isn't that both more simple than trying to put BIP32 on top of multisig, and no reason for having the chaincodes be independent?

I thought to derive like this from a multisig given by a CScriptID called id:
- get the basescript with GetCScript(id)
- extract the pubkeys with Solver()
- get the chaincode by calling a new function GetCChaincode(id)
- call CKD() for each pubkey
- put together with SetMultisig()
- store with AddCScript()

As you describe it, you would have to keep track of several chaincodes or run another lookup at the third line. What if some of the individual pubkeys are simply not present in pwalletMain? Maybe they aren't on some of your machines. Just seems like more to take track of this way.

Of course, combining pubkeys from arbitrary chains into a multisig is somewhat more flexible. But deriving from multisig scripts may be more straight forward than we thought. Individual pubkeys and multisig scripts are nicely unified as a "destination" after all. Why shall BIP 323 break that up again?

Where does the CScript from if you don't know the other keys in the first place? P2SH transactions do not contain the actual (public) keys anyway, so whatever you do, you need some metadata about the P2SH script in your wallet. I don't see the problem with extending this with the individual BIP32 public parent keys (if you need to be able to access the entire chain of multisig addresses in the first place).

I don't understand, if some pubkeys aren't present, then what exactly do you claim that you could do now, which you couldn't do if c_i depends on K_par ? If there's a single chaincodes tree, you still cannot derive a new child pubkey if its parent pubkey isn't present. Sync'ing the multisig keys just according to the derivation indices makes more sense as far as I can see.
This appears to be once again an argument for gaining efficiency in exchange for potential loss of security, and in the context of multisig the security concerns are more pronounced, because the whole point of having separate keys on different machines that control an address once they are combined is that the data that's stored on a single machine isn't enough to steal the coins, and now you're proposing that the chaincode data will be shared across the separate machines, just for (dubious?) gains in efficiency?
Even if it's a good idea, you haven't shown how to support a single chaincode tree when type-1 derivations are allowed.

I mean you do have the other keys, of course, inside the CScript. But that doesn't necessarily mean that the other keys are present as entries of their own in the key database. HasKey() will still return false for the ids of the individual pubkeys of the script, unless you imported them individually.

My impression was you wanted to stay as close as possible with current key/address handling and in particular wanted a map addr -> chaincode. The easiest multisig generalization (in terms of handling) would be one chaincode per multisig address. Matter of taste I guess.

Individual chaincodes per pubkey in a multisig can do potentially more, like combining different pubkeys from unrelated chains into a multisig. But that's far beyond scope of BIP 32 I assume. With one chaincode per address there is no handling issues and you can trivially implement derivation from a multisig address with very few additional lines of code.

Btw, it is my intention with Armory to do exactly what you just said is out of scope.  There's no reason to optimize the case of multiple wallets coming from the same seed, because most of the time you don't ever want a single device seeing all the keys.  You want your phone to create one key, your computer to create another key, completely independently.  In the case of a big organization, you want different branches to create their wallets independently, and swap pubkey-chaincode pairs.  They need to do that to guarantee that no one employee ever has access to all the pieces.  And that all the pieces are never geographically co-located. 

Plus, if there's, say, a vulnerability in one of the devices' RNG, you'd prefer that it only affect one piece of the multisig wallet. 

There's a lot of possibilities there.  While there may some use cases where keys are generated on the same device, that's far from guaranteed.  In fact, I think it's the opposite, if we want to promote security best practices.

Exactly: swap chaincodes. If they swap their chaincodes anyway they could just as well use the exact same one. (It doesn't make a difference securitywise if they do.)


That's an argument, indeed. Plus, a party may not want to rely on another party's entropy but prefer to use it's own.


Yes, lot's of different ways. I'm just saying prepare for the fact that chaincodes will get re-used across different pubkeys. Whether it's for multisigs or some other purpose. Even if it's not the default behaviour for multisigs and even if you don't promote it in any other way, people might still find applications for it and do it. Chaincodes are only semi-secret after all.

I still haven't seen a compelling argument for being able to change chaincode independently of keys. As far as I'm concerned, they constitute an somewhat-less-secret overflow entropy buffer for keys, and are thus intimately linked with them.

Yes, I understand there are use cases, but they seem far-fetched and either assume it is hard to set up a secure communication channel between trusted parties (which I think in practice is easy), or integrating them more tightly into multisig schemes (which I don't like; scripts/addresses are a layer strictly above key derivation, imho; in that sense I also dislike using the term "address" for identifying keys - it should only be called address when you're talking about the script template associated with a particular key, with the intention of receiving coins on it).

Maybe at some point there will be a use case important enough, and we can still standardize a system for "updating" a BIP32 chain with a new chaincode, though I don't like the complexity of reasoning about the security of that.

Unless someone comes up with a use case that it worth supporting (and hopefully doesn't require pretty much rewriting it from scratch...), I'm going to announce the current specification as final on the conference next week.

BTW, there has not been a compelling argument for making I_L in type-2 depend on Kpar either. IMO this just closes a door, is completely unnecessary, and even complicates reasoning about the security of the whole scheme. But ok, let it be as it is and close that discussion now, as time pressurizes before the conference.

Pieter, can you please address these three points:
  


All this might get implemented on smardcards one day. I really don't understand why you'd want to rely on a new, second hash function here, SHA512. Entropy is _not_ a reason.

And third, can you change in the public derivation to ? I see the provability of the link as a quite an important property (cf. #228).

BTW, the function I will propose for payer-derived payment addresses (which is basically just a deterministic wallet of the payee in the hands of the payer) will be where m is the (hash of the) invoice or contract that is being paid for.
This would fit nicely together, as it would be the exact same function just with m substituted for HMAC(cpar,i). We could re-use code as well as security reasoning.

I offered you some arguments with regard to reduced security and privacy in post #218, and Pieter and I mentioned that you'd feed less than optimal entropy into the hash function (e.g. you'd repeatedly feed 256 pseudorandom bits to derive the next 512 pseudorandom bits, instead of 512-->512 as in BIP32). One reason why you might not find the entropy argument compelling is that you don't spell out your exact proposal on how to do type-2 and type-1 derivations. I'm not sure if you think that the chaincode should depend on the parent privkey with type-1 derivation.

What would be some possible use cases for your (2) and (3) here?
You can prove that you know c_par such that both (I_L,I_R)=hash(c_par, K_par, i) and K_i=I_L*K_par, without revealing c_par itself, via zero-knowledge computational integrity (PCP) proofs. There will be a talk about it by my PhD supervisor in the upcoming Bitcoin conference (unfortunately I cannot attend the conference).
So we could achieve your goals with (significantly) more complexity which would be used only when needed, instead of pushing this hash(hash()) extra complexity on everyone.

Really, you can zero-knowledge prove that you know a preimage of a hash?

Yes, you don't send the entire proof (this wouldn't be ZK and the proof is long anyway), you just let the verifier query a few bits from the proof, and if you didn't know the preimage then the verifier will catch you w.h.p.

Edit: actually you can send a very short full proof by building a Merkle tree from blocks of the long PCP proof and using the Merkle root as seed for pseudorandom queries, see SNARKs for more info.

How does it depend on the choice of hash function?
I guess this is something purely theoretical, right?

Adding more flag bits is certainly possible, but we can extend the length of the serialized i value in that case, so the only thing that needs to change is the serialization format.


I like the simplicity of a single existing construct that operates natively on 512 bits. Yes, separate SHA256 calls would work too, but are less elegant IMHO. I don't mean to say it would be less secure, and this is just bike shedding.

If smartcards have a problem with SHA512, they'll have a huge problem with ECDSA.


That provability argument is interesting, but can you come up with use cases? I'm also interested in knowing the complexity of iddo's zero-knowledge proofs that could avoid this.

It's not related to hash functions, it's a generic proof of computation.
Not purely theoretical, there's a compiler in relatively early stages that's already working. For computation of a specific hash function, major optimizations could be done.
But let's not hijack this thread with unrelated matters, please PM me if you'd like.

Do you mean to change the serialization format even for the two derivations that we have now? Like add another byte?


Ok.


iddo and you asked about use cases. Say a company has two departments A and B that have publicly known pubkeys P (for A) and Q (for B). They receive incoming payments on derived keys P_i and Q_i. At the end of the fiscal year the company wants to prove their balance sheet to an auditor. They want to prove to the auditor that A had this amount of income, and B that amount of income. I am assuming they don't want to give the chaincodes to the auditor. So for each i they tell the auditor the multipliers I_L such that P_i=I_L*G+P, and also the multipliers such that Q_i=I_L*G+Q. Right? No! The company can set up P and Q from the beginning so that they can decide at the end of the fiscal year to which department they like to associate each individual incoming payment. Dividing the incomes however they like between A and B, as long as they don't exceed the total sum of course. If we have P_i=HMAC(I_L,P)*G+P they can't do that.

The "setup" works like this: The company picks P and r and sets Q:=P+r*G. Say P_i = I_L*G+P. If they want to associate P_i to P they give the auditor I_L, if they want to associate P_i to Q they give the auditor I_L-r instead (never both, of course, because then they blow up).

Did you mean P_i=HMAC(HMAC(secret),P)*G+P and reveal HMAC(secret) for the linkage proof, as you suggested in post #228 ?
So the company wouldn't be able to workaround the issue with Q:=P+r*G because they couldn't compute an x such that P_i==HMAC(x,Q)*G+Q ?

Yes, that's exactly what I meant. You can either use the I_L as it was before, from I:=HMAC(chaincode,P||i), and plug that into P_i:=HMAC(I_L,P)*G+P,
or redefine I_L := HMAC(HMAC(chaincode,i),P) and do P_i:=I_L*G + P, as you like.

Peter and Timo, it was great getting to meet both of you at the conference!

Now Peter, where are those test vectors!? ;D

Have a look :)

Excellent, thank you! (https://en.bitcoin.it/wiki/BIP_0032_TestVectors)

Peter, can BIP32 be changed to a status of Final on the wiki (https://en.bitcoin.it/wiki/BIP_0032) now?

I've made it 'Accepted' by now, as per BIP 01, 'Final' requires a reference implementation...

Great, thanks! It's not showing up for me yet, but that may just be how the wiki works.

What makes an implementation a reference implementation?

I have an implementation here, that passes the test vectors and other tests:
https://github.com/bitsofproof/supernode/blob/1.1/api/src/main/java/com/bitsofproof/supernode/api/ExtendedKey.java
Here is the code running the tests:
https://github.com/bitsofproof/supernode/blob/1.1/api/src/test/java/com/bitsofproof/supernode/api/ExtendedKeyTest.java
Here are the test vectors in JSON format for the above test:
https://github.com/bitsofproof/supernode/blob/1.1/api/src/test/resources/BIP32.json

I think it means that it needs to be an implementation in the official bitcoin client.
Otherwise all the BIP ceremony would not make any sense, since there had been different unofficial deterministic wallet implementations, and pretty 'Active' ones, for like years already.

It's actually quite funny because this topic is already over 2 years old, and let's be serious; implementing a deterministic wallet seems more like a 2 month job. Maybe even 2 days... It's actually easier than the current wallet.
Unless you work for a bank - then of course, you need a flowchart, even for going to a bathroom :)
It is sort of a bank though, at the current stage. It should be split into independent components, so bugs in one part would not affect the core (meaning: the blockchain protocol) - then it would be faster to improve things.

I understand the importance of the "reference implementation" for things related to consensus on the ledger.

This however is the wallet where we expect to see different implementations. The purpose of the standard here is to enable interoperability across implementations. I think the JSON file I provided is a reusable piece of data for any other implementation's unit test and the algorithm I wrote helps to clarify what is evtl. not obvious in writing. Let me know if more is needed to have "a" reference.

I should probably read a bit more before asking what is the "interoperability across implementations", in this case :)

Means being able to transfer keys and key hierarchies from one wallet to an other even if they use different implementations.

Now I understand.
So you are saying that it should be 'Final' already.
OK - I'm with you, assuming that it works, though please don't ask me to test it. ;)

You do not need to test mine, but feel free to refer to it.
I suggest you to use the JSON parseable test vectors in https://github.com/bitsofproof/supernode/blob/1.1/api/src/test/resources/BIP32.json for your unit test.

I personally don't see a reason to swap wallet format between different wallets.
And even if there was, I'm sure someone can build a converter.
So I personally don't really care about a compatibility of my wallet with other wallets - especially that I keep my wallet it simple

Not wallet formats. Key export and import.

OK, then sorry.
I should had read more :)

May I ask, do you really need such a hi tech for a business?
It seems like 100x more sophisticated than MtGox

I think to clarify, in the case of HD wallets, it's less about the individual keys and more about ensuring that all clients, given a seed, will derive the same keys from that seed.

BIP 32 defines a serialization for extended keys. I meant to exchange those extended keys. This is what the unit tests I mentioned test.
A serialized extended key determines all keys derivable from it, and carries its place in the key hierarchy.

BIP32 also defines the algorithm to derive extended keys from a seed. This is also implemented in BOP in the class I quoted.

Ah, ok. Thank you for the clarification.

so have deterministic wallets been implemented in the reference client?

just wondering how often I have to update my backups ...

Before I start a new topic, I thought I'd ask here first. I'm really excited about the possibility of deterministic wallets. Bear with me here. I understand about 65% of how this works.

As far as I understand BIP 32, it will be possible to derive additional public keys from someones extended public key, right?

So if someone gives me an extended public key, I can generate public keys to addresses that the other person can unlock (by generating the appropriate private key on their side). Is this correct?

What I want to know. Let's say person B has given their extended public key to person A. Person A can now generate additional public keys to send BTC to. If person has not already generated the corresponding private keys, do they still 'receive' the value in their wallet? ie, how does person B's wallet know that the extra public keys that was generated by A, is theirs? Does it check new addresses coming into the blockchain and determines whether they can generate the correct private keys to unlock them?

Am I being clear here?

To put it another way. Can I pay to a person's deterministically generated public addresses without them having had to pre-generate themselves? Is this possible?

Current deterministic clients pre-generate a number of private keys in the chain. If you don't have the private (or public) keys generated though, you won't recognize a transaction ad being your own.

You will recognize your own transactions if you use consecutive numbers of keys (with limited gaps if any) and you have a server that supports scanning with a master key.
I happen to have such a server.

Not quite.
You need to give him your public key and the secret.
From these two, one can "guess" further private keys. (EDIT: public)

But you should also know that this might be dangerous for your privacy.
It you make your "public key + the secret", anywhere, anyone can find out that all the further addresses determined from it belong to you.

This isn't a problem because you can create an arbitrary number of extended public keys, up to and including a new one for every transaction.

Yes, that's correct.

If he has an extended private key, and gives you the corresponding extended public key, you will be able to derive all public keys (and thus addresses) that correspond to the private keys generated from his extended private key.

so that is why the secret (being part of the extended public key) is basically reveling all your further desposit addresses, for a given branch (customer).

unless you can keep it secret.
but assuming that the first reason for anyone would be to use it for non secured environments, keeping it secret seems kind of a problem

So like I said, if you pregenerate the private (or public) keys in your chain. Unless you're saying that there is a way to identify the child keys of a extended private key without pregenerating them, but it doesn't sound like it.


An extended public key is the public key + secret/chain code. From this you can determine the following public keys in the sequence, not private keys.


Yes, that is the point of giving someone an extended public key, so that they can generate addresses that you own without having any of your private material.

The bolded part is incorrect. It might be a typo. You can never derive private keys from public keys. If you could do that it would shake the very foundation of bitcoin and public key cryptography.

piotr_n must have meant public key.

I have only used electrum so I will explain what I understand of their implementation. In electrum you configure a "gap limit" which is 5 by default. It basically means how many empty addresses, counting from the used address with the highest "index", should electrum scan for coins. So that is how it determines if you've received coins to one of the addresses derived from your seed.

If you expect a lot of transactions you can set the gap limit to a high number like 100 or something.

I see. I understand now! Thanks.

@chrisrico:

That's what I thought. Thanks! You have to pre-generate your keys in order for your wallet to know from the blockchain that those public keys are yours.

@Abdussamad:

Regarding Electrum's gap limit: Does it keep that gap at 5? So it keeps watching the blockchain for the 5 next set of public keys that belong to you? If someone deterministically generated a public key of yours, you get the BTC. If then, does it generate a new key to keep the gap at 5?

So. If deterministic wallets just keep up to date (keeping a limit ahead), people using an extended public key of yours can generate as many public keys as they want (considering you keep the limit at a reasonable level) and you will receive the funds in your wallet if they pay out to those addresses? And considering your wallet is generating the correct addresses from the extended public key that you shared to another person?

You can adjust the gap in the settings. The default is 5. Yes to all the other questions.


Yep. Cool isn't it :) The best part is that no one can spend your coins if they get access to the master public key. All they can do is predict the future set of generated addresses. This is not a problem if you use a dedicated wallet for each purpose. You can easily create a new wallet using the -w command line switch when starting up electrum:

electrum -w /path/to/mynewwallet.dat

There are quite a few projects out there that take advantage of this. There is an ecommerce plugin for woocommerce:

http://wordpress.org/plugins/bitcoin-payments-for-woocommerce/

Then this concise PHP script by @stick:

https://github.com/prusnak/addrgen

Very very cool! As Bitcoin for Woocommerce shows, it removes third-parties from transactions. Thanks for the links. Amped!

To be fair you still need a way to verify transactions. Bitcoin for woocommerce uses blockexplorer.com with fall back to blockchain.info.

There is a way to get both master public key based address generation and transaction confirmation without relying on third parties. There is an example script called merchant.py in the electrum repository that shows you how to do this:

https://github.com/spesmilo/electrum/blob/master/scripts/merchant.readme

It runs as a daemon and you can configure it to callback your script each time a transaction hits one of your addresses.

But I don't know python so I haven't succeeded in getting it to work.

Yeah, sorry guys - I indeed meant public keys.
Thanks for correcting

This topic is 15 pages long, so please forgive me it it was discussed already.

Having in mind the recent same K-value problems in the signatures, I have been thinking about a deterministic wallet solution where exposing one private key does not expose all the others, that come after it.

So in my solution (which I call type-3), I do something like this:
Where SHA256 is actually the double sha256 and my wallet is a brain wallet (based on the seed_password).

Could you please give me any feedback on whether you see any security risks with such an approach?

What do you mean by || ?  If that is the OR operator, then you are going to set the least significant byte to all 1's, since after 256 values n will have 1 in every possible bit position.


One of the big benefits of deterministic wallets is that a public server can generate the public keys without compromising the private keys.

The OP in this thread has a way to do it with safety (I think).

Root private key: k
Root public key: K = kG

You can then generate a public key by picking an offset n.

Private key(n): k(n) = k + X(n)
Public key(n): K(n) = (k + X(n))*G = kG + X(n)*G = K + X(n)*G

However, you need to keep the X(n) function secret.

If some obtains

- the X(n) function (available by hacking the server)
- the private key k(n) for a public key K(n) (ECDSA break/implementation error)

They can compute k from

k(n) - X(n) = k + X(n) - X(n) = k

It seems to me that deterministic wallets are inherently less secure than normal wallets. 

If a normal address is only used once, then it is protected by both the RIPEMD160 hash and the ECDSA system.

Deterministic wallets are only protected by the ECDSA.

By || I mean appending one byte at the end of the seed_key, that gets hashed later to get the next private key.
So next time you calc a private key, you are hashing what you had hashed before, plus one byte more...

I was worried that maybe this could be somehow exploited, especially when the attacker knows that I append the bytes always with the same sequence (0,1,2,3,...)?


Yeah. That's type-2. I have it implemented in my app, but I personally don't use it, because it allows the "public server" to predict my further public keys and I see more cons than pros with this. It might make a lot of sense for e-commerce apps, but I don't really need such a feature for a private use.

BTW, I also had second thoughts about the anonymity issue, with the type-2 wallets.

Initially I had thought that keeping "B_secret" secret does prevent others from guessing further public keys... but then it came to my mind (though, please correct me if I'm wrong) that just by having two consecutive public keys that came from the same type-2 deterministic wallet, it should be rather simple to calculate the B_secret - shouldn't it?

I mean, if
Then:
Right?

Or isn't it possible to do the second math?

Most system use hashing.

The Armory system is that you work out a multiplier based on the chaincode and the current public key.

Multiplier(n) = ChainCode XOR Hash256(PubKey(n))

Public Key(n+1) = multiplier(n) * public key(n)
Private Key(n+1) = multiplier(n) * private key(n)

So, if you have the nth private key, you can work out the nth multiplier and then compute the (n+1)th key pair and by iterating, you get all the later pairs.

It doesn't let you work out the keys from before n (since that would require reversing the hash function).

You need the chain code, which isn't suppose to be public info.

Under your scheme, the private keys are directly generated by the server, so that is the worse than just having the chain code and root public key on the server.  

An attacker with public key(0) and the chain-code can obtain all private keys after the first private key they obtain.  

If someone hacks a server using your system, they get all the private keys.

Oh, I see. Thanks for explaining.


It's not really my scheme, it comes from the OP, but I do not quite get your logic that under this scheme "the private keys are directly generated by the server".
From what I understand, the whole idea of Type-2 scheme (from OP (https://bitcointalk.org/index.php?topic=19137)) is about generating the private keys outside the server. And I even checked it - it surely works.

EDIT: unless here you were talking about the scheme I described in this post (https://bitcointalk.org/index.php?topic=19137.msg3006588#msg3006588)?
There I generate the public addresses in my offline wallet and them move them online, for balance tracing.

Ahh ok.  You would get the same thing by having the chaincode.  However, if the chaincode is not on the public server then it doesn't matter either way.  You are just generating a set of public keys one way or another.

I sort of mixed up two different issues here.

One was my request for an audit of my deterministic wallet solution, which does generate public keys in the wallet, but is supposed to be "resistant" when one on the private keys gets compromised. I did not get much feedback here, but since nobody has stolen my coins yet, I'm guessing it's somehow secured enough ;)

The second issue was the privacy of the deterministic wallets, as they are being implemented now, by other parties; the kind of solution where you can generate further public addresses without having an access to the actual wallet. My concern was: how easy it will be for the attacker to figure out the secret/chaincode, while already having a couple of public keys from such a deterministic solution... From what you said, it won't be possible to figure out the chaincode, even having millions of consecutive public keys, or in other words: as long as you keep the chaincode secret, nobody can just calculate it from your public addresses. That's good to know - thanks.

Your type-3 appears to inferior to type-1: with type-1 there's one master secret, and in case that master secret leaks then all the other privkeys in your wallet also leak, but in the case that certain privkeys themselves leak the all the other privkeys don't leak. With your type-3, for efficiency the user's client may opt to store many seed[n] values, and if any of those seed[n] leak, then all the subsequent privkeys leak too. And just like with type-1, with your type-3 wallet if the master secret leaks then the entire wallet leaks. You haven't explicitly tried to claim what's the supposed advantage of type-3 over type-1, but maybe what you had in mind is that in order to generate the next privkey the user wouldn't need to access the most sensitive piece of data which is the master secret, and will only need to access the seed[n-1] data instead, We have discussed similar properties here before. If you think that your type-3 has any advantage over type-1, please describe with precise details how the client software is supposed to retrieve an arbitrary privkey[k] without access to the master secret. Do you propose to have multiple layers of encryption every time that a new seed is derived?


If SHA2 is pseudorandom then it's infeasible to figure out chaincodes from the pubkeys. The more tricky question is whether you could carry out a related-key attack after seeing many signatures, and the answer is "no".
In practical settings, the issue that concerned us is that if you're running a listening-only server that doesn't have access to the privkeys but does have access to chaincodes, and your server is compromised, so if an attacker could obtain a single privkey from another source (not from the listening-only server because that server doesn't even know the privkeys) then all the privkeys in your wallet will leak. Our solution is to use type-1 derivation for the root of the branch that the listening-server would be using, so that any leakage of privkeys will be confined only to that branch, and the user is advised to store privkeys that control high amounts of coins in different "cold storage" branches.

Thanks, you are so right.

When I read it again now, it is actually doing quite the same, as my "just invented" type-3 :)


So honestly, I don't know where I got this idea from, when I was thinking that the type-1 was about:

But now I see it was a stupid idea, and it existed only in my head - so never mind... Sometimes it is worth to make an idiot of yourself, just to learn something :)

Cheers, guys.

noob question is how can I apply the HD wallet to a web environment with multiple users. Once the wallets are created I can store everything in a MYSQL or something. Wouldn't I be able to query the blockchain  and update the web wallets. I think we can give the world a safe BIP0032 HDwallet that can be used online and on devices at the same time as a paper backup. Any help would be welcome. 

The point of HD Key Generation, that is BIP32, is to protect you against accidental loss of keys (not theft!). Once you have a backup of a master key you are able to recreate any key to any address that is derived from that. The master keys may form a hierarchy that is helpful in a larger or more complex setup such as a multi-user environment.

Querying the block chain in a performant manner is a non-trivial task for a large number of addresses. I claim that querying is not even feasible for a bigger implementation. You rather need an architecture of monitoring and persistent caching of the subset you care.

Security is an even bigger concern as storing the master keys on-line that are capable to spend multiple user's entire balances instantaneously, or creating backups that if fall into wrong hands give same level of access are sure recipes for disaster. Practically all wallet services that did so got compromised and lost all their customer's money.

You need to deploy a set of techniques if dealing with other people's money in a large installation, of which BIP32 is only one basic building block. Contact me for a complete solution.

The issue isn't validity, it's uniformity, i.e. we wouldn't want some privkeys to be more likely than others.
Please see posts #220 and #226 of this thread.

Re: deniable encryption

The simple use-case for deniable encryption is an attacker who points a gun at you and demands that you decrypt your Bitcoin wallet so that he can take your coins, hence you decrypt by using a decoy secret key that only gives the attacker a smaller portion of your coins, and while you're in a safe environment you decrypt your wallet with another secret key to access the larger portion of your coins. The attacker might see your screen with your wallet before he approaches you, therefore for everyday use you should prefer to operate with the version of your wallet that only controls the smaller portion of your coins (i.e. the pubkeys that correspond to the larger amount of coins will also be encrypted). This can be done by separate wallet.dat files, but built-in support for BIP32 wallet can be nicer, by selecting some branch in the deterministic tree as your decoy wallet, so you can easily transfer coins to/from that branch (see also post #192 in this thread).

It is easy to see that symmetric deniable encryption implies that the ciphertext must be bigger than the plaintext, simply because ordinary symmetric encryption is highly efficient. Suppose that you have two incompressible files f1 and f2 (i.e. files with high entropy) of same size, and note that the size of AES(f1) is the same as the size of f1. If you could create a ciphertext c1 of same size as f1 that can be decrypted into f1 by using the secret key k1 and can be decrypted into f2 by using another secret key k2, then you effectively compressed (f1,f2) into (c1,k1,k2), which is impossible.

This implies that if the attacker controlled which symmetric encryption algorithm we must use then there's no hope to have deniable encryption, but fortunately we can choose to use by default a symmetric encryption algorithm that expands the size of the ciphertext. Since wallet.dat files are quite small, that isn't really a big deal for end-users.

The straightforward construction for symmetric deniable encryption is simply concatenation, meaning that if we have the real plaintext f1 and the decoy plaintext f2 then the ciphertext is c=(c_1,c_2)=(enc_AES_k_i1(f1),enc_AES_k_i2(f2)) and the decryption algorithm dec(c,k,idx) will invoke dec_AES_k(c_idx), meaning that for {i1,i2}={1,2} the real secret key is (k1,i1) and the decoy secret key is (k2,i2).

The reference Bitcoin client can have by default a checkbox that reads "Support for deniable encryption", and when a user (who doesn't care about deniable encryption) encrypts his wallet the client will simply create a ciphertext that's twice the size of the plaintext where one random half is random data. This checkbox should be on by default, and each user can turn it off if he wishes to have a smaller ciphertext. If the user does care about deniable encryption, he encrypts his wallet with real half and decoy half by using the simple concatenation construction. If an attacker points a gun at this user, he will decrypt with his decoy key, and the attacker cannot tell whether the other half is random data (which would be the case with an ordinary user who didn't specifically choose to use deniable encryption) or not.

To protect against scenarios where the attacker has a reason to suspect that the user did use deniable encryption, and therefore try to force the user to reveal his 2nd secret key, it might be preferable to concatenate some n<N ciphertexts of variable sizes, instead of two ciphertexts of equal size, where n is random and N is some fixed bound. This way, the attacker wouldn't even know how many decoy wallets are contained in the ciphertext.

Edit: actually it isn't completely clear whether AES can be obliviously generated, meaning that (for random k) enc_AES_k(random) could be distinguishable from random (thanks to Hong-Sheng Zhou for this info), but in the worst case we'd just need to invoke AES once to encrypt random plaintext with random key and throw away the key...

quick question: deterministic wallets like electrum that have a master public key from which the public addresses may be (re-)generated subsequently. does one really need the master public key in order to generate those addresses or would it be possible to generate the subsequent addresses from e.g. the first public key (address)?

Yes you do need the master key.

An address is just a hash, and even if you knew the public keys
of specific addresses, you would not be able to determine
the other elliptic curve points of other addresses without the
master key.

Ah, alright, thanks! But you would be able to do that with the master public key, even though thats also just a public key!?

The master public key can generate addresses but not the private keys of those addresses.

that's clear, I was just making sure that indeed the master public key is needed in order to generate subsequent addresses even though it's just a public key (is it still a hash, though? what is it compromised of?)

I can only tell you how it works in Electrum:

The master public key is not a hash.  It's simply a hex-encoded
public key to the master private key, which is an elliptic curve
key based on the deterministic seed.

New addresses are generated from the master key by
generating new ECDSA coordinates, basically by
combining new sequence numbers with that master key
to create a new point.

As with a normal Bitcoin address, you can calculate
the public key from the private key, but not the
other way around.  This is no different.

One consequence of the master key scheme,
is that if a single address in your wallet is compromised
(the private key becomes known), and the
attacker knows the master public key,
they can crack the entire wallet, because
they could use the one private key together
with the master public key to discover the
master private key.

For that reason, the master public key should be
kept secret.  Its purpose (at least in Electrum)
is to create a watching-only wallet.

Ah alright, thanks! That's interesting, I really didn't know that the master public key may actually be an attack vector when compromised (in combination with an according private key). But it makes sense if it isn't a hash after all.

Public keys in bitcoin are calculated by multiplying a private key by the generator point of the secp256k1 curve. This is a trapdoor function, where there are a lot of possible private keys, and a lot of public keys, and the oeration

Similarly, you can add numbers to private keys to get a new number, which would yield a different point.
You can also add two points together, which is equivalent to adding two numbers together.

Since public keys are by definition public, no harm comes by revealing them besides a loss of privacy. Public keys can be used to generate deterministic offsets between points on the elliptic curve.

By hashing the 'master public key', and a sequence number for the public key, you have deterministic 'offset' from the master public key - which is just a 256bit integer.. Which like private keys, can also be converted to a point.

So for public derivations, you have the master public key (a point) and an offset (another point), and you add these two together.

The private derivation assumes you have the private key, and want to obtain a child private key. You take the private key (a number), generate the offset from the master public key (a number, but this time it's not converted to a point, you keep the number), and then you do modulo addition..

Lo and behold, it yields a number (the private key), which when multiplied by the generator, gives the same point as when you added two points together using purely public information. The private derivation works because the person has the master public key and could hash it also.

The reason you cannot share a master public key AND private key, is that someone can deduce it in this way (in a simple example)

// Attacker has Master Public Key, Address6/PublicKey6, PrivKey6
hash = hash('mpk'+'6')
offset = hash * G
Pub6 = PointMPK(x,y) + offset

Priv6 = k.

Main Priv Key = Priv6 - offset
Main Priv Key * G == mpk.

Now to calculate every private key in the chain:
PrivKey(n) = MainPrivKey + hash('mpk' + n)

At it's core, this is an HD Wallet question: 

I'm looking into developing a special purpose alt-coin and would like keep it largely the same as bitcoin except for what follows.  I would appreciate if someone would help me by telling me if a new protocol could be developed to support these requirements:

1.  we need to be able to have an internal organization create the seeds on behalf of a user (at their request.)
2.  this internal org would securely and confidentially maintain the user-to-seed relationship (no one else would know and it's a key requirement
3.  the user would be able to create any number of private or public keys themselves but always maintain the connection back to the original seed

Users would send and receive coins as bitcoin works today, with a blockchain as the ledger.  Users would be awarded coins by the company and can spend them/trade them with anyone else who also has a PK.

With these requirements, I would essentially have an audit trail of everyones transactions but only the internal organization could tie the transactions to a real employee.

I don't think that you want this organization to create the "seed" because it implies that this organization can also steal the user's coins.

Maybe what you want is that any user can generate a fresh seed (that derives privkey/pubkey pairs so that only the user knows the privkeys), where the master pubkey and master chaincode (that are derived from the seed that he generated) must be signed by this organization before this "user account" becomes valid on this network? This implies that new users are at the mercy of this organization, e.g., this organization may refuse to sign a new account unless it receives a bribe on the side. Also, if the signing key of this organization is compromised then all bets are off.