A Recipe for Creating Fully Decentralized Token Exchanges

Editor’s Note: You are viewing outdated material from the DFINITY blog that is being preserved for archival purposes.

Many who have been around crypto for a while have experienced some kind of losses on exchanges, including yours truly in both the Gox and Bitfinex hacks. Never in history have thieves been able to get away with such huge bounties so easily! The unique nature of crypto tokens, which exist only in cyberspace and cannot be easily retrieved once stolen (notwithstanding what the forthcoming Blockchain Nervous System on the DFINITY chain might do) make it highly likely that other hacks and insider thefts will occur.

That is, unless we can create real decentralized exchanges where we do not have to pass our tokens and money over into the custody of intermediaries. The emergence of such fully decentralized and tamperproof exchanges, which should also involve much lower transaction fees, is a critical pending step in the continuing maturation of our industry but so far the objective has been elusive. However, in this post I will explain how some recent innovations in cryptography make it possible to realize the future today.

This article will explain how to create decentralized token exchanges from smart contracts written in Solidity and Dapp user interfaces written in HTML/Js of the kind you might create using Truffle (for a ready-to-go development environment packaged as a docker image that includes the Cloud9 IDE alongside truffle and other tools, checkout instant-dapp-ide). Although some special accompanying software clients must also be created to apply the cryptography, we will not need side chains, state channels, special consensus hubs or any other such things that either don’t exist quite yet or come with their own serious drawbacks. Nothing beyond what is already available today is needed!

We will therefore cover how to create a crypto-to-crypto exchange on Ethereum (or eventually DFINITY) that will make it possible to trade BTC/ETH and other pairs safely and inexpensively.

Step 1 — Smart contract logic

Ethereum smart contracts already provide us with the means to run logic of continuous double auction exchanges— such as GDAX, Bitfinex, Kraken or Poloniex—on a blockchain computer. The speed of today’s networks present practical challenges with respect to user experience because the market can potentially be reorganized for a few minutes after new orders are submitted and trades have apparently executed, but solutions are already in the wings. Threshold Relay will bring finality down to a handful of seconds (a 50X+ speedup compared with Ethereum today) and the Casper team is also working on solutions too so we might make do for a while. The real challenge is that the tokens we create in our smart contracts cannot be trustlessly connected to the valuable native tokens on other chains. For example, we are unable to create an XBT token in an Ethereum smart contract that is trustlessly connected to a bitcoin/BTC that we can then exchange for native ether/ETH.

Advanced technical note: Here is some sample continuous double auction style exchange code in Solidity for those interested (this was actually my first Solidity contract, written when the language first became available). There are several design considerations you must make. For example, it is necessary to address the problem of HFT “sniping” by arbitragers watching prices change on faster centralized exchanges. There are also good reasons to look at using other exchange models, such single price batch auctions. These considerations are worth another post if there’s time.

Step 2 — Threshold signature hack

For simplicity, hereafter we will only talk in terms of custodying bitcoin/BTC on an exchange hosted by Ethereum, although the same technique would in fact work for custodying any native crypto token from a chain that uses ECDSA signatures to authorize transactions.

Our requirement is for some large number of independent parties to collaboratively control a standard Bitcoin address, such that users can send their bitcoins there, but bitcoins can only be transferred out upon agreement between some threshold proportion of those parties. For example, let’s imagine our exchange will have 50 custody “guardians” drawn from well-known and independent persons and companies inside the crypto industry. They must control a Bitcoin address where users can send their bitcoins in exchange for XBT tokens hosted within the exchange on Ethereum, and they must be able to dispense bitcoins from this address to those redeeming XBT tokens. Traditionally in cryptography this kind of functionality is created using “threshold signatures”.

Advanced technical note: the Bitcoin network only relays native “multi-signature” transactions with a maximum of 3 participants. Pay-to-script-hash provides some relief, but still limits participants to 15.

We can now cut the line for the impatient :) Although Bitcoin and Ethereum transactions are signed using standard ECDSA signatures, and neither natively supports threshold signatures, some innovative researchers recently demonstrated a hack whereby a kind of threshold signature can be produced that is backwards compatible with the standard ECDSA signatures Bitcoin and Ethereum use. That is, our guardians could create a threshold signature for an address that would be accepted by the Bitcoin network as a standard ECDSA signature that unlocks a UTXO!

You can find the papers describing how to do it here:
https://eprint.iacr.org/2016/013.pdf
https://www.cs.princeton.edu/~stevenag/threshold_sigs.pdf

To be clear, these threshold signature schemes are not like the optimized BLS system we use in DFINITY Threshold Relay that can combine outputs from hundreds of signers to create a unique deterministic threshold signature in a few milliseconds. In fact, this system is so horribly inefficient that combining the signing outputs of our guardians will take a very long time indeed and their CPUs will glow red hot, but this isn’t a problem here. It is perfectly acceptable to institute modest withdrawal fees to cover the computational cost and require that withdrawals from our Ethereum based financial exchange take a while to process — after all, many will happily leave their funds on a safe exchange for convenience!!

Application of this technology will allow us to spread trust between some number of guardians such that they can both accept bitcoins in return for XBT allocations and dispense bitcoin when redeeming XBT tokens, thus pegging bitcoins to the XBT tokens in a trustless and safe manner. Of course, we must consider that some guardians might lose their signing keys or get run over by the metaphorical bus, but threshold signatures allow us to address this issue. We can simply require that the outputs of only 35, say, of our 50 guardians are needed to create a new signature.

Step 3 — Guardian incentives

We need to create an incentive scheme for our guardians, since we wish to involve and advertise trustworthy persons and companies who will not disappear or collude. The simplest means is to grant them a small transaction fee on all withdrawals from the exchange.

Step 4 — Governance

The decentralized financial exchange needs its own management system since guardians must be elected, software updates to the smart contracts adopted and so on. We will therefore minimally design the exchange as a DAO (Decentralized Autonomous Organization). If the systems are available in time, we might even derive a more advanced Governance Nervous System from DFINITY Blockchain Nervous System technology (the DFINITY team very much hopes the BNS will be repurposed this way). Within the governance system there will be holders of tokens with “voting rights” that receive pro rata shares of tiny fees levied on trades. Periodically, the smart contracts will hold beauty parades where potential guardians may apply for roles, and these will ultimately be assigned by the voters.

Advanced technical note: An attacker might try to buy up all the voting tokens and then switch out the guardians for his own stooges (the usual DAO 51% attack) and steal deposited funds. For this reason, upon a vote the contracts must only switch out the guardians after some extended delay that provides crypto holders plenty of time to withdraw their funds safely if such an attack occurs. This also applies to adoptions of software updates.

Step 5 — Threshold crypto setup

Once the set of guardians has been setup, they must setup their threshold signature scheme. This means that some kind of process or protocol must be run that upon completion ensures that each of our 50 guardians has a private “key share” used to contribute towards collaborative production of a threshold signature that can act as the single simple ECDSA signature authorizing the network to dispense bitcoins from the deposit address. As mentioned, the threshold signatures schemes referenced are really hacks that create signatures that are backwards compatible with the normal ECDSA signatures currently used by Bitcoin and Ethereum networks. This means that, in contrast with the BLS threshold signature scheme used by DFINITY Threshold Relay, setup is rather more challenging.

The simplest way to proceed is to perform a trusted setup in a secure ceremony as the Z-Cash network recently did, and have each guardian signal to the exchange’s smart contracts that they are happy with the output before allowing the deposit address to become “live”. While the trusted setup process will be much simpler to implement than that used by Z-Cash, many will wish for a trustless distributed setup, especially since it is easier to repeat when it is necessary to rotate the guardians. This will comprise of two parts. The first involves distributing normal keys among the guardians, and can be done very simply by applying, say, IPFS as a log that aggregates and shares the messages involved in a distributed key generation protocol. The second part (made necessary by the homomorphic encryption techniques used in the hack) involves distribution of Paillier key shares. It is this last part that requires some careful analysis with regards to implementation costs if you wish to get your exchange up and running fast!

Step 6 — Guardian client software

We must create some special “guardian client software” that watches the exchange’s smart contracts and periodically collaboratively signs Bitcoin transactions when users wish to redeem XBT.

Step 7 — Crowdsale

A crowdsale should be run to collect funds used for R&D and perhaps as incentives for the first to move funds there (that would perhaps be specially locked there for some time) helping to bootstrap liquidity. Note we might simply start with the governance system then allow it to dispense funds to developers to get the exchange finished.

Once the exchange goes live, we should expect the volumes to ramp up quickly! The fundamental costs involved in decentralized exchanges are orders of magnitude lower than centralized exchanges run by corporations, and this will be reflected in transaction fees. Furthermore, the decentralized system described is also orders of magnitude more resistant to hacks and attacks. You can expect vast volumes of crypto to be safely parked and traded in such an exchange.

Fingers crossed someone builds this!

Final Note. The decentralized financial exchange on first sight only appears to make crypto-to-crypto trading possible. This may be true in the near term, but those interested should review the PHI system currently under development by researchers associated with String Labs in Palo Alto. This mimics the workings of the commercial banking system and creates decentralized “crypto-fiat” currencies backed by loan collateral. Once we have this token available on the Ethereum and DFINITY chains — and there are hopes this can be achieved within two years — it will be possible to park funds on the decentralized exchange in tokens whose value mirrors that of some chosen fiat currency.