Bitcoin Forum
January 21, 2018, 03:13:27 AM
 News: Latest stable version of Bitcoin Core: 0.15.1  [Torrent].
 Home Help Search Donate Login Register
 Pages: 1 2 3 4 5 6 7 8 9 10 11 12 [13] 14 15 16  All
 Author Topic: Deterministic wallets  (Read 47373 times)
thanke
Member

Offline

Activity: 104

 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 zero-knowledge computational integrity (PCP) proofs.

Really, you can zero-knowledge 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.
1516504407
Hero Member

Offline

Posts: 1516504407

Ignore
 1516504407

1516504407
 Report to moderator
iddo
Sr. Member

Offline

Activity: 360

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

Offline

Activity: 104

 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
Legendary

Offline

Activity: 1050

 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.

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

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

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
iddo
Sr. Member

Offline

Activity: 360

 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
Member

Offline

Activity: 104

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

Offline

Activity: 360

 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
Member

Offline

Activity: 104

 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,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
Hero Member

Offline

Activity: 496

 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
Legendary

Offline

Activity: 1050

 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
Hero Member

Offline

Activity: 496

 May 26, 2013, 10:58:23 AM

Now Peter, where are those test vectors!?

Have a look

Excellent, thank you!
chrisrico
Hero Member

Offline

Activity: 496

 June 22, 2013, 04:33:47 PM

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

Offline

Activity: 1050

 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
Hero Member

Offline

Activity: 496

 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.
grau
Hero Member

Offline

Activity: 836

bits of proof

 June 22, 2013, 06:07: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 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
Legendary

Offline

Activity: 1820

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 full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
grau
Hero Member

Offline

Activity: 836

bits of proof

 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: 1820

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 full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
grau
Hero Member

Offline

Activity: 836

bits of proof

 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: 1820

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 full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
 Pages: 1 2 3 4 5 6 7 8 9 10 11 12 [13] 14 15 16  All
 « previous topic next topic »