Yes please, mods...

Relatedly, approximately how long are we looking at before we have features enabling multi-signature escrow in the client and we can start building stuff that relies on them?

So isn't multisig part of BIP 16 and now implemented?

Multisignature adoption has to follow a multi-step process:

1. A majority of miners have to put multisignature transactions into blocks so they get confirmed.

2. A significant fraction of everybody else has to relay multisignature transactions so they reliably get to the miners (preferably more than 50%).

3. Depending on what you're using multisig FOR (escrow? secure wallets?), more technical infrastructure will need to be built.

4. After all of the above is done... y'all will be able to reliably use multisignature transactions.

April 1'st was the first step and we're doing pretty well with the second step, version 0.6 has a lot of support on the network already.  In fact, it is going so well I think we should turn on the 'addmultisigaddress' JSON-RPC method so people can start creating and experimenting with multisig with the 0.6.1 release.

Alright, here goes...

I have two major ideas planned for multi-signature transactions to go into Armory, as soon as I finish up with the some other priorities.  The first one is fairly straightforward, so I'm just posting for reference.  The second is a bit more controversial and could use some ironing out.

(1) Two-factor authentication without a third-party

There's a more-general version of this for two equally-capable devices, but I'll be implementing this version due to its simplicity and it accommodates one of the most desired use-cases of multi-sig

Setup Wallets:

• Create two new wallets in Armory, A and B
• Print off paper backup of each wallet.
• In wallet B, choose "Remove/Delete Wallet" and delete just the private keys to make it a watching-only wallet, B'
• Scan paper backup B with smartphone
• Stash both paper backups in safe or safety-deposit box

Now your online computer has wallet A (full) and B' (watching-only) and your phone has B (full).  I will probably make a special wallet format for 2-of-2 wallets that makes this process even simpler (and symmetric:  A+B' on one device and A'+B on the other device).

Generate Addresses:

• On computer Armory:  generate new address for this special wallet (A+B')
• Armory finds next unused address index, n, in wallet A.  Computes PubKeyA(n) and PubKeyB(n).
• Create 2-of-2 multisig address

Spending coins:

• On computer, construct transaction as normal.  "Send" button is greyed out.
• Click "Sign for wallet A"
• Signature added, transaction is converted to BIP 0010 packet and displayed as a QR-code (or sequence of them).
• Phone scans QR code(s), displays transaction details, verifies signature A, requests confirmation
• Phone adds second signature, B, and connects to the Bitcoin network and broadcasts

I will probably find QR codes to be difficult to use here.  I'm thinking of other ways I might do it:  perhaps send data to the phone via special email that can automatically be detected by the phone and parsed.  Unfortunately it would never fit into a text message...

But a sequence of QR codes may not be bad... you can tile a lot of QR codes on the screen, and phones are very fast at scanning them.


(2) Buyer-Seller Escrow, with or without third-party

Alice posts an item on craigslist, knowing that unknown, untrusted Bob will try to buy it.  In this case, Alice is the seller and will set the "Risk Deposit" (could also be "Escrow Deposit").

• Alice makes craigslist posting identifying the item for sale, the price (25 BTC), and the desired "Risk Deposit" (20%)
• Bob finds the posting and emails Alice saying "I'll buy it for 20 BTC, 20% deposit is fine, here's a public key, and let's use a third-party Charles."
• Alice agrees so she obtains a public key from Charles, and constructs a very wacky transaction:
  
• Inputs:
  
  • (1) Alice 4 BTC (20% deposit) -- signed using SIGHASH_ANYONECANPAY
  Outputs:
  
  • (1) 28 BTC to TwoOfThree(PubKeyA, PubKeyB, PubKeyC)
  • (2) Alice's change output, if necessary
• Sends incomplete tx to Bob
• Bob verifies that PubKeyC belongs to Charles.
• Bob creates a perfect-sized input of 24+fee BTC, adds it to the tx, signs and broadcasts (Alice's sig is still valid because of ANYONECANPAY)

Now there is 28 BTC locked up in the network requiring two-of-three signatures from Alice, Bob or Charles.  This could be a 2-of-2 tx without Charles, but if one party disappears (before tx completion) the money will be locked forever.

Three possible outcomes:

• Everything goes smoothly, Alice creates "completion transaction":  Inputs:  2-of-3 for 28 BTC and an optional fee input,  Outputs:  Alice 24, Bob 4.  Signs and sends to Bob who signs and broadcasts
  
• Something went wrong, Bob needs a refund.  He constructs tx:  Inputs: 2-of-3 for 28 BTC and optional fee,  Outputs: Alice 4, Bob 24.
• DISPUTE:  Charles contacts both parties, figures out who gets the money -- assume it's Alice -- then Charles creates a Tx;  Inputs:  2-of-3 for 28 BTC + fee;  Outputs:  Alice 20, Charles 8;  signs and sends to Alice who signs and broadcasts.
  

In this case, the "Risk Deposit" serves two purposes:  (1) guarantees that Bob has incentive to complete the transaction after he receives his merchandise, and adds incentive to the seller not to randomly back out and leave the multi-sig money stranded. (2) It's an already-included, equally-funded-by-both-parties fee, in case the tx needs arbitration.

Someone had brought up the possibility that only the "loser" of the arbitration should pay, and the "winner" would get their risk deposit back.  I'm not entirely sure which is better...

While many of these steps look complicated, I think my GUI-fu is good enough to make a lot of this transparent.  Third-parties can register to be included in a global list on most clients (to retrieve and verify addresses).  Users will not see all the script magic going on in the background, they just have to enter their amount, and their risk preference.  But of course, I have to iron out the under-the-hood stuff, first, so that I can implement it soundly and then make it transparent to the user...

I am still hoping for a multisignature paper only solution to make secure cash that can be spent at a store just as fast as a credit card or dollars.
[Edit]
The output private key is not active until point of sale when the final signatures are presented and it becomes sweepable.

Sally presents a bitbill to buy groceries. Bob the clerk scans the public key and sees that there are adequate funds available, but are escrowed. The final private key is given from Sally's key book and the bitbill is loaded with value which is then instantly swept with the change as another escrow (using the public key from the next key in the key book) to the next bill in the series. A receipt is given showing the escrowed funds available on the next bitbill in the series.

This can all be done with paper. Electronics can replace or add to any of the steps. The nice thing about paper is that it is cheap and easy to replace if lost or stolen. If you lose only your bitbills, they are useless without the key book and you can simply recover a backup and print a new bitbill checkbook.

Multisig has nothing to do with 51% attacks.