Cryptocurrency Exchange without a trusted third party
I love strong encryption. It protects us in so many ways from bad people but it takes us to a place - absolute privacy - that we have not been to before
-- FBI Director James Comey, keynote at Kenyon College (2016)
I originally posted this to the Metzdowd Cryptography mailing list...
It's a bit rough, but I hope it fosters some discussion. Constructive flames welcome!
- Alice has Altcoin, but wants Bitcoin
- Bob has Bitcoin, but wants Altcoin.
How can they exchange cryptocurrencies without a trusted third party?
Protocol #1
- Alice moves Altcoin to a new Altcoin address
- Bob moves Bitcoin to a new Bitcoin address
- They exchange private keys
- 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:
- Alice tells Bob her Bitcoin address
- Bob tells Alice his Altcoin address
- Alice moves Altcoin into Bob's Altcoin address
- Bob moves Bitcoin into Alice's Bitcoin address
- 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:
- Alice tells Bob her Bitcoin address
- Bob tells Alice his Altcoin address
- Loop until we have exchanged the required amount
- Alice moves a little bit of Altcoin into Bob's Altcoin address
- Bob moves a little of Bitcoin into Alice's Bitcoin address
- 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.
The cool thing about this protocol is it can be used today between most 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
- Alice creates an Altcoin ransom transaction with a refund timeout
- Bob creates a Bitcoin ransom transaction with a refund timeout
- They exchange ransom unlock keys
- 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:
- We progress to Coin Exchange if and only if Co-op/Co-op was played within Ransom Setup. Otherwise the game exits early
- 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:
- Alice and Bob exchange ransom unlock keys
- Loop until ransoms are at least twice the size of the required funds
- Alice moves a little bit of Altcoin into an Altcoin ransom transaction with timeout
- Bob moves a little bit of Bitcoin into a Bitcoin ransom transaction with timeout
- 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 do that today. Anyone want to trade :)