有价证券订购簿

Question

下面的工作是为令牌制作订单(用令牌换以太/用令牌换取令牌等等)吗？

下订单时，会将其添加到相应的struct数组中。买入/卖出订单价格越低，其成本就越低，因为需要迭代和修改的数组越少(使其成为一个更有效的市场)。

显然，我必须改进它和减少气体，但这样的东西在实践中可行(似乎在测试中很好)？不确定真正的实现是否会随着并发订单的发生而崩溃，从而改变数组的状态。

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() {} 
}

Answer 1

我认为更有效和更可预测的改变是使用二进制搜索方法，首先检查最低价格的订单，然后是最高的价格，然后是两者的中间，等等，直到找到正确的定价订单。最大的争论是，你需要保持你的订单按价格排序，使插入的成本比天真地把它附加到数组的末尾稍高一点，但是使整个气体成本更可预测，并且有一个更合理的上限。除此之外，我认为您还需要有一些方法来确定谁应该首先得到交换。ie：

1. A将100枚硬币的卖出价定为0.1
2. B在500枚硬币上加上0.1的卖出订单
3. C在50枚硬币上加上0.1的买入订单，然后由合同填写

你得确定是谁拿的硬币。应该是谁先下命令的。因此，如果您要使用二进制搜索方法，那么最好是让订单结构只是一个简单的结构，价格和数量，然后有一个有序的列表发送者和他们各自的订单数量。这样，假设大多数人在特定的墙壁上下订单，您的总体订单簿就会更小。

Answer 2

不存在“同时命令改变状态”之类的东西。Ethereum事务，由于协商一致的算法，以一个完美的顺序发生。一个接一个。完全没有不确定性。如果调用未知的智能契约，您可能会得到某种递归的东西，但这是一个不同的问题。一旦事务启动，它就会在下一个事务开始之前完成。

不过，你可能需要担心的是那些不择手段的矿工，他们看着你的订单进来，阅读你的参与者的意图，产生他们自己的命令，让你的正常用户“领先”。这些不择手段的矿工不会赢得每一个街区，但他们可能会赢得一些，在这种情况下，你的用户输了。

这里有一篇关于BanCor https://hackernoon.com/front-running-bancor-in-150-lines-of-python-with-ethereum-api-d5e2bfd0d798问题的有趣文章

Answer 3

是的，全功能订购书是可能的。例如，请参见这一实现。它实现单面订单，只持有“买入”订单，而“销售”订单则由智能合同本身发出，并且总是以“市场”订单的形式下单。然而，这个实现可以很容易地转换成两面订单簿.设计思想(略为简化)如下：

1. 同一侧的所有订单都存储在AWL树中，按价格排序，然后按顺序顺序排序。因此，价格较好的订单(“买入”订单较高，“卖出”订单较低)是在价格较低的订单之前下单的，而较早创建的订单则是以与后来相同的价格提前下单的。在AWL树中下订单的复杂性是O(ln N)，其中N是订单的总数。
2. 订单的数量和值(数量*价格)聚集在AWL树的节点中，因此，除其他外，每个树节点在相应的子树中存储所有订单的总量和总价值。当下了新的订单时，所有受影响的树节点的聚合数据都可以在O(ln N) gas中更新。
3. 当新的秩序到来时，对面的树会从顶部向下遍历，以找出目前价格最低的订单，这些订单仍然可以用来实现新的秩序。在O(ln N)时间可以找到这样的订单，因为订单是按价格排序的。
4. 然后再次遍历树，以找到最右边的顺序，以便该节点左侧的总数量不超过新顺序上的数量。
5. 然后，在第3步和第4步中发现的最左边的订单处砍树。
6. 向左的所有订单都被删除(在O(ln N)时间中，聚合数量和值用于(部分)填充新订单(聚合数量和值可以在O(ln N)时间内计算)。
7. 如果必要的话，树被切割的顺序是部分填充(因此新的顺序也被(部分)填充)。
8. 如果在所有这些步骤之后，新订单尚未完全填满，则将其放入订单簿的其一侧。

上述代码经过充分测试，生产就绪，每棵树级约消耗35K气体进行新订单(即约350 K气体用于订购手册，1000份订单，350万份天然气用于订购单，100万份订单)。