Review and test something-for-nothing check

[theoreticalbts]

EDIT: TLDR: I believe we did think about this and the current code tries to implement (c), but I think the implementation may be buggy and/or untested. And even correctly implemented it may behave in a way which sometimes makes perverse decisions from an economic policy perspective.

Long version: (end EDIT)

The amount == 0 check here is apparently testing for a something-for-nothing situation, whereby the quantization of trade leads to a fill logic which results in something-for-nothing trade.

We need to carefully analyze the trade and determine that this logic can only trigger for dust values. Also, I think this logic is in the wrong place.

What needs to be done on this is:

• Clearly and carefully define the situation(s) which need(s) to be prevented.
• Clearly and carefully define the system's desired response to the situation.
• Provide robust set of unit tests which check the above definitions match the implementation.

[theoreticalbts]

The situation to be prevented is, roughly, when a something-for-nothing trade would occur due to quantization effects. In this case, the desired response, roughly, is to cancel the order of the party who would receive nothing.

[theoreticalbts]

The simple situation to handle is when an order is fully satisfied with a surplus balance. E.g. if Alice is top-of-book buying 3 B for 99 A, and Bob enters an order to sell 3 B for 100 A, then Bob should be totally filled and become the new top-of-book; but he should be immediately cancelled as he has a zero quantity.

• Cancel orders whose "have" or "want" reaches zero as a result of trade (i.e. completely filled).

The more subtle problem is a quantization problem. Say Alice has the existing top-of-book order which is matching Bob's incoming order. Let a/b be Alice's order price after cancelling any common denominator. Then a trade a-for-b satisfies Alice's order price exactly, and any smaller trade must have some premium or discount.

Define an a-for-b trade to be a unit trade.

If the matched volume is greater than or equal to a then at least one unit trade is possible. After all such unit trades are completed, there will likely be some residue.

If the matched volume is smaller, the system must find trades that don't occur at Alice's exact price, but rather have some premium or discount to her exact price. To be consistent with the definition of price [1], this premium / discount must be more favorable than Alice's price. It must similarly match Bob's price. This can lead to situations where no integer-valued trade can occur between Alice and Bob, even though their prices overlap.

It is tempting to simply rule that any order with an insufficient balance to perform a unit trade is subject to cancellation when matched. However, the matched order may be a margin call, which cannot be cancelled.

We need to either cancel orders which nearly match a margin call, or walk (potentially unboundedly?) deep in the book in order to find a match which is capable of unit exchange.

[1] Price can be defined as "the least favorable exchange rate a party is willing to accept in trade."

[theoreticalbts]

Here is an example:

Alice's order: Sell CORE at $3 / 8, balance 1000000 CORE
Bob's order: Buy CORE at $19 / 50, balance $10

Both assets have precision of 1, i.e. the order balances are 1000000 CORE-satoshis and 10 USD-satoshis repectively.

Alice is selling at $3/8 CORE = $0.375 / CORE and Bob is buying at $19 / 50 CORE = $0.38, so based on the price, Alice and Bob should match.

Bob's $10 / $0.38 ~ 26.3. So 26.3 is the fewest CORE he is willing to accept (assuming that the meaning of "price" is "the least favorable exchange rate a party is willing to accept in trade"). Combined with the design restriction that satoshis are indivisible, in practice this means Bob will only accept 27 or more CORE for his $10.

But $10 / 27 gives a price smaller than $0.370 and $0.371, which is smaller than Alice's sale price of $0.375. So neither party can fill this offer.

[theoreticalbts]

Here are the possible solutions to the problem:

• (a) Fill someone at a less favorable exchange rate than the price they specified in their order. Downside: This violates the above definition of price; i.e. if a user enters a price intending the system to never sell below that price in any circumstance, the system will not always behave in a way which fulfills that user intent.
• (b) Keep both orders on the books. Downside: This complicates the matching algorithm, as now Alice might be able to match an order behind Bob's order. Naive implementation would have potentially unbounded matching complexity; a more clever implementation might be possible but would require substantial design and testing effort.
• (c) Cancel an order. This is complicated by the fact that an order such as a margin call cannot be cancelled. Downside: When there are margin calls happening, it seems perverse to delete a large order that's willing to fill them just because the lead margin call happens to fall in a narrow window which causes a rounding issue. Also, orders cancelled by this mechanism cannot be refunded by Refund Create Order Fees on Cancel (Worker Proposal) #445. Otherwise an attacker who wants to consume a lot of memory on all nodes could create a large number of orders, then trigger this case to cancel them all, getting their investment in deferred cancellation fees back without paying the cancel op's per-order fee as intended.
• (d) Require all orders to use the same denominator. Altcoin exchanges and many real-world markets like the stock market solve this problem by specifying one asset as the denominator asset, specifying a "tick" which is the smallest unit of price precision, and requiring all prices to conform. Downside: Complicates the implementation of flipped market UI, may require re-working part of market GUI, reduces user flexibility, new asset fields required to specify precision, if n assets exist then O(n^2) markets could exist and we need to figure out how to determine the precision requirement for all of them.

[theoreticalbts]

TLDR: I believe we did think about this and the current code tries to implement (c), but I think the implementation may be buggy and/or untested. And even correctly implemented it may behave in a way which sometimes makes perverse decisions from an economic policy perspective.

[theoreticalbts]

Assigning to @bytemaster for analysis / opinion on what course of action to take. In particular, I need to know if this is problem enough to be considered a blocker for the next release.

[bytemaster]

The proper response is to cancel the dust order and do nothing to the order the dust order was attempting to match against.

So if I have a large order to buy $100 worth of BTS, and someone tries to buy an amount of bts worth less than 0.0000 BitUSD from me, my order should stand and they should get canceled.

By definition all orders are for an amount greater than 0 (or they are removed/filled).

The order that would "receive nothing" is by definition paired against a dust order that will receive something (dust). The dust order is what should be canceled, not the order that would receive nothing.

[bytemaster]

Upon further review of the code and the math involved, it is not possible to construct a new order with a price and amount that would get matched with an existing order and trigger the existing order to be canceled.

We have defined a dust order as one where

ORDER_PRICE * ORDER_AMOUNT == 0

This is the point at which the unfilled portion of the order is smaller than the resolution of the orders price and thus should be refunded to the user.

[svk31]

There's a consistent issue with orders that are not perfectly match causing the left-over to execute at prices far above/below the actual prices of the original orders, and bypassing the orderbook completely. As an example, here's the market history for OBITS:BTS yesterday:

Price OBITS BTS DATE
25.56522 0.0023 0.05880 7/2 20:30:57
29.28000 0.0005 0.01464 7/2 20:30:30
25.67381 0.0084 0.21566 7/2 19:43:18
27.40000 0.0004 0.01096 7/2 19:43:15
37.50000 0.0002 0.00750 7/2 19:42:54
25.64848 0.0033 0.08464 7/2 17:49:12
26.86111 0.0018 0.04835 7/2 17:48:57
27.90000 0.0010 0.02790 7/2 17:48:39
29.52000 0.0005 0.01476 7/2 17:48:21
26.76667 0.0003 0.00803 7/2 17:48:06
25.49850 80,790.9324 2,060,047.22548 7/2 17:47:45

Throughout this there was massive sell support at around 25 BTS/OBITS, but the dust orders executed well above this. I'm not sure if this deserves a new issue or if it fits with the problem described in this issue.

[nmywn]

price bts open.BTC
0.00000353 0.00283 0.00000001 3/07 18:14:45 market OPEN.BTC : BTS
0,00000001*0,00000353 = 0

but

price open.BTC BTS
283,000.00000 0.00000001 0.00283 3/07 18:14:45 market BTS : OPEN.BTC

283000×0,00283 = 800,89

so ORDER_PRICE * ORDER_AMOUNT == 0
is true only at one market?

Im not sure how its working just guessing.

[pmconrad]

See also https://steemit.com/bitshares/@skriptroid/openledger-trade-engine-bug-or#@cyrano.witness/re-skriptroid-openledger-trade-engine-bug-or-20160729t095720645z

My conclusion is that the market engine is correct, and that what users are complaining about is merely a display issue. The UI displays the trade price as calculated from paid/received, which can be significantly different from bid/ask on low-volume orders.

A possible fix might be to somehow include the order price in market history entries and have the UI display that instead of the trade price.

[vikramrajkumar]

This issue was moved to bitshares/bitshares-core#132