Bitcoin Forum
October 27, 2020, 06:42:39 AM *
News: Latest Bitcoin Core release: 0.20.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1] 2 »  All
  Print  
Author Topic: Atomic coin swapping  (Read 13212 times)
jgarzik
Legendary
*
qt
Offline Offline

Activity: 1596
Merit: 1008


View Profile
September 22, 2012, 07:17:46 AM
Last edit: September 22, 2012, 05:00:15 PM by jgarzik
 #1

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 Smiley  See below.

Jeff Garzik, Bloq CEO, former bitcoin core dev team; opinions are my own.
Visit bloq.com / metronome.io
Donations / tip jar: 1BrufViLKnSWtuWGkryPsKsxonV2NQ7Tcj
1603780959
Hero Member
*
Offline Offline

Posts: 1603780959

View Profile Personal Message (Offline)

Ignore
1603780959
Reply with quote  #2

1603780959
Report to moderator
1603780959
Hero Member
*
Offline Offline

Posts: 1603780959

View Profile Personal Message (Offline)

Ignore
1603780959
Reply with quote  #2

1603780959
Report to moderator
1603780959
Hero Member
*
Offline Offline

Posts: 1603780959

View Profile Personal Message (Offline)

Ignore
1603780959
Reply with quote  #2

1603780959
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1603780959
Hero Member
*
Offline Offline

Posts: 1603780959

View Profile Personal Message (Offline)

Ignore
1603780959
Reply with quote  #2

1603780959
Report to moderator
1603780959
Hero Member
*
Offline Offline

Posts: 1603780959

View Profile Personal Message (Offline)

Ignore
1603780959
Reply with quote  #2

1603780959
Report to moderator
jojkaart
Member
**
Offline Offline

Activity: 97
Merit: 10


View Profile
September 22, 2012, 09:14:49 AM
 #2

What's wrong with doing this all in one transaction that requires signatures from both parties to be valid?
Mike Hearn
Legendary
*
expert
Offline Offline

Activity: 1526
Merit: 1011


View Profile
September 22, 2012, 11:50:02 AM
 #3

It's a part of the same transaction indeed.
jgarzik
Legendary
*
qt
Offline Offline

Activity: 1596
Merit: 1008


View Profile
September 22, 2012, 04:16:08 PM
Last edit: September 22, 2012, 04:57:53 PM by jgarzik
 #4

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)


Jeff Garzik, Bloq CEO, former bitcoin core dev team; opinions are my own.
Visit bloq.com / metronome.io
Donations / tip jar: 1BrufViLKnSWtuWGkryPsKsxonV2NQ7Tcj
jgarzik
Legendary
*
qt
Offline Offline

Activity: 1596
Merit: 1008


View Profile
September 22, 2012, 04:42:14 PM
 #5

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.


Jeff Garzik, Bloq CEO, former bitcoin core dev team; opinions are my own.
Visit bloq.com / metronome.io
Donations / tip jar: 1BrufViLKnSWtuWGkryPsKsxonV2NQ7Tcj
Mike Hearn
Legendary
*
expert
Offline Offline

Activity: 1526
Merit: 1011


View Profile
September 22, 2012, 05:02:37 PM
 #6

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

Quote
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
Legendary
*
qt
Offline Offline

Activity: 1596
Merit: 1008


View Profile
September 22, 2012, 05:25:29 PM
Last edit: September 22, 2012, 05:41:45 PM by jgarzik
 #7

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

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


Jeff Garzik, Bloq CEO, former bitcoin core dev team; opinions are my own.
Visit bloq.com / metronome.io
Donations / tip jar: 1BrufViLKnSWtuWGkryPsKsxonV2NQ7Tcj
phelix
Legendary
*
Offline Offline

Activity: 1708
Merit: 1010


nmc:id/phelix


View Profile
October 12, 2012, 06:33:49 PM
Last edit: October 13, 2012, 07:51:27 AM by phelix
 #8

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

blockchained.com ■ bitcointalk top posts
killerstorm
Legendary
*
Offline Offline

Activity: 1022
Merit: 1000



View Profile
October 13, 2012, 06:00:40 PM
 #9

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 Smiley

Chromia: a better dapp platform
phelix
Legendary
*
Offline Offline

Activity: 1708
Merit: 1010


nmc:id/phelix


View Profile
October 16, 2012, 05:50:19 PM
 #10

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 Smiley

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



blockchained.com ■ bitcointalk top posts
phelix
Legendary
*
Offline Offline

Activity: 1708
Merit: 1010


nmc:id/phelix


View Profile
October 16, 2012, 05:52:00 PM
Last edit: March 29, 2013, 10:24:37 PM by phelix
 #11

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

swap tx? split tx? mutual tx?



blockchained.com ■ bitcointalk top posts
killerstorm
Legendary
*
Offline Offline

Activity: 1022
Merit: 1000



View Profile
October 16, 2012, 07:44:28 PM
 #12

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.

Chromia: a better dapp platform
killerstorm
Legendary
*
Offline Offline

Activity: 1022
Merit: 1000



View Profile
October 26, 2012, 02:25:47 PM
 #13

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

Chromia: a better dapp platform
killerstorm
Legendary
*
Offline Offline

Activity: 1022
Merit: 1000



View Profile
December 27, 2012, 02:30:44 PM
 #14

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

Chromia: a better dapp platform
jtimon
Legendary
*
Offline Offline

Activity: 1372
Merit: 1000


View Profile WWW
December 27, 2012, 03:07:37 PM
 #15

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

2 different forms of free-money: Freicoin (free of basic interest because it's perishable), Mutual credit (no interest because it's abundant)
killerstorm
Legendary
*
Offline Offline

Activity: 1022
Merit: 1000



View Profile
December 27, 2012, 03:17:38 PM
 #16

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.

Chromia: a better dapp platform
grau
Hero Member
*****
Offline Offline

Activity: 836
Merit: 1000


bits of proof


View Profile WWW
December 27, 2012, 04:41:20 PM
 #17

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
Legendary
*
Offline Offline

Activity: 1372
Merit: 1000


View Profile WWW
December 27, 2012, 05:46:04 PM
 #18

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.


2 different forms of free-money: Freicoin (free of basic interest because it's perishable), Mutual credit (no interest because it's abundant)
casascius
Mike Caldwell
VIP
Legendary
*
Offline Offline

Activity: 1386
Merit: 1065


The Casascius 1oz 10BTC Silver Round (w/ Gold B)


View Profile WWW
December 27, 2012, 06:20:44 PM
 #19

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.

Companies claiming they got hacked and lost your coins sounds like fraud so perfect it could be called fashionable.  I never believe them.  If I ever experience the misfortune of a real intrusion, I declare I have been honest about the way I have managed the keys in Casascius Coins.  I maintain no ability to recover or reproduce the keys, not even under limitless duress or total intrusion.  Remember that trusting strangers with your coins without any recourse is, as a matter of principle, not a best practice.  Don't keep coins online. Use paper or hardware wallets instead.
phelix
Legendary
*
Offline Offline

Activity: 1708
Merit: 1010


nmc:id/phelix


View Profile
March 29, 2013, 10:24:15 PM
 #20

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

blockchained.com ■ bitcointalk top posts
Pages: [1] 2 »  All
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!