fleupold
commented
5 years ago It's an interesting proposal. I have a few specific questions below. Generally I feel this is making our trust assumptions more prone to attacks and I feel we would need to do a more thorough analysis of the implications (the point about watch-towers delaying/selectively withholding data is scary).
Questions
The number of orders to be considered by the solution will be bounded to at most M orders and only these M orders will be published on-chain together with their trading volumes
Why do those have to published again? Wouldn’t the watch tower approach guarantee data availability in the first place? It seems like we are not really confident in that mechanism if we require an extra publication on chain.
Also, how would we prove that M is a true subset of N (and that the solver didn't add some more orders to increase surplus)?
once the order-collector has enough of these signatures, he will generate a snark to ensure that he has the signatures from the watch-towers.
Isn’t it likely to be cheaper to send and validate the signatures on-chain? In what order of magnitude are you thinking?
josojo
bh2smith
Idea: Since, data availability is expensive, reducing data availability to the required minimum is essential. This approach ensures data availability for orders with a positive trading volume only, and has weaker data-availability assumptions for all other orders and hence reduces the costs for placing orders. Several order collectors are collecting off-chain N orders. These operators create an order bundle and get it signed off by a distributed set of watch-towers ensuring the data availability. Then, each order collector posts the hash representing the order bundle on chain. The pool of valid orders for the optimization problem is then defined as the union of all orders represented by the different order hashes. The solutions to the optimization problem will then only be based on a fraction of the original orders. The number of orders to be considered by the solution will be bounded to at most M orders and only these M orders will be published on-chain together with their trading volumes. This is enough to ensure that at any time the data availability is given to calculate the current state of the chain, ensuring the non-custodial feature of the exchange.
Actors: Anchor-contract: The anchor contract is orchestrating the whole auction by allowing certain operators to do certain things in a specified timeframe. Also, it keeps track of all balances by storing important information as the balance hash.
Order-collectors: Order collectors are collecting orders from users for a small fee and then make sure that the orders are represented on-chain for the next auction. They collect the orders and hash them. After they are signed from several watch-towers, they will be sent the order hashes into the chain
Watch-towers: Watch-towers are ensuring data availability by signing order-hashes from order-collectors. They can be seen as powerful, paid archive nodes.
Optimizer: The optimizers are scanning all orders represented by all order-collectors and their provided hashes. Then they try to solve the optimization problem, by collecting a fixed-size subset of orders and optimize the trader's utility ( surplus).
Protocol description:
The protocol is a batch-auction with uniform clearing prices. Each auction collects orders for 3 minutes and then finds fair prices by solving an optimization problem maximizing the trader's utility. The number of orders being considered in the solution of the optimization problem is bounded by a predefined number.
The batch-auctions are run on a roll-up/snapp side chain with full data availability for the actual balances in the system and guaranteed liveness. However, the orders of the system have a weaker data-availability ensured just by watch-towers.
Each auction the order collectors are collecting orders from end users for a small fee. The order collectors put concatenate the orders into a string, which is then getting hashed. Then, they send out the orders together with the hash to a list of watch-towers, in order to get their signature that the order hash is calculated correctly and that the watch-towers will store the order data. Then, once the order-collector has enough of these signatures, he will generate a snark to ensure that he has the signatures from the watch-towers. This snark will be sent into the blockchain together with the hash. The orders considered for the next batch will then be the union of all orders represented by the different hashes from the order collectors.
After the orders for a batch are defined on-chain via a set of hashes, and they are possibly decrypted, the optimizer will try to find the best solution for the traders utilization optimization. Once they have found a solution, they have to register the solution cheaply at the anchor contract by sending their found utilization. After another time-period (3 mins), the optimizer with the best solution has to prove that their solution is valid. Additionally to the validation that the actual solution is valid, the optimizer also has to provide the order data of the used subset of orders, their positive trading volume and a snark proof that the used orders are actually a subset of the orders represented by the different order hashes and that each order is valid.
OrderHashing
Let’s assume an order is represented by (‘accountId’, ‘buyToken’, ‘sellToken’, 'buyAmount', 'sellAmount') with a bit vector of the following size (24, 8, 8, 32, 32) = 104. Additionally, each order will have the fields: auctionIndex and signature, however, they do not need to be considered for the hash. Each order collector will take a fixed amount of orders and concatenate them. Then the resulting string will be hashed using the Pederson hash. If each order collector is allowed to collect N orders, he has to hash 104*N bits.
Orders included in the solution:
When the optimizer is required to submit all necessary data of their solution, such as trading volume and the utilized orders together with their signatures, they also need to provide a snark to prove that their orders were part of the original order hashes.
This snark has the following tasks: Public inputs: orderhashes of order-collectors Public output: orderhash of orders used in the solution.
Logic:
This snark logic is quite simple. The main contributor for circuits will be the pederson hashing (it requires 1.7 circuits per bit). Since the snarks need to calculate pederson hashes of data blobs, a snark with 228 circuits could theoretically hash 228/(1.7*104) = 1.5 million orders. Of course, as constraints are also used needed for validation step 2, and 3, probably, we can only consider 0.5 million orders, but still this is a magnitude more than current implementations.
Instead of snark proofs, we could also use smart contracts challenges to get the assurance that the orders were included. Though, in order to load 0.5m orders onchain, it would cost already over 442 mio gas.
Risks:
Watch-towers withhold data and only publish their order, if withholding order makes a good profit. Malicious watch-towers will be voted out by a DAO;
Watch-towers publish data only later in order to have an edge in computing the solution. Every solution calculator could operator one or several watch-towers.
Watch-towers might delay their signatures for order-hashes and thereby screw order-collectors. The outcry caused might make the watch-tower operator losing their position. Maybe not, if it happens once, but if it happens frequently.
Orders might not be available for anyone. Still a solution can be found on a subset of orders provided by other order collectors and/or watch-towers.
Order-collectors might censor orders: If we encrypt orders, no meaningful censoring is possible and users can always post their order to several order collectors
If some (dx)DAO members do liveness tests on watch-towers and monitor their performance, watch-towers are forced to behave well. Otherwise, they will be voted out by (dx)DAO.
Additionally, staking for order-collectors and watch-towers might incentivize them to behave honestly as a collective.
Challenges: Snark calculation for order-collectors might take quite some time and prevent them from submitting order hash in time BLS signatures from watch-towers are an alternative if needed
Overall assessment:
Of course, it is theoretically cleaner and incentives are better protected if the orders are collected on-chain. However, in order to reduce order costs, improve liquidity and make the whole system more attractive, such an offline order collection scheme would help a lot.