Topic: Deterministic wallets - page 4. (Read 48413 times)

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

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.

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

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.

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.

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

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.

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.

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.

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.

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

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?

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: