Novel Application: Two-of-three Signature Scheme

[casascius]

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.

[1714017933]

1714017933

[1714017933]

1714017933

[1714017933]

1714017933

[1714017933]

1714017933

[db]

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]

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]

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.

[Meni Rosenfeld]

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.