First Grin atomic swap!

Grin is a new cryptocurrency that is still under development. It implements the MimbleWimble protocol, named after the tongue-tying spell in Harry Potter. Some of the key properties of Grin/MimbleWimble are

• Privacy by default. There are no “addresses” as typical cryptocurrencies have and amounts are hidden using Pedersen Commitments. Grin also implements the Dandelion protocol with transaction aggregration to further improve privacy.
• Better scaling compared to other blockchains, scaling primarily with the number of users.
• Proven cryptography, only relying on Elliptic Curve Cryptography which is a very well researched area of mathematics.

Despite the distinct lack of scripting or smart contracts in Grin, much of the advanced applications are still possible, such as: multi-signature wallets, lightning-type network and atomic swaps. The latter feature will be discussed here today. We have managed to perform the first atomic swap between Grin testnet3 and Ethereum Ropsten testnet and will explain it below. This article assumes some cursory knowledge on UTXO based blockchains as well as the MimbleWimble protocol.

Let’s get started

There are two parties involved in an atomic swap, let’s call them Alice and Bob. Alice has some grin that she wants to sell for Ether. Bob is interested in buying them. The first thing they need to do, is determine the amounts they want to exchange. They settle on swapping 500 grin for 2 ETH. The broad steps that Alice and Bob need to follow are:

1. Lock up Alice’s grin in a 2-of-2 multi-signature output, where Alice and Bob each have a key. At the same time they are building this output, they need to build a refund transaction back to Alice, with a decently long locktime. We have to do this simultaneously, or Bob has the ability to hold Alice’s coins hostage. In this example we chose a locktime of 12 hours.
2. Lock up Bob’s Ether in a smart contract. This smart contract will pay out to Alice (and only Alice), as soon as she provides a secret key q. This secret key is previously generated by Bob. The smart contract also has a refund option, but with a longer locktime than the grin output. Here we chose 24 hours.
3. Finally Alice and Bob need to collaborate to let Bob transfer the grins to an output owned by him. We have to set it up in a way that when Bob claims them, he reveals x to Alice, allowing her to submit it to the Ether smart contract.

If we implement these steps correctly, we have allowed Alice and Bob to exchange their coins without an intermediary. Either both parties can claim the other coins, or neither of them can. This is why it is called an atomic swap.
Now let’s explore each step more in depth!

The Grin side

An output in Grin is a Pedersen Commitment of the form a*G+b*H, with G and H elliptic curve point generators. In this Commitment a is the secret key that has possession of amount b. To spend this output, the sender has to prove that they know the secret and since amounts are hidden, also has to show that the whole transaction balances out (i.e. no new coins are created). This is done by creating a signature for the excess value, defined as the sum of the outputs minus the sum of the inputs. A more in depth explanation can be found here.

Alice has to lock 500 grin in a multi-signature output. This output looks like:

Here v = 500 grin and x_mA and x_mB are the secret keys belonging to Alice and Bob, respectively. Since spending this output requires a signature for both secret keys, Alice and Bob have to work together to spend it.
To make sure their secret keys stay secret, they will only send the public keys x_mA*G and x_mB*G to each other.

Time-locked refund

Before actually putting this output on chain, Alice wants to make sure she can get a refund if they don’t manage to finalize the swap. To that end, they build and sign a transaction where the multi-signature output is used as input and the coins (minus a transaction fee f_r) are returned to secret key x_rthat only Alice knows:

Grin uses Schnorr signatures to prove ownership of the in- and outputs. These signatures have the convenient property that they are linear, meaning that multiple parties can each independently produce a signature for their part, which can then be combined to obtain the final signature. In our case Alice produces a signature for x_r-x_mAand Bob for -x_mB. The refund transaction has a lock height of 720 blocks in the future, which means it can only be included in a block roughly 12 hours later. The final slate for the refund transaction can be found here. It is easy to verify that this transaction is valid (provided the input exists and is unspent) and can be mined from block 73,425.

Multi-signature output

Now that Alice knows that she can get her grin back if Bob refuses to cooperate, they can safely create the multi-signature output. Alice has an unspent output of v_i = 1000 grin. Because she only needs 500 of those for the swap, the transaction also has to contain a refund output. The transaction has fee f and consists of the following elements:

Like before, Alice and Bob now generate partial signatures for their contributions, which are x_mA+x_c-x_i and x_mB respectively.

This transaction is missing one important component, namely the rangeproof on the multi-signature output. All outputs require a proof that shows that the amount doesn’t under- or overflow. Producing this proof requires knowledge of the secret key and the value of the output. But in our case neither party knows the full key. As it turns out Alice and Bob still can create such a proof without revealing their key to the other party, by sending some data between each other a couple of times. It is outside of the scope of this article to explain this process, but a future article will explain how this method works in detail.

Now that the transaction is done, Alice submits it to the grin network. It is mined in this block. Note that this special transaction is indistinguishable from “regular” transactions, the output looks just like any other.

The Ethereum side

Bob needs to deploy a smart contract on the Ethereum Ropsten testnet that pays 2 ETH to Alice if she proves she knows q, or it gives a refund to Bob if sufficient time has passed. To achieve this, he sends q*Gto Alice and deploys the following Solidity code:

This contract stores 4 variables, that are initiated on deployment:

• sign_address: the Ethereum address that corresponds to public key q*G
• receive_address: Alice’s address
• refund_address: the address that Bob used to deploy the contract, which will receive the refund if necessary
• unlock_time: after this time, Bob can get a refund. Set to 24 hours in the future

The contract can be found on-chain here. Since Alice knows q*G , she can verify that calling the claim function with a signature using secret q will pay her 2 ETH. She also checks that the refund unlocks far enough in the future.

(Tongue) tying it all together

Now that both sides have their funds locked up, we can execute the swap. Alice and Bob start building the transaction that will pay the grin to Bob (using secret key x_s only known by Bob):

Bob can now build a partial signature (s_B, k_B*G), using his secret keys:

s_B = k_B + e*(x_s - x_mB)

However, instead of sending this to Alice, he sends a adaptor signature (s_B', k_B*G), with s_B' = s_B + q. Alice can verify that the following relation holds:

s_B'*G - q*G - e*(x_s*G - x_mB*G) = k_B*G

In other words, she knows that when Bob finally submits the transaction using the total signature (s_s, k_s*G) = (s_A+s_B, k_A*G+k_B*G), she can perform a simple calculation to obtain q:

q = s_A + s_B' - s_s

Thus she is safe to send her partial signature (s_A, k_A*G) to Bob.
Bob combines the partial signatures and submits the final transaction to the network, thereby claiming the grin. This transaction has been mined in block 72,729. Alice sees this and calculates q using the formula given above. She creates a signature and submits it to the smart contract and receives the Ether. This completes the swap!

Summary

This article explained how we did the first atomic swap (that we know of) between Grin testnet3 and Ethereum Ropsten.
We have open-sourced the code that was used to perform the swap, it can be found here. It requires a modified secp256k1-zkp library. Note that the code is far from ready to be used in production, not in the least because it requires a (already planned) modification in Grin to be fully secure.
A future article will explain how the bulletproof for the multi-signature output was generated.
For any questions regarding this article, please refer to the grin forum topic.

About us

Our goal with GrinSwap is to build a full fledged atomic swap exchange. Users will be able to place buy and sell orders. We will match these orders and allow the parties to execute the swap trustlessly. If you are interested in receiving updates of our progress, sign up to our newsletter on our website or follow us here on Medium.

Acknowledgements

The ideas outlined in this article are not new. In fact it is merely an application of previously done research by a lot of people. Below is a non-exhaustive list of work that this article is based on:

• The first formulation of MimbleWimble by Tom Elvis Jedusor and subsequent improvements by Andrew Poelstra
• Bulletproofs by Benedikt Bünz et al.
• Scriptless scripts research by Andrew Poelstra
• Multi-hop locks by Giulio Malavolta et al.

Appendix

All communication between Alice and Bob can be found here.
If you would like to verify the validity of the swap, here are the required parameters: