EthCC 2: Benjamin Smith

foreign all right hello my name is Ben Smith and I'm happy for the opportunity to present all the hard work we've been doing on the diffusion Exchange in short we're going to talk about a scalable fair and decentralized exchange this is Joint work with Alex Harmon Felix lloydpold Tom Walther and Oliver beige at gnosis so just to mention the research area here is mainly scalable Market mechanisms batch auctions and snark applications so we'll break this down into three parts first I'll provide a motivation for the need for such a market mechanism then we'll talk about the details regarding um the batch auction as an exchange mechanism and then we'll get into sort of how the how we achieve scalability and decentralization um with this mechanism as a snark application for those of you who are hoping to see a lot of details about snarks today there won't be that many but just know that we're using snarks more for um for compression and verification rather than uh the purpose of zero knowledge so what we see right now in uh current exchanges is a lot of dominant trading pairs this is because of stable coins a lot of these dominant trading pairs for example would be eth Bitcoin Fiat currencies USD Euro however what we expect to see once uh with the rise of many stable coins is slightly less dominant trading pairs but a more of a complete graph of trading Pairs and the current mechanisms for exchange don't necessarily support uh support a lot of trading volume when we get this kind of demand so the token growth thesis is that we're seeing approximately 200 tokens being created per day uh this little graph chart here taken from stat dot blockly Block C dot info just demonstrates the number of erc20 tokens over up until about last week and this looks like about an average about 200 per day so we're getting into this realm where there's a lot of trading volume between a bunch of dominant pairs stable coins but with the growth the growth of token and the lower lower liquidity tokens uh we're going to see this this curve go way out here and we'll see we're seeing a lot less trading volume so a lot of different types of low liquidity tokens uh one very pretty one that we are fond of at gnosis is prediction tokens so um uni swap tokens derivatives tokenized game assets and with this rise of tokens we're going to need a means of exchanging them it that does anybody know how to get rid of that I don't I don't think that's going to do it no all right so anyhow this mechanism we're going to describe here is to aim to Target some of these low liquidity tokens and make exchange a reality so in particular for those of you who are familiar with our prediction Market platform this uh this project is sort of intended to be the underlying engine of exchange for predict prediction tokens at some point when we're ready um so just as a brief sentence here uh the diffusion project is essentially a permissionless decentralized trading Pro protocol that will allow anyone to add their own tokens or if you're familiar with these the popular theme of dows and maybe the the whitelisting of tokens would be handed over to something like that so now we get to talk about this cool Market mechanism anybody who's a keen mathematician will be happy to know that this is essentially modeled as a combinatorial optimization problem and those of you who are not super mathematically inclined will be happy that we're going to start with a small example so we're going to talk about batch auctions and this is just an example of back auctions for two token pairs essentially this could actually be uh this problem could be solved by hand the optimization problem here so what we'll do is collect or orders over a predetermined amount of time these are limit orders between two token pairs um this once the batch closes we now have a collection of orders between two pairs we could arrange and plot the orders in a way that to get a graph sort of like this and what the yellow line is uh orders from B to a and token B to a and the blue line representing orders from token A to B um the vertical length of these lines is representing the volume in an order and it's possible that these orders are aggregated so maybe two people submitted an order at the same limit price and the the volume is represented there in the vertical line anyhow you could sort of plot these orders together and put it in here and what you want to optimize here is the Traders Surplus and in this picture here the trader Surplus is the area under the Curve um so essentially with an order book between two two token pairs you could essentially you could plot this and you could determine the price between those two tokens that would maximize the Trader's Surplus um and settle all the orders at an optimal price so um now we're going to Envision a situation where we have three tokens and an order comes in from A to B another order comes in from B to C another order comes in from C to a but we're still waiting on an order from in the opposite direction in order to actually so with the tradition oh with the traditional order book um this situation no exchange could actually occur when you're collecting orders just between two token pairs because no reverse order has has come in yet so while we're waiting on this we just think okay let's do some sort of a ring trade because there is sufficient demand there for some exchange to occur so what we do here now is collect orders uh in a sort of multi-dimensional order book it's one order book with all the limit orders between all the different token pairs we've got a little cute picture here representing the order book between all the pairs there but now we're going to Envision them all in the same in the same place and uh we turn this this is essentially a combinatorial optimization problem we can no longer sketch this in a two-dimensional play place and try to optimize this area under the Curve so however with you know computers and linear optimization uh we can sort of plot um what would the trade we could determine what the trader Surplus would be for a bunch of different uh prices over this grid here oh executing all right so we'll we'll do the same thing again that we just talked about in the example before but now we're just going to have subtly different constraints and things like this so now orders are collected between any token pair and this kind of looks like a picture we've seen a little bit earlier um the order collection is still being done over a predefined amount of time so this is the concept of a batch order collection rather than continuous order collection so this looks a little bit scary but uh essentially now what we're gonna do once the batch closes is compute the uniform clearing prices so first thing we want to do is maximize Traders Surplus conjecturally this is somewhat analogous to maximizing trading volume and this is even an open problem in the in the research area if anybody wants to help contribute um uh so the constraints here in a little bit are a little subtly different because we have to ensure a few things for fairness um we always need the limit orders to be respected this was true in the two-dimensional example as well but now that we have uh prices being determined between many pairs we also need to ensure a few other things price coherence and Arbitrage freeness so price coherence just says that uh the price from one to the other is is the in the multiplicative inverse of the price from the other back to the one so you wouldn't be a an Arbitrage freeness is is actually a little bit more and implies the price coherence uh just saying that um you shouldn't be able to make any money by going around any cycle in this diagram this is uh yeah and uh and of course the conservation value this says that all the no tokens are created or destroyed during the settlement of an auction all of the money that goes in comes out and is exchanged so finally we have settlement of orders so just reminding us today we see dominant trading pairs where continuous order books and traditional exchanges are sufficient but in the future we expect to see a lot more orders between a lot more pairs and those kinds of exchange mechanisms just won't suffice so this is my favorite part just talking about some of the finer details about how we implement this how do we achieve scalability decentralization we've already seen how uh this is inherently Fair since the salute the the solution to these optimization problems the feasibility range implies the Arbitrage freeness um so we're doing these batch auctions as a snark application a few fun facts we'll expect to have quick back batch times um we can execute a thousand orders with costs about this much if you want to see the details of that computation I recommend scanning that QR code and reading the formal specification and of course this will be a fully decentralized trading engine and we will get into that right about now so essentially of course there's a smart contract on the ethereum blockchain this contract sort of has let's say limited storage and execution but it's sufficient to ensure the security of everyone's balances and with that we can say the account balances are represented as a root hash on chain this means that the contract itself doesn't know the balance of any particular um user and transactions come in and these transactions are sort of hashed together the transactions come into the contract as a payload they're hashed together and the contract really only stores this rolling hash of information and um of course the contract will emit events containing the relevant information to reconstruct this hash and anyone can listen so then what happens is that anyone can propose the state transition of all of these transactions which have been collected over time which is essentially the update of account balances so you can think of it as uh you have so a bunch of account balances somebody wants to deposit somebody wants to withdraw they're submitting deposit withdrawal requests and limit orders are another form of requests coming into here these are all collected in a batch hashed together and just sort of waiting until somebody drives the contract into a new state and this means okay taking the old account balances taking all the requests that have come in over the last little little while and um updating the account balances driving the the contract into a new State Route representing the new account balances and and um and what we have is the updated set of account balances um so the security of this is enforced by a snark this sort of this means there's a challenge response and rollback um feature in place so whenever submitting a state transition you'll submit a bonded a bonded transition for which you could lose if your transition was proven to be incorrect of course all this data is available for anyone to be able to see whether these account balances were updated correctly and um in order to resolve such a dispute one would have to supply a snark proof on chain in the form of a smart contract verification so in the event that a state transition was challenged the proposer would have to provide a snark verification that it was actually correct and in the event that they didn't then this sort of rollback to the previous state and some rewards would be obtained for doing so so with this model we can achieve about 25 x scaling uh 10 10 times scalability comes from the fact that the transactions are coming in as a payload and not actually the information of all these requests is not stored on chain and another 2.5 comes from some other uh fun features we can do such as actually submitting all of our requests as a batch of requests in a single transaction so now sort of just with this uh basic account representation uh in the contract state of mind we have essentially the auction processes occurring in three different stages so first we have the order collection any user can submit their limit orders on chain correctly or to a say order collection service which would submit all of their requests or limit orders in in one transaction that's where the 2.5 x scalability comes from but of course anyone can feel free to submit their orders individually um once the batch the auction batch is closed it's time for Price calculation and this is something that anyone can do we've described the optimize the combinatorial optimization problem that is the sort of how are the actions settled what is the price calculation and how are the orders matched anyone can propose solutions to this thing bonded bonded proposals and the contract will choose the best uh the best solution which means the the feasible solution with the highest objective value the most Traders Surplus um the contract will then choose the best solution and maybe there will be sort of a challenge period or just a a little this once the solution is chosen the solution proposer will have to provide sufficient information now they're not actually revealing their solution they're only revealing okay I have a solution with uh this this much objective value as someone else might have you know this much Trader Surplus contract will choose the right one and upon that uh the the person whose solution was chosen will provide the prices that they've found and the sort of fulfillment the fractional or the fractional or or full fulfillment of all the limit orders that were provided just sufficient information to be able to um update the account balances appropriately settle the auctions so then what we see in the settlement phase is just a state transition of account balances according to the uh to the auction results so there are essentially two snarks in place here of course um people will need to provide snark verification in the event of a challenge for any state transition but also they'll need in the event that a solution is challenged people will need to be able to provide a snark proof of of feasibility of the solution they proposed this means Arbitrage free I mean for the most part and conservation of value the things we talked about uh as the constraints of the problem so just to summarize a couple things scalability here is achieved by limited but sufficient on-chain storage uh the snarks are being used here for compression and security uh balances are updated in a single transaction um just also sort of the status of the project at the moment where are we in building we spent a long time researching the capacity of snarks the capacity the price of snarks because the bigger snark in this problem here is the the snark proof of the solution to the order collection the state transition of account balances snark is a little bit smaller but the capacity we need a lot of capacity for the um Solutions at the moment we have sort of a core framework um for a basic snap this includes end-to-end testing um deposits withdrawals making people making sure people can submit their requests for deposits making sure they can update the account States and making sure that uh people can withdraw their funds um the limit orders and auction settlement is somewhat analogous in the sense that the limit orders are a form of a batch collected request and of course the state transition is already there so we have some basic contracts as a snap base so keep in mind this is also something if this seems appealing to you the basic snark application deposits withdrawals and state transitions can be used for sort of any purposes not just a decentralized exchange so right now we've got account registration token registration deposits and exits um of course there are a few services that are listening to to the events in order to reconstruct the necessary information to drive its contract Drive the contract into its new state um so yeah we've got a couple Services ready with end-to-end test and so the next steps just for us is to sort of start to implement the order collection and challenge response rollback and this will just be integration with the the snarks themselves and ensuring that uh that we can do with this so This is actually a good place to mention that we at gnosis have an ecosystem fund we're funding projects that integrate with our uh our platform um and uh we're offering desks at full node in Berlin support and I want to just go back a little bit and point out a couple places where you could probably have a good shot at contributing here so you'll notice the the order collection as a service this is something you could do you could build something like this start collecting orders from people as a service maybe charging a small fee and submitting that or those orders on behalf of those people to to the auction uh you can become a solver start competing for for rewards and finding the the best solution to these problems just a couple places where the gnosis ecosystem might help get you started uh so here we have just a couple places where you can look at what we're up to uh the research the formal specification is there there's a paper on the optimization problem and how it's modeled there's uh the formal specification of this uh as a as an app as a as an application snark application uh the contracts are here at Dex contracts and some of the services this is the event listener the contract driver and integration with the snarks will be found here just to take away picture a multi-dimensional order books using making use of combinatorial optimization to to maximize Trader Surplus between limit orders for any token pair and thanks for your attention here is a list of a bunch of other people who have helped contribute [Applause] yeah foreign I was just wondering what's the reason behind the challenge response rollback mechanism rather than just having to submit the snark proof like every time you propose a new state so first of all thanks for mentioning roll up I wanted to to say that uh part of this is inspired by rollup um so I think the reason I think what you're looking for here is that the snarks are expensive and so we don't want to have to actually compute the snark proof unless uh unless absolutely necessary so it's easy for anyone to verify that what's what's happening is feasible or that the state transition is accurate as long as you're collecting the information and you have the sufficient like essentially the state transition corresponds to what are the old balances what are all the things that are about to change it and then what should the new balances be that's just essentially going through an array and then doing a couple pluses and minuses it's easy to verify but um Computing the snark for that is just much more expensive does it not enforce like a liveness aspect for all the users though to have to be like watching out if anyone's trying to steal money off them rather than just knowing that it will always work right of course so um I think also because there's some you know there's there's some reward in place for the solvers you can expect that maybe a solver will be uh sort of a contract listener there will be somebody keeping chat I mean and you know in the event that you're not actually keeping track of the whole thing you can always replay the entire transaction history on that contract from its deployment date we can expect that there will be you know I mean we'll at least be keeping a database of all the the transactions that have gone on and uh even if even if such a database is lost it can just be replayed and rebuilt all right thank you I see one right over there hey yeah um so um just a question like what what not I mean given given your kind of a quite quite quite like significant death of experience in in this um in constructing these kind of ZK snark circuits what do you think are kind of some of the challenges the industry faces um to um for like widespread adoption um and development of like quite like application specific Zeke snacks to perform like large like large series of computations of chain well for sure one of the challenges uh I don't know about adoption but uh the capacity of these snacks and the amount of information that you can actually compress and prove in a reasonable amount of time is a as a limitation um I don't know you were looking for as an adoption yeah I mean like in in for for stocks like to full basically um like right now you have to be quite like literate in cryptography uh to work with any zero launch system um and kind of what like which quite quite like I mean there are a lot of barriers to entry into this into this industry um what do you think we can do as a community to kind of lower some of those barriers well I think maybe in the community it would be good to have a lot of uh easy to use um snark Frameworks there's a a lot of them out there we've looked through many um just maybe having something that's easy to install and easy to get get up and running is is a good way to ensure a little bit more adoption at some point uh it you know I know Socrates has a really nice library with a sort of very readable interface that you can construct your proofs this doesn't require a huge amount of combinatorial literacy but more of a sort of programming literacy it's like um it's like how the Python language can be learned in a day or something thank you do you really think that having all the possible pairs helps the price discovery so I didn't quite catch that do you really think that having all the possible pairs helps the price discovery because in the financial Market yes or an Essence Market we basically usually exchange against uh US dollar or against some common uh asset uh for a very varied reason yes that people tend to to have a benchmark yeah so if we if we just get into the like all the possible combinations we we lose some liquidity and in my opinion yes the the price Discovery could be impacted uh negatively so I think you're referring to sort of this uh prediction that yes the price itself oh sorry the prices yeah well keep in mind that we're sort of hope we're we're working with the sort of uh assumption that we'll see many stable coins so we'll see less dominant trading Pairs and less of a common reference um or and you know also we may be thinking about just the exchange between certain categories of tokens like prediction tokens prediction tokens don't necessarily um uh need to have any sort of reference to some dominant dominant pair but maybe sort of exchanged amongst one another you make any simulations that people will be really willing to have a direct exchange between not popular tokens instead of going through um a common token like stablecoin for example well I mean do you have any simulations which will prove how this will impact the prices and the human behavior so I mean we have kind of sort of we've kind of scraped some of the uh the the we've taken advantage of some of the apis from other exchanges gathered uh you know some info I mean these are the sort of simulations we've done with what the sort of trading um looks like between these things yeah right by all the exchanges they don't allow to um exchange you know any to any there is usually you have three or four common uh tokens against Video Exchange I think this is something I'm gonna have to discuss with you later okay I don't entirely understand the question all right then thanks again [Applause]