Topic: Deterministic wallets - page 14. (Read 48267 times)

can someone explain this to me?

I'd like to direct you to a proposal which could be seen as implementing a type 2 deterministic wallet on funder's clients. The hash function in this case is choosing the x coordinate of an elliptic curve multiply in a similar fashion to ECDSA.

I believe that this would satisfy the goals of a deterministic wallet and have a number of other fairly obvious beneficial effects.

ByteCoin

No, you are correct. But it doesn't matter. Here "easier" means that if you dedicated every computer on the planet to breaking a key, it might take a few dozen centuries rather than a few hundred centuries. In fact, the system is so strong, even if you released the master public key, allowing an attacker to generate as many related public keys as he wanted, it would still be impossible (for practical purposes) for him to compromise a single private key. (In fact, this scheme was originally developed with the idea of using it exactly that way.)

This is the interesting thing about public key cryptography. Attacks are always possible. Every conceivable compromise is doable in principle. So you can't just check if an attack is theoretically possible, you have to ask if it is practical.

As it is currently not (in realistic time) possible to get a private key to a public address, you are likely also not able to determine how these private keys might be linked together.

I am wondering the same thing: if the wallet is deterministic and you publish several public keys shouldn't it be possible to calculate the original private key? Especially regarding merchants, restaurants and such who most likely will publish a lot of keys. The more keys published the easier it should get to find the private key!

Or am I missing something?

Doh, it's like I read https://en.bitcoin.it/wiki/Securing_your_wallet many moons ago, forgot it, then wrote it back out again, thinking I was being original.  Squishy data storage (brains) aren't very good. http://www.htmlhelpcentral.com/messageboard/showthread.php?13363-Mind-Control-Magic-and-the-Value-of-Branding-Online

It already does.

Even after a PGP key has expired, you can simply edit it to extend the expiration date. Passwords on deterministic wallets can be changed like any other.

I like that this idea makes it more convenient to back up your wallet addresses, lessening chance of losing bitcoins through hard drive failure/fire/whatnot, but the proposed solution creates an unacceptable trade-off in that it's too easy for an attacker to compromise all future transactions.  If the attacker has access to a wallet just once, they can clear out the victims wallet at any future time, and at a time of their choosing when they believe they will get maximum value out of the wallet.  And when the attacker chooses to act, the victim will never know what hit them, or when the wallet was compromised - it could have been months or years in the past.  This seems scary to me, and would keep me from using the same wallet over a period of years.  Regularly creating new wallets rather defeats the purpose of the idea of a deterministic wallet that doesn't need multiple back-ups.

How about a middle ground: the client could pre-generate the next, say, 100 addresses, and then whenever a backup is performed, these pre-generated future addresses are also saved.  "New" addresses are actually being pulled from this pool of pre-generated addresses.  Enough addresses should be generated to cover, say, a month's worth of transactions, the maximum supported time between wallet backups (yes, some people only back up monthly).  Pre-generated addresses that were unused for a month would be discarded.  Exact number of pre-generated addresses would be set in Preferences page.

With this scheme, even if a hard drive fails right after receiving a transaction using a "new" (but actually pre-generated) address, the transaction address used would have already been backed up in the past month.  It would be kind of like the new video cameras that are always recording, overwriting their cache constantly, and when you press the button _after_ the action has happened, the previous 10 seconds of video in the cache is saved to memory. 

An attacker that compromises the wallet with pre-generated addresses would then want to act within a month since they could not compromise all future transactions as with the deterministic wallet.  This tighter coupling between the time of compromise and the wallet being emptied is a Good Thing for post-hoc failure analysis.  And if you transfer all of your coins to a "new" address, you can be guaranteed that your wallet is secure, even if someone finds, say, an old backup you forgot about and threw out in the trash.

This scheme also avoids the potential cryptographic problems of creating a seed address that might, just might, have a cryptographic vulnerability. Using a set of pre-generated addresses avoids this issue by using future randomness in generating future keys.

Finally, philosophically, I think wallets need to be living entities, and an immortal wallet is not a good idea.  I can't concisely explain the reasons why this is best besides the above example about the backup found in the trash.  There's a reason the PGP key system is designed to allow keys to expire, and all good security systems require occasional password changes.

It depends on the country, in the US you have 1 year to file after demonstrating your invention in public.

I'm curious, are you allowed to file a patent AFTER discussing it in a public forum? I was informed, perhaps wrongly, that if I had intentions of patenting something, prior to actual filing I should never disclose it in public or discuss it without making clear it is confidential, otherwise it would render the idea inadmissable.

FWIW, I may be filing a patent on this, so I'll report back if I find anything problematic.

If I do so, I will be offering it under terms no more restrictive than the Xiph.Org patent license: https://datatracker.ietf.org/ipr/1524/  (e.g. a free license to anyone who doesn't conduct patent litigation against bitcoin users)
 

If this mechanism is being seriously considered, someone needs to make sure it's not encumbered by a patent. I remember when I first heard the notion of a "family of public keys" such that a single private key would allow deriving the corresponding family of private keys, I seem to recall it being patented. That was at least three years ago, I think, so it may not even be covered any more.

This is a fascinating thread, and although the maths often fly over my head, I'm earnestly trying to keep up. Please correct me if I have been derailed from the very beginning, the goal is to base an entire infinitely expandable wallet on a single seed. While subsequent data (generated keys, transaction references, etc) could be stored with a wallet, all that is critically necessary to back up is this (what?) 100 byte seed. Everything else can be regenerated ad nauseum.

No. Because it's the secret keys that are correlated and an attacker would only have the public keys.

Even if he did have some secret keys, it wouldn't matter. This attack would be possible in theory but impossible in practice because the scheme is specifically designed to make it impractical. (It's not particularly hard to do that. Both schemes proposed use well-known methods to prevent this even if an attacker had some private keys somehow.)

Of course, if the seed gets out, all future keys are compromised.

Yep, you're correct. I'll update my posts to use SHA-256 with HMAC, which is used as a PRF in IPSec, TLS, DKSPP, etc.

I'm no cryptographer, but hashcoin said "it will yield something noone knows how to break, but its security is not provable assuming the security of the hash function". So the problem isn't that there's a known weakness, but that it's not provably secure, as PRF is, assuming the security of the function.

So instead of using a hash we should be using a block cipher?

I presume that the difference between the two with the most practical impact is the presence of collisions in the former and the absence thereof in the latter.

I'm not really calling in to question the validity of what you say but, to make your point more obvious, could you give a realistic example of a situation in which using a hash function instead of a pseudorandom function gives noticable problems?

ByteCoin

I just looked at OP but be aware when designing a scheme like this you must be very careful to use the correct cryptographic primitive.

The primitive you are looking for here is a http://en.wikipedia.org/wiki/Pseudorandom_function_family.
A http://en.wikipedia.org/wiki/Cryptographic_hash_function is NOT the same thing.  In particular, it is not true that given a hash function H, taking family F(K)(X) = H(K | X) will yield a PRF (perhaps, for a particular hash function, it will yield something noone knows how to break, but its security is not provable assuming the security of the hash function).

PRFs are mainly used to construct other things and so may be unknown to you.  You likely do know something very similar, the "PRP" or Pseudorandom Permutation, which is like a PRF but which is indisinguishable from a random permutation by bounded adversaries (note the two are basically the same to an adversary, since they could never distinguish a random function from a random permutation anyway, as querying a random function on a reasonable number of places will never show two values mapping to the same).  PRPs are what applied crypto people call "Block ciphers".  So you can use a block cipher, e.g., AES, to do what you are trying to do.   But do NOT use a hash function, that is not what it is for.

Again I cannot stress enough how important it is that correct crypto primitives are used for their intended purposes.

Agreed very much. I was quite surprised to discover this feature after muddling through a lot of very geeky documentation. People can't be expected to comprehend this sort of quirks.

Good point, I should have been more specific. So here is the chain variation in detail.

Let s_n be the second part of the private key which the merchant's webserver generates.

The private and public keys are therefore:

b_n = a + s_n
B_n = A + s_n*G

The first hash s₀ is generated by the wallet as follows:

s₀ = SHA256(a i C)

i ... A 64-bit integer (LE) that starts at 0 and is incremented if the same wallet is used for more than one chain.
C ... Some constant, e.g. "BITCOIN_CHAINHASHSEED_gZ5hA5S7237RoJ" - this is the same globally for everybody.

The merchant then takes s₀, i and A and inputs them as settings on his webserver. The server initializes the transaction serial number n as 0. It is now ready to accept orders.

A user wants to do an order and pay in Bitcoins. The merchant server now runs through the following steps:

1. Increment n.

2. Generate new s_n:

s_n = SHA256(s_n-1 n C)

n ... The current serial number as a 64-bit integer (LE).
C ... Another constant, e.g. "BITCOIN_CHAINHASH_2bIyLHNXlHe77u" - this is the same globally for everybody.

3. Derive the public key B_n:

B_n = A + s_n*G

4. Create, output and store the Bitcoin address corresponding to B_n.

5. Securely delete s_n-1.

Note that storing the address in step 4 depends heavily on the specific use case. Here are a few examples:

(A) The server stores the address until the payment arrives and then sends the details of the order via email to the merchant at which point it deletes its own stored information about the order.

(B) The server doesn't store the address in plain text, but instead encrypts it with a public key and stores it like that. Every day the orders are downloaded, decrypted and processed on an offline system.

(C) The server stores the address until the payment arrives, then enables the user's account to access the digital content he/she has purchased. After that the server encrypts the address and other information related to the transaction with a public key and stores it for archival.

Implementation-wise we would probably wrap the chainhash stuff in a library that takes A as a configuration value and s₀ and n as initialization values and just spits out new addresses on demand. It would also provide utility functions to write data to the metadata storage like setDescription(chainSerial, transactionSerial, description). This information could be submitted to the wallet metadata using asymmetric encryption and later be retrieved by the wallet software and displayed in the list of transactions - similar to Bitcoin's address book feature.


Hmm, I don't think that attack is possible - or I haven't understood it correctly. My chain consists of private information only. Having the public key and the serial number would not enable you to predict the next address. Curiously, even breaking ECC and finding out any number of b_n wouldn't give you access to s_n, because you'd still only have sums a + s_n with no way to solve for a.

More realistically, breaking into the server you could compromise the current s_n and the current serial number n, which would tell you how many transactions have taken place as well as predict any future addresses - both with respect to this specific chain. It would not allow you, however, to find out any of the previous addresses unless that information is still stored on the server in some other fashion.

Caveat: The chain serial i increases the dimensionality of the address space. If all metadata of the wallet is lost and we want to recover our money based on only the private master key a, we have to in theory try every n for every i. In practice, the user will likely have a small number of chains per wallet and/or know roughly how many he/she has. So the search would be limited to very small values for i. Given that a total loss of metadata is a worst case scenario and other types of backup are likely being used as well, a certain amount of computational work for the recovery procedure seems acceptable.

With Webcoin specifically we hope to eventually store the encrypted metadata in a DHT. At that point the deterministic wallet concept serves two goals: (1) Reducing the amount of data that needs to be stored (a serial number like i and n could be stored as a var_int, 1 to 9 bytes, compared to a private key (32 bytes) or even a public key (65 bytes)) and (2) Providing a "last resort" recovery mechanism if all else fails - namely by scanning for unspent outputs using the private master key.