Making MAST Meaningful; Bitcoin Atomic Swaps Become Private

Atomic + MASTs

There has been a lot of talk recently about atomic swaps. What hasn’t gotten much attention, though, are the privacy implications. The current way they get implemented, are not very private. MASTs (Merkleized Abstract Syntax Trees) have been described generally as a privacy improvement. This example shows a practical and significant privacy improvement (assuming MAST gets integrated into Bitcoin).

The community at this point is generally concerned more with ease of use than privacy. For example, all Shapeshift transaction are public. These are surely being saved and used by coin tracking services. I suspect that most users would opt for enhanced privacy if given the opportunity.

All Shapeshift transactions are public

Atomic swaps are even worse from a privacy perspective. As they are currently used, the trade is permanently and publicly recorded on the blockchain. Coin trackers at any point in the future can trace a transaction across blockchains. Lets examine how a CLTV based cross-chain swap currently works.

Today’s atomic swaps

With the above procedure, both parties’ coins are returnable if the other party disappears. Either the timer expires, and they get their coins back, or x is revealed and both Alice and Bob can claim coins. The atomic part is where Alice publicly reveals x on the W chain. Bob can find x, since it is now public, and use that to claim his coins. Alice cannot take the W coins without giving Bob the missing piece needed to take the Y coins. While safe, it has the disadvantage of publicizing that these are the same transaction. The presence of both Hash(x) (shown as x=?) and x on both transactions shows they are linked.

Keep in mind, the value of the atomic swap is to prevent loss in the event of non-cooperation after the process has begun. If there is cooperation throughout the transaction, the parties can act together to finalize. It would look like this:

Cooperative atomic swap available today

This is still not private, since the hash of x appears in both chains. They would use different pubkeys on the different chains, so the pink key on chain W would differ from the pink key on Y, but the x value must be the same on both chains. MAST allows the first transaction to be rewritten so that only one of the three redeem conditions needs to be revealed. In the cooperative case, neither x nor hash(x) needs to be revealed publicly on Blockchain Y. Both Alice and Bob will know the all the redeem conditions to protect themselves, but won’t reveal unless needed. Here is how the first transaction would be constructed:

Merkle tree of possible spending options

MAST allows us to instead represent this script as a tree. The combining of colors represents hashing. The brown hash at the top is what locks up the coins. The coins can be spent if a proof that colors (hashes) can be combined to a leaf color which matches a spend condition. Also, the tree can be unbalanced, where a shorter proof (smaller cheaper transaction) is used in the common cooperative case. In the below example, they show that blue and pink combine to make a violet multisig. They then show violet and orange make brown. Thus after proving pink and blue are allowed, 2 of 2 signatures from Alice and Bob can move the coins. This looks like any ordinary MAST based 2 of 2 multisig on the blockchain. The public sees none of the fancy protection parts, just the orange hash. The important part is neither x nor hash(x) appears on Blockchain Y, increasing privacy. The public can’t even see that it’s a swap transaction.

Cooperative private atomic swap with MAST

In the non-cooperative situation where Alice disappears, then Bob can still retrieve his coins. Bob has the yellow x published in Blockchain W.

Uncooperative Alice atomic swap

Alice is protected too. If Bob disappears before starting his transaction, Alice can get a refund after a timeout period.

Uncooperative Bob atomic swap

There are multiple open proposals for how to implement MAST, each with different tradeoffs.

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/014932.htmlhttps://github.com/bitcoin/bips/blob/master/bip-0114.mediawiki#hashed-time-lock-contract

This example is just scratching the surface. So much more is possible, and we are just getting started. Far more complex contracts can be created in the future using MAST, more complex than can be imagined today.

Additionally, if Schnorr signatures get added to Bitcoin, things can get even more private. One optimization would be to collapse the multisig transaction down to what looks like a single signature, hiding even more information about the transaction. If both chains support Schnorr, then Simultaneous Scriptless Signatures can be combined with MAST for even more privacy (see page 31). The swap would appear as unrelated 1 of 1 transactions on both chains. The explicit x revelation could be substituted with elliptic curve math. The link between transactions would again only be detectable in the non-cooperative situation.

Thanks to Mark Friedenbach, Russell O’Connor, Paul Snow, & Justin Hanneman for feedback and additional insights.

Discussion here.

Brian Deery serves as the Chief Scientist at Factom, a data layer for the Bitcoin blockchain. He also co-founded Factom.

Brian can sometimes be heard at Let’s Talk Bitcoin on The Crypto Show, where the hosts have named him Dances With Bitcoin.

Follow him on Twitter at https://twitter.com/deery_me.