Deterministic wallets

[thanke]

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.

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

[1714840989]

1714840989

[1714840989]

1714840989

[1714840989]

1714840989

[1714840989]

1714840989

[1714840989]

1714840989

[iddo]

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.

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.

[thanke]

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

[Pieter Wuille]

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.

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.

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?

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.

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.

And third, can you change

Code:

I = HMAC( cpar, Kpar || i)

in the public derivation to

Code:

I = HMAC( HMAC(cpar,i),  Kpar)

? 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

Code:

K_derived := HMAC( m, K_base) *G + K_base

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.

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.

[iddo]

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

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.

[thanke]

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.

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.

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

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

Ok.

And third, can you change

Code:

I = HMAC( cpar, Kpar || i)

in the public derivation to

Code:

I = HMAC( HMAC(cpar,i),  Kpar)

? I see the provability of the link as a quite an important property (cf. #228).

That provability argument is interesting, but can you come up with use cases?

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

[iddo]

If we have P_i=HMAC(I_L,P)*G+P they can't do that.

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 ?

[thanke]

If we have P_i=HMAC(I_L,P)*G+P they can't do that.

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.

[chrisrico]

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

Now Peter, where are those test vectors!?

[Pieter Wuille]

Now Peter, where are those test vectors!?

Have a look

[chrisrico]

Now Peter, where are those test vectors!?

Have a look

Excellent, thank you!

[chrisrico]

Peter, can BIP32 be changed to a status of Final on the wiki now?

[Pieter Wuille]

Peter, can BIP32 be changed to a status of Final on the wiki now?

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

[chrisrico]

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.

[grau]

Peter, can BIP32 be changed to a status of Final on the wiki now?

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

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

[piotr_n]

Peter, can BIP32 be changed to a status of Final on the wiki now?

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

What makes an implementation a reference implementation?

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.

[grau]

Peter, can BIP32 be changed to a status of Final on the wiki now?

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

What makes an implementation a reference implementation?

I think it means that it needs to be an implementation in the official bitcoin client.

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.

[piotr_n]

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

[grau]

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

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

[piotr_n]

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

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.