Security of [ (A and B) or C ] transaction types

[etotheipi]

I guess this isn't so much about security, as it is more about privacy.  I really like the concept here, that you send yourself much, such that the only way to spend it is to get a second signature from a third-party who will do a two-factor authentication before offering their signature.

(A and B) or C

A:  Your normal, online wallet.
B:  Third-party verification website
C:  Backup key stored in safety deposit box

Casascius described this best:  it can be implemented such that when you tell your computer to spend some funds from one of these transactions, it will sign with private key A, and send the partial transaction to the third-party who will then, say, send you a text message asking "Did you authorize 23.7 BTC to be sent to address 1Ptk21Fjk38?".  When they receive confirmation, they sign it and broadcast it, making it final.  If the third-party goes out of business, you can always go to your safety deposit box to get key C, which is sufficient alone to spend the funds.

Here's my problem with this though.  There are numerous reasons it is good to use a different address for every transaction.  However, in this case, that different address amounts to changing A every time.  The problem is what about B and C?  No matter how you do it, the address of B and C must be visible to the blockchain at some point (either in the original transaction, or after getting spent in the case of Casascius' OP_CHECKSIG modification proposal).  If B or C is the same on every one of these transactions, then you have now created a verifiable link between every address A you ever used.  So how do you handle creating transactions that send money to this (AandB)orC-encumbered account and have different B and C addresses?

Let's look at Addr/PubKey B:
This is the easy one.  There are three options here:
(1) Third-party gives you a single key to use on every transaction.
(2) You periodically download a new batch of 1000 publickeys/addresses from B to be used until you run out and get more.
(3) The application queries the third-party and requests a new addr/key to be used before each transaction is constructed.

Option 1 is clearly the worst, but it's the easiest.  (If the service uses the same single addr/pubkey for every user, we don't have this problem, but that puts all users at risk if that private key is leaked...I wouldn't use that service)
Option 2 is probably the best, as it allows you to sync online or through an update packet every now and then, but mainly remain offline and sign transactions remotely.  (This is most relevant for systems that are entirely offline that want to sign these transaction types.
Option 3 is the best for always-online services, but puts a burden on you to have internet and for the 3rd party to be available, just to send money via this kind of transaction.

The problem here is that if you pick option 2 or 3, you have to develop extra infrastructure to handle the communication of keys/addr between parties.  Not terrible, but it's not trivial, either.

For Addr/PubKey C:
This is your key in your safety-deposit box.  This is the part that's a little more difficult.   The options are (1) and (2) above, because you can't query for a new address every time even if you wanted to.  My main concern is that if you use a batch of 10,000 keys, you probably won't be printing the QR codes of the private keys onto paper into your safety deposit box (it'd be a lot of pages).  But who knows what happens if you only store it on a USB key:  you might get the USB key out of storage to find out the memory is corrupted.  Sure, store the keys on multiple USB sticks and some ZIP disks.

This may not actually be a problem.  Perhaps Option 2 for both can just store 1,000,000 keys/addresses and you'll never run out.  But it is a concern/decision that will have to be addressed when this becomes a standard transaction type.  At the very least, software developers might consider including a feature allowing you to store pools of keys/addr to be used just for this purpose.  You would have a third-party pool, and a backup pool.  You "fill" both of them when you start this kind of account and the client will automatically pull addresses from each one into B and C fields every time you want to construct this kind of transaction.

[ByteCoin]

It was precisely this issue that prompted me to devise this solution.

ByteCoin

[kjj]

Let's look at Addr/PubKey B:
This is the easy one.  There are three options here:
(1) Third-party gives you a single key to use on every transaction.
(2) You periodically download a new batch of 1000 publickeys/addresses from B to be used until you run out and get more.
(3) The application queries the third-party and requests a new addr/key to be used before each transaction is constructed.

Option 1 is clearly the worst, but it's the easiest.  (If the service uses the same single addr/pubkey for every user, we don't have this problem, but that puts all users at risk if that private key is leaked...I wouldn't use that service)
Option 2 is probably the best, as it allows you to sync online or through an update packet every now and then, but mainly remain offline and sign transactions remotely.  (This is most relevant for systems that are entirely offline that want to sign these transaction types.
Option 3 is the best for always-online services, but puts a burden on you to have internet and for the 3rd party to be available, just to send money via this kind of transaction.

The problem here is that if you pick option 2 or 3, you have to develop extra infrastructure to handle the communication of keys/addr between parties.  Not terrible, but it's not trivial, either.

You have to do this no matter what.  If you use option 1, you need a system to communicate your keys to the signing service, otherwise it won't know which user's policy to apply.  If the system uses a fixed policy for every user, the attacker will just steal slightly less than X BTC per user per day, or whatever.

Also, you need a way to present the partially signed transaction to the service, so that it can finish signing it (if policy allows) and send it to the network.  I don't think that you can avoid this step by using sequence and lock time, yet.

For Addr/PubKey C:
This is your key in your safety-deposit box.  This is the part that's a little more difficult.   The options are (1) and (2) above, because you can't query for a new address every time even if you wanted to.  My main concern is that if you use a batch of 10,000 keys, you probably won't be printing the QR codes of the private keys onto paper into your safety deposit box (it'd be a lot of pages).  But who knows what happens if you only store it on a USB key:  you might get the USB key out of storage to find out the memory is corrupted.  Sure, store the keys on multiple USB sticks and some ZIP disks.

This may not actually be a problem.  Perhaps Option 2 for both can just store 1,000,000 keys/addresses and you'll never run out.  But it is a concern/decision that will have to be addressed when this becomes a standard transaction type.  At the very least, software developers might consider including a feature allowing you to store pools of keys/addr to be used just for this purpose.  You would have a third-party pool, and a backup pool.  You "fill" both of them when you start this kind of account and the client will automatically pull addresses from each one into B and C fields every time you want to construct this kind of transaction.

The emergency key is going to cause problems, no matter what you do.  Most people that don't really care about anonymity will probably prefer to generate, store and use a single key C.  The people that really do care about anonymity will want to make a new one each time, and deal with the hassle of storing it safely.

I really can't think of any way to avoid having to make the trade off.  Mechanic's shops usually have a sign that says "Fast, Good or Cheap.  Pick any two."  I think we are going to need to think in terms of "Anonymity, Security or Convenience.  Pick a linear combination where the vector sum is less than 2."

[etotheipi]

Just for clarity of point, there's two separate events here:

(1) To create the transaction into the [(A and B) or C]-encumbered account, you need three addresses or public keys.
(2) To spend one of these encumbered transactions, you need to contact the third-party with a partially-signed transaction. (or use backup key, C)

These two situations have completely different use-cases.  Perhaps you make a weekly deposit to such account which is used as a savings account.  For years you might only use transaction (1), and only use (2) one time to move the money to a seller for a house.  There's no way around contacting the third-party to use (2)... this was actually the point of the entire exercise.  But unless you're using a pool of keys or one key for everything, you can't even give someone your own address without contacting the third party to get another B address.  If you use a single key for B, then all your transactions are linked.

I suppose the part about your own backup key is made easier if you use a Private-key-generator.  The actual secret is a 256-bit random number, A.  Then you can compute a semi-infinite sequence of private keys through:

Code:

PrivKey[i+1] = hash256( A xor PrivKey[i] ) 

or something to that effect.  You create the generator on the offline computer, and compute and copy 100,000 public keys to your online computer key pool.  Then you only need to store the single generator key A in the safety deposit box, which can be stored in a single QR code on one sheet of paper.  I'm sure I'm not the first person to think of this generator idea, but it seems like a feasible way for regular online wallets too.  That way you can backup the wallet once, ever.