(**THIS ALGORITHM IS BROKEN** .. OOPS! LEAVING FOR POSTERITY, BUT I HAVE MARKED WITH *** A COMMENT IN THE BELOW THAT IDENTIFIES THE FLAW IN THE REASONING. Also, there is a way I think it could be made to work, but only in a more restricted context than initially envisioned; again, see the comment below marked with ***).
(Note as of 30 Jun: edited to alter the algorithm steps; note there is more than one way to do this.)
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:
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:
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 point 2 (XBI) and most critically 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.
The new flavour of swap I'm going to propose addresses points 4 and 5 in the above, and partially point 2 ("XBI"), if we allow that one half of the swap is identifiably a non-standard transaction (revealing hash preimage). You can increase privacy by adding more interactivity, but what I present from here is a version with interactivity minimized.
So, since it's rather a niche, and it doesn't address point 3 and only partially point 2, 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 in utxo UB 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 in value) in utxo UA.
M(N, M, key1, key2, ...) refers to a N of M multisig on those keys.
First some commentary on the design before explaining in detail the meaning of Cut and Choose here (the next subsection, below).
You'll recall from the "CoinSwaps" blogpost that a simple atomic swap allows the participants to simply pay into custom scriptPubKeys of type "HTLC" (hash, key1 or timeout, key2), which removes XBI at the price of having hash preimages linked across the txs. The alternative is to have the two parties pay into a shared control outpoint - i.e.e a 2 of 2 multisig - this allows use of "overlay" payout transactions which don't involve hash preimages and thus preserve privacy. This you get at the cost of XBI since you have to wait for the funding 2 of 2s to confirm (as in Lightning).
So, here, what we are doing is to remove the XBI by not requiring Alice, the holder of the secret, to pass it across to Bob after this 1 phase of interactivity (after any confirmations), like in the basic atomic swap, but we won't lose the privacy since the hash preimage will only be revealed one side. This will be clear after the "Second stage" is written out, hopefully. 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.
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:
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.
The remaining steps of the protocol can be done without Alice and Bob communicating, but each side's security does critically depend on timely access to the blockchain.
These steps must be in the following "serial" order, not done in parallel, for reasons that'll be clear if you think about it.
IF HASH H(k_i) EQV A3 CHECKSIG
ELSE L2 CHECKLOCKTIMEVERIFY DROP B3 CHECKSIG ENDIF
where i is just one of the 42 real-hash indices at random. Bob broadcasts this. Alice must wait for this to confirm.
After it confirms, Alice can now, at any time before L2, broadcast a transaction spending from this TX2, claiming her 1BTC and revealing \(x\). Bob will then decrypt \(E_k(\sigma)\) and retrieve his 1 Alice coin.
A final note (common to all these designs): the locktime L2 must be closer in time than L1 so that Alice can't wait until after L1 to backout her commitment and claim the 1BTC with \(H(x)\).
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:
Adam Gibson (21)