Fully On-Chain Order Books

Transcript

all right yeah sure sure just please let me know if you can see my screen okay the presentation too okay all right so uh hi everyone my name is masa and it's my pleasure to be back at ecc2 this year but although i'm very sad that i couldn't make it again in person hopefully next year there will be like no virtual talk at cc and then we will all be able to meet in person all right so my talk as you can see here in the title is going to be about fully unchained order books but before i start very briefly about myself i'm

doing phd at concordia university in montreal canada and my research is mainly on decentralized finance and blockchain applications and also very recently i have joined the offchain labs to be working on arbitrom as a part-time software engineer all right so let's dive in and to begin with let's assume that you have a very great idea of some sort of uh financial application for blockchains and the good news for you is that there's really no barrier for you to do so you can just go ahead you can write it up in some form of code we call it smart contract and then you push it to the term blockchain

and the term will give you some sort of security guarantee that the code that you wrote will be executed exactly the way that you wrote it and that's actually the the message that i'm trying to communicate here is there is really no barrier to entry for any kind of decentralized financial application now nowadays on a blockchain and that's the reason why we're seeing a huge growth in defy space now and at this moment that i'm talking to you there's actually the total value of 56 billion us dollars worth of tokens or other ethereum assets that are locked in decentralized finance and that number is huge

and i guess it's scary too because the term is really like is a very hostile environment because it's totally unregulated so on the other side of the story we have governments and financial regulators who really want to provide consumer protections for traders or other users of these kind of defy services but they are really worried and they're concerned because they almost have no ability to do so when it comes to those services that operate fully on chain and among those regulators was quebec's regulator authority demacia financier or mf that they actually approached us it was a

year ago that they came to us then they were really worried and concerned about unchained order-driven exchanges and they really wanted to know if such a service is feasible to be operating on ethereum today or anytime soon so to answer the mf uh question what we had to do as researchers was we actually went out to see if there's any order driven exchange that operates fully on chain that we could find so that we started running some performance tests or do some investigations but unfortunately all we found was a bunch of white papers they were just talking about

what a fujian chain exchange is or what would be the benefits so to avoid any sort of speculations uh what we did was we actually rolled up our sleeves and we started building and implementing an order drip and exchange on ethereum so that we could see what would be the performance benchmark so all the results of our research and investigations are provided in this research paper that is publicly available online and in the rest of my talk i'm going to provide some high-level details and like interesting discussions of the paper for you so basically more specifically actually what we're going to learn in this presentation first off is that

we want to know if secure trading such as resistant to front running is really feasible as a fully unchained service on a public blockchain specifically ethereum today and if it is possible and feasible what would be the performance performance benchmark and we're also very curious to see what would be the effect of a novel ethereum scaling solution for example roll ups on the performance of such a system all right so for designing and implementing an order driven exchange we had to first decide about the data structure so we know that most of the exchanges use something like called an order book which is an

electronic data structure for storing the incoming orders like and keeping them sorted so what we thought was so order book is a ledger and blockchain technologies give us distributed ledger so what we thought was uh there's this data structure that it works like a table and it gets updated so why don't we just throw it in a form of some smart contract on ethereum that sound really cool right so that was the potential design that we had in mind but it actually like it turned out to be really invisible because there were quite a few challenges that we faced and i'm gonna explain them to you now first off most of the exchanges they operate on a

price time priority manner meaning that orders in the order book they are sorted and they're executed based on their price and if there are two orders that they arrive to the order book with the exact same price the one that has like arrived to the order book first it gets executed first but that's a problem that we have on a blockchain there is no centralized time server on a blockchain there's no way that we can establish the time priority and if if alice actually is more well connected to the network than bob is then her order is executed before bob even though she sends it after so we actually have no way to say who was first on a blockchain another problem that we have is that

blockchains are typically slow in compared to markets and stock market they actually move very very fast and the example is high frequency trading where there are active dealers or computers that they are trading based on nanosecond levels and this is really a problem because blockchains are slow and it takes intervals for transactions to be confirmed and included in a blog and the other problem that we have on a blockchain is that blockchain is an open public network so everything is public so every transactions that is broadcast to the network it

it can be seen by everyone before it can be included in a block so what we have here is notes they can send certain transactions so they can see an order and they can just they feel like this is really competitive for them and then they can just drop the orders and simply not propagate it enough to the network and miners are even in a more powerful positions because a they are the ones who decide what to put inside a block and b they're the last ones to see the transaction inside a block before it gets mined and basically what they can do is they can just wait till the very last moment after seeing all the transactions inside a block they can just insert

their owns and just benefit from that and the other problem is front running that we have in a minor they can actually see all the transactions inside a blog and they can just beat you with a better price all right so because of these challenges that i just explained to you it turned out that we cannot really dump an order book on a public blockchain so what we had to do was we had actually two options either we closed the network and instead of ethereum we would just use something like hyper ledger or r3 corda where not everybody can be a miner so we would actually eliminate the problem of censorship and front running and also there would

be some centralized time server that enforced the time priority the other option that we had ahead of us was to stay on a public blockchain and still get all those benefits that we could get from ethereum but we use an alternative data structure to the order book so we choose the second one we actually wanted to stay on ethereum because first off it's a more hostile environment so if we can get something to work on ethereum it can only work better on other private network and so what we chose was something called a call market so unlike an order book the way call market works is more like an auction

so the auction sort of opens and bids and asks are submitted but they're not executed immediately you just sit inside that data structure inside a call market until the auction is closed and then the orders that are overlapping against each other they trade against each other so how would a call market solve those problems that i just explained first off uh here in a call market you're batching the transactions so there's no time priority anymore so either you get inside the auction then the auction is open or you you know so there's no no priority time priority here and about blockchain being slow timer and cog markets are slow too and

be actually accumulating all the orders in a seven minute period or so so that that solves the problem too for censorship of transactions in our design we we urge the nodes to broadcast as much as they can so that at least one honest node in a network would see the transaction i would include it inside her block and for miners front running we use the mev and turn it around for good and we give the price improvement to the miners in our design and implementation and that would disincentivize miners to front run well priced order all right so now that we know we want to implement a call market

we have to choose the ideal data structure for storing the orders that arrive to the market and in a call market closing the market and processing all the orders is done in a batch in one single transaction and having the the limit the block gas limit in ethereum that would be the really like it would be the bottom leg for us because it's the most expensive step for us so we had to choose an ideal letter structure to handle this issue and what we chose was a priority queue which is a data structure in which each order each each element has a specific priority here would be the price

so we use two priority queues one to store the beads when the highest price is the highest priority and one to store the incoming ask when they're where the lowest price is the highest priority so i won't go really through the details of the performance test but we implemented five different priority queues we ran a lot of performance tests on different like in queueing or dequeuing different elements inside each pq to find out which one has a better performance because again performance was the main bottleneck for us so uh it turned out that the link list with mapping is the best priority queue for our implementation so in the implemented a call market that our system is called lissy

it's written in 324 solidity lines and it we kept it as a simple module so that it could be extended by developers the way they want and yeah so how it works it basically works like an auction so the market opens uh traders would submit their bids and asks the market closes and then in one single transactions all the orders will be traded against each other so there are eight main operations in bc uh we have deposit token and ether so uh traders would have to deposit their erc20 tokens and ethers they want to trade um inside a smart contract then we have open market and close to open and close

the market then we have submit beats and ask function for traders to go ahead and submit their orders and after the market is closed and the orders are set out the traders they can come along and they claim their tokens and incurs calling the claim tokens and claim interest functions all right so now that we have the design we revisit this question again how many orders we can process in one single ethereum transaction when closing the car market on ethereum today so we ran a lot of performance tests again for each different priority queue that we implemented and the first column shows the highest number of trades we could handle in each case uh current like and you have to uh pay

attention that this is for the block estimate of around 12 million dollars when i run these in a performance test and the the the call the next column is those gas costs for those numbers and because we knew that the terms going to be improved and we would be able to handle more transactions inside each block we just ran the test for 200 trays to see how much gas it would cost and the last column shows the the gas price for submitting the orders for each priority queues so as you just saw the bottom line is we can only handle 100 trays on every single closing on ethereum meaning layer one today

and that would really like it would position lissy or call markets for a small set of markets for like low liquidity markets or a low number of traders but there are ethereum scaling solutions that they actually improve uh scalability of a theorem a lot so um using one of like we actually use arbitrary roll up so we implemented a variant of our system on arbitrary test net rank b and we actually found that it reduces the cost for executing the trades by around 99 and nine percent and pay attention that it was using such and scaling solution we

could actually do an infinite number of trades per closing and this is really fascinating so if you want to know what arbitrary is it was it was actually came out as a research paper in 2018 by a group of colleagues at princeton university you can just go ahead and read the paper and yeah that's it so we have a lot more discussion points inside a paper that i couldn't cover in this talk because of the time we have front running evaluation of different kind of order books call markets mm and that that is really interesting if you want to go ahead and take a look we have discussions around who would close or open the market or how we calculate or not calculate the market cream price

and we have some gas refunds discussion and we have talked we have talked about their limitations as well so that would include my talk thank you so much for attending if you need to contact me this is the first one is my twitter handle the paper is again publicly available on the archive feel free to go ahead and read it and yeah don't hesitate to reach out if you have any questions or suggestions thanks uh

i'm sure yeah so for your first question we actually thought about this too and in the discussion point we have some alternative design decisions for closing the market and we actually have such a design too that closed market would happen in different stages so in the first closed market only n number of orders will be processed and the second market second closed market like another set of transactions will be yeah clear too yeah we just wanted to find the benchmark of like what would be the benchmark the baseline of uh how many orders we can process but of course there are more kind of like design alternatives to this too yeah and for for market clearing price

in our design like intentionally we don't calculate any market clearing price because we thought uh miners could really manipulate this like on ethereum so we don't do that and uh if that's needed we can just use some third-party services to uh yeah to calculate the market green price uh

uh yeah but uh yeah so we we intend to open the market inside a block and at the end of the block we closed the market but of course that would really need us to monopolize all did all the block right like yeah and the market and the market that we design is a short-lived market so the orders like it's only like five minute period so we open the market for five minutes and then after that the market is closed and orders are matched right right of course yeah

yeah that's that's actually that's a very good point and that's right i don't know but yeah because we could look at it as a trade-off between using an unchain exchange and a centralized exchange maybe yeah but yeah sure of course yeah i'd be happy to because this is a very interesting point that's also a potential solution right yeah but yeah i'm happy to take this

offline with you because it was a really interesting point yeah all right thanks uh yeah because uh like on decentralized exchanges so-called decentralized exchanges there's there's one sum of functionalities are being done on chain for like loading balances but still

matching orders and other settlements are being done of chain so if anything happens there would be some some entities that regulators they can go after and find out what happens but when everything is done fully on chain there's if anything happens like stole of funds or like like any other issue there's no way for regulators to go ahead and like find find out what's happening because there's no actual person like behind these things it's fully unchained it's fully anonymous oh yeah so i'm not like i'm not actually comparing myself to mm

i'm just talking about an order driven markets like us with an order driven centralized exchange sure all right thanks good luck take care bye hi there good and you