Atomic Swaps as American Call Options - possible without new opcode?

[d5000]

Note: My original approach was flawed, but aliashraf designed an interesting proposal for a protocol in post 6.


Atomic swaps, at least in Tier Nolan's variant, include optionality: One of both parties can decide if the swap is been carried out or not. It has thus been argued that they are, in reality, equivalent to an American Call Option: The "option buyer", which is the party that initiates the swap, has time to decide from the moment the other party signs their part of the contract until the timeout of the HTLC.

Now this "bug" or "unfairness", as some descibe it, can be used as a "feature" to implement trustless option contracts where the party who benefits from the optionality pays a premium for that, like described in this article by Runchao Han, Haoyu Lin and Jiangshan Yu (2019).

The authors of this paper, however, argue that Bitcoin Script is currently not providing all functionality for that kind of contract, so a new opcode would be needed.

But is this really the case? I looked at Tier Nolan's protocol and in my opinion there should be a possibility to add a premium payment without needing new opcodes. I am however not a Bitcoin Script expert, so I ask people with a better understanding.

Let's first re-quote Tier Nolan's protocol:

A picks a random number x

A creates TX1: "Pay w BTC to <B's public key> if (x for H(x) known and signed by B) or (signed by A & B)"

A creates TX2: "Pay w BTC from TX1 to <A's public key>, locked 48 hours in the future, signed by A"

A sends TX2 to B

B signs TX2 and returns to A

1) A submits TX1 to the network

B creates TX3: "Pay v alt-coins to <A-public-key> if (x for H(x) known and signed by A) or (signed by A & B)"

B creates TX4: "Pay v alt-coins from TX3 to <B's public key>, locked 24 hours in the future, signed by B"

B sends TX4 to A

A signs TX4 and sends back to B

2) B submits TX3 to the network

3) A spends TX3 giving x

4) B spends TX1 using x

The place where I would add the premium payment is in TX3. What would have been done is to add an UTXO which is spendable by Alice as an input to TX3 and an output of the same value going to Bob. The transaction would have to be signed by Alice and Bob, not only by Bob like in the original protocol.

From my understanding, TX3 is the moment where Bob locks his funds, so he positions himself in an "unadvantageous" position because he is forced to wait, while Alice can initiate the transfer or not. So this would be the moment when a premium payment would be appropiate.

(In the specific case TierNolan described, the premium would have been paid in altcoins, not in Bitcoin. But this depends on who is the option buyer and who the seller and which currencies are used.)

Is this model possible, perhaps it was already implemented in an application? And how would the scripts for TX3 look like in this case?

(I'm sorry if this has been asked before, but I did already a search and didn't find exactly what I wanted to know. The use case I have in mind is a "collar" to hedge from crashes, but it would also make generally trustless American-style options possible. If it's possible without additions to Script I'll post it as a feature request to platforms like Atomic DEX.)

[elvisage]

You should assume Alice is honest if using tx3 to pay for the premium. Alice can choose not to pay the premium in tx3. As you mentioned, Bob is "unadvantageous" at this moment, so cannot enforce Alice to pay for the premium in tx3 or punish Alice.

[d5000]

You should assume Alice is honest if using tx3 to pay for the premium. Alice can choose not to pay the premium in tx3. As you mentioned, Bob is "unadvantageous" at this moment, so cannot enforce Alice to pay for the premium in tx3 or punish Alice.

Well that's just what I want to avoid.

Originally I imagined a "workflow" like this:

1) Bob creates the "structure" of TX3 (modified from TierNolan's post):

"Pay v1 alt-coins from <B-private-key> to <A-public-key> if (x for H(x) known and signed by A) or (signed by A & B), and pay v2 alt-coins from <A-private-key> to <B-public-key>"

2) Bob sends this transaction to Alice.
3) Alice must sign her input for v2 (provide the ScriptSig). Then she sends the tx back to Bob.
4) Bob signs his input and broadcasts the transaction.

Now I think I'm approaching the problem: When Alice signs her input and sends it to Bob, then maybe Bob could simply spend it including it into another unrelated transaction. So in this model Alice would have to trust Bob, if I'm interpreting right.

What we would need is a mechanism that the TX3 transaction "as a whole" must be atomic as well - i.e. that Alice's input only could be spent by Bob if he signs his input. This is where I still struggle if this is possible with multisig scripting. I was imagining something like to realize TX3 as a 2-of-2 multisig transaction. Probably that involves some P2SH trickery.

Edit: Another doubt I have is if it's possible to order the inputs in a manner that really Alice's input is used for the direct payment of the premium to Bob, and not Bob's input. But I think the Bitcoin protocol should determine which input is processed first. Thinking about that again, this should be irrelevant, as TX3 always spends everything.

[elvisage]

> What we would need is a mechanism that the TX3 transaction "as a whole" must be atomic as well - i.e. that Alice's input only could be spent by Bob if he signs his input. This is where I still struggle if this is possible with multisig scripting. I was imagining something like to realize TX3 as a 2-of-2 multisig transaction. Probably that involves some P2SH trickery.

Atomic Swap happens after order matching. tx1~2 have explicit sender and receiver. This gives Bob opportunity to withhold (tx2). This is different from real-world options.
Then, the key issue here is to enable the script (on Bob's blockchain) to distinguish between Alice's misbehaviour (e.g., withholding tx3) and Bob's misbehaviour (e.g., withholding tx2).
To this end, the script paying the premium should examine whether tx2 has been paid within its timelock. If paid, then it's the normal case and premium should be paid. If not after timelock, then Bob misbehaves and premium should not be paid.

To conclude, Bob's misbehaviour space requires the script to distinguish between Alice's and Bob's behaviour, which requires the script paying premium to know the status of tx2.

[aliashraf]

I would propose the following protocol for selling put options:
NOTE: An improved version is presented in my next post, though I preferred to keep this version.

0- Bob, asks xBTC for the premium of a put option, exchanging his v bitcoins with w Xcoin within 48 hours where x << v. Alice accepts the trade:

1- Alice generates a (P2WSH) TX_p sending (in its first output) x BTC to the hash of following  script:

Code:

IF
      <7 days> CHECKSEQUENCEVERIFY DROP
      <Bob'e Pubkey> CHECKSIGVERIFY
ELSE
    2 <Alice's Pubkey> <Bob'e Pubkey> 2 CHECKMULTISIG
ENDIF

Basically it locks the value of put option (x) for a week meanwhile it is spendable with a 2 of 2 signed transaction.

2- Alice, gives Bob an unsigned version of TX_p and the redeem script behind it, letting him compute ID(TX_p). Note that the segregation of witness data (Alice's signature) plays a vital role here for Bob being able to compute the transaction Id without havin an opportunity to seize the funds and getting away without further commitment to the process.
 
3- Alice generates TX_Xcoin on the Alt-chain paying w to Bob's XCoin address through an HTLC contract locked on SHA256(u) for 72 hours

4- Bob genrates TX_btc which is:

a) total amount is fee + v + x + extra(>=0)
b) first input spends TX_p the other input(s) (which also belong to Bob) spend fee + v + extra(>=0)
c) one output is Bob'e receivig address and gets x (the premium)
d) one output is Alice's btc receiving address and gets v, it is HTLC locked for 48 hours on SHA256(u)
e) other output(s) (belong to Bob, if any) receive the extra amount

5- Bob provides his signatures for TX_btc sending it to Alice to provide her signature for the 2-of-2 requirement of the first input.

6- Alice has a decision to make:
1) She could choose to ignore the whole process, waiting for the 72 hours lock time on TX_Xcoin to become void, redeeming her Xcoins.
2) She can follow the trade by publishing both TX_p and TX_btc .

In either case, Bob is safe because his bitcoins are not locked unless the premium is paid by Alice (locking transaction, TX_btc, depends on the premium payment, TX_p, as one of its inputs).

7- Alice has another decision to make within 48 hours
1) providing hash(u) while spending her input from TX_btc.
2) doing nothing and waiting for locks to expire.

in case 1, bob claims w Xcoins in exchange for his v BTC which is already claimed by Alice, and in both cases, he receives x BTC for the premium he has offered to Alice.

[aliashraf]

In the above protocol, I missed one critical point: After step #6, Bob is able to make TX_btc void by double-spending his other input(s) with higher fees, then he can simply wait for 7 days and take the premium value (x_BTC) without committing to the exchange process anymore.

To mitigate this bug, I'd Improve the protocol by requiring Bob to lock his funds (v_BTC+fee) for a very short period of time (like 12 blocks) in another multi-sig address and using this transaction as the second input to TX_btc.

So the new version would be:

0- Bob, asks x_BTC for the premium of a put option, exchanging his v bitcoins with w Xcoin within 48 hours where x << v. Alice accepts the trade:

1- Alice generates a (P2WSH) TX_p sending (in its first output) x_BTC to the hash of following  script:

Code:

IF
      <7 days> CHECKLOCKTIMEVERIFY DROP
      <Bob'e Pubkey> CHECKSIGVERIFY
ELSE 
    2 <Alice's Pubkey> <Bob'e Pubkey> 2 CHECKMULTISIG
ENDIF

Basically it locks the value of put option (x_BTC) for a week meanwhile it is spendable with a 2 of 2 signed transaction.

2- Bob generates a (P2WSH/P2SH) TX_btc0 sending (in its first output) (v+fees)_BTC to the hash of following  script:

Code:

IF
      <12 blocks> CHECKSEQUENCEVERIFY DROP
      <Bob'e Pubkey> CHECKSIGVERIFY
ELSE 
    2 <Alice's Pubkey> <Bob'e Pubkey> 2 CHECKMULTISIG
ENDIF

It locks Bob's coins (v_BTC) for a very short period of time meanwhile it is spendable with a 2 of 2 signed transaction.


3- Alice, gives Bob an unsigned version of TX_p and the redeem script behind it, letting him compute ID(TX_p). Note that the segregation of witness data (Alice's signature) plays a vital role here for Bob being able to compute the transaction Id without having an opportunity to seize the funds and getting away without further commitment to the process.
 
4- Alice generates and publishes TX_Xcoin on the Alt-chain paying w to Bob's XCoin address through an HTLC contract locked on SHA256(u) for 72 hours

5- Bob genrates TX_btc which is:

a) The first input spends TX_p (x_BTC)
b) The second input spends TX_btc0 (fee_BTC + v_BTC)
c) The first output is Bob'e receivig address and gets x_BTC (the premium)
d) The second output is Alice's btc receiving address and gets v_BTC, it is HTLC locked for 48 hours on SHA256(u)

6- Bob provides his signatures for TX_btc sending it to Alice to provide her signature for the 2-of-2 requirements of both inputs.

7- Giving a heads-up to Alice, Bob publishes TX_btc0 and remains online scanning the network for a while

8- In the short period of time after TX_btc0 is published by Bob and confirmed by the blockchain, Alice has a decision to make:
1) She could choose to ignore the whole process, waiting for the 72 hours lock time on TX_Xcoin to become void, redeeming her Xcoins, while her x_BTC payment is not (and won't be ever) published.
XOR
2) She can follow the trade by publishing both TX_p and TX_btc .

In either case, Bob is safe as either Alice is not offered any premium at all or she has paid for it. He could decide to prevent TX_btc from being confirmed, if Alice hesitates to publish it for too long, by double-spending its second input once it becomes unlocked after 1-2 hours.

9- Given the process is not interrupted by any party and all of the transactions (three bitcoin txns and one Xcoin txn) are properly published and confirmed, Alice has another decision to make within 48 hours:
1) providing hash(u) while spending her input from TX_btc.
2) doing nothing and waiting for locks to expire.

In case 1, Bob claims w Xcoins in exchange for his v_BTC which is already claimed by Alice.
In case 2, Bob reclaims his bitcoins after 48 hours.
In both cases, he receives x_BTC for the premium he has provided to Alice.

[d5000]

@aliashraf: Impressive, thanks! I have not checked every step in detail for double-spending potential, but looked at the general sequence of the first and the second variant, and I think I understood the sense of every step. So from my interpretation the second variant should work. It is interesting that it needs Segwit to work properly, never thought about these implications of the signature data segregation.

Obviously we can also realize call options with that scheme, simply inverting the coins involved (when Alice buys an option to "sell BTC", with this operation she "buys the altcoin", so it can also be done the other way around).

Atomic Swap happens after order matching. tx1~2 have explicit sender and receiver. This gives Bob opportunity to withhold (tx2).

I think you mean that he can withold tx3 (instead of tx2, which is under Alice's control). But your post made me think about the whole process and my original approach has a deep flaw - Alice could get into a state where she would have her coins locked until the option's expiration. From my interpretation, she would not have paid the premium in this case, and Bob wins nothing, but she would lose access for a considerable amount of time, which is inacceptable.

So let's throw away that approach and continue with aliashraf's mechanism. I'll re-look at it with a fresh brain these days (it's still not accustomed to these HTLC constructions ) to examine it for potential problems, but so far it looks good.

[elvisage]

I think you mean that he can withold tx3 (instead of tx2, which is under Alice's control). But your post made me think about the whole process and my original approach has a deep flaw - Alice could get into a state where she would have her coins locked until the option's expiration. From my interpretation, she would not have paid the premium in this case, and Bob wins nothing, but she would lose access for a considerable amount of time, which is inacceptable.

Ah sorry I refer to wrong txids. Yes I mean tx3 (Bob htlc-pays Alice coins). Alice waiting for timelocks to expire is inevitable. There should always be someone initiating the swap. As long as the swap is timelock-based, the initiator Alice should wait until the participant Bob participates in the swap.

The problem is that, if Bob stalls (tx3), Alice should not pay the premium. Meanwhile, if Alice stalls (tx2), Alice should still pay the premium.
Neither combining premium into tx1-4 trivially or paying premium independently works.
If the premium is paid in tx1, then Alice does not need to pay premium if she stalls tx2. But she should have paid as she uses her option.
If the premium is paid in a separate transaction without any dependency with tx1-4, then Alice can choose not to commit the premium transaction.
If Alice is forced to pay premium, then Bob may stall tx3-4 while receiving premium. But he should not receive premium as he does not participate in swap at all.


@aliashraf

This is an interesting one, thanks!
Here is my analysis. It's a complex protocol, so please correct me if I'm wrong somewhere.
My understanding is that, this is still an American Call Option.
You refer this as "selling put option". Although Bob "asks for" Alice to do this, Alice is the one with option, and she pays for this option with premium.
Also, in this protocol, Alice pays premium using Bitcoin rather than altcoins.

So the key techniques here are:
- Premium transaction tx_p has two branches. One branch requires multisig, while the other has a long timelock and only requires Bob's signature.
- You couple tx_3 (Bob htlc-pays Alice BTC) with tx_p as follows. In tx_btc, you use premium (i.e., output of tx_p) as input. In this way, no one can commit tx_3 before committing tx_p.

As you mentioned, the first post does not work, as Bob can get premium for free by waiting for 7 days.
To prevent this, you further use a transaction tx_btc0 with BTC as both input and output. Bob should wait for 12 blocks if he wants to spend BTC elsewhere. The tx_btc0 output is also used in tx_btc.

Here are some issues I identified:
1. I'm not sure whether such a transaction with overlapped conditions is acceptable on Bitcoin. I'm also not sure how Bitcoin deals with chained timelocks, i.e., whether a htlc-ed output can be spent by another htlc-ed output. For example, what if both tx_btc and tx_btc0 are committed, but after 12 blocks (before 48 hours) Bob spends tx_btc0's output? Then tx_btc is no longer valid. I'm not sure how Bitcoin deals with this.
2. The timelocks need to be chosen in a very careful and proper way. If tx_p's timelock is too short, Bob gets premium for free. If tx_p's timelock is too long, Alice may not have enough time to redeem BTC in tx_btc. Also, why 7 days for tx_p? It can be much shorter. Maybe we can couple tx_p with tx_btc0/tx_btc?
3. The option's strike time should be re-considered. Alice's option may not be 48 hours anymore. It's more like 48 hours - 12 blocks or something more fine-grained.

I believe these two techniques can lead to some more succinct and straightforward constructions. This is quite interesting and I will think about it.

[aliashraf]

@aliashraf
{snip}
My understanding is that, this is still an American Call Option.

Sure. Tier Nolan(2013) protocol fails because it goes the wrong direction: trying to build a protocol for a fair p2p swap. I could mathematically prove that it is not possible no matter how complicated the protocol may be. There is always a premium in a p2p swap and the right thing to do is to evaluate and sell this premium.

Here are some issues I identified:
1. I'm not sure whether such a transaction with overlapped conditions is acceptable on Bitcoin. I'm also not sure how Bitcoin deals with chained timelocks, i.e., whether a htlc-ed output can be spent by another htlc-ed output.

HTLC is not being treated specially in bitcoin, just an output script that is run once someone is trying to spend it.

For example, what if both tx_btc and tx_btc0 are committed, but after 12 blocks (before 48 hours) Bob spends tx_btc0's output? Then tx_btc is no longer valid. I'm not sure how Bitcoin deals with this.

When TX_btc is committed by a block, the first output of TX_btc0 which (being an input for the first transaction) is no longer a UTXO and by no means Bob would be able to spend it.

2. The timelocks need to be chosen in a very careful and proper way. If tx_p's timelock is too short, Bob gets premium for free. If tx_p's timelock is too long, Alice may not have enough time to redeem BTC in tx_btc.

TX_p is spent by utilizing the multi-signature branch of its script as soon as TX_btc is confirmed, no matter how long the lock in the other branch may be.

Also, why 7 days for tx_p? It can be much shorter. Maybe we can couple tx_p with tx_btc0/tx_btc?

The amount of bitcoin Alice locks in TX_p is equal to the value of the premium which is much lower than the trade volume, so, it is chosen to be long enough for both parties' convenience.
Although I didn't get what you mean by 'coupling', I would say they are already 'chained' in the protocol.

3. The option's strike time should be re-considered. Alice's option may not be 48 hours anymore. It's more like 48 hours - 12 blocks or something more fine-grained.

In practice, selling a put option online and p2p takes preparation time and it looks to be more reasonable not to calculate that time as part of the main trade.

[d5000]

I had a bit of time to look a little bit deeper into @aliashraf's proposed protocol. I think it is sound so far, and I'm preparing a rudimentary infographic about it.

There are possibly two minor issues I stumbled upon:

Bob can decide to abandon the trade after step 4 (after Alice's publication of TX_Xcoin). This would give Alice a disadvantage as she would lose transaction fees and her coins would stay locked for 72 hours. But she wouldn't pay for the premium in this case. Bob could get an advantage from that if there is a very fast price change in the time before the operation which would benefit Alice if she performed the trade (in our example, Bitcoin going up fastly against Xcoin).

I think however, that this would simply lead to slightly lower prices for the option (i.e. the premium payment) than if this issue didn't exist. I don't know if the issue is solvable.

A more dangerous but highly unlikely attack is maybe possible if Bob bribes a strong mining pool. In step 8, if Alice's decision to follow the trade comes late (e.g. one block before the timelock expiration for TX_btc0) or has low fees, Bob and the miner could collaborate to orphan Alice's transaction, so Bob can double spend the input and thus could invalidate TX_btc in the next block. But Alice can always prevent this reacting fast and including a generous miner fee. Maybe, however, 12 blocks is a bit short for the timelock. It is however difficult to imagine a situation where the miner would accept a bribe for this operation which is lower than the premium payment, and it also isn't guaranteed to be successful if the miner doesn't own 50%+.

There is a thing I don't understand: Is the 7 days timelock branch in TX_p really necessary? From my interpretation, if TX_btc is published by Alice together with TX_p then the second condition (2-of-2 multisig by Alice & Bob) would always be triggered, so the 7-day-timelock branch in this case would not become active. But does it make sense for Alice to only publish TX_p without also publishing TX_btc - that would mean, she pays for the option but abandons it? I guess that has to do with a double spending attack, but I still don't get it.

I'll wait a bit if there is more feedback on this, but I would like to propose this protocol to be added to atomic swap tools like AtomicDEX and Liquality if there are no major issues with it.

Edit: I have maybe found a way to deal with the problem that Bob can abandon the trade after TX_Xcoin which would not need additional complexity.

Instead of waiting for Alice to confirm TX_Xcoin and then publishing TX_btc0, Bob could sign TX_btc0 and send it to Alice. It would be Alice the party which would broadcast this transaction, together with TX_Xcoin.

The advantage: Alice would only lose transaction fees for TX_Xcoin if Bob decided to abandon the trade while the 12 block timelock of TX_btc0 lasts. But then Bob would also lose the transaction fees for TX_btc0.

A "malicious" Alice could obviously broadcast TX_btc0 and then abandon the trade. However, Alice has absolutely no incentive for that (other than harming Bob) and the harm to Bob is minimal as the timelock is short. Instead, if Bob abandons the trade after TX_Xcoin, the timelock for Alice is longer than the time until the option expiration, and as I wrote above he could indeed have incentives to abandon the trade if the BTC price is increasing.

In theory, Alice and Bob could even provide half of the transaction fees for TX_btc0 each, so both have something to lose. This would obviously only make sense if the fees are very high (and there is extremely little trust between both).

(I've found my thought flaw: From the point Bob publishes TX_btc0 on, Alice has also control about TX_btc.)