[Cryptography] Cryptocurrency Exchange without a trusted third party

Alfie John alfie at alfie.wtf
Sat Jan 14 08:25:32 EST 2017

```It's a bit rough, but I hope it fosters some discussion. Constructive flames welcome!

1. Alice has Altcoin, but wants Bitcoin.
2. Bob has Bitcoin, but wants Altcoin.

How can they exchange cryptocurrencies without a trusted third party?

Protocol #1
-----------

1. Alice moves Altcoin to a new Altcoin address
2. Bob moves Bitcoin to a new Bitcoin address
3. They exchange private keys
4. Alice now has Bitcoin, Bob now has Altcoin.

There are many problems here, but let's concern ourselves with this one - as
they both know each other's private keys, stealing can occur.

Protocol #2
-----------

To solve the stealing problem, they should keep their private keys to
themselves:

1. Alice tells Bob her Bitcoin address
2. Bob tells Alice his Altcoin address
3. Alice moves Altcoin into Bob's Altcoin address
4. Bob moves Bitcoin into Alice's Bitcoin address
5. Alice now has Bitcoin, Bob now has Altcoin.

The problem now is that if Alice skips step 3, she gets to keep her Altcoin
and her newly aquired Bitcoin (this is essentially stealing from Bob).

Protocol #3
-----------

What we have here (and in the above protocols) is a trust issue - Alice doesn't
trust Bob, and Bob can't trust Alice. I don't blame either of them.

Here's a way for them to build some trust between them:

1. Alice tells Bob her Bitcoin address
2. Bob tells Alice his Altcoin address
3. Loop until we have exchanged the required amount
3.1 Alice moves a little bit of Altcoin into Bob's Altcoin address
3.2 Bob moves a little of Bitcoin into Alice's Bitcoin address
4. Alice now has Bitcoin, Bob now has Altcoin.

At each step, they could move the same as the last iteration, or they could
increase by some function with faster growth.

cryptocurrencies without modification.

The problem here is that Alice can still skip step 3. If she does this between
a big increase of the iteration function, it could lead to a significant
steal.

Protocol #4
-----------

An alternative to building trust could be used if only there was a way of
punishing cheaters rather than rewarding them...

"Guys, itâ€™s time for some game theory":

1. Alice creates an Altcoin ransom transaction with a refund timeout
2. Bob creates a Bitcoin ransom transaction with a refund timeout
3. They exchange ransom unlock keys
4. Proceed to Protocol #2.

If cheating is detected during stage 3 or 4, the player spends the other
player's ransom (e.g output disappears to an invalid address forever).

Protocol #4 can be considered a game with stages, having the following rules:

1. We progress to Coin Exchange if and only if Co-op/Co-op was played within
Ransom Setup. Otherwise the game exits early

2. The Co-op/Co-op selection within Ransom Refund can only be played if and
only if Co-op/Co-op was played within Coin Exchange.

Here's the payoff matricies:

1. Ransom Setup

+-------+--------+-------+
|       |        |       |
|       | Co-op  | Cheat |
|       |        |       |
+-------+--------+-------+
|       |        |       |
| Co-op | -r, -r | -r, r |
|       |        |       |
+-------+--------+-------+
|       |        |       |
| Cheat | r, -r  | r, r  |
|       |        |       |
+-------+--------+-------+

2. Coin Exchange

+-------+------------+------------+
|       |            |            |
|       |    Co-op   |    Cheat   |
|       |            |            |
+-------+------------+------------+
|       |            |            |
| Co-op |    x, x    |   -x, 2x   |
|       |            |            |
+-------+------------+------------+
|       |            |            |
| Cheat |   2x, -x   |    x, x    |
|       |            |            |
+-------+------------+------------+

3. Ransom Refund

+-------+--------+-------+
|       |        |       |
|       | Co-op  | Cheat |
|       |        |       |
+-------+--------+-------+
|       |        |       |
| Co-op |  r, r  | 0, 0  |
|       |        |       |
+-------+--------+-------+
|       |        |       |
| Cheat |  0, 0  | 0, 0  |
|       |        |       |
+-------+--------+-------+

If we progress to completion, the total payoff matrix follows Stag Hunt:

+-------+------------+------------+
|       |            |            |
|       |    Co-op   |    Cheat   |
|       |            |            |
+-------+------------+------------+
|       |            |            |
| Co-op |    x, x    | -x-r, 2x-r |
|       |            |            |
+-------+------------+------------+
|       |            |            |
| Cheat | 2x-r, -x-r |  x-r, x-r  |
|       |            |            |
+-------+------------+------------+

However unlike a usual Stag Hunt, players choose the Co-op/Co-op payoff
dominant strategy because of the credible commitment via Ransom Setup.

tl;dr: a ransom made high enough (i.e at least r > 2x) make a strong case for
players to play cooperatively.

Caveat: This assumes ideal conditions. As two cryptocurrenices move at
different speeds, there could be moments where it is too late for one player to
spend the ransom while the other player still can, thus leaving risk on the
table for one player.

Protocol #5
-----------

The problem with Protocol #4 is that if Alice skips step 1, Bob loses the
ransom (luckily enough though, Alice can't steal anything). Let's fix that:

1. Alice and Bob exchange ransom unlock keys
2. Loop until ransoms are at least twice the size of the required funds
2.1. Alice moves a little bit of Altcoin into an Altcoin ransom transaction with timeout
2.2. Bob moves a little bit of Bitcoin into a Bitcoin ransom transaction with timeout
3. Proceed to Protocol #2.

Like Protocol #4, we again have a game with stages, only this time Ransom Setup
is now split into a finitely repeated game. Luckily, our total payoff matrix is
the same.

Anti-caveat: As the ratcheting up of ransom transactions was done over time, so
too do the ransom transactions expirations. This effectively leaves an ever
decreasing total ransom that can be spent by only one player.

Implementation
--------------

All that's needed to perform Protocol #4 and #5, is the ability to create
transactions that allow refund timeouts. Peter Todd's OP_CHECKLOCKTIMEVERIFY
(BIP 65) for Bitcoin does exactly this.

As for Protocol #3, we can already do that today. Anyone want to trade :)

Alfie

--
Alfie John
https://www.alfie.wtf
```