Topic: Backups in a Multi-sig world (Read 2183 times)

I've talked a lot before about various ways to do various multi-signature schemes, with and without OP_CHECKMULTISIG's help.  Let me start by repeating the most important one, which is what I plan to implement in Armory:  Two-factor authentication, computer+phone, without third-party.  This is made possible because of Armory's deterministic, watching-only wallets, and BIP 0010 to transfer data to the cell phone.


Setting up the wallets:

• Create Wallets A and B on the primary computer (or an offline computer if you want to make sure both wallets never touch the same online computer)
• Print paper backups of A and B
• Scan QR code on paper backup B with phone
• Delete private keys of wallet B on the primary computer (Armory has an option for deleting private keys only, converting to watching-only wallet)
• Put both paper backups away in a safe place (safety-deposit box preferred)
• (optional) Put watching-only copy of wallet A on the phone (if you want to give out addresses from your phone)

Now to give out addresses:

• Device gets next unused public key from its own wallet, n, and then gets public key n from the watching-only wallet of the other device
• Generate 2-of-2 multi-sig address

To spend the money:

• Computer generates transaction like normal.
• Create BIP 0010 Tx Distribution Proposal (TxDP; I really need a better name for this) and add signature for wallet A
• Display BIP 0010 packet as a QR code on the screen (or multiple codes, if it's a long tx)
• Phone scans QR code(s), displays transaction details, asks user to confirm
• Phone adds signature B, and connects to the network just long enough to broadcast it to 3+ nodes

To recover loss of one or both devices

• Restore both paper backups
• No per-address/tx backup information needed, at all

BIP 0010 guarantees that the phone doesn't need the blockchain, yet it can still verify the details of any given transaction.  The determinism guarantees that we can create an infinite sequence of these multi-sig addresses and each one will be unique and unpredictable to strangers.  By designating these wallets are dedicated to 2-of-2 transactions, we can guarantee that we only use "parallel" public keys in both wallets:  that way you don't have to check all combinations of keys in wallet A with all keys in wallet B:  you only have to check publicKeyA(i)-and-publicKeyB(i)

A similar scheme can be concocted for ((A and B) or C), using a designated full wallet for A, and requesting a watching-only wallet for B (which is the third party).  C is then created on an offline computer and never touches the internet, backup is stored in safety deposit box.  Again, you only use ((PubKeyA(i) and PubKeyB(i)) or PubKeyC(i)) to keep a simple search space in case of a restore-from-backup situation.

-----

There are lots of magical things you can do with ECDSA, but to me they feel like hacks with multi-sig right around the corner (except for the [[A and B] or C] case).  They are secure, but they usually come with caveats:  such as requiring one party to give up their private key to the other party, who then gets full control of the funds--works fine in some situations, but a complete fail here, since giving them one private key is giving them all of them with a determinstic wallet.

How are signatures created when the phone or computer needs to spend some coins?

I'm told it IS possible to break a single ECDSA key in half and then have a complete signature generated without either device ever knowing the entire key, but, if I recall correctly, the solution involves several communication round trips between the devices and some very sophisticated cryptography.  The multikey solution is much simpler.

If I'm wrong, then great! The single ECDSA key solution will get adopted for wallet security and multisigs will only be used for escrow.

RE: makku's question "How do you identify transactions that belong to you in the first place?"

I think it is wrong to think of coins involved in a multiparty multisignature transaction as "belonging to you."  They don't belong to you-- you have to agree and cooperate with other keyholder(s) for the transaction to be spent.

You are involved in the transaction, but you need some extra information that isn't in the blockchain to know how you are involved (are you an arbitrator? a person getting paid?  a person paying somebody? something else?).

The most common use case I can see for multisig is to allow a user to use their smartphone (or a 3rd party security service) to sign their transactions.  This alone was the urgency for getting P2SH working.  I believe every other use case for multisig lacks mass appeal, they will only be used by users advanced enough to understand backups.

The custom transaction type for that most common use case is ((A AND B) OR C).

Keep in mind that the whole point of P2SH is to ensure that no single device ever has access to the money.  If a single deterministic seed is used to generate the wallet (specifically, if any machine gets to generate key C - which can spend funds alone), that objective is broken.  If we assume that the deterministic seed should be generated in two parts in the first place, the solution sort of falls in our lap as a side effect.

Here is the typical workflow as I'd see it, when a user wants to make a brand new wallet:

• User downloads a free app for their smartphone meant as a mobile companion to Armory
• User uses the smartphone to generate a deterministic seed.
• User does the same thing with Armory on the PC.
• An ECDSA derivation of the seed is sent from the smartphone to the PC.  This allows Armory on the PC to calculate a stream of the P2SH scripts in combination with the seed created on the PC.  Armory knows how to calculate the private key for A.  The smartphone knows how to calculate private key B.  Neither device can calculate private key C unless the user explicitly allows both private keys to be on a single machine (e.g. in a "recovery mode" where the user types both passphrases into the computer).
• The user has to back up the deterministic seed from both the phone and the PC to reconstruct their wallet.
• Anything other than ((A AND B) OR C) remains encumbered with the need to take backups.

The more I think about it, the more I realize that this workflow is possible without P2SH: it's also possible with simple elliptic curve multiplication.  Smartphone generates a stream of key A's from a seed, computer generates a stream of key B's, and given the public keys from the smartphone, the computer can generate the public key for C, which is used as the receiving address.  Recovery remains the same: two seeds instead of one.

No, you don't need to back up after every transaction.  You need to back up after every address generation, just like you need to do now.

And as I explained earlier, even with multiparty keys where no one party knows more than a single key used to generate the script/address, you can still do it if at least one party stores an identifier along with their key and all of the parties are able to identify which of their keys was used based on that identifier.

This is a problem (the big problem I mentioned), but it's only tangentially related to backups. How do you identify transactions that belong to you in the first place? With P2SH multi-sig, the sender knows he is transferring money to you, but there is not sufficient information in the blockchain for you to figure it out. The solution to this problem (say, DHT of P2SH scripts) is also a solution to the backup issue.

@up

OK, thanks for clearing that matter up, guys. Clearly I was wrong, and P2SH is not as bad as I thought.

Shadow,

I made an oversight in one of my earlier posts, and the tried to correct it later (scratch that, I thought I did, but that must've been a different thread where I tried to correct myself on this topic...).   I will clarify both for you, and so others can correct me if I misunderstand it:

-- Regular transactions will not need to be backed up immediately.  The only thing about Luke's BIP 18 is that regular transactions might have a different "format", but you'd still always be able to identify them from the deterministic backup you made 10 years ago.

Multisignature transactions fall into two categories:  multi-sig with yourself (computer + phone for two-factor auth), and escrow/contracts multi-sig

-- For multi-sig with yourself, you should be able to identify those transactions without backups.  (I didn't think of this at first, but Gavin corrected me)  You can use two synchronized deterministic wallets, and all 2-factor-auth transactions will use address n in your computer wallet and address n on your phone.  Then, since it uses a constant format to combine those two addresses, search the blockchain for such addresses is no harder than a regular wallet;  as long as you know which two wallets were used for the 2-of-2 transactions.   You only have a couple permutations and orderings to try if you have lots of wallets.

-- For multi-sig with others, this is where it gets fuzzy.  You do have to backup after every multi-party transaction, because you have no way of identifying your own transactions with any P2SH/OP_EVAL type system, without the other person's addresses.  So that is where the real issue might be.

But there are two things to note about this scenario:

Let's say you lost all your computers and restored from backup and you were using regular OP_CHECKMULTISIG.  Well yes, you can identify the tx as your own, but who the hell owns that other address?  Shit, I lost all that information with my computers...  It seems you have some critical (but not necessarily sensitive) data that needs to be stored on each transaction regardless of the multi-sig system system used.

Also, I generally approve of the goal of P2SH or other OP_EVAL strategies, I just started this thread to fully understand the consequences of it.  I'm pretty sure it's not nearly as bad as I originally, incorrectly thought it was.

@ShadowOfHarbringer, it depends on how you use P2SH. etotheipi is going a little overboard in that regard. With (currently) standard transactions, you shouldn't need to back up P2SH scripts as those scripts are fully recoverable from your wallet. However there are new types of transactions/crypto protocols on the drawing board would involve both your key and one or more keys not currently in your wallet. The fact that you are involved in that transaction would become opaque with P2SH, and some system would have to be put in place to recover the scripts involved. That is a big problem, but a solvable one.

Many thanks @etotheipi.

Untill this post (and your other posts in BIP18 topic), i haven't collected enough data to make an opinion in the BIP16/BIP17 debate.

Now I have a clear point on the matter: P2SH sucks totally and should be deprecated. A solution which requires backup of wallet after every [P2SH] transaction is flawed by definition. It has always been the standard that making a backup of wallet secures you for the future transactions (unless you generate more than 100 addresses in the wallet and use the 101-th generated address). This was a very good and well-thought over standard created by Satoshi himself.

I find changing it highly irresponsible & potentially dangerous for the network.

Unless, of course I am misunderstanding something (sb please correct me then).

One way or another, you have to store the scripts.  Everything being discussed here is optimization and implementation detail.  You have to think of the current situation with single signature transactions as an optimization of the more general case.  The optimization is that you don't need to store the script because the address type specifies that it is a single signature transaction.

You could have a set of standard transactions that are referenced by a number and one or more modifiers and parameters…for example:

   scriptType, [modifiers], [parameters]

An M of N transaction might have a type of 1.  The modifiers would specify the M and the N.  The parameters would specify the publicKeys (or the privateKeys if you have them).  A table could be maintained that maps scriptTypes to transaction templates.  A custom transaction could be represented by a type of 0 with the modifier being the full template for the script.  With this information, you could reconstruct the script and its hash (the address).

I'm pretty sure that you can spend a transaction that hasn't been confirmed, but only if both transactions end up in the same block.

Also, in cases where not all keys are known to any one party, there will need to be a protocol of some sort to generate P2SH addresses.  Since it doesn't exist yet, I'm sure we can lobby for some sort of replay feature to be included.  See my previous posts in this thread for details on how that could work.

Sure, but you'll lose any donated money that hasn't received enough confirmations to claim yet.

(Mine OR Yours) is not the sort of transaction anyone would use to store their money.  The only safe thing to do when getting paid by a transaction like that is to immediately send the money to a different address, hopefully of the form ((Mine AND My Agent's) OR Mine).

Not sufficient. What if I send money to you with a return address in case you don't claim it (your-key OR my-key)? The backup won't have my public key, so there's no way to recreate the P2SH hash.

If you're using multisig to secure your wallet, then I think backup could be "free" ; all the involved multisig keys could be derived predictably from singlesig keys that you'll already need to backup. Disaster recovery from a lost wallet would mean importing all the backed up singlesig keys, then deriving (say) the first 1000 multisig ScriptSigs that would have been derived from those keys and scanning the blockchain for transactions involving those (and, hand-wave, hand-wave, doing something smart to derive more than 1000 in case it looks like more than 1000 were used).  (or, in other words: what kjj said)

If you're using multisig for escrow involving other people... then the escrow transaction has to be recorded and backed up, including all the keys involved.  In that case I'm pretty sure you'll want to record and backup other information about the escrow-- like "100 BTC escrow to my cousin Bob; release them if he's still not smoking on June 1."

Backup should be part of the user experience design for the escrow function; for example, I think a lot of escrows will an associated date, so the client should store the escrow transaction id AND the public keys involved in the escrow AND a "remind me to do something on June 1" AND (maybe) a link to my Address Book entry for Bob so I can call him on June 1. For me, I think the best way to backup that kind of escrow information would be for the client to send me an email containing all of that stuff in a standardized mini-file-format; I'll let gmail archive it and that would be my emergency backup.

So, emergency recovery of a lost wallet would then be:

1. Recover all private keys from paper backup (or whatever the singlesig backup solution is).
2. Re-import all escrows that involve other people from email archive.


RE: Bytecoin and "OR BACKUP_KEY" :  In either the OP_EVAL or the BIP16 case you need a new type of 'standard' transaction (and bitcoin address) to make that work.

It should be fairly easy to recreate P2SH addresses as long as the keys aren't lost.  Assuming a standard for key ordering, all else that is needed is an identifier that can be negotiated when the keys are created.  Sequence numbers or hashes should be enough to synchronize the two keysets.

Basically, if everyone is using deterministic key sequences, they can all store the seed and when they need key N, they just make key N.  But, if anyone is using random keys, then they need to store the key indexed by (the hash of or the sequence of) at least one of the other keys.

This is the exact reason I came up with OP_EVAL rather than something functioning along the P2SH lines. With a script containing two nested OP_EVALs I can implement multisignature transactions of the type (BLAH... AND BLAH... OR BLAH...) OR BACKUP_KEY so that the transaction can always be identified provided you have the public backup key and always redeemed provided you have the private backup key.

ByteCoin

There has always been this nagging discomfort with me with regards to P2SH...  and now I finally know what it is...  Backups.  I have put a lot of work into deterministic wallets and paper backups in Armory,  to try to solve one of the most frustrating modes of failure: HDD failure or overwrite combined with either no backup or a stale backup. 

The issue that I am finding with P2SH (which would happen with any similar multi signature scheme that hide addresses),  is that the user is back to requiring a persistent backup solution, because he cannot even identify, much less spend his multi-sig-encumbered coins if he doesn't have the P2SH script.

On the upside,  the P2SH scripts are not nearly as sensitive as private keys.   But they are just as important! If you lose them,  you (probably)  lose the money behind it...

This presents a serious implementation issue:  how do I modify Armory to accommodate backing up the scripts.   I had originally made space for them in the wallet file but now I am realizing that will not enable easy backups (not everyone wants to backup their wallets remotely,  encrypted or not).  So I'm thinking that I should instead create a separate P2SH scripts file,  separate from the wallet,  allowing the user to place it in,  say,  the Dropbox folder.   If the user doesn't want the data stored unencrypted (for privacy reasons),  asymmetric encryption can be used to encrypt each script before appending it to the file.   It would seem that there is no grace time for backups like the Satoshi wallet has (generating 100 address pool)   because you don't know what scripts you're going to receive until you actually get/create them.   They need to be backed up immediately. 

On the other hand,  if these multi-sig scripts require multiple parties,  they are like to have the scripts too,  and you might be able to request them. But this could be a royal pain in the ass if you do business with a lot of different people...

Any recommendations are welcome.  Obviously,  tying the user to dropbox is sub-optimal, but I'm not seeing any other solution that a regular user could put up with that would provide the appropriate level of backups.   Using standard OP_CHECKMULTISIG would solve this,  but there are other reasons it is not being adopted (though I always believed it should be an option even if it isn't the recommended,  but this is a different discussion...)