Darkpool

Screenshots

Problem Statement

I created a darkpool, which is a private orderbook, using FHE. This means that all the orders in the orderbook have encrypted prices and quantities.BackgroundDarkpools provide the following advantages over public orderbooks:increased market efficiency and liquidityMEV resistancemarket manipulation resistanceWith the recent introduction of Touring complete fully homomorphic encryption that is also computationally feasible we are finally able to provide mathematical guarantees to the privacy of darkpools.

Solution

Design and ArchitecturePublic order book implementationTraditionally order books are implemented as linked lists (representing sorted price levels) of linked lists (representing orders sorted by timestamp), with the additional mapping of prices to the corresponding nodes that allow for O(1) amortized time complexity of accessing orders at a given price level and removal and addition of orders at new price levels.Challenges of darkpool implementationsHowever, the above approach is not feasible when implementing an onchain darkpool using FHE for a number of reasons that I discovered over the course of the hackathon:linked lists can't be usedfirst of all, length of the linked list is dynamic and cannot be made privatesecond of all, the time complexity advantages don't apply when using FHE because we need to go over all of the elements anyway to obfuscate any modificationsthird of all, implementing a private linked list is not really possible. Solidity linked list implementations use mappings to map to neighbouring elements, however, using FHE, the same number encrypted twice leads to different cipher texts, so it can't be used as a key of a mapping. If we wanted to decrypt the cipher text to use it for the mapping then it effectively becomes public because any memory changes outside of view functions (even local ones) can be observed publicly. Moreover using decrypt in a non-view function is unstable as in the future it might lead to networking issues as decrypt will require a different verification networkbecause of obfuscation we can't really have better time complexity than O(n), where n is the number of ordersbecause of order modification obfuscations and computational overhead we need to limit the number of orders in the orderbookwe already established that the length of a dynamic data structure cannot really be made private unless it's abstracted away inside of a fixed length data structurecomputational overhead of FHEcurrent gas limit on Fhenix - 50 milliona single FHE operation might take around 100k gasa single FHE encrypted variable might contain around 50kB worth of data (which limits networking and cross-chain interactions)conditional logic is very hard/impossible to be done in a privacy-preserving waythat means that e.g. we can't really execute the orders when we see that they cross. This should be done in a separate step and we need to be very thoughtful about this execution.Implementations considered/implemented throughout the hackathonPublic order book implementationFirst of all, I familiarised myself with the way that public order books are efficiently implemented. My plan was to adapt it to use FHE: https://github.com/KramPiotr/private-orderbook/commit/bff999be532ca68a81d8b0fa96ce144e3cda98f1However, upon realising the above challenges and trying out half-baked solutions with public prices but private quantities, I decided to abandon this code and approach all together.Fixed number of distinct price levels and fixed number of orders per price levelMy first implementation was an order book with a fixed number of distinct price levels and fixed number of orders per price level. This implementation can be found when exploring the repo at the following commit: https://github.com/KramPiotr/private-orderbook/commit/1ec1c7e6df14446eb52936c9aac6214c48599683The idea behind it was that the least competitive price levels would be removed as more competitive price levels ariseThis solution seemed quite efficient from the computational perspective (seemingly O(d + n / d) time complexity where d is the depth of the price level), however it contained a few major flaws:with fixed number of orders per price level, all the additional orders at this price level don't end up in the book, which might result in a pathological situation in which a less competitive order gets filled instead of the more competitive one just because there were more orders at the more competitive price levelthis could partially be solved by allowing different price levels to contain the same prices but then this approach doesn't contain any obvious benefits over an approach with just one big array of sorted by competitiveness ordersthe perceived time complexity advantage doesn't really apply to a fully private solution as you need to modify all orders at each new state modification in order to achieve full obfuscationSorted by competitiveness fixed-length list of ordersThis is the final approach at which I arrived.This has the following advantage:by keeping the array sorted and performing an encrypted bubble sort every time we see an order, we can guarantee O(n) time complexity for order insertion, done in a fully private wayThe challenge I stumbled across with this approach:when filling opposite side orders, if you want to avoid the situation in which empty (fully filled) orders are left in your fixed length array, you need to implement the operation of shifting an array by k elements. There is a way to do that in O(n) time complexity, however, this would require decrypting an encrypted variable outside of a view function, which we established earlier leaks information and is unstable (in the future decrypt could be subject to network issues etc.). That's why I decided to follow the O(n^2) approach in which I shift by 1 element k times but iterate over the array n - 1 times in order to obfuscate k.Future directionIt would be very interesting to research into how sacrificing some privacy constraints but limiting computational overhead could lead to achieving a 'sweet spot', at which the FHE darkpool could actually become usable by industry.Some possible approaches I would like to research:randomizing modificationsinstead of modifying all the orders at every operation maybe we could modify a couple of randomly chosen as well as the ones that we actually want to modify?Another area of research is to make this solution as efficient as possible. A couple of ideas I can think of:merging orders together into bit mapslook into building more sophisticated data structures to store the orders e.g. treesimplementing encrypted mappingsWe know that FHE is Touring complete at this point so it's just a matter of finding the way :)Practical tipsSteps to run locally:pnpm installpnpm run localfhenix:startTo test the contract after modifying OrderBook.sol:pnpm localfhenix:stop && pnpm localfhenix:start && pnpm hardhat run scripts/DeployLocal.ts && pnpm hardhat run scripts/MintToken.ts && pnpm hardhat run scripts/PlaceOrder.tson testnet it's enough to dopnpm hardhat run scripts/TestnetScript.tscurrently# Private Order Book