Motivation:
Alice would like to pay Bob, but doesn't want the whole world (or even Bob) tracing her transactions.  Carol offers to receive Alice's coin and pay Bob with unconnected coin, but none of these parties trust each other— and Carol being able to steal coins makes Carol into a systemic risk, since the need for trust means that there can't be many Carols and Carol could be earning income on the side spying on Alices, or could get robbed, etc.

Oh, and they don't want to invoke novel cryptography or change the Bitcoin protocol.

Here I present a protocol where Alice can pay Bob by way of Carol where Carol can not rob them. The protocol requires four published transactions, but the transactions look like regular 2 of 2 escrow transactions (two escrow payments, two escrow releases) in the common case where everyone is honest. If Alice or Carol try to renege on their part of the protocol, it either cleanly unwinds or additional transactions are published to push through the transaction but without privacy.

A key concept behind this protocol is understanding that transactions can be protected by knowledge of the preimage of a hash.  E.g., you can write a transaction with a value HX specified in it, where to redeem the transaction the redeemer must provide some X such that Hash(X) = HX.   An example scriptPubKey would be "OP_RIPEMD160 PUSH{0xDEADBEEF} OP_EQUALVERIFY  PUSH{PUBKEY} CHECKSIGVERIFY"; to spend this coin the signature would need to end with a push of whatever value hashes to 0xDEADBEEF.

We form hashlocked transactions in the protocol proposed here, but they're not actually used or announced unless someone tries to cheat.

The general idea is that Alice<>Carol form a 2of2 escrow with Alice's coins,  and Carol<>Bob form a 2of2 escrow with Carol's coins. These escrows have a layer of precomputed time-out redemptions in case any of the parties vanish (Phase zero).  Then they setup a set of mutually signed escrow redeeming transactions which share a common hash-lock so that both of them can be redeemed if one is, but they do not announce them (Phase one).  By doing that, Carol can be confident that if Bob gets paid that Carol will also get paid.  Once Carol is confident that she can't get cheated, she releases her escrow to Bob, and then Alice releases her escrow to Carol (Phase two).

The result is a somewhat complicated protocol simply because it has many stages. Because of this it's explained in detail in the protocol diagram below.

History:
In "Idea for a mixer that can't run with your coins" Murphant proposed increasing financial privacy by performing pairs of transactions which were publicly unlinked if everyone was honest, but if someone tried cheating the funds could be redeemed by exposing the linkage. His proposed protocol would have resulted in unusual-looking transactions and, unfortunately, can't work without some pretty strong enhancements to Script—it would need to be able to verify SPV proofs embedded in transactions. Similar ideas without the SPV proof have been proposed from time to time, but they have extreme holdup/extortion risk.

In P2PTradeX Sergio had proposed a remarkably similar protocol using a SPV proof for doing trades between distinct blockchains. In that thread I proposed a transformation of the protocol that allowed most of the security but worked with Script today by using hash-locking to bind otherwise independent transactions and wondered if the same transformation could be applied to what Murphant was proposing.

My first attempt failed because of disabled OP codes—I wanted to use OP_ADD to blind the hash-locking so that in the common no-cheating case the hash linkage would be hidden, but OP_ADD only works for small integers and the suitable opcodes are disabled. In #bitcoin-wizards, Gavin noticed my mistake and Peter Todd rescued the protocol by pointing out that the hash-locking part could be made hidden by simply never announcing it. This greatly enhanced the protocol because it resulted in all of the transactions in the common case looking like plain escrow usage, plus it made it actually work in an unmodified Bitcoin network. Jcorgan suggested the name.

CoinSwap protocol:
In the protocol all parties are assumed to have private communications channels.

Phase 0. Sets up the escrows and their timeout refunds.
Phase 1. Makes it so that if Bob gets paid there is no way for Carol to fail to get paid.
Phase 2. Just releases the escrows directly because everyone is happy that cheating isn't possible.

  Alice                        Carol                        Bob
  =====================================================================================
0.Computes TX_0: 2of2{A,C}    |Computes TX_1: 2of2{C,B}    |                           \
1.Send TX_0 TXID ------------>                             |                           |
2.                            |Send TX_1 TXID ------------>                            |
3.                            |Computes TX_0 locked refund |Computes TX_1 locked refund|  
4.               <------------ Send TX_0_refund            |                           | Phase 0
5.                            |               <------------ Send TX_1_refund.          |
6.Announces TX_0 to network   |Announces TX_1 to network   |                           |
7.                            |                            |                           |
8.******    Network confirms TX_0: Alice pays according to 2 of {Alice, Carol}   ******|
9.******     Network confirms TX_1: Carol pays according to 2 of {Carol, Bob}    ******/
A.                            |                            |Selects secret value X     \
B.                            |                            |Computes HX = H(X)         |
C.                            |               <------------ Send HX                    |
D.               <----------------------------------------- Send HX                    |
E.Computes TX_2: TX_0>Carol+X |                            |                           | Phase 1
F.Send TX_2     ------------>                              |                           |
G.                            | Computes TX_3: TX_1>Bob+X  |                           |
H.                            | Send TX_3     ------------>                            |
I.                            |               <------------ Send X                     /
J.                            | Computes TX_4: TX_1>Bob    |                           \
K.                            | Send TX_4     ------------>                            |
L.                            |                            |Signs and announces TX_4   |
M.******       Network confirms TX_4: Carol pays Bob via 2 of {Carol, Bob}       ******|
N.Computes TX_5: TX_0>Carol   |                            |                           | Phase 3
O.Send TX_5      ------------>                             |                           |
P.                            |Signs and announces TX_5    |                           |
Q.******     Network confirms TX_5: Alice pays Carol via 2 of {Alice, Carol}     ******/
  =====================================================================================


Note that Alice could also pay the role of Bob, so that Bob doesn't have to take part in the protocol. She could then send on the freshly disconnected coins directly to Bob in the final release.

Also note that care related to mutability is required for the refunds until transaction mutability is solved.

Another key point is that Carol also receives unlinked coins (from Alice), and so in a P2P network a party could equally play the role of Alice or Carol, taking on whichever position was required.

TX_0_refund must have a further future locktime than TX_1_refund. Otherwise Bob can delay step (I.) in the protocol until the refunds become valid and then announce TX_3 while Alice announces TX_0_refund in order to try to cause Alice to get refunded while Bob still gets paid.

Comparison to CoinJoin:
There are a number of comparative advantages and disadvantages between CoinSwap and CoinJoin.

CoinJoin transactions are efficient—when people combine they can even save a little space over a common transaction. By contrast a CoinSwap requires a minimum of four transactions, although two CoinSwaps could effectively be performed at once. This means that CoinJoin is something wallets could reasonably do opportunistically on many transactions while CoinSwap would need to be some kind of periodic process.

CoinJoin's anonymity set is equal to the number of participants in a transaction (or a cascade of transactions). CoinSwap's anonymity set is all CoinSwaps going on at the same time, even if the users don't interact with each other, and all 2of2 secured wallet transactions going on at that time.

CoinSwap transactions look like regular 2of2 escrow transactions. If 2of2 escrows become common, then CoinSwap transactions may be less identifiable than large CoinJoin transactions with a bunch of equally-sized outputs, and thus more censorship-resistant.

To achieve privacy a CoinJoin transaction must have many participants. This somewhat complicates software design (basic state machine handling, dealing with DOS attacks, etc). If Alice plays the role of Bob in a CoinSwap, it's a two-party protocol, which may make it simpler to implement even though it involves roughly eight times the number of operations compared to a maximally simple CoinJoin.

CoinJoins can be done with a single round trip and no waits on the Bitcoin network. CoinSwaps require many more back and forths as well as waiting for confirmation of escrow payments.

CoinSwaps can happen across chains. CoinJoins are inherently single chain operations.

It's possible to construct cryptographically-blinded CoinJoins where _no one_ learns whose output is whose (except for each output's owner). CoinSwap results in the participants knowing the linkage.

I think there is a place for both kinds of transactions. CoinJoins can be used opportunistically and can be used to achieve stronger anonymity in smaller groups (avoiding the risk of sybil Carols), while potentially CoinSwaps could achieve much larger anonymity sets at the cost of additional transaction fees.

Absolutely, in fact CoinSwap itself can be used with CoinJoin for the transactions going into and out of the swap.

Basically, a really good implementation would be if we had a P2P messaging layer to arrange for both CoinJoin and CoinSwap transactions. CoinJoin can be done in such a way that every transaction can use it, with no performance issues and a small cost savings, so using it for every transaction makes sense. CoinSwap can be used on demand for a small increase in transaction cost, and the requirement to wait for a confirmation or two before the transaction can go ahead. Good wallet software would handle the detail in the background, and counter-parties for your CoinSwap transactions can be picked randomly from whomever is available. (remember that you don't need dedicated "Carol"'s, if you want to send coins to Bob, you can do it by having Carol send them, or acting as Carol yourself and using Alice's coins to pay Bob)

Followed thread from CoinJoin ... looks like a promising avenue.

Yes, it's a major flaw of the idea and I'd be very interested to hear if anyone can figure out how to solve it.

+1

I hope your intellectual contributions to Bitcoin are (widely) heralded someday the same way we recognize the contributions of academics today.

(bolded by me)

Proof-of-your-payment is very important, proof-of-someone-elses payment, on the other hand isn't something we want to make possible.

Note how for the proof-of-payment case, the CoinSwap should be designed such that the escrow transactions are released not with signatures, but by giving the other party the relevant private keys. This lets that other party re-use those keys if needed later to fully prove they made the payment. The alternative, SIGHASH_NONE|ANYONECANPAY is also worse because it's not a standard way to sign a transaction input, and thus leaks more information.

gmaxwell I always love reading the proposals you (and a few others of course) make in the technical discussion sub forum here; even if I don't really have a clue about what is going on in the hardcore crypto/maths aspects, I can ususally always keep up with Alice and Bob and their desire to spend and use coins in new, innovative and exciting ways!

So as usual thanks for this, it's always great to read about something awesome you don't fully understand to try and learn more. Now I will stop commenting so that I can give the other intellectuals more room to disect and scrutinise your proposal! 

Yep. Privacy requires new keys, but in general any protocol with a blind refund must always use a new key.

Petertodd proposed above that the final releases should be accomplished by handing over the keys, which also is another reason why you want to use fresh keys.

A couple points of comparison come to mind:

The paper proposal has a probability of cheating related to a security parameter, and requires communications in the setup phase linear in that security parameter (though I'd previously described a cut-and-choose communications optimization that could help).

The paper's proposal has an anonymity set of only all such transactions, as the hash commitments will be made public. In the case where a CoinSwap is successful the transactions just look like 2-of-2 escrows which likely results in a larger anonymity set.

CoinSwap doesn't require a third party, Bob can be alice and I noted this in the post. I just thought it was easier to describe using three (or four) parties then trying to make distinct one party operating in multiple roles... an effort to try to simplify some of that complexity you mention.

Generally I prefer protocols that have complexity moved into the initial setup, but the widened anonymity set achieved here by using all escrow transactions is probably worth losing the ability to front-load the complexity.

There is an address in my BCT profile, or you can contact me in PM for a unique address.