generating new addresses on 'online' computer instead of cold storage system

[Jace]

At Bitcoin 2014 I spoke to Alan (I think?) after his presentation on Armory. Afterwards I asked him how new addresses (well actually, new public keys) can be generated in a typical two computer setup, where one is used for cold storage (private keys stored only there, system never comes online) and the other 'online' one is used to broadcast transactions and communicate with the network.

I understand how subsequent private keys can be derived deterministically from a single seed, so one backup is sufficient even for future keys still to be generated. But from my understanding of secp256k1 curves (used in Bitcoin's ECDSA) I always thought public keys are 'derived' from private keys, so public keys cannot be created or generated without the corresponding private key.

However Alan explained that by means of some special root key, which can be split into a public and private part, subsequent public keys can be generated on the live system, in such a way that they correspond with future private keys to be generated on the cold storage system, but without the need of actually having those private keys.

How does that work? Is there a tech explanation for that somewhere?

[goatpig]

Alan loves to respond to these types of posts with in-depth answers, including nicely laid out paragraphs, punctuation, proper grammar, bold and underlined key points, COLORS, and sometimes even pictures. So I'm gonna beat him to the bush with a half assed answer just to frustrate him =P

http://en.wikipedia.org/wiki/Elliptic_Curve_DSA

This is the basic math behind the EC signing scheme. Somewhere there, they give you the formula to get a public key from a private key, something like:

dA * G = QA

where dA is the private key, G is the base point of your curve, and QA is the resulting point on the curve. I wont go into the modulo part or the scalar vs curve point part. Im too lazy, and it's funny portraying Alan torn by this dilemma: knowing all of these omissions and inconsistencies are just baits, but being unable to resist his inner smartass.

So, there's some math property which names I forgot that let's you do this:

dA * k * G = k * dA * G

where k is some random number with the same properties as a private key. This means if you have a private key that is something like dZ = dA * dB, you could do something like:

QZ = dZ * G = dA * dB * G

and

dA * G = QA
dB * QA = dB * dA * G = dA * dB * G = QZ

Put in words it means that for a given private/public key pair, you can multiply both the private and public key by the same scalar and achieve a new pair of matching private/public keys. So to create a chain of public and private keys, you only need to create a chain of scalars, multiply your original (root) private key by these scalar, do the same with your (root) public key and get the matching public keys for all those private keys without having to expose them to the online machine.

I hope this reply answered just enough for you to want to know more, and for Alan to get fuming and hissing!

[etotheipi]

Alan loves to respond to these types of posts with in-depth answers, including nicely laid out paragraphs, punctuation, proper grammar, bold and underlined key points, COLORS, and sometimes even pictures. So I'm gonna beat him to the bush with a half assed answer just to frustrate him =P

Haha, well done.   I do these elaborate, polished presentations because I feel like most n00bs will gloss right over it unless it's visually quite clear what point is being made.  I want to make sure that if they are determined to understand it, that it as clear as possible.  Colors and bold help with that.  I won't repeat your explanation, but I will correct it... and with some color (I also don't like the multi-letter variables).

a is your private key (a scalar, lowercase)
G is the generator point of the secp256k1 curve  (an EC point, upper-case bold)
* is the operator for multiplying a curve point by a scalar
* is the operator for multiplying a scalar by another scalar modulo the size of the curve

Your public key, Q is:   Q = a*G

The important property that we leverage with Bitcoin and ECDSA (which wouldn't exist if Bitcoin used any other crypto system) is this:  we pick any scalar c.  The following equality holds by the property of ECDSA:

(c * a) * G  =
 c * (a * G) =
 c * Q

What this shows us is that if you multiply your private key by a scalar c (mod N), you can multiply your public key by the same scalar (EC-scalar-point-multiply) and you get matching keys.  Note that (c*a) is a scalar and thus could be used as a private key, and that (c*a)*G would be the associated public key, but that the equality above shows you can get the same public key without touching the private key... just use the same scalar on the public key.  So you can keep multiplying by c (or any deterministic sequence of c-values) and you get chains of private keys from the private root, and matching chain of public keys from the public root.  

That's how "type-2" determinsitic wallets work, and the basis of BIP32.

[Jace]

Very late reply, but still thanks for both your explanations (I did actually read them at the time ). All clear.

Something just occurred to me: I know that given some a*G (with commonly known generator point G), obviously one cannot divide by G to retrieve a, otherwise you could calculate private keys from public keys.

However, suppose I know someone is using a HD wallet, and in particular I know a few subsequent spending transactions. In other words, I know:
c*Q
(c+1)*Q
(c+2)*Q
for some unknown scalar c (I don't know how far they are within the HD wallet sequence).

Now, could I substract (c+1)*Q from (c+2)*Q for example (this is possible in EC, right?) thus extracting Q. Now I can restore all their previously used addresses, and brute force c (assuming the number of used addresses for a person's wallet will typically be within the thousands at most), allowing me to predict all their future public keys as well.

Or do HD wallets not generate keys as 1*Q, 2*Q, 3*Q etc but rather some deterministic yet irreversible sequence of c-values? e.g. scalar = sha256(c||Q)

Not that this would be a serious issue (private keys are still 100% safe) but it would somewhat harm one's privacy.