I wanted to share some thoughts about how Webcoin is going to handle DWs. I'll use the same symbols as TierNolan.

First of all, I don't see the need for a seed. Since the seed has to be stored with the private key anyway, you might as well regard it as part of the private key.

Next, the master private key should have a full 256-bits of entropy. So we use a random number 0 < a < 2²⁵⁶. Yes, it's a pain to type. In practice you'd normally use more convenient ways to transfer DWs, such as USB sticks, QR codes, etc.

(However, if your house just burnt down and you lost every backup but the printed hardcopy at your safety deposit box, I don't think having to type a very long password is going to concern you too much.)

Here is an example of a 256-bit number using base58 encoding:

"6QPCJCRhPSVoKL4hhLoqRuBEk4VYzAFMAC1GwQ7JbSR4"

In reality we'll also add a checksum and a version byte, similar to a Bitcoin address.

In our version, there is no seed, so we've been working with v(t, n) instead of v(n, t, s).

t ... type is included only for future use. Currently it is a zero-length string, i.e. it is omitted.
n ... serial is a 64 bit unsigned integer (LE).

So a new keypair b, B is generated as:

b = a + SHA256(A t n)
B = A + SHA256(A t n)*G

A is an ECPoint encoded using standard non-compressed form (0x04 x y)

To generate a new public key for the wallet, you need to know A, t and the next serial number to use.
To spend the coins on any of the addresses, you need to know a, t and the serial number.

During normal use, we assume that we have access to a metadata storage system. The metadata storage is retrievable using an access key SHA256(A "access"). It's contents are unencrypted, symmetrically encrypted or asymmetrically encrypted depending on the application. For example, a merchant server whose only job is generating addresses would encrypt metadata for those transactions using a public key and the wallet would retrieve it using the corresponding private key. That way, if the merchant server is compromised, privacy for previous transactions is still guaranteed.

If the metadata is lost for any reason, the user can use a recovery tool to get their coins back. The recovery tool needs a full database of unspent outputs in the block chain and will simply generate public keys using sequential serial numbers using the method above. Whenever it finds coins it will add an entry to a new metadata array.

Note: Using t will make coin recovery more difficult, because the recovery tool will have to a) know all values for t and b) separately scan them all. That's why we're more interested in keeping t an empty string for all normal use cases and using the metadata to synchronize what the next available serial number is.

The maximum number of addresses for one wallet is 2⁶⁴ or 18,446,744,073,709,551,616 (for each t).


Correct. I want to add one more: As long as the master public key A is secret, nobody can break the privacy of the other addresses.

Am I correct in thinking that if you keep A a secret between you and a friend, and agree to use some agreed upon sequence of serial numbers (could this just be trivial and the same for everyone?), that they could have access to an infinite number of your public keys that can't be associated by an outsider?  Edit: lol I think you just said this in the last sentence.

If so, then it seems like it could enable people to interface in the client with a contacts list instead of ugly addresses, but without having to reuse them or manually request new ones all the time.

I guess one major problem would be losing the master private key, and having people continue to send to addresses derived from the associated public key.

This could be mitigated by having your contact instead for each transaction get the master public key from an (untrusted) online storage server who stores it encrypted to your private key and your contact's public key, and check that it hasn't changed.  That way if you lose your wallet, you can stop everyone from sending to it in one step by deleting the master public keys from your storage server, and restart it again by uploading new ones for each of your contacts, without having to notify them, since their client can just start the agreed upon serial number sequence anew if they notice that the master public key has been changed.

Edit: Damn, I read your post two days ago, and forgot to re-read it before responding.  I apologize for basically restating what you did.

Actually, my post specifically mentions this use case:



You don't need a seed to generate addresses securely. Knowledge of A is enough to generate addresses and you don't need to have the master private key at all.

The only problem is that if the hacker has A, he knows all your addresses, so while he can't spend your money, he can see all your blockchain activity. If you extend your seed concept a bit you could use a changing seed, so that an attack would only compromise the current seed.

Going one step further, I've recently been thinking about using a hashing chain. I.e. the hashes no longer depend on A, but instead depend on the previous hash plus the serial number. Then you make the server forget each hash as soon as it's no longer needed. The first hash would be derived beforehand from the master private key in some fashion and is then part of the deployment package to the webserver. That way you can still generate all private and public keys from the master key (full determinism), but a hacker gaining access to the merchant's webserver would only be able to spy on future transactions, not past ones.

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.

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.

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.

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.

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.

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.