Atomic coin swapping

[jgarzik]

gmaxwell was talking about colored coins in IRC recently.  They are potentially interesting in the context of distributed bonds, which I am currently pursuing with pybond.

Here is the problem I am trying to solve, does the crowd have an answer?

1. Alice transfers a 1-satoshi colored coin to Bob.
2. Bob transfers 100 BTC to Alice.  May be restricted to 1 txout, if that eases implementation details.
3. Steps #1 and #2 happen as a logically atomic unit, all-or-none.
4. Alice and Bob must both approve this atomic transfer of coins, with appropriate signatures.

Is this possible within the current bitcoin system?  As far as I can see, the answer is "no" but maybe I'm missing something.

My best guess to the answer is "possible, but requires a new SIGHASH_* type"?

It seems like atomic coin swapping has great potential.

Edit: thanks, crowd   See below.

[jojkaart]

What's wrong with doing this all in one transaction that requires signatures from both parties to be valid?

[Mike Hearn]

It's a part of the same transaction indeed.

[jgarzik]

Certainly it is part of the same transaction.  Let us adapt the example from the Smart Property thread:


Definitions

previous-txout 0: "smartcoin", standard send-to-pubkeyhash, nvalue==1
b5bb9d8014a0f9b1d61e21e796d78dccdf1352f23cd32812f4850b878ae4944c,0

previous txout 1: normal transaction, standard send-to-pubkeyhash, nvalue==100000
7d865e959b2466918c9863afca942d0fb89d7c9ac0c99bafc3749504ded97730,0

smartcoin seller
        pubkey for to-be-sent smartcoin (CK)
        pubkey destination for smartcoin payment (SK)
        smartcoin required price (P): 100000

smartcoin buyer
        pubkey for to-be-spent payment (PK)
        pubkey destination for smartcoin (BK)


Round 1, smartcoin buyer and seller agree on a transaction

Presumably the smartcoin seller has <somehow> advertised for sale smartcoin b5bb9d8014a0f9b1d61e21e796d78dccdf1352f23cd32812f4850b878ae4944c,0 at price P.

Presumably, the buyer knows how to create a standard 2 txin, 2 txout format transaction that the seller expects.

The buyer and seller communicating this basic information is outside the scope of this discussion.


Round 2, smartcoin buyer creates incomplete TX, sends to seller

txin 0 (smartcoin transfer)
  prevout (b5bb9d8014a0f9b1d61e21e796d78dccdf1352f23cd32812f4850b878ae4944c, 0)
  scriptSig = zero-length (null)

txin 1 (payment transfer)
  prevout (7d865e959b2466918c9863afca942d0fb89d7c9ac0c99bafc3749504ded97730, 0)
  scriptSig = <PK-derived signature> <PK>, SIGHASH_ALL

txout 0
  nValue = 1
  scriptPubKey = OP_DUP OP_HASH160 hash<BK> OP_EQUALVERIFY OP_CHECKSIG

txout 1
  nValue = 100000
  scriptPubKey = OP_DUP OP_HASH160 hash<SK> OP_EQUALVERIFY OP_CHECKSIG


Round 3, smartcoin seller signs TX, and broadcasts completed TX to network

txin 0 (smartcoin transfer)
  prevout (b5bb9d8014a0f9b1d61e21e796d78dccdf1352f23cd32812f4850b878ae4944c, 0)
  scriptSig = <CK-derived signature> <CK>, SIGHASH_ALL

txin 1 (payment transfer)
  prevout (7d865e959b2466918c9863afca942d0fb89d7c9ac0c99bafc3749504ded97730, 0)
  scriptSig = <PK-derived signature> <PK>, SIGHASH_ALL

txout 0
  nValue = 1
  scriptPubKey = OP_DUP OP_HASH160 hash<BK> OP_EQUALVERIFY OP_CHECKSIG

txout 1
  nValue = 100000
  scriptPubKey = OP_DUP OP_HASH160 hash<SK> OP_EQUALVERIFY OP_CHECKSIG


Discussion

Potential attacks, neither resulting in a direct loss of value:

• Buyer may stall or refuse to send incomplete transaction (wasting seller's time and DoS'ing an issue, if the seller prevents other buyers from attempting purchases in parallel)
• Seller may stall or refuse to send completed transaction (wasting a buyer's time and leaving the fate of their coins unknown)

[jgarzik]

It sounds like SIGHASH_ALL is the hidden magic solution, that prevents parties from reordering or tampering.

Edited example accordingly.

Documentation on SIGHASH_*, particularly on the wiki, is severely lacking.

[Mike Hearn]

SIGHASH_ALL is the default which is why it's not mentioned. There are descriptions of the SIGHASH flags in the theory section of the contracts page:

   https://en.bitcoin.it/wiki/Contracts

SIGHASH_ALL: This is the default. It indicates that everything about the transaction is signed, except for the input scripts. Signing the input scripts as well would obviously make it impossible to construct a transaction, so they are always blanked out. Note, though, that other properties of the input, like the connected output and sequence numbers, are signed; it's only the scripts that are not. Intuitively, it means "I agree to put my money in, if everyone puts their money in and the outputs are this".

[jgarzik]

SIGHASH_ALL is the default which is why it's not mentioned. There are descriptions of the SIGHASH flags in the theory section of the contracts page:

   https://en.bitcoin.it/wiki/Contracts

SIGHASH_ALL: This is the default. It indicates that everything about the transaction is signed, except for the input scripts. Signing the input scripts as well would obviously make it impossible to construct a transaction, so they are always blanked out. Note, though, that other properties of the input, like the connected output and sequence numbers, are signed; it's only the scripts that are not. Intuitively, it means "I agree to put my money in, if everyone puts their money in and the outputs are this".

Yeah, tucked into a bit of a corner it is, away from other documentation on signatures and scripts.

Might warrant its own page, or at least a reference from the Scripts page, for an enterprising volunteer.

Anyway, it definitely works for this purpose, solving the problem.

[phelix]

could this be used for mixing? p2p style like ab boss?
edit: 

[killerstorm]

could this be used for mixing? p2p style like ab boss?

Yes, it can be used for mixing. I even did some analysis like how many rounds of mixing you need if there are 10 FBI agents for each honest person

[phelix]

could this be used for mixing? p2p style like ab boss?

Yes, it can be used for mixing. I even did some analysis like how many rounds of mixing you need if there are 10 FBI agents for each honest person

you mean here: https://bitcointalk.org/index.php?topic=106373.msg1267002#msg1267002

seems like it would take a lot of mixing as the two partners are always linked

[phelix]

is there a good name for this kind of tx yet?

swap tx? split tx? mutual tx?

[killerstorm]

you mean here: https://bitcointalk.org/index.php?topic=106373.msg1267002#msg1267002

seems like it would take a lot of mixing as the two partners are always linked

You do mixing in rounds, each time finding some random partner. Amount of entropy you get in the end depends on how many honest partners (i.e. ones which won't rat you out) you met, but "FBI agents" do not decrease your entropy.

So you get optimal mixing when you've mixed with everybody. But since it's stochastic, you cannot know for sure. But as a rule of thumb, if you do N rounds with N participants you'll some good mixing, not optimal, though.

If we want to make it more efficient we can add a facilitator. He doesn't need to be trusted. Instead of submitting your transactions to blockchain you will submit them to facilitator. He will create a large transaction with all inputs and all outputs. Each participant can check whether his output is in that large transaction, and if it is, he will sign his input.

So you can do large number of rounds, say 1000 or 10000, without adding any additional strain to blockchain.

[killerstorm]

I think this requires specialized software, doing it manually would be slow and painful.

[killerstorm]

"Colored coin" ArmoryX p2ptrade was able to create its first atomic coin swap transaction: http://paste.lisp.org/display/134280

So implementation is here. We only need to create a good front-end now.

[jtimon]

"Colored coin" ArmoryX p2ptrade was able to create its first atomic coin swap transaction: http://paste.lisp.org/display/134280

So implementation is here. We only need to create a good front-end now.

This is great.
Since asking is free...I'm looking forward the first transaction where more than two colors are swapped (the first ripple transaction on top of the bitcoin chain). It's probably not the first priority use case though.

[killerstorm]

Since asking is free...I'm looking forward the first transaction where more than two colors are swapped (the first ripple transaction on top of the bitcoin chain). It's probably not the first priority use case though.

Technically speaking simplest ripple transaction A->B->C does not require any special handling: A will use B's offer to send money to C. C is receiving party, he doesn't need to sign anything. And only two colors are involved (A's and B's).

Bigger chain (A->B->C->D) might involve more than two colors.

[grau]

It sounds like SIGHASH_ALL is the hidden magic solution, that prevents parties from reordering or tampering.

Edited example accordingly.

Documentation on SIGHASH_*, particularly on the wiki, is severely lacking.

Unfortunately all values not SIGHASH_NONE, SIGHASH_SINGLE are interpreted as SIGHAS_ALL and that even enters into the digest of the transactions. Therefore defining and using a new SIGHASH_* is only possible if that was not yet used in the chain otherwise we fork.

I already saw transactions using some random value in that byte.

[jtimon]

Technically speaking simplest ripple transaction A->B->C does not require any special handling: A will use B's offer to send money to C. C is receiving party, he doesn't need to sign anything. And only two colors are involved (A's and B's).

Bigger chain (A->B->C->D) might involve more than two colors.

Well, yes, you're right. Usually C would have pre-signed a credit line to B, but that's not really necessary.
In two phase ripple C signature is required so that A can demonstrate that he has paid and C knows it. But since the chain is public, not necessary neither.
So, yes, as you say, the simplest colored coins ripple transaction only needs two colors.

[casascius]

Discussion

Potential attacks, neither resulting in a direct loss of value:

• Buyer may stall or refuse to send incomplete transaction (wasting seller's time and DoS'ing an issue, if the seller prevents other buyers from attempting purchases in parallel)
• Seller may stall or refuse to send completed transaction (wasting a buyer's time and leaving the fate of their coins unknown)

Neither of these ever occurred to me to be serious issues because:

1 - the sending of the incomplete transaction could be the action that constitutes the buyer's execution of the transaction, eliminating any time window between "execution" and "settlement".
2 - I would assume that the seller "refusing" to send a completed transaction might be a legitimate outcome (e.g. if a buyer sent an incomplete transaction but from the seller's view, the offer was no longer available, such as it having been completed with someone else).  Assuming the buyer was concerned that the seller could surprise him later, the buyer could recover from the "fate of coins unknown" condition simply by broadcasting a new transaction that sent those coins to another address of his own, which would invalidate the seller's unsent transaction.

[phelix]

you mean here: https://bitcointalk.org/index.php?topic=106373.msg1267002#msg1267002

seems like it would take a lot of mixing as the two partners are always linked

You do mixing in rounds, each time finding some random partner. Amount of entropy you get in the end depends on how many honest partners (i.e. ones which won't rat you out) you met, but "FBI agents" do not decrease your entropy.

So you get optimal mixing when you've mixed with everybody. But since it's stochastic, you cannot know for sure. But as a rule of thumb, if you do N rounds with N participants you'll some good mixing, not optimal, though.

If we want to make it more efficient we can add a facilitator. He doesn't need to be trusted. Instead of submitting your transactions to blockchain you will submit them to facilitator. He will create a large transaction with all inputs and all outputs. Each participant can check whether his output is in that large transaction, and if it is, he will sign his input.

So you can do large number of rounds, say 1000 or 10000, without adding any additional strain to blockchain.

I wonder if that would be possible in a decentralized way, too? Atomic coin laundry...