2

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

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.