Can m-of-n secret sharing generate a bitcoin public key without knowing the private key
while still empowering a future m-of-n quorum to generate that private key?
Yes.
Exploit the distributive property of elliptic curve operations, i.e.
G*(A + B + ... + X) = G*A + G*B + ... G*X
where * and + represent elliptic curve multiplication and addition.
Simple example: 2-of-3 secret sharing among Alice, Bob and Carol.
The procedure
Step 1.
Bob and Carol collaborate to create raw PrivKey0, and publish the hash. Each party keeps their own copy of PrivKey0.
Alice and Carol collaborate to create raw PrivKey1, and publish the hash. Each party keeps their own copy of PrivKey1.
Alice and Bob collaborate to create raw PrivKey2, and publish the hash. Each party keeps their own copy of PrivKey2.
Alice Bob Carol
PrivKey2 + +
PrivKey1 + +
PrivKey0 + +
Step 2.
The group generate PubKey0, PubKey1, PubKey2 by performing Bitcoin secp256k1 elliptic curve multiplication on the PrivKeys.
Then they perform elliptic curve addition PubKey0 + PubKey1 + PubKey2, which creates a group public key.
Bitcoins then get sent to an address generated from the group public key.
Step 3.
When it comes time to retrieve bitcoins, two people from the group form a quorum, combine their resources and gather the PrivKeys.
(The combinatorial distribution illustrated in the table above ensures that two people are necessary and sufficient to source PrivKey0, PrivKey1 and PrivKey2.)
Elliptic curve addition PrivKey0 + PrivKey1 + PrivKey2 generates the group private key, unlocking the bitcoins. Done!
The private key never manifests itself at all until the quorum gathers, collocates information, and performs the elliptic curve operations.
This is safer than secret sharing schemes that need to start with some party recording the group's private key.
Note:
If the key construction goes wrong because a rogue member provides a false PrivKey, checking the hash exposes the perpetrator.
Appendix: Larger Groups
Combinatorial arrangements cover any size group.
Example
3-of-6 secret sharing requires "6 choose 4" = 15 PrivKey combinations.
3 people are necessary and sufficient to construct the secret.
There are 20 ways to form a quorum of three people out of six (6 choose 3 = 20).
Alice Bob Carol Dave Edna Frank
PrivKey14 + + + +
PrivKey13 + + + +
PrivKey12 + + + +
PrivKey11 + + + +
PrivKey10 + + + +
PrivKey 9 + + + +
PrivKey 8 + + + +
PrivKey 7 + + + +
PrivKey 6 + + + +
PrivKey 5 + + + +
PrivKey 4 + + + +
PrivKey 3 + + + +
PrivKey 2 + + + +
PrivKey 1 + + + +
PrivKey 0 + + + +
Biggest drawback to combinatoric secret sharing: combination table size increases exponentially with the number of participants.
Poll
