Posted by: Adam Gibson | in Bitcoin, Cryptography | 21 hours, 25 minutes ago | 0 comments

A curious, hybrid, unlinkable, signature algorithm independent atomic swap

Previous blog posts (here, here) covered the idea of atomic swap, how to make it private/unlinkable (at least under cooperation), and how to get a much better version after the advent of Schnorr signatures (the "scriptless script" primitive of Poelstra).

In this blog post I want to show one of a number of possible variations. It is "hybrid" only in a loose sense: there are a lot of previously existent ideas that I've here mixed together to form this particular set of properties.

The TLDR is: an atomic swap (one blockchain or cross-chain) with *no* linkage between the transactions, even if one party chooses to be uncooperative, and not dependent on the two chains using the same signature algorithm.

Before starting, it's worthy of note that I may be slightly abusing the term "unlinkable" here; the swap described is not unlinkable by the participants, but only by third party observers. Achieving the former is possible: see Tumblebit (linked below), but also a recent proposal by Jonas Nick, which uses Schnorr blind signatures.

To go into the details, we first need some background for context:

Weaknesses of multi-transaction contracts

For the purposes of this discussion, it's quite useful to start (assuming you're already au fait with what an atomic swap basically is, and/or have read the above two blog posts) by noting what the limitations and problems are with doing atomic swaps (not shared by all variants). They are:

• Interactivity - (this is also shared by CoinJoin, except see SNICKER (which doesn't apply here))
• XBI - A term I just coined, meaning "cross-block-interactivity" - I consider this a separate and far more important limitation than the previous. For two parties to simply share some data over a network is a bit of an issue, but a far bigger issue, in my opinion, is having multiple rounds of interactivity separated by waiting for confirmations on the blockchain. This somewhat overlaps with the next issue:
• Security assumptions about the blockchain - any contract that involves more than one disconnected transaction must be protected from deadlock with timed backout paths (separate txs or paths in script); which means that the inherent miner censorship risk goes from "I may not be able to spend for a while until Jihan gets bored" to "I may lose all the money in this contract if a cartel of miners decide they don't like me for a few hours" or, far more likely "if the internet is blocked for a few hours in the Republic of Bitcoin where I live". The "a few hours" is, of course, configurable, but with a usability tradeoff. In short, there's a liveness assumption and a non-censorship assumption, with the former being the really important one.
• Privacy - the naive atomic swap construct in Script (using hash preimages) has no privacy, necessarily (due to entropy requirement of hash preimage), from any even slightly competent snooper. On the other hand, the best (afaik) variant of atomic swap/CoinSwap we have today, somewhat confusingly called "scriptless script atomic swap" (see second of two blog posts), completely solves this issue (even in non-cooperation) as well as having other advantages. It can't be done today with Schnorr signatures on Bitcoin, because we don't have them; it can be done according to the recent work of Moreno-Sanchez et al using ECDSA 2PC, but this is relatively new (which I may talk about in a future post).
• Compatibility - both transactions ideally occur on the same blockchain, or if different, they must be compatible in having either the same signature algorithm and perhaps elliptic curve (thinking scriptless scripts), or the same hash function in their Script (if they even have Script).

You'll note I've been talking about "atomic swaps", but that the subtitle heading refers to "multi-transaction contracts". These concerns all apply to Lightning network which in its "network" part currently uses HTLC hops (with HTLC being the basic atomic swap) and in its "Lightning" part uses the Poon-Dryja bidirectional channel construct, which also uses timing control as a crucial element of its security promises.

I hope it's clear why some combination of bullet point 2 (XBI) and most critically bullet point 3, above, (security assumptions about the blockchain itself) are a very big issue for all of these constructions. If you're planning to CoinSwap your life savings (or Lightning-swap/route through channels), you'd better be sure your internet is working, your blockchain access is viable, and (far fetched, but..) the miners aren't out to get you. To be fair, the Lightning people are working on watchtowers, but that's an amelioration, not a solution, to this inherent problem.

Lastly, in this section, I want to point out a small nuance which will become important in my next blog post: these concerns don't apply to a certain class of multi-transaction contracts which are connected (i.e. a tree structure with a single root). But that's another topic and not relevant here.

Motivation, and previous related ideas

Unfortunately the new flavour of swap I'm going to propose only addresses points 4 and 5 in the above, so not points 2 and 3 which I've just argued are the most important. So I think this idea is interesting but not exactly amazing :)

In thinking about how to try to solve some of these issues, I remembered in particular the mechanics of Tumblebit (my blog post, original paper), and also the general idea of Greg Maxwell called Zero Knowledge Contingent Payments from 2011.

In recent discussion Olaoluwa Osuntokun also pointed me at this paper from 2015/2016 by University of Warsaw researchers Banasik, Dziembowski and Malinowski, which actually is discussing a lot of closely related ideas: how can we effect something like zero knowledge contingent payment using cut and choose, but it also discusses ways of creating single ECDSA pubkeys through 2PC and the Paillier encryption system. It also uses a number of other elements which I decided weren't needed for my goal as described here.

Tumblebit involves two cut-and-choose protocols, with a blinding step between them to prevent the server learning a linkage. But the root idea of the first protocol, called the "Puzzle Promise Protocol", struck me as quite generic: I will give you an encryption of a signature and a hash of its decryption key. If you can learn the hash preimage, you can learn the signature and spend the coin (basically). This cut and choose is a very generic kind of interactive zero knowledge proof, although it has a quirk - to gain reasonable security, you need a whole set of valid signatures, not just one; in the Bitcoin transaction scenario, however, that doesn't matter, because the entire point of the blockchain is to prevent double-spending.

(Of course, the ZKCP construction is basically doing the same thing, just more generically/powerfully, and doesn't require provision of multiple puzzle solutions simultaneously, and importantly, it's non-interactive: you can encrypt a solution to a puzzle and prove in zero knowledge using systems like zkSNARKs that your solution is valid and then sell the preimage of the decryption key, as above. These more powerful proving systems, though, have bigger computational requirements, see the first example ZKCP, in which 20s was recorded as the proving time; note this has almost certainly improved, although Sudoku is kind of a toy example. Also, I believe the example shown there was proven to have invalid assumptions, specifically that the payer can be trusted to generate the CRS, but it turned out that this broke the witness indistinguishability property that guaranteed the zero knowledgeness property of the proof; see this paper for details and fixes. But - tangent over! ))

So what if we do such a cut-and-choose, and then have the hash preimage revealed in a separate, disconnected transaction? There are two advantages of doing things this way: (1) no linkage is possible because the hash preimage is only revealed in one transaction (and only in the non-cooperative case), and (2) the exact signature algorithm of the first payment (the one whose sig is encrypted) is irrelevant. This might mean, for example, that doing a swap between Bitcoin and a blockchain which uses a different elliptic curve for its signatures (e.g. curve25519) and/or a different signature scheme (edDSA, which is a variant of Schnorr, for example, or perhaps less well known things like hash-based signatures).

The next 3 subsections will discuss the steps in what has just been outlined very briefly. We'll revisit our friends Alice and Bob; we'll assume Bob's 1 coin resides on the BTC blockchain and we'll say Alice's 1 Alice-coin is on the Alice-chain (not specifying which blockchain it is, and magically assuming that 1 Alice coin = 1 BTC).

Move coins to shared control

This is by now a design pattern. To start doing contracts, you have to have both parties put their coins into shared control, which effectively means 2 of 2 multisig outputs. Before doing so, however, to prevent deadlock/MAD scenarios, you pre-sign backout transactions (or backout script paths) to return coins to the original owner in case of disappearance of the other party. There is a small twist here though: only Alice puts coins into "escrow" this way, before the cut-and-choose described next; but that's OK because it reveals no information to Bob on its own.

1. Both sides share the necessary ephemeral pubkeys
2. Both sides deduce txs TX1, which pays from Alice's 1 coin to a destination 2-2-AB-1, and TX2, which pays from Bob's 1 coin to a destination 2-2-AB-2. They then note the txids of TX1, TX2.
3. Bob signs a transaction from 2-2-AB-1 to Alice's backout destination, but with nlockTime L1. Alice will sign a transaction from 2-2-AB-2 to a custom redeem script, as described in "Preparing Bob's payment" below, with nLockTime L2 where L2 < L1. This will happen after Cut-and-Choose, described in the next section.
4. Alice broadcasts TX1, safe that after a fixed time period she can retrieve 1 Alice-coin in non-cooperation. The asymmetry in timeout values described above so that Alice cannot wait till after her nLockTime and claim both coins using the secret which only she, initially, knows.

You'll note that we have tacitly assumed that Alice-chain supports 2 of 2 multisig in some or other form, and nLockTime or something directly equivalent.

Cut-and-choose

This is a brief refresher that is basically identical to what was called the "Puzzle Promise protocol" in Tumblebit (for links see above). Since it's the core idea here, it's worth going over the steps:

• Bob prepares \(N\) fake hashes of format \(H(\textbf{fixed-string-for-all-fakes}||y)\) where \(y\) is random, for blinding.
• Bob prepares \(M\) real transactions paying from 2-2-AB-1 to his own destination addresses. Each destination must be different.
• Bob commits to a jumbled order of the \(N+M\) real and fake hashes and sends that commitment along with the hashes themselves (which are all, also, commitments - both real and fake have the hiding and binding property)
• Alice signs all of the hashes, not knowing the difference. The signing algorithm on Alice-chain, remember, is unspecified. Then she chooses independent symmetric encryption keys \(k_i\) for each of them, and encrypts each of them to \(E_i\) with those keys (using e.g. xor). She sends to Bob \((H(k_i), E_i) \ \forall i\)
• Bob sends to Alice the openings of the \(N\) fake hashes; Alice verifies correct preimage format, then passes to Bob the decryption keys for the fakes.
• Bob verifies that the preimages of \(H(k_i)\) values match the revealed \(k_i\)s, and that the fake hashes were properly signed using the appropriate verification function for the signature algorithm on Alice-chain (digital signatures must all have at least the three algorithms KeyGen, Sign and Verify).
• Now Bob knows that each of the remaining \(H(k_i)\) values are in fact hashes of the correct decryption keys for the corresponding \(E_i\)s with security \(~1/\left(\frac{N+M}{M}\right)\). This can be about 80 bit security with \(N=M=42\), from a simple combinatorial argument, as observed in the Tumblebit paper and blog.

This process requires a bit of interactivity of course; but it's not XBI and it's not crazy large (with fast network connections, this basically 2 rounds of interactivity could be effectively immediate, which may (although it's a stretch) be considered an advantage over a non-interactive protocol like zkSNARKs which may take an appreciable amount of resources/time.

Prepare Bob's payment

Bob now prepares a transaction paying from 2-2-AB-2 (i.e. using as input the txid of TX2) to an output whose scriptPubKey is roughly:

IF HASH H(k_i) EQV ALICEPUB CHECKSIG 
ELSE L2 CHECKLOCKTIMEVERIFY DROP BOBPUB CHECKSIG ENDIF

where i is just one of the 42 real-hash indices at random, and of course ALICEPUB, BOBPUB are just pre-specified ephemeral keys belonging to Alice, Bob. The transaction pays 1 coin (here BTC; remember we assume Bob is transacting on the BTC chain).

Both Alice and Bob now sign this transaction, and Bob broadcasts TX2. After it confirms, Alice can now be sure that at any time before L2 she can sign and broadcast this new transaction, and then spend out of it, receiving her coin in the scriptSig/witness of that second transaction, as intended, and perforce revealing to Bob the decryption key \(k_i\) which he in turn knows by the cut and choose argument that he can use to decrypt a signature on a payout of 1 Alice-coin from 2-2-AB-1. The atomicity is precisely here.

If she spends into it (the TX2->custom redeem script transaction) but doesn't spend out of it, Bob retrieves his 1 coin and of course cannot claim the Alice-coin.

As we have seen before in CoinSwap protocols, it makes sense to, at this point, create an "overlay" output. If Alice is cooperating and trying to create the best privacy, she will, instead of signing/broadcasting the first transaction described in the previous paragraph, send the decryption key directly to Bob over the private channel. Then Bob and Alice can cooperatively create a new payout from 2-2-AB-2 to Alice's chosen output destination, paying the 1 BTC coin. Bob takes no risk doing this once he has the decryption key allowing him to claim his 1 Alice-coin, and Alice takes no risk since if Bob refuses to cooperate in this last step, she can always sign/broadcast the transaction to the custom redeem script above (note it is locked to her pubkey), and spend out of it before the locktime expires. These steps of reasoning are ~ the same as in the blog post "CoinSwaps".

Summary

As was mentioned at the beginning, this is not a very interesting alternative to existing atomic swap constructions, but I wanted to write it out for a few reasons:

1. It does not involve any correlation between the two payments, whatever blockchain they're on, even in the case of non-cooperation (when Alice has to broadcast the transaction paying to a hash preimage). This is because the cut-and-choose "side" of the protocol doesn't have any information in its redeeming step; just a spend of a multisig output, whether it was cooperative or not. This is better than the Maxwell-style CoinSwap or the original atomic swap based on hash preimages on both sides (which therefore correlate).
2. There are corner cases where it solves a problem that even scriptless scripts couldn't - specifically with incompatible blockchains, different curves, different signature algos, or perhaps the lack of a hash scripting facility (although it needs both multisig and some kind of timelock, so not sure how many such blockchains exist!)
3. Perhaps most importantly, I wanted to write this out so that it might give other people ideas about how to use this toolset - cut and choose, interactive ZKP, multi transaction contracts, in other interesting ways. I'm particularly interested to know if people have ideas about how to make the interactivity less, but it might not be possible if your goal is specifically to swap coins into different histories.

Share on Twitter Share on Facebook

• ← The steganographic principle