Post
Topic
Board Development & Technical Discussion
Re: Deterministic wallets
by
iddo
on 12/05/2013, 14:40:32 UTC
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):
Code:
I := HMAC( HMAC(cpar,i) , Kpar)

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.