Skip to content

Instantly share code, notes, and snippets.

@RubenSomsen
Last active July 31, 2024 14:09
Show Gist options
  • Save RubenSomsen/8853a66a64825716f51b409be528355f to your computer and use it in GitHub Desktop.
Save RubenSomsen/8853a66a64825716f51b409be528355f to your computer and use it in GitHub Desktop.

SAS: Succinct Atomic Swap

Works today with single signer ECDSA adaptor signatures, or with Schnorr + MuSig.
Other than the explanation below, there's also a diagram and a video.

 
Advantages:

  • Requires merely two on-chain transactions for successful completion, as opposed to four
  • Scriptless, and one of the chains doesn't need to support timelocks
  • Can be used for efficient privacy swaps, e.g. Payswap

 
Disadvantages:

  • Access to money is contingent on remembering secrets (backup complexity)
  • Online/watchtower requirement for the timelock supporting chain (not needed with 3 tx protocol)

 
Protocol steps:

 
0.) Alice & Bob pre-sign the following transactions, with exception of the signatures in [brackets]:

  • success_tx (money to Bob): [sigSuccessAlice] + [sigSuccessBob]
  • revoke_tx (timelock): sigRevokeAlice + sigRevokeBob, which must then be spent by:
    • refund_tx (relative timelock, refund to Alice): [sigRefundAlice] + {sigRefundBob}
    • timeout_tx (longer relative timelock, money to Bob): sigTimeoutAlice + [sigTimeoutBob]

{sigRefundBob} is an adaptor signature, which requires secretAlice to complete

 
1.) Alice proceeds to lock up 1 BTC with Bob, using keyAlice & keyBob as pubkeys

If protocol is aborted after step 1:

  • Alice publishes the revoke_tx, followed by the refund_tx & sigRefundBob, to get her BTC back
  • If Alice neglects to publish the refund_tx in time, Bob will claim the BTC with the timeout_tx

 
2.) Bob locks up altcoins with Alice, using secretAlice & secretBob as pubkeys

If protocol is aborted after step 2:

  • Once Alice publishes sigRefundBob, Bob learns secretAlice and regains control over the altcoins

 
3.) Protocol completion:

  • Alice hands adaptor signature {sigSuccessAlice} to Bob, which requires secretBob to complete
  • Bob could now claim the BTC via the success_tx, reveal secretBob, and thus give Alice control over the altcoins (= 3 tx protocol)
  • Instead, Bob simply hands secretBob to Alice
  • Likewise, Alice hands keyAlice to Bob to forego her claim on the refund_tx
  • Bob continues to monitor the chain, because he'll have to respond if Alice ever publishes the revoke_tx

 
More graceful protocol failure:

If the protocol aborts after step 1, Alice would have been forced to make three transactions in total, while Bob has made none. We can reduce that to two by introducing a second refund_tx with timelock that can be published ahead of the revoke_tx and directly spends from the funding transaction. Publishing this transaction would also reveal secretAlice to Bob via an adaptor signature. In the 3 tx protocol, this output can go directly to Alice. In the 2 tx protocol with online/watchtower requirement, this output needs a script: spendable by Alice + Bob right away OR by Alice after a relative timelock. It is important to note that this transaction must NOT be published during step 3. Once Bob can complete the success_tx, the revoke_tx is needed to invalidate the success_tx prior to revealing secretAlice.

 
FAQ:

  • Why not allow Alice to still claim the altcoins if she accidentally lets Bob publish the timeout_tx?

    Alice could send the revoke_tx at the same time, revealing both secrets and causing likely losses. This can be solved by adding yet another transaction, but it wouldn't be efficient and wouldn't motivate Alice to behave.

  • Is it possible to implement this protocol on chains which only support absolute timelocks?

    Yes, but then Bob must spend his swapped coins before the timelock expires (or use the 3 tx protocol). Be aware that the revoke_tx MUST confirm before the timeout_tx becomes valid, which may become a problem if fees suddenly rise. The refund_tx can also not be allowed to CPFP the timeout_tx, as they must confirm independently in order to invalidate the success_tx first.

  • Can't Alice just publish the revoke_tx after protocol completion?

    Yes, she'd first have to move the altcoins (to invalidate secretAlice), and could then try to claim the BTC by publishing the revoke_tx, forcing Bob to react on-chain before the refund_tx becomes valid. The eltoo method of paying for fees (requires sighash_anyprevout) or a second CPFP-able output may be an improvement here (and also mitigates fee rising issues), but note that this also increases the required amount of tx data if the protocol doesn't complete successfully.

  • Can this be made to work with hash locks?

    Yes, by making the altcoins spendable via sigAlice + preimageBob OR sigBob + preimageAlice, and ensuring the contracts on the BTC side reveal either pre-image. Do note that this is not scriptless and will thus increase the transaction size.

 
Open questions:

  • Perhaps it's possible to perform an atomic swap in and out of Lightning with only a single on-chain transaction. This would require some kind of secondary set of HTLCs, allowing the sender to cancel a Lightning payment by revealing a secret after a certain period of time.

 
-- Ruben Somsen

 
 
Thanks to Lloyd Fournier for feedback and review.

 
Related work:

Tier Nolan Atomic Swap: https://bitcointalk.org/index.php?topic=193281.msg2224949#msg2224949
Monero Atomic Swap: https://github.com/h4sh3d/xmr-btc-atomic-swap/blob/master/README.md
Private Key Turnover: AdamISZ/CoinSwapCS#53  

Display the source blob
Display the rendered blob
Raw
Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
@xrqin
Copy link

xrqin commented Sep 19, 2020

I think it is not so succinct. Since you should transfer 1 BTC first. I think this step should count. If so, it still needs four transactions.

@RubenSomsen
Copy link
Author

@mt2Qx3R that step does count. The on-chain steps are:

  1. Alice locks up money.
  2. Bob locks up money.
  3. Bob watches the blockchain and reacts if Alice tries to claim a refund.

Depending on what Alice does, step 3 may or may not occur. Bob can also just perform step 3 if he does not wish to keep watching.

Alice does not have to watch anything. Her side of the swap is instantly settled.

@fresheneesz
Copy link

fresheneesz commented May 12, 2021

I went through all the cases, and after some clarification, convinced myself that it all should work. For anyone that's interested, I wrote up all different edge cases here. I also wrote a node.js script that runs through and validates all the steps (and prints out the state of things after each step). Read the readme for how to run it.

A couple things that tripped me up in my understanding of the cases:

  • I misread that Alice gives Bob serectAlice at the end, when the actual protocol is that Alice gives Bob AliceKey. I think my mindset was that "secrets" were something that could be shared, and keys were private. However, I think the real distinction is that secrets are revealed upon use, whereas keys are not revealed on use (signing).
  • I treated things a little too abstractly and forgot that at the end of the day the main outputs (Created by On-chain transaction BTC and Revoke transaction) are just 2-of-2 addresses that then have things presigned off them. By that I mean, I forgot that once Bob got AliceKey that he could spend from the outputs created by those transactions.
  • The name of the "Success Transaction" is a bit misleading. I took that to mean that in normal operation, Bob would eventually send that transaction. However that's not the case. Instead, Bob will have AliceKey and can send directly from the output created by On-chain transaction BTC to any address he wants. This was compounded by my first two misunderstandings.
  • Also, I was unsure whether refund_tx was presigned by Bob or not (I wasn't sure of the curly braces used there were considered "brackets" that meant it wasn't presigned). It turns out refund_tx is in fact presigned with the adapter signature.

@seresistvanandras
Copy link

Hi Ruben! This is a really nice protocol! Congrats! I agree that the online requirement from Bob's side is kind of suboptimal, but I don't see why statefulness would be an issue as you mention both here and in your video. Wallets, already have a state (they store where you are in the HD-tree used for key-derivation). I think statefulness is not an issue, since this is already the case, no?

To me, it seems that Chris Belcher's CoinSwap proposal got the community's support even though it requires significantly more on-chain space (4 transactions), and hence coordination. Any proposal that relies on interaction over multiple blocks is almost doomed. That's the reason why CoinJoins are deployed way earlier than Coinswaps. Your proposal seems to be optimal in the cooperative case. In the non-cooperative case, we have 3 transactions (with the being online requirement), which is still better than Belcher's proposal. Do you have any insights into why the community wants to go with that proposal instead of this? Anyways, it would be really exciting to see if coinswaps could be deployed and widely adopted soon in the Bitcoin community. You should also try to convince @nopara73 to have Coinswaps in Wasabi soon :))) cc @nothingmuch

@RubenSomsen
Copy link
Author

Thanks for taking the time to understand my protocol, @seresistvanandras :)

they store where you are in the HD-tree used for key-derivation

It's not crucial information though. If you delete your wallet and restore your backup, all your coins will be found, because you just keep searching all keys in deterministic order until you hit a gap of X (I think it's 100) unused keys, and then you stop. If you add state to it, then you continually have to make new back-ups in order to be able to restore all your coins, and I suspect this is also one of the reasons why @chris-belcher preferred to go with a more traditional coinswap method. The uncooperative case in SAS is also a bit awkward, because one person will have to carry the majority of the on-chain cost, so I can imagine that may have played a role as well.

@seresistvanandras
Copy link

But the state (i.e., all the keys used throughout the protocol) could be derived from the HD-tree, no? Or not sure what exactly you refer to a state in SAS. I think you just need the ability to derive as many keys as you want, which is already given via BIP-32.

Yes, the uncooperative case is a little bit nasty. Maybe, it could be improved? Either way, I think it is not a big disadvantage of the protocol that one party bears all the on-chain costs in the non-cooperative case. This asymmetry is also implicitly assumed in Belcher's proposal, where you have takers and makers in the CoinSwap protocol akin to JoinMarket. If you don't like this asymmetry, we can make it a bit fairer. Participants could do off-chain a coin-tossing protocol to decide who will be bearing the costs of the non-cooperative case. I would still bet on this protocol in the long run. 4 on-chain txs sound a way bigger burden than the slight suboptimality of the non-cooperative case.

@nopara73
Copy link

You should also try to convince @nopara73 to have Coinswaps in Wasabi soon :)))

Happy to hear out the arguments. But make it good, because me convincing the developers that it's worthy spending their time on will be the hard part :)

@RubenSomsen
Copy link
Author

@seresistvanandras

But the state (i.e., all the keys used throughout the protocol) could be derived from the HD-tree, no?

The keys that come from your counterparty are new to you (e.g. secretBob if you're Alice), and need to be backed up to ensure access.

Participants could do off-chain a coin-tossing protocol to decide who will be bearing the costs

A malicious party would abort as soon as they lose the coin toss.

@seresistvanandras
Copy link

Thanks, Ruben for the clarifications. In both cases you're right!

I'll answer to @nopara73 a bit later to collect all my convincing arguments why we need Succint Atomic Swap-based CoinSwaps in Wasabi.

@chris-belcher
Copy link

My coinswap design (or rather, gmaxwell's) doesn't necessarily require 4 transactions, in the co-operative case it only needs 2, because of private key handover.

A lot of my thinking around the design was about other issues with coinswap such as the "who goes first problem" (which your post alludes to and which my design deals with using fidelity bonds), the amount correlation problem, the problem of a single party being able to unmix a coinswap and payjoin-with-coinswap.
These problems are what I've spent most time implementing. SAS is orthogonal to those.
Right now my project actually uses 2-of-2 multisig in p2sh addresses, which obviously pretty rubbish for privacy. The plan is to first get working all the other hard parts like the maker/taker liquidity market, multiple transactions, routed transactions, recovering from aborts, etc and afterwards we can swap in ECDSA-2P code or taproot code. There's nothing to say we can't swap in SAS as well or instead of.

BTW, has anyone thought much about extending SAS to support multi-transaction coinswaps? That's pretty necessary for good privacy. So if not then a user could be coinswapping say 1.23456 BTC, the adversary will see that amount go in and can scan the blockchain for later transactions for nearly the same amount. To avoid that any coinswap scheme needs to support multiple transactions. That also means you'll never really get on-chain usage of just 2 transactions, it would need to be more like 6+

@RubenSomsen
Copy link
Author

has anyone thought much about extending SAS to support multi-transaction coinswaps?

@chris-belcher, do you mean swapping with more than two participants like Multiparty S6, or two people swapping more than one output each? I suspect the former may be difficult, but the latter should be fine. It's probably easiest to see on the "LTC" side from the diagram, as that's a simple 2-of-2 output with no scripts. Instead of receiving 200 LTC for 1 BTC, you'd receive e.g. 20 + 60 + 40 LTC for 1 BTC, as soon as the key is revealed on the BTC side.

Anonymity wise supporting cross-chain swaps between Liquid may be beneficial, as it means outputs on Liquid also have to be taken into account when analyzing where a swap could potentially have gone, and because of Confidential Transactions the list of suspects will be equivalent to every recent output. And if high-value exposure to Liquid is not desired, you could swap only a fraction of the value to it (e.g. 1 BTC for 0.95 BTC and 0.05 L-BTC), which could help throw off on-chain amount linkage.

@xrqin
Copy link

xrqin commented Sep 27, 2022

why don't you publish your result?

@nikicat
Copy link

nikicat commented Nov 23, 2023

Hello, is this scheme implemented?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment