3

Would the following work for making an order book for tokens (trading tokens for ether / tokens for tokens etc.)?

When an order is placed, it is added to its respective struct array. The higher a buy/lower a sell order price is, the less gas it costs because less of the array has to be iterated through and modified (making it a more efficient market).

Obviously I have to refine it more and reduce gas but is something like this feasible in practice (seems to work fine in testing)? Not sure if real implementation would breakdown with concurrent orders changing the state of the arrays.

contract OrderBook {
    OrderStruct[] public buyOrderBook;
    OrderStruct[] public sellOrderBook;


    struct OrderStruct {
        uint price;
        uint quantity;
        address sender;
    }

    // Submit Buy Order
    function buy(uint _maxPrice, uint _amount) {
        while (_amount > 0) {
            if (_maxPrice >= sellOrderBook[sellOrderBook.length - 1].price) {
                // Match Orders
                // Delete Order From Sellbook
                // Adjust Sum
            } else {
                addBuyToBook(_maxPrice, _amount);
            }
        }
    }

    // Submit Buy Order
    function sell(uint _minPrice, uint _amount) {
        while (_amount > 0) {
            if (_minPrice >= buyOrderBook[buyOrderBook.length - 1].price) {
                // Match Orders
                // Delete Order From BuyBook
                // Adjust Sum
            } else {
                addSellToBook(_minPrice, _amount);
            }
        }
    }

    // Add Order Details to Buy Order Book
    // Place in correctly sorted position (ascending)
    function addBuyToBook(uint _maxPrice, uint _amount) private returns(bool success){
        if (buyOrderBook.length == 0) {
            buyOrderBook.push(OrderStruct({
                    price: _maxPrice,
                    quantity:_amount,
                    sender: msg.sender}));
            return true;
        }
        uint iterLength = buyOrderBook.length - 1;
        for (uint i = 0; i <= iterLength; i++) {
            if (_maxPrice > buyOrderBook[iterLength - i].price) {
                if (i == 0) {
                    buyOrderBook.push(OrderStruct({
                        price: _maxPrice,
                        quantity:_amount,
                        sender: msg.sender}));
                    return true;
                } else {
                    buyOrderBook.push(buyOrderBook[iterLength]);
                    for (uint j=0; j < i; j++) {
                        buyOrderBook[iterLength - j + 1] = buyOrderBook[iterLength - j];
                    }
                    buyOrderBook[iterLength - i + 1] = OrderStruct({
                        price: _maxPrice,
                        quantity:_amount,
                        sender: msg.sender});
                    return true;
                }
            }
        }
        buyOrderBook.push(buyOrderBook[iterLength]);
        for (uint k=0; k < iterLength + 1; k++) {
            buyOrderBook[iterLength - k + 1] = buyOrderBook[iterLength - k];
        }
        buyOrderBook[0] = OrderStruct({
            price: _maxPrice,
            quantity:_amount,
            sender: msg.sender});
        return true;
    }

    // Add Order Details to Sell Order Book
    // Place in correctly sorted position (descending)
    function addSellToBook(uint _minPrice, uint _amount) private returns(bool success){
        if (sellOrderBook.length == 0) {
            sellOrderBook.push(OrderStruct({
                    price: _minPrice,
                    quantity:_amount,
                    sender: msg.sender}));
            return true;
        }
        uint iterLength = sellOrderBook.length - 1;
        for (uint i = 0; i <= iterLength; i++) {
            if (_minPrice < sellOrderBook[iterLength - i].price) {
                if (i == 0) {
                    sellOrderBook.push(OrderStruct({
                        price: _minPrice,
                        quantity:_amount,
                        sender: msg.sender}));
                    return true;
                } else {
                    sellOrderBook.push(sellOrderBook[iterLength]);
                    for (uint j=0; j < i; j++) {
                        sellOrderBook[iterLength - j + 1] = sellOrderBook[iterLength - j];
                    }
                    sellOrderBook[iterLength - i + 1] = OrderStruct({
                        price: _minPrice,
                        quantity:_amount,
                        sender: msg.sender});
                    return true;
                }
            }
        }
        sellOrderBook.push(sellOrderBook[iterLength]);
        for (uint k=0; k < iterLength + 1; k++) {
            sellOrderBook[iterLength - k + 1] = sellOrderBook[iterLength - k];
        }
        sellOrderBook[0] = OrderStruct({
            price: _minPrice,
            quantity:_amount,
            sender: msg.sender});
        return true;
    }
    function OrderBook() {} 
}
1

I think it would be more efficient and predictable to change this to use a binary search method where first check the lowest priced order, then the highest priced, then the middle of those two, etc until you find the correctly priced order. The big contention is that you need to keep your order book sorted by price, making the insert cost a bit higher than naively appending it to the end of the array, but making overall gas cost more predictable and with a more reasonable upper-bound. Beyond that though I think you'd also need to have some way to determine who should get the swap first. ie:

  1. A adds a sell order at 0.1 for 100 coins
  2. B adds a sell order at 0.1 for 500 coins
  3. C adds a buy order at 0.1 for 50 coins, which is then filled by the contract

You need ot determine who gets the coins for that. It should probably be whoever put up the order first. So, if you were to use a binary search approach it would probably be ideal to have the order struct just be a simple structure with price and amount, and then have an ordered list of senders and their respective order amounts. This way your overall orderbook can be smaller assuming most people put orders at particular walls

  • I agree that binary search is more efficient gas-wise. But I was trying to use the gas inefficiency (of iterating through a price sorted array) to create a more efficient order book (where entering an order well below/above the market price is more costly in gas and therefore dissuaded). But I agree a runaway gas-cost is definitely an issue with that. – Kaizen Bran Jul 19 '17 at 20:28
1

There's no such thing as "concurrent orders changing the state." Ethereum transactions, because of the consensus algorithm, happen in a perfect order. One after the other. There is exactly zero indeterminism. You might get some sort of recursive thing going on if you're calling into unknown smart contracts, but that's a different issue. Once a transaction starts, it completes before the next transaction starts.

What you might have to worry about, though is unscrupulous miners who watch your orders come in, read the intentions of your participants, and generate their own orders to 'front run' your normal users. These unscrupulous miners won't win every block, but they might win some, in which case your user loses.

Here's an interesting article on the problem as described concerning BanCor https://hackernoon.com/front-running-bancor-in-150-lines-of-python-with-ethereum-api-d5e2bfd0d798

0

Yes, full featured order book on Ethereum is possible. See this implementation for example. It implements single-side order book, holding only "buy" orders, while "sell" orders are placed by the smart contract itself and are always placed as "market" order. However, this implementation may be converted into two-side order book quite easily. The design idea (somewhat simplified) is the following:

  1. All orders of the same side are stored inside AWL tree sorted by price and then by order sequential order. So orders with better price (higher for "buy" orders and lower for "sell" orders) are placed ahead of the orders with worse price, and orders that were created earlier are placed ahead of the orders with the same price that were placed later. The complexity of placing an order into AWL tree is O(ln N) where N is the total number of orders.
  2. Quantities and values (quantity * price) of the orders are aggregated in the nodes on AWL tree, so among other things, each tree node stored total quantity and total value of all the orders in the corresponding subtree. When new order is placed, the aggregated data for all affected tree nodes may be updated in O(ln N) gas.
  3. When new order comes, the opposite side tree is traversed from downward from the top to find the the worst-priced existing order that still may be used to fulfill the new order. IT is possible to find such order in O(ln N) time, as orders are sorted by price.
  4. Then tree is traversed again to find a rightmost order such that total quantity to the left of this node does not exceed the quantity on the new order.
  5. Then, the tree is cut at the leftmost of the orders found at step 3 and 4.
  6. All the orders to the left are dropped (in O(ln N) time, there aggregated quantity and value are used to (partially) fill the new order (aggregated quantity and value could be calculated in O(ln N) time).
  7. The order at which tree was cut it partially filled if necessary (and thus the new order is (partially) filled as well).
  8. If after all these steps the new order is not yet fully filled, it is placed into its side of the order book.

The code referred above is fully tested and production ready, and consumed about 35K gas per tree level for placing new order (i.e. about 350K gas for order book with 1000 orders, order 3.5M gas for order book with 1 million orders).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.