...by Daniel Szego
"On a long enough timeline we will all become Satoshi Nakamoto.."
Daniel Szego

Sunday, September 23, 2018

Creating a Byzantine fault tolerant decentralized exchange with Hashgraph

The ordering algorithm of the Hashgraph architecture provides a way to realize a real decentralized exchange among different internal cryptoassets. Let we imagine that we have several native cryptoassets in a account/state based system. What we have to do is to introduce special transactions that represent buy and sell orders. As an example a buy order might look like:

Tr_order: buy 100 cryptoassets at 10 - signed by a private key of an account that has the balance of buying.

Similarly, a sell order might look like:

Tr_order: sell 50 cryptoassets at 11 - signed by the private key of an account that gets the cryptoasset at the end. 

The order transactions are validated and ordered with the help of the gossip of the gossip protocol and after a couple of rounds every node will see exactly the same order of the order transactions. This list of order transactions is actually the order book of the decentralized exchange. 

At applying the transactions to the state, we have to do two things: 
- there must be a kind of order matching algorithms on the order book, with other words on the ordered order transactions. Examples might be like FIFO or Pure Pro Rata. A list of possible order matching algorithms can be found for example under the following link.
- the orders that are matched has to be applied to the state. It practically means increasing and decreasing certain balances, similarly a simple transaction is applied to the state. In this case however there might be more than two accounts that has to be modified in the same time.

As the above mentioned algorithm is deterministic and the nodes see exactly the same order of order transaction, the nodes can calculate the algorithm independently from each other and getting the same result. As the core algorithm is Byzantine fault tolerant, the exchange will probably have the same property.

The decentralized exchange can be further improved in a way that instead of hard-coding the order matching algorithm, realizing an on-chain governance process to change order-matching on the fly. 

For experimental implementation take a look the following github repository.