Bitcoin Forum

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 (https://bitcointalk.org/index.php?topic=318122.0)" 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 (https://bitcointalk.org/index.php?topic=91843.msg1011956#msg1011956) 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 (https://bitcointalk.org/index.php?topic=279249.0):
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.

Very interesting. +1 for the diagram.

Would it still make sense if say, 50% of TXs were done using the elegant CoinJoin trick?

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)

I guess the interesting thing about CoinSwap is that the participants do keep some records about what they did. One topic I'm interested in exploring right now is if there are ways to obfuscate the block chain an invertible manner, such that if the people who took part in the obfuscation decide there's a really good reason to do so, the obfuscation can be undone. For example if it turned out that some coins were stolen and there was a desire to combine it with some kind of tainting mechanism.

It may well be that this sort of thing is unfeasible, but it's a topic worth research.

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

Thank you gmaxwell for looking into things like this..

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.

I love the diagram. This must go right to the wiki.

+1

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

Hah. I don't _generally_ consider that a flaw. Selectable audibility is useful, so long as its the participants that control it.  What is a flaw here is that Carol can tell you about Alice.   In CJ, even a cryptographically blinded one, if setup right, you could also keep logs that enable you to prove to others how you transacted... but no one but you has that power. Doing so enables things like transparent business records— but ones which are only transparent to your investors, not your competition.

With privacy I generally want people to have the freedom to chose to not be private, but only if they can choose when and to whom to not be private with respect to. There are cases where you don't want this to be so— e.g. secret ballot elections need to have no way to opt out of privacy in order to defeat vote buying, so techniques need to exist for that so long as power imbalances between people can exist... but on the whole being able to selectively opt out is worth a little coercion risk for most applications.

(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.

I'm on my phone at work right now but this seems similar to the mechanism I proposed here (https://bitcointalk.org/index.php?topic=152334.0) and prototyped (badly) in the link in my signature. I'll be able to take a closer look in a few hours but I'm glad to see a core developer thinking along these lines because it means hopefully scripts supporting hash preimage checks will make it as standard script types sooner rather than later.

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! :D

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!  ;D

Possible vector of attack:
If Carol does not give Alice a newly generated public key C each time the protocol is run, then Alice can provide Carol a fake TX_0 TXID (for example, a TXID of another transaction that Alice wants to steal from Carol).
Same happens if Bob does not give Carol a newly generated address each time, then Carol can attack Bob.

Also when the protocol reads {A,C} and {C,B} , these C's should be different, so it would be better to call the second key C'.

To avoid another (minor) problem on how to establish secure and authenticated connections between 3 participants it would be preferable that step D is changed so instead that Bob sends HX to Alice, is Carol who sends XH to Alice (received in the previous step). This removes the need that Alice connects to Bob.

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.

This is an interesting proposal. I'm curious to hear any thoughts on how it compares to the protocol in Section 7 of this academic paper: http://crypto.stanford.edu/~xb/fc12/bitcoin.pdf

Both it and CoinSwap appear to enable two party mixing, with unlinkable transactions, providing an anonymity set of all similar transactions happening concurrently. Both depend on what you call hash locking. Both are complex but the complexity is in different spots: in CoinSwap, it requires a number of rounds and a third party Carol. In the paper, it requires a complex setup, including the cut-and-choose.

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 (https://bitcointalk.org/index.php?topic=284194.0)).

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.

@gmaxwell

WHERE IS THE DONATION ADDRESS ???

I WANT TO THROW SOME COINS AT YOU !!!!!!!!11111ONEONE.

----
(But seriously, give us a donation addr)

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

Actually it would be simpler for me if they were only Alice and Bob.
I'm trying to compare it with the "classical" trading across chain contract (https://en.bitcoin.it/wiki/Contracts#Example_5:_Trading_across_chains) but I'm not able to see what you gain with coinswap or having Carol in the middle.

Oh, yeah...not even bob...sorry.
Time to re-read with new eyes. I guess my preferred use case blinded me.

Well even ignoring the non-even bob part, the classical across chain contracts are trivially traceable by everyone.

A useful point I should have made here is that you can basically apply this same protocol encoding to any script-releasable-escrow in order to keep the release details private.

E.g. something like the zero knoweldge contingent payment (https://en.bitcoin.it/wiki/User:Gmaxwell/why_hash_locked) protocol could be used in place of the normally-not-announced first release transaction in order to keep private that you were using a ZK-payment.

Would it be possible to extend this idea into a Tor-like mix-cascade payment network? Both Alice and Bob would choose their own CoinSwap 'circuit' to a rendezvous intermediary, each escrow tx is hash-locked to that of the next intermediary, so that Eva would have to compromise at least three intermediaries to know Alice has paid Bob.

OMG, i think what you described is a serious material for next Bitcoin-level breakthrough...

Onion TX routing?

I'm sure this is a dumb question, but, I don't fully understand how the refunds work.

So, we have a refund for the TX_0 transaction, but don't announce it. If Carol announces a transaction  that spends TX_0, and then announces a refund for TX_1, how does the refund work to prevent cheating? Isn't TX_0 spent at that point?

I think I am missing something re: the time-out redemptions. Do these refund transactions somehow supersede other transactions, even if the other transaction is announced before the refund?

TX_0's output is a 2-of-2 multisignature output. It can't be spent unilaterally, the other user must sign it too. Does that answer your question?

I think my confusion stems from my use case: where Alice and Bob are the same person (2-party with only Alice & Carol) who will calculate the X Value?

Doesn't one of them knowing this value before the other allow someone to cheat?

Or, would a 3rd party need to generate X, calculate and send Alice & Carol HX, and release X after they have exchanged TX_2 & TX_3?

Alice does, and it's perfectly fine that alice knows it first.  It might help you to try to describe the attack you're feeling might be there in concrete terms.

I'm looking at the point where Alice generates X & HX, Alice sends Carol HX. They both then create, sign & exchange TX_2 & TX_3 transactions that spend TX_0 & TX_1 with the common hash lock.

It seems that whomever holds X has an advantage here.

What is to stop Alice from simply not sending Carol X (so Carol can't spend TX_2) announcing TX_3 which spends TX_1, and then announcing the TX_0_Refund as well?

I am sure I am missing something here, I appreciate your patience :)

TX_3 is created and announced by Carol.  Alice can't collect TX_3's output without making X public (as TX_3 requires X to be in the signature). The TX_0_Refund is nlocked for the future: "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."  (I believe thats describing what you're thinking about there)

Ahh, I neglected to consider that X would be made public if TX_3 was spent.

Thanks!

Just bumping this real quick. This might actually become a thing if coinvalidation takes off. Trade tainted coins for clean ones. Ideally coinvalidation will just fade away like a fart, but in case it doesn't, coinswap!

I came up with the idea, on reddit (http://www.reddit.com/r/Bitcoin/comments/299y8k/psa_alex_waters_is_one_of_the_big_three_pushing/cij8ntv?context=3), then someone pointed out this thread here where it was already done.

I read about the "atomic cross chain transfer" stuff quite a long time ago but I have yet to ever see *one single tx* using it.

Is there a reason why not one single "atomic cross chain transfer" has ever been done?

(sorry if this is a little OT - but I think it is related)

Hoping I don't point something out that is already known - but this protocol would be vulnerable if Bob and Carol were the same person. It's vulnerable in the sense that Bob could trace the transactions from Alice which defeats the purpose of the protocol. It might be worth highlighting how important it is to trust the identity of Carol.

I have a proposal above  to link several intermediaries together, so in essence it becomes some sort of a Tor-like network, you can only compromise Alice/Bob's privacy when you control all the three relaying nodes.

Do you mean that you would do CoinSwap with 3 different people to send your fund to Bob?

So Alice sends escrow to node1, node1 sends escrow to node2, node 2 sends escrow to node 3, node 3 sends escrow to Bob?

This would make it more difficult for Eve, but it still has that fundamental problem of trusting an intermediary not to spill the beans doesn't it? Which CoinJoin manages to avoid from what I remember.

So does this thread have anything to do with coinswap.net exchange?

You realize this is a bit of a necrothread.

What do you mean?

So which is better lol?. Coinswap or coinjoin?. ???

Thanks.

I agree with prior commenters ~ having both [CoinSwap and Coinjoin) available (in wallet, I think) would be good.  With support gradually being added in different wallets and cryptosystems for stealth send, what is available in combination will be significant.

[Note: I am aware that Stealth transaction technology (https://sx.dyne.org/stealth.html), a strong privacy development, has been incorporated into Vertcoin (https://vertcoin.org/) and Shadowcoin (http://www.shadowcoin.co/), with the latter coin type also incorporating an implementation of zk-snarks, which provides anonymity.  Stealth send is also becoming available for Electrum (https://github.com/spesmilo/electrum/pull/817) ~ beyond that, I'm not sure where stealth is actually supported, but if you know of more examples by all means please add them here.]

If not directly in wallet, then one could design a plugin (am thinking of the Electrum mixer plugin example, here, though Electrum also has greenaddress and coinapult plugins you could examine):


Regarding the details of 'byzantine cycle mode,' after reading the description and paper, it is my sense that it will also serve tremendously useful for implementation of trans-identical proposals which incorporate 'facet-based' and/or multisignature-oriented anonymous-option identity-related implementations.  Repeating part of the original post below:


My (very generalized) feedback statement is that this is an excellent idea, thus I've linked to the discussion and paper in my Trans-Identical post at the Unsystem forum, which I originally created to simply to discuss possible 'trans-identical' possibilities, but which I now also see as being a launchpad to help defeat the Windhover regulation principle (the pro-regulatory element of Windhover). ~ The idea of tying regulation to decentralized identity is anathema to everything that we should stand for in this community, and just as CoinValidation was defeated by digital fire (in that case, by CoinJoin), so now must we also support and develop technology to defeat the Windhover regulation principle.

The Unsystem forum post I refer to is here:
https://forum.unsystem.net/t/interoperability-and-trans-identical-identity-decentralization-proposals-thoughts-for-review/333/4?u=abisprotocol

I also wanted to address the question that arose relating to Zerocash, here:


It was my understanding that the concerns regarding element of trust needed to launch zerocash were being planned to be ameliorated via some sort of multiparty mechanism, so that there would not actually be a single party that someone would have to trust somehow to kickstart zerocash.  I'm not sure if I have the right twitter thread on it, but I believe this was related to it:
This one alludes to a multiparty computation protocol (yes, he's a zerocash dev)
https://twitter.com/matthew_d_green/status/448856221765095426
And this one refers to the multiparty computation protocol being developed for the setup itself, as I alluded to above:
https://twitter.com/matthew_d_green/status/472208415867928576

Note ~ I am not on the Zerocash team or affiliated with it but I am in full support of their proposals.  They have been subjected to tremendous scrutiny.  It's my understanding that zerocash is going open source (like zerocoin/libzerocoin already is though that's different), but I don't know when that will happen with zerocash, so ask the devs or keep checking their website (http://zerocash-project.org/).

Here is a private atomic swap that doesn't need the multiphase "CoinSwap" transform, as I've come to call the generic protocol here that makes smart contracts private by hiding them from the blockchain.


B computes nonce x and  P = xG, P2 = P + H(P)G

B sends P to A

B pays to   if() {Apub+P2 CHECKSIG} else {CLTV Bpub CHECKSIG}

A pays  to   if() {Bpub2 CHECKSIG P2 FORCEDDISCLOSURECHECKSIG} else {CLTV Apub2}

What is a FORCEDDISCLOSURECHECKSIG? it's a signature construct that forces you to sign in such a way as to disclose the private key.

I am aware of two ways to get this construct in unmodified (no disabled opcodes) Bitcoin today.

One of them is: OP_SIZE 57 OP_LESSTHANOREQUAL OP_VERIFY <P> OP_CHECKSIGVERIFY

I don't think this will work - I was looking into private key reveal schemes in order to try and counteract the problems with double spending in a proof of burn consensus scheme.

The problem is that the payer can simply construct another transaction in which they send the funds of that private key somewhere else, and then use one of the many techniques to make sure this double spending transaction gets confirmed first.

uh. Your response isn't making any sense to me. I think you've misunderstood the protocol, but I am not sure where-- nothing about the above exists to prevent double spending, the transactions are all confirmed before further action is taken. Please reread and if you still hold the same view write out a sequence diagram that shows your attack so I can understand it.

If the private key is revealed to the recipient on receipt of the transaction, by the time the transaction is confirmed, the sender could already have removed the funds at that location via another transaction.

There are no funds at that 'location'.  No funds are ever sent the revealed key P, funds are sent the the key P+Recipient_Pubkey, which only the recipient knows the private key for (and only after the private key for P is revealed).
 

Understood. I wasn't aware of the specifics of your design.

...

There is a new Bitfury white paper out (published today, Aug. 23, 2016) that references this thread:

http://www.coindesk.com/bitfury-research-seeks-shine-light-bitcoin-mixing-methods/

It is all way above my head, but may be of interest to the community.

I was looking into this a few weeks back and there seemed to be a flaw in the original setup as proposed in the OP here. After some time I came up with this:

https://gist.github.com/AdamISZ/350bb4038834019eb0c06ec69446aec9

(It links at the top to a (apologies, poorly formatted) schematic; the last part of which has a diagram which may be a useful aid to understanding).

Would appreciate thoughts, a couple of people looked at it, so far comments included possibly replacing CLTV with CSV.