Is this possible (2)?

[Inca]

Another conundrum for anyone interested on here.

I have been considering the following theoretical problem. I wonder if it is possible to trustlessly and randomly generate a bitcoin address from a private key assembled from multiple separate random number fragments, say nodes on a peer-to-peer network and produce a public key without ever revealing the private key to any individual node on the network.

Assembling the private key (256bit random number) is straightforward.

Running the ECDSA algorithm to generate a public key is the tricky (impossible?) step. Suggestions please

 

[Peter R]

@Inca

Yes, this is possible. Assume Alice knows private key k_a and Bob knows private key k_b. They can each calculate public keys:

Q_a = k_a * G
Q_b = k_b * G

where G is the base point of the elliptic curve. If Bob tells Alice Q_b, then Alice can construct a new public key

Q_ab = k_a * Q_b = k_a * k_b * G

without knowing Bob's private key (k_b)! The key that can spend from Q_ab is the product of Alice and Bob's private keys (k_ab = k_a * k_b), which neither of them know (well, unless they share their private keys with each other).

 

[Inca]

Peter R,

What if there are more than two people in this situation. Does this work if there are 3 or more keys involved?

i.e is it possible to generate Q_abcde for example..if several parties offer up public keys?

 

[Peter R]

Good question. I think using addition might work then:

Q_a = k_a * G
Q_b = k_b * G
Q_c = k_c * G
…
Q_z = k_z * G

And then

Q_a + Q_b + Q_c + … Q_z = (k_a + k_b + k_c + … k_z) * G

which means

Q_abc…z = k_abc…z * G

In words, the sum of the public keys would be a new public key that can be unlocked by a private key equal to the sum of the individual private keys.

Try it out and report back!

 

[Inca]

Thanks Peter. I'll have a look this week. Exciting.

Pete

 

[Peter R]

I should add (perhaps you know this), but the addition has to be done according to the rules for adding elliptic curve points in the case of the pubkeys, and modulo the elliptic curve's n parameter when adding privkeys.

 

[Inca]

Peter R,

I would be grateful if you would write the equation in long form. I am no mathematician!

 

[Peter R]

@Inca

Unless you're using something like Mathematica, it can be difficult to write custom code to do the modulo arithmetic and point additions. But there should be lots of existing code to play with. For example, I think Vitalik's pybtctool does everything you need:

 

[Inca]

So your first example is functional:

Yes, this is possible. Assume Alice knows private key k_a and Bob knows private key k_b. They can each calculate public keys:

Q_a = k_a * G
Q_b = k_b * G

where G is the base point of the elliptic curve. If Bob tells Alice Q_b, then Alice can construct a new public key

Q_ab = k_a * Q_b = k_a * k_b * G

>>> priv1=sha256('this is one')
>>> priv2=sha256('this is two')
>>> pub1=privtopub(priv1)
>>> pub2=privtopub(priv2)
>>> priv1
'2b458382cfc3577db27c3b59114152f6e0d255c557106101cb88c1fae65c478a'
>>> priv2
'a426868cfc6232bb7884666907d5835cdb3b1e97174fbb7e9b350360814fe9a3'
>>> pub1
'04e6d02c22fdba1ad143329beda73fd8d88e37ef59eb79a7608f8f43f3df98a73365cc650adc7bf693c211379c717b62ad9864759aea066b9568bf577f4331b5fb'
>>> pub2
'04d4d6955fbe15fca70154b84f380a0e812566cd998e2334fc1bc27b74b960b7b51bec9bfd3ab788fcd6be69b6319f0f5b5a6e4ba30b19867e53c48194e4d33266'
>>> pub3=add_pubkeys(pub1,pub2)
>>> priv3=add_privkeys(priv1,priv2)
>>> pub3
'04c401cac8aa964a6c00cfd221a0738663812ac06b3430b8e60c9ebe015ddae94bd3112244003be5c19e565ff8de58e49740c71a6ee8323a0d01e3dc83879ce482'
>>> priv3
'cf6c0a0fcc258a392b00a1c21916d653bc0d745c6e601c8066bdc55b67ac312d'
>>> pub4=privtopub(priv3)
>>> pub4
'04c401cac8aa964a6c00cfd221a0738663812ac06b3430b8e60c9ebe015ddae94bd3112244003be5c19e565ff8de58e49740c71a6ee8323a0d01e3dc83879ce482'
>>> pub3
'04c401cac8aa964a6c00cfd221a0738663812ac06b3430b8e60c9ebe015ddae94bd3112244003be5c19e565ff8de58e49740c71a6ee8323a0d01e3dc83879ce482'

 

[Inca]

After playing further..

The add_privkeys and add_pubkeys function in pybitcointools only allows two keys to be combined per operation. But simply adding the output to remaining keys (to n) sequentially ends up with a combined private or public key pair which do match! So it works Peter R!

This is interesting to me because it means that it is possible to assemble a bitcoin address from multiple public keys whilst keeping the private keys separate and piecemeal.

 

[Peter R]

Nice work Inca! I'm glad to hear that it worked out! Thanks for keeping us posted on your progress.

 

[Inca]

An extension of this is multi sig which i am playing with in python currently. Vitalik butterin's pybitcointools is really quite remarkable.

 

[Vitalik Buterin]

> What if there are more than two people in this situation. Does this work if there are 3 or more keys involved?

I just tested it, and it does:

http://vitalik.ca/files/pybitcointools_key_test.py

Output:

a ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb
b 3e23e8160039594a33894f6564e1b1348bbd7a0088d42c4acb73eeaed59c009d
c 2e7d2c03a9507ae265ecf5b5356885a53393a2029d241394997265a1a25aefc6
x 3738952c73a591f7943876ce346e1328ac292f148b2bee165e946d4957aef7dd
A 044da006f958beba78ec54443df4a3f52237253f7ae8cbdb17dccf3feaa57f3126da0a0909f11998130c2d0e86a485f4e79ee466a183a476c432c68758ab9e630b
B 0410c283aac7b35b4ae6fab201d36e8322c3408331149982e16013a5bcb917081ce524905eae685ebf6dcc0361402ced1b7aba0bfdac66b52a4ed8ef0493d89675
C 0492a762e0123945455b7afe675e5ab98fb1586de43e5682514b9454d6edced724357ebd928cf9e425085c4acf5575d41b69952cfdabd982967ab248b2870c3c57
X 04015f54a9e217aa5089c68361fd2852f2f7f8e8b1aced3ebd91a2d343cc5249ec00933832ef65b660f6acfa1caf3f295815918f49f0edb13f83897d2dcb4f9177
X2 04015f54a9e217aa5089c68361fd2852f2f7f8e8b1aced3ebd91a2d343cc5249ec00933832ef65b660f6acfa1caf3f295815918f49f0edb13f83897d2dcb4f9177

 

[Inca]

Using pybitcointools I worked it out Vitalik. Thanks for dropping by

 

[theZerg]

@Peter_R I haven't looked much at the elliptical curve math involved. Does G need to be mutually agreed upon for all participants or the opposite (kept private from all other people)?

 

[Peter R]

@theZerg
The participants need to agree on the elliptic curve, the base point (G) and an integer (n) of order G: {CURVE, G, n}. It's really no different than the things we need to agree on for the ECDSA signatures used in Bitcoin.