The half scriptless swap

Posted by: Adam Gibson | in Bitcoin, Cryptography | 1 year, 3 months ago | 0 comments

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

(**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:

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:

  1. Interactivity - (this is also shared by CoinJoin, except see SNICKER (which doesn't apply here))
  2. 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:
  3. 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.
  4. 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).
  5. 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 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.

Motivation, and previous related ideas

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 stage - the interaction

  1. CONNECT
  2. Negotiate keys: A1,A2, A3, B1. Create M(2,2,A1,B1). Alice create txid for TX1 from UA to M(2,2,A1,B1), give to Bob. Bob pre-sign backout to A2 with nlocktime L1.
  3. Alice gives key A3 as ephemeral key for BTC side of swap.
  4. A and B do "cut and choose" (see below), ending with Bob receiving \(H(k)\) and \(E_k(\sigma)\) for M distinct cases, where \(\sigma_M\) is a signature on M(2,2,A1,B1)->B2_M.
  5. DISCONNECT

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.

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 M(2,2,A1,B1)->B2_M to his own destination addresses. Each destination must be different (he does not communicate these addresses of course).
  • 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/\binom{N+M}{M}\). 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 REASONING IS FLAWED: Tumblebit used the RSA quotient test to ensure a vital property: that if any one of the M remaining decryption keys is valid, so will they all be; without that property, and allowing successful decryption with any one of them, we don't get the required combinatorial argument; to succeed in cheating you just need to have guessed which specific "real" decryption key hash is the one that's going to get picked. So it's linear rather than combinatorial, which is far too weak for realistic N, M. If we wanted to keep this property without RSA we'd need to use a similar homomorphism; I think if we replace the hashes of keys with curve points (like K = kG, with k the decryption key), it might be possible to make the construction work; but this would probably mean assuming the use of something like Schnorr, which we were trying to avoid. I haven't yet tried to work out the details.).

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.

Second stage - the broadcasts

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.

  1. A broadcasts the transaction TX1: UA->M(2,2,A1,B1). Bob must wait for this to confirm.
  2. Bob now prepares a transaction TX2 paying from UB to an output whose scriptPubKey is roughly:
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)\).

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 (here, 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. You can certainly write a different version of this protocol (as I did originally before editing! - where you avoid publishing a hash preimage in the cooperative case; as mentioned, the tradeoff is you put in more "XBI" which I think is very undesirable).
  4. 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.
Currently unrated

Comments

There are currently no comments

New Comment

required

required (not published)

optional