Topic: Deterministic wallets - page 11. (Read 48267 times)

That's exactly what Armory does.  See the Offline wallet tutorial.  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.

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?

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.

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.

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.

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.

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?

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.

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), 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?

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

 

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?

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.

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.

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.

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.

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

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.

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.

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.

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?