Quote from: gmaxwell on July 14, 2011, 02:33:31 PM

I'd need to see a more concrete version of the chain version.

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.

Quote from: gmaxwell on July 14, 2011, 02:33:31 PM

The simplest implementation with just H(prior-key|type|serialnumber) would be insecure because the serial number would not have enough entropy. e.g. I'd generate two addresses keys on your site, getting sequential serial numbers, then I'd send money to both and wait for you to spend it and disclose the public keys in the process, then I'd search the space of likely serial numbers such that one address leads to the next. Then I can generate all future public addresses.

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.