Bitcoin Forum
May 26, 2018, 10:17:57 PM
 News: Latest stable version of Bitcoin Core: 0.16.0  [Torrent]. (New!)
 Home Help Search Donate Login Register
 Pages: [1]
 Author Topic: Novel Application: Two-of-three Signature Scheme  (Read 1264 times)
casascius
Mike Caldwell
VIP
Legendary

Offline

Activity: 1386
Merit: 1039

The Casascius 1oz 10BTC Silver Round (w/ Gold B)

 December 02, 2011, 09:29:25 AM

I can't stop thinking about new applications for Bitcoin ever since I learned the details about elliptic curve addition.

Anyway, I think I have come up with a very simple way where Alice can make a payment to Bob, Charlie, and Dave, but only when TWO of the three pool together and decide to combine their key material in order to unlock the payment.  Perhaps when Alice dies, she wants her money to be found, and puts one piece in her safe, leaves one piece with her mom, and puts the last piece in a safety deposit box.  I suppose this isn't elliptic curve addition, but it just got me thinking along those lines.

So, here it goes.

Alice generates two 256-bit random numbers, X and Y.  She uses X as a private key, and sends her bitcoins there.

Alice gives Bob X+Y.
Alice gives Charlie X-Y.
Alice gives Dave 2Y.

None of them know who has what.  When they get together, they use a utility and basically brute force all the combinations (there aren't that many, like six) until they find the funds left by Alice.

If Bob and Charlie get together, they'll find that ((X+Y) + (X-Y)) / 2 reveals the funds.
If Bob and Dave get together, they'll find that (X+Y) - (2Y/2) reveals the funds.
If Charlie and Dave get together, they'll find that (X - Y) + (2Y / 2) reveals the funds.

Companies claiming they got hacked and lost your coins sounds like fraud so perfect it could be called fashionable.  I never believe them.  If I ever experience the misfortune of a real intrusion, I declare I have been honest about the way I have managed the keys in Casascius Coins.  I maintain no ability to recover or reproduce the keys, not even under limitless duress or total intrusion.  Remember that trusting strangers with your coins without any recourse is, as a matter of principle, not a best practice.  Don't keep coins online. Use paper or hardware wallets instead.
1527373077
Hero Member

Offline

Posts: 1527373077

Ignore
 1527373077

1527373077
 Report to moderator
1527373077
Hero Member

Offline

Posts: 1527373077

Ignore
 1527373077

1527373077
 Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1527373077
Hero Member

Offline

Posts: 1527373077

Ignore
 1527373077

1527373077
 Report to moderator
1527373077
Hero Member

Offline

Posts: 1527373077

Ignore
 1527373077

1527373077
 Report to moderator
db
Sr. Member

Offline

Activity: 279
Merit: 251

 December 02, 2011, 09:53:21 AM

Can't you just use a transaction script that requires 2 of 3 signatures? I think this is what Open-Transactions will do to prevent Bitcoin banks from running away with the money.
dogisland
Sr. Member

Offline

Activity: 262
Merit: 250

 December 02, 2011, 09:57:18 AM

Can't you just use a transaction script that requires 2 of 3 signatures?

I think is a bit different to 2 or 3 signatures.

M of N transactions allow no individual to access funds. This use case Alice always has access to the funds, with the added benefit you could implement this right now.
casascius
Mike Caldwell
VIP
Legendary

Offline

Activity: 1386
Merit: 1039

The Casascius 1oz 10BTC Silver Round (w/ Gold B)

 December 02, 2011, 10:13:09 AM

Another simple scheme that would work for M of N where the desired M is N-1 for any N would be as follows:

Alice generates N large prime numbers (no limit on size), and gives one to each person, as well as the product of all the primes.  The bitcoins are sent to a private key consisting of the hash of all the factors sorted in ascending order.

If N-1 of the people get together and share their numbers, the missing factor can be determined by simple division.

This still leaves Alice with access to the funds.  Maybe that is desired, maybe it is not.

If Alice should be kept away from the funds, the following enhancement could work.  All of the N people agree on an EC private key, and give Alice the public key, but not the private key.  Instead of Alice sending the bitcoins to the hash of the prime factors, she combines that public key with the one given to her by the others.  Since all of the others have that private key, they are the only ones who can recreate the private key needed for spending when they successfully recalculate the hash of the prime factors.

Companies claiming they got hacked and lost your coins sounds like fraud so perfect it could be called fashionable.  I never believe them.  If I ever experience the misfortune of a real intrusion, I declare I have been honest about the way I have managed the keys in Casascius Coins.  I maintain no ability to recover or reproduce the keys, not even under limitless duress or total intrusion.  Remember that trusting strangers with your coins without any recourse is, as a matter of principle, not a best practice.  Don't keep coins online. Use paper or hardware wallets instead.
Meni Rosenfeld
Donator
Legendary

Offline

Activity: 2044
Merit: 1000

 December 02, 2011, 10:40:50 AM

Alice generates two 256-bit random numbers, X and Y.  She uses X as a private key, and sends her bitcoins there.

Alice gives Bob X+Y.
Alice gives Charlie X-Y.
Alice gives Dave 2Y.
Nice. Seems to work as far as I can tell. It doesn't really allow anything that wasn't possible before - Alice could just encrypt a private key, distribute the encrypted copy everywhere, and create an m-of-n shared secret for the password.

None of them know who has what.  When they get together, they use a utility and basically brute force all the combinations (there aren't that many, like six) until they find the funds left by Alice.
Doesn't seem to be a security risk if they do each know what they have.

Can't you just use a transaction script that requires 2 of 3 signatures?

I think is a bit different to 2 or 3 signatures.

M of N transactions allow no individual to access funds. This use case Alice always has access to the funds, with the added benefit you could implement this right now.
I'm not an expert on Bitcoin scripting but it should be possible to have a script that says "either a signature from this address, or 2 signatures out of these 3 addresses". Anyway, the OP's protocol has the advantage that there is less data in the block chain and no need for either different transaction types or fancy stuff like OP_EVAL.

Another simple scheme that would work for M of N where the desired M is N-1 for any N would be as follows:

Alice generates N large prime numbers (no limit on size), and gives one to each person, as well as the product of all the primes.  The bitcoins are sent to a private key consisting of the hash of all the factors sorted in ascending order.

If N-1 of the people get together and share their numbers, the missing factor can be determined by simple division.
You could also use a scheme like in the OP for a general M (I haven't thought it through but it should work). Alice chooses X_1,...,X_M and sends to the address corresponding to X_1. She sends to participant k the value $\sum_{i=1}^M i^k X_i$ (each knows what his serial number is). If M get together they have a basis for F^M (see Vandermonde matrix) so they can find X_1. If there are less than M then their set does not span (1,0,...,0) (otherwise the Vandermonde matrix with this row added would be singular) so they cannot find X_1.

This should be extendable to the case we don't want Alice to know the private key (maybe using homomorphic encryption).

In case you're unaware, there's work (spearheaded by Stephan Thomas) to create a protocol that uses ECC magic to have m-of-n transactions with a single signature and without having to recombine the private key, so the address can be used repeatedly while maintaining the status that m participants are required.

1EofoZNBhWQ3kxfKnvWkhtMns4AivZArhr   |   Who am I?   |   bitcoin-otc WoT
Bitcoil - Exchange bitcoins for ILS (thread)   |   Israel Bitcoin community homepage (thread)
Analysis of Bitcoin Pooled Mining Reward Systems (thread, summary)  |   PureMining - Infinite-term, deterministic mining bond
 Pages: [1]