Atomic swaps between BTC/Omni

[CraigSellars]

Referencing @dexX7 from OmniLayer/spec#281 (comment)

This diagram outlining @petertodd's Decentralized digital asset exchange with honest pricing and market depth post is a topic that I believe deserves its own issue.

@dexX7, you mentioned that:

this scheme, as it is, would be vulnerable to double-spending of tokens due to the balance based nature of MSC, but there are two ways around: one involving third-party trust, where the party cannot steal per se, or by introducing a new transaction type to bind tokens to an output.

I’m curious about a few things, as I am absolutely a fan of this direction. Are the two solutions above the only ones that solve the issue? If not, I’d like to hear what other options are available. If so, I’m curious what the binding of tokens to an output would need to look like.

To address the concerns of MSC, this would only affect BTC transactions with Omni tokens, not DExv2 transactions between Omni tokens and MSC, which are already atomic (we could also limit to atomic BTC->MSC swaps for simplicity sake, but that’s a bit of a stretch).

If we bind tokens to an (originally?) unknown output (assuming that an original output contained the instruction to do so), could a subsequent transaction (once the atomic swap had been completed) “unbind” it such that the value would return to the balance method (for use in other features where output-based tokens aren’t feasible)? Or would we need to bind the tokens prior to the sale offer (in the event the buyer was the one contributing the tokens (the opposite direction from the example given)?

This one opens a can of worms, for sure.

For my own education, I haven’t found a good description of how SINGLE|ANYONECANPAY transactions are handled by the p2p and clients. What gets relayed, stored for later (in case a buyer shows up), discarded and/or confirmed? Please don’t tell me they’re entirely out-of-band.

[dexX7]

Nice!

The topic is pretty broad, but I highlighted some parts, which seem relevant. It would be awesome to dive into this and support atomic MSC/BTC trades at some point, and there are some parts which can be addressed in one way or another. Further discussion is very welcomed. :)

---

@CraigSellars: I haven't found a good description of how SINGLE|ANYONECANPAY transactions are handled by the p2p and clients. What gets relayed, stored for later (in case a buyer shows up), discarded and/or confirmed?

Generally, to spent bitcoins, a transaction must satisfy certain criteria, in particular the outgoing amount must not be higher than the input amount, and further, the script execution must be successful. Usually, to satisfy the later, the spender provides valid signatures for all outputs to spent.

Signatures come with a flag, and outputs are usually signed with the flag "ALL", which can be seen as indicator to "provide a signature for an output, where the whole transaction is unmodifiable". It's not possible to add more inputs, and neither any other outputs.

However, there are some other interesting flags: "SINGLE" basically equals "sign one of the outputs, but don't care where the others go", and "ANYONECANPAY" equals "let other people add inputs to the transaction, and don't care where the rest of the bitcoins come from".

Combining flags is possible, as done in the example, where Alice uses "SINGLE|ANYONECANPAY" to sign the (colored) transaction input and to "lock" the payment output to herself, while it's still possible to add more inputs and outputs, and in the example even required, because the input amount of 0.0001 BTC is lower than the output amount of 15 BTC.

It doesn't matter, which signature flags are used, and it also doesn't matter, if Alice provides one part of the transaction, and Bob another one, as long as the transaction is valid at the end.

Incomplete transactions can not be broadcasted, because they are (not yet) valid. Valid transactions, however signed, can be broadcasted and are mined, like any other transaction.

So one problem to solve:

Where can Alice publish the incomplete transaction and how does Bob learn about it?

Anywhere, really.

The user could publish transactions via a P2P network or on some website, or ... embed incomplete transactions as data payload in the blockchain. ;)

---

@CraigSellars: Are the two solutions above the only ones that solve the issue?

Let's take a look at a sequence and a token transfer via an Omni transaction, with currently enabled transaction types, but without explicit token-to-output binding. It would probably look like this:

Transaction 1 (not relevant, just to provide a starting point):

Input 1:  1Njbpr7.. (Anyone)

Output 1: Embedded payload with the instruction to "simple send 50 MSC"
Output 2: 1EXoDus.. (Exodus marker)
Output 3: 1Njbpr7.. (Ignored as change output, optional)
Output 4: 1LifmeX.. (Reference output to indicate the token receiver, it's Alice)

Transaction 2 (actual BTC/MSC swap):

Input 1:  1LifmeX.. (Alice's, should have a balance of 100 MSC, inserted by Alice)
Input 2:  1CE8bBr.. (15 BTC worth, previously owned by Bob, inserted by Bob)

Output 1: 1LifmeX.. (15 BTC worth, goes to Alice, ignored as change, inserted by Alice)
Output 2: Embedded payload to "simple send 50 MSC" (inserted by Bob)
Output 3: 1EXoDus.. (Exodus marker, inserted by Bob)
Output 4: 1CE8bBr.. (Reference output, pointing to Bob, inserted by Bob)

Note: the order of outputs is not relevant here, and it's fine, if the first output goes to Alice, because the change output is generally ignored. Also, this example would fail in reality due to the "contribution by sum" sender identification, but this doesn't seem crucial for the general discussion.

So far, this was nothing special and just some transfer of Mastercoin via "simple send": Alice previously received 100 MSC, which were then sent to Bob. The fact that Bob funded the transaction with 15 BTC, which were transferred to Alice is (almost) irrelevant, likewise how that transaction was constructed, or whether Alice provided an incomplete transaction, which Bob later completed, doesn't matter at all, at least in the context of the Omni layer.

The pitfall here is that it's not certain, whether transaction 2 is a valid Omni transaction, and if indeed 100 MSC were transferred from Alice to Bob.

Even if transaction 1 was valid, and Alice had 100 MSC associated with 1LifmeX.. earlier, when she published the incomplete transaction, it is entirely possible that Bob just lost 15 BTC, because Alice actually transferred the tokens associated with 1LifmeX.. in another transaction.

So the second problem to solve:

How to prevent a token transfer in another transaction, which is not the actual payment or swap transaction?

As mentioned before, the underlying issue is the balance based nature, and the lack of an explicit relation between bitcoin and token movements.

There is no way around establishing a link between the bitcoin movement and the token transfer, but there are probably more than one solutions to do so.

I haven't really come up with anything else than explicitly binding tokens to an output by introducing a new transaction type, and the other mechanism I had in mind would basically involve a third party, to simulate the binding of tokens to an output, by creating a script-hash output that can only be spent, if both, the third party and Alice, cooperate. Certain trust in the third party would be required, such that tokens are not spent somewhere else, but this is vulnerable, if Alice and the third party cooperate in a malicious way.

---

@CraigSellars: If we bind tokens to an output, could a subsequent transaction "unbind" it such that the value would return to the balance method (for use in other features where output-based tokens aren’t feasible)?

Sure! So far, it appears that the crucial part would be to bind tokens to an output, and it would also be required, to have an explicit or implicit mechanism to move the tokens back onto to balance-based layer.

There could be a transaction type, much like a "simple send", but instead of associating the transferred tokens with an address as destination, which is provided via the reference output in a "simple send", the tokens could be associated and bound to an output. Such an output could then be considerred as valid sender/source for other transaction types. There are some special cases to handle, for example, if tokens were spent from an output, and used to participate in a crowdsale (who receives the bought tokens?). It is also thinkable to have an explicit "unbind" transaction type, or to establish an implicit rule, such that tokens, spent from a "loaded" output, are credited to the balance of some receiver of the transaction that spends the "loaded" output, even without explicit "command".

---

It's notable that there is no strict requirement of a "publish offer transaction", and once tokens are bound to an output, an atomic trade could be initiated, unrelated to where the incomplete swap-transaction was published. The incomplete transaction basically is the offer.

Let's assume Alice bound some MSC to an output, and indeed published an incomplete swap-transaction, say where 50 MSC are offered, and 5 BTC required to finalize the trade.

Anyone could now take the offer and complete the transaction by providing the missing bitcoins, and broadcasting the transaction, but Alice could as well revoke the offer at any time, simply by spending that output (and maybe creating a new offer, or moving the tokens back onto the balance-layer). The payment of 5 BTC is only required to complete the specific transaction with the payment requirement, which Alice prepared for this purpose. If Alice wants to spent the output, she doesn't have to send 5 BTC to herself, and she could just create another transaction, spending that output.

Also, if Alice already spent the output, or another buyer finalized the trade, the output is (obviously) spent, thus there is no situation where purchases collide and one party might loose coins - it either happens and the trade completes, or it doesn't. This is very relevant, because chaining unconfrimed transactions (thus instant trading) is possible without actual risk for anyone. At worst, a chain of unconfirmed trades may not be valid, but this just equals "it didn't happen, there was no token and no coin movement".

[CraigSellars]

The user could publish transactions via a P2P network or on some website, or … embed incomplete transactions as data payload in the blockchain. ;)

I could kiss you. It was non-obvious to me until you said it. :-D

[CraigSellars]

There could be a transaction type, much like a "simple send", but instead of associating the transferred tokens with an address as destination, which is provided via the reference output in a "simple send", the tokens could be associated and bound to an output. Such an output could then be considerred as valid sender/source for other transaction types.

I see how explicit tx could be used to make the binding, but that would still make a two step process.

So I’m thinking when Alice posts her offer/tx as metadata, this is the transaction that binds her offered tokens to an output (not necesssarily contained in the example outputs above). In order to cancel the trade, she needs to move the tokens back into balance-mode (with a special simple send which does so) or just spends the output?

What about the reverse case? In the example above, Alice is expecting to get BTC for her tokens. What if she were selling BTC and expected to get tokens?

This is where things start to get interesting.

[dexX7]

So I’m thinking when Alice posts her offer/tx as metadata, this is the transaction that binds her offered tokens to an output (not necesssarily contained in the example outputs above).

Let me think about this.. but let's go through it in short (edit: please correct me, if this doesn't make sense, it's a bit late here):

Explicit binding:

1. Alice binds an amount of tokens in transaction A1 with the instruction "bind x MSC to output n of this transaction, and if that output is spent, the tokens shall be moved". This transaction in broadcasted.
2. Alice prepares an incomplete swap transaction S, spending A1.output[n] of transaction A1, with a payment output to herself. The incomplete transaction is embedded as payload in transaction A2, and transaction A2 is broadcasted.
3. Once A1 confirms, to be certain the tokens were indeed bound, Bob adds the missing coins to transaction S, which spends A1.output[n], and broadcasts that transaction. This finalizes the trade.

Embedded binding:

1. Alice prepares an incomplete swap transaction S, spending output n of some transaction A1, with a payment output to herself.
2. Alice creates transaction A2, which embedds the incomplete swap transaction S, and binds an amount of tokens with the instruction "bind x MSC to the output A1.output[n] of that other transaction, and if that output it spent, the tokens shall be moved". This binding transaction, with swap transaction S as addtional payload, is broadcasted.
3. Once A2 confirms, to be certain the tokens were indeed bound, Bob adds the missing coins to transaction S, which spends A1.output[n], and broadcasts that transaction. This finalizes the trade.

Actually, there is not really a difference when comparing both routes, at least on the first glimpse?

Combining output binding and publishing seems convenient, but there might be use-cases, where no on-chain publishing is required, or there could be the case where Alice wants to use a very low fee for the publishing transaction, but a high fee for the binding transaction, because only the later is really important. Binding and publishing transactions could be created and broadcasted in one go and without delay, though it's required for Bob in both routes to see that the binding transaction (either seperated or embedded) actually confirms and is valid (= really bound tokens).

In order to cancel the trade, she needs to move the tokens back into balance-mode (with a special simple send which does so) or just spends the output?

In any case, spending the "loaded" output moves the bound tokens - this is the foundation of the whole approach, but the actual specifics are yet to define. Alice cancels an offer by spending the "loaded" output, and I think it would be nice to have a choice here, and whether Alice spends the output, or Bob, they should be able to:

• transfer and move the tokens back onto the balance-layer
• or bind them to a subsequent output, e.g. to setup another trade

... but that would still make a two step process.

Sort of: from the buyer's POV it's one step - the atomic trade. We have an overhead for the seller, because tokens need to be bound to outputs, and because offers might be embedded on-chain.

Nevertheless, in my opinion, even if all offers were published on-chain, and there would be output-binding, followed by moving back onto the balance-layer, it's probably a significantly better experience, mostly due to the reasons why the traditional DEx is pretty annoying:

• a buyer accepts a DEx offer, but has to wait until the transaction confirmed, and only then he or she can continue with the payment - the actual success rate is low (very wild guess: less than 20 % of accepted offers are finalized)
• buyers can accept DEx offers, but never finalize the trade, and intentionally (or not), this locks tokens for time periods of usually 10 blocks or more
• this can be abused to black out the market, targeting or shutting down sellers/offers
• as soft-prevention there are fees to pay for accepting an offer
• but at the same time it's still uncertain, whether an offer is really going to be accepted, or if it might be taken by someone else

What if she were selling BTC and expected to get tokens?

I'd really, really love to see that as well. The underlying issue is the lack of token-awareness on the Bitcoin-layer, and even though a lot of things can be done with Bitcoin script, see for example cross chain transfers, payment channels with refund transactions or hash puzzles, I'm not aware of a feasible solution. The problem appears to be related to a cross chain transfer, but I haven't digged into it, if something similar could be adopted for this purpose.