Topic: An implementation gotcha with "split" keys (Read 424 times)

That's a good guess, but in this case the problem was caused by applying the modulo operation too many times, not too few.


I've made a topic about this here, when you find the time I'd appreciate your input!

Fixed (as well as in the linked thread), thanks!

That cited sentence is ill-formed to me, you likely meant: ... the key space of 2^256 is bigger than the public address space of 2^160 ...

I see, I was looking at the problem through a testing lens, and so was stuck at wondering how to check the following identity (pseudocode):


It seemed to me, that to test if the above is true for randomly generated pairs of private keys (like I was doing for the additive case), that I would have to implement non-scalar point multiplication (the operation on the left).

Now I see that because G (the generator point) acts like the number "1" (i.e. any point P multiplied by G is simply P), you can dodge the non-scalar point multiplication by simplifying the relationship to:


Thanks @NotATether, I (think) I get it now!

You don't multiply two points together, you multiply one of the points with a private key.

Suppose you generate a public/private key pair that is secret. Then you can send the public key to any service, the service can also generate a second private key (not associated with any public key), share the private key with you, and multiply your public key by the second private key to get a third (product) public key. Similarly, you can multiply your two private keys together to get the corresponding private key for it.

Basically, if A is your pubkey, a is its secret privkey, and b is some random privkey generated by the service and shared with you, then:


Where G is the generator point of SECP256K1.

Then you have the public/private keypair (C, c).

---

How you could make a vanity address out of A and b? Well, you know that this makes another private key C, so just cycle through random values of b until you get an address hash that matches the prefix. And there will eventually be a collision becuase the number of keys (2^256) is bigger than the number of addresses (2^160) and is somewhat less than the number of addresses containing the alphanumerical prefix (or suffix) that you are trying to generate.

It is always true. Only half keys passed, because you probably skipped modulo "n". All operations are always modulo "n".
Edit: Doing multisig with addition is dangerous, always do that with multiplication. Or better: use homomorphic encryption, then you can make N-of-N multisig with raw public keys, so that means you can use it on all address types, you are not limited to Schnorr signatures.

Edit: It is better than that: you can join sub-fields if you know how it works. For example, you have two public keys with the same x-value, and you have three public keys with the same y-value. That means, for a given public key, you always have six "trivial" points, forming some area. And you can do crazy stuff if you start dealing with such rectangles.

Another interesting property is that because n is lower than p, then there are some points that are "weak". It is the case if you have some point, where n*Point is not zero. But there are only (p-n) such points, so they are hard to find, also because getting any of them could make secp256k1 weak enough to be broken.
Those points are "weak", because in some protocols, you could give some user such point outside of secp256k1, and then reach something that is easier to break.

That's a nice post! I'm still not clear on how to multiply a point by another point, so can't yet appreciate how "multiplicative" split-keys would work. I obviously have some more reading to do. Thanks for the merit!

You might want to read my thread Analysis of the "split-key" vanity address method: How does it work? for more information about split-keys and how they are created.

In particular, I have a section at the bottom with implementations in JS (it's easily ported to Python).

I'm new to Bitcoin and have been making a serious attempt to learn it by programming bits & pieces of it in Python.

I recently learned about "split" keys and ran into something interesting that I thought I'd share here.

As I understand it, "split" keys emerge from the following identity (pseudocode):


This allows for surprising things like securely outsourcing vanity address generation or doing "multisig" with plain old P2PKH addresses.

I was adding a test-case to my code to check that the above relationship is always true and instead found that it was only true about 50% of the time. That is, if I generated pairs of private keys at random only about half of them would pass this test.

Now, obviously I was doing something wrong, but I couldn't figure out what. I was making sure to take the sum of the two private keys modulo the group order and I carefully checked my EC multiply logic and it passed all the tests I could dream up for it.

The confusing thing was that if I just stuck to ordinary key generation (Private -> Public -> Address) then my implementation agreed with everything I compared it to (Electrum, bitaddress.org) but as soon as I tried to "split" the keys things went wrong, and even then, only about half the time.

Anyway, I just fixed it and had a small epiphany at the same time!

I'm not a mathematician, so I may bungle the terminology but here goes:

For whatever reason, I had internalized the mathematics of address generation as essentially having two parts: A single finite field, and a group defined over that field.

To represent this in my code I have a "Scalar" class for elements of the finite field and a "Point" class for elements of the group.

Because I thought of private keys as belonging to the finite field I naturally made them "Scalar". What I failed to realize was that whenever I added them together and then applied the group order modulo operation I was actually applying a second modulo operation (the first being applied under the hood by the "Scalar" class). This double modulo, one with P (the field order) and then one with N (the group order) was what was causing all the trouble.

This made me realize that there are actually two finite fields, F_P and F_N and that they should not be mixed up. F_P should be used for point co-ordinates and F_N should be used for private keys.

So, now I model them in my code with a "Scalar" class (as before) a "Point" class (as before) and a new "Secret" class for elements of the other finite field.

In summary, don't do math on private keys in the wrong field