thanke


May 12, 2013, 03:55:20 PM 

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 zeroknowledge computational integrity (PCP) proofs.
Really, you can zeroknowledge prove that you know a preimage of a hash?







Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.


iddo


May 12, 2013, 04:19:35 PM 

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 zeroknowledge computational integrity (PCP) proofs.
Really, you can zeroknowledge 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


May 12, 2013, 04:36:42 PM 

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




Pieter Wuille


May 12, 2013, 06:38:13 PM 

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 HMACSHA256 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 I = HMAC( cpar, Kpar  i) in the public derivation to 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 payerderived payment addresses (which is basically just a deterministic wallet of the payee in the hands of the payer) will be 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 reuse 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 zeroknowledge proofs that could avoid this.

aka sipa, core dev team
Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa



iddo


May 12, 2013, 06:54:21 PM 

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


May 13, 2013, 10:29:24 AM 

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 I = HMAC( cpar, Kpar  i) in the public derivation to 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_Lr instead (never both, of course, because then they blow up).




iddo


May 13, 2013, 12:49:49 PM 

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


May 13, 2013, 04:00:35 PM 

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


May 25, 2013, 01:03:50 PM 

Peter and Timo, it was great getting to meet both of you at the conference! Now Peter, where are those test vectors!?




Pieter Wuille


May 25, 2013, 10:32:19 PM 

Now Peter, where are those test vectors!? Have a look

aka sipa, core dev team
Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa




chrisrico


June 22, 2013, 04:33:47 PM 

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




Pieter Wuille


June 22, 2013, 04:44:28 PM 

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

aka sipa, core dev team
Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa



chrisrico


June 22, 2013, 05:21:52 PM 

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.





piotr_n
Legendary
Offline
Activity: 1540
aka tonikt


June 22, 2013, 06:40:29 PM 

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.

Check out gocoin  my original project of a bitcoin client written in Go, with some unique features.PGP fingerprint: AB9E A551 E262 A87A 13BB 9059 1BE7 B545 CDF3 FD0E



grau


June 22, 2013, 07:03:30 PM 

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
Legendary
Offline
Activity: 1540
aka tonikt


June 22, 2013, 07:08:15 PM 

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

Check out gocoin  my original project of a bitcoin client written in Go, with some unique features.PGP fingerprint: AB9E A551 E262 A87A 13BB 9059 1BE7 B545 CDF3 FD0E



grau


June 22, 2013, 07:11:32 PM 

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
Legendary
Offline
Activity: 1540
aka tonikt


June 22, 2013, 07:18:23 PM 

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.

Check out gocoin  my original project of a bitcoin client written in Go, with some unique features.PGP fingerprint: AB9E A551 E262 A87A 13BB 9059 1BE7 B545 CDF3 FD0E



