Bitcoin Forum
December 11, 2016, 08:25:50 AM *
News: To be able to use the next phase of the beta forum software, please ensure that your email address is correct/functional.
 
   Home   Help Search Donate Login Register  
Pages: « 1 2 3 4 5 6 7 8 9 10 11 12 [13] 14 15 16 »  All
  Print  
Author Topic: Deterministic wallets  (Read 39640 times)
thanke
Member
**
Offline Offline

Activity: 104


View Profile
May 12, 2013, 03:55:20 PM
 #241

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?
1481444750
Hero Member
*
Offline Offline

Posts: 1481444750

View Profile Personal Message (Offline)

Ignore
1481444750
Reply with quote  #2

1481444750
Report to moderator
1481444750
Hero Member
*
Offline Offline

Posts: 1481444750

View Profile Personal Message (Offline)

Ignore
1481444750
Reply with quote  #2

1481444750
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
iddo
Sr. Member
****
Offline Offline

Activity: 360


View Profile
May 12, 2013, 04:19:35 PM
 #242

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 Offline

Activity: 104


View Profile
May 12, 2013, 04:36:42 PM
 #243

How does it depend on the choice of hash function?
I guess this is something purely theoretical, right?
Pieter Wuille
Legendary
*
qt
Offline Offline

Activity: 1036


View Profile WWW
May 12, 2013, 06:38:13 PM
 #244

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 Offline

Activity: 360


View Profile
May 12, 2013, 06:54:21 PM
 #245

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 Offline

Activity: 104


View Profile
May 13, 2013, 10:29:24 AM
 #246

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 Offline

Activity: 360


View Profile
May 13, 2013, 12:49:49 PM
 #247

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 Offline

Activity: 104


View Profile
May 13, 2013, 04:00:35 PM
 #248

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 Offline

Activity: 496


View Profile
May 25, 2013, 01:03:50 PM
 #249

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

Now Peter, where are those test vectors!? Grin
Pieter Wuille
Legendary
*
qt
Offline Offline

Activity: 1036


View Profile WWW
May 25, 2013, 10:32:19 PM
 #250

Now Peter, where are those test vectors!? Grin

Have a look Smiley

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
chrisrico
Hero Member
*****
Offline Offline

Activity: 496


View Profile
May 26, 2013, 10:58:23 AM
 #251

Now Peter, where are those test vectors!? Grin

Have a look Smiley

Excellent, thank you!
chrisrico
Hero Member
*****
Offline Offline

Activity: 496


View Profile
June 22, 2013, 04:33:47 PM
 #252

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

Activity: 1036


View Profile WWW
June 22, 2013, 04:44:28 PM
 #253

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 Offline

Activity: 496


View Profile
June 22, 2013, 05:21:52 PM
 #254

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 Offline

Activity: 836


bits of proof


View Profile WWW
June 22, 2013, 06:07:29 PM
 #255

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 Offline

Activity: 1512


aka tonikt


View Profile WWW
June 22, 2013, 06:40:29 PM
 #256

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 Smiley
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
Hero Member
*****
Offline Offline

Activity: 836


bits of proof


View Profile WWW
June 22, 2013, 07:03:30 PM
 #257

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 Offline

Activity: 1512


aka tonikt


View Profile WWW
June 22, 2013, 07:08:15 PM
 #258

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 Smiley

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

Activity: 836


bits of proof


View Profile WWW
June 22, 2013, 07:11:32 PM
 #259

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

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 Offline

Activity: 1512


aka tonikt


View Profile WWW
June 22, 2013, 07:18:23 PM
 #260

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

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

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
Pages: « 1 2 3 4 5 6 7 8 9 10 11 12 [13] 14 15 16 »  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!