Rounding issue when matching orders

[abitmore]

As @alexpmorris reported in this steemit post, there is an rounding issue when matching orders. For example:

The last matched order was selling 0.185 BTS, but apparently it's not enough to get 21 satoshi of HERO, so finally it got 20. However, to get 20 satoshi of HERO, only need to pay 0.1838 BTS.

Current implementation is in favor of the maker (it gets all the amount that below a satoshi of the other token). I propose to change it to in favor of the taker, or anything that is fairer. For example, if the rest is less than a satoshi, cancel the order and return the rest to the taker. I guess it's hard to implement due to the design of price structure. Another side effect is that people may be unable to sell all balance of one token.

Earlier discussion in #338. Probably related: #132, #184.

[abitmore]

Actually there is a deep discussion in #132 which IMHO worth reading.

[alexpmorris]

@abitmore, as I posted on bitsharestalk last night...

I just updated the post to reflect a new understanding of the problem. You'll still have to get through @abit's flagging. However, it turns out that @abit, @pc, and myself are both right and wrong on particular aspects. It turns out it's not a margin-call related issue, though there are some things that could probably be revisited given some of the things that were brought up. And it turns out it is also a bit of a "rounding issue" after all, but not quite in a way that anyone's brought up.

Part of the update on my post:

The "problem", at least for the community to decide if they consider it a "problem", is that you're not just "buying", you're "Buying at least". THAT's where the "rounding errors" are compounding.
...
What if I want to buy 1.5 INTELLIGUYPIZZA at 4.50 TEST, but by accident I entered 345 instead. Yes, I'm aware of the "GUI warning". But that's not the point here. The offer is 4.50, and there's plenty available. So, no problem... instead, I'll just get my 1.5 at 4.50 instead of 345, right?

WRONG! Here's what you'll really be getting... bought 113 INTELLIGUYPIZZA at 4.50 TEST/INTELLIGUYPIZZA.

Now, while all this seems to answer most cases that I came across, it DID NOT seem to properly address the WHALESHARE_BTS buy 40% higher than the inside offer. UNLESS, of course, this "size adjustment" is targeting the NON-DECIMAL LEG for adjustment...

For reference, here's the link for original post with the full update: http://bit.ly/2tKiDfb

[abitmore]

@alexpmorris Thanks for the contribution. We all aware of the issue, the challenge is we need a solution or maybe find a better trade-off. If you've read through the comments in issue #132 (which I guess you haven't), perhaps you'll come with more ideas.

[abitmore]

The picture attached above explains exactly why we described it as a rounding issue: the taker has never overpaid more than 1 satoshi of WHALESHARE every take.

[alexpmorris]

There's got to be a better way to handle this @abitmore, and I'd be happy to work with you to figure it out. Now that I know exactly what's going on, I'm pretty sure I know what needs to be solved. I'll try to come up with an ideal solution, and defer to you on if and how it can be safely implemented with minimal likelihood of "unintended consequences".

[alexpmorris]

#master...alexpmorris:patch-1

@abitmore Here's a potential fix for this problem. As I described in the pull request:

I'm not sure this is the exact ideal solution, but it does appear to work in conjunction with my testnet orders, which I've included in the associated ticket for this pull request. It makes changes both in match() and fill_order() methods, with both segments marked "APM". I also had to change pays to rawPays so I could adjust the for_sale amount in fill_order().

I also tried running the tests over the new code. HOWEVER, it seems the test code anticipates that if you overpay, you will receive MORE at a lower price, as opposed to simply receiving the amount you requested at a better price. I have included that example in the ticket as well. In operation_tests2.cpp, the "buyback" tests places an order for 100 at 1000, with a buy of 1 for 100. My new code fills 1 at 10, as I believe would be expected. The test case expects to receive 10 at 10 instead (ie. from the testcase perspective, 1 at 100 should equal 10 at 10).

I also left in some additional idump() code that I used in attempting to tackle this issue, in case it is of assistance to others attempting to evaluate this as a potential fix / solution.

Here is what the test case is expecting to receive:

Since I couldn't get through all the tests, and I've already spent quite a bit of time on this, I at least wanted to share what I came up with so far, and give the community the opportunity to "rip it" apart a bit to see what else I may have missed so far.

Here were the results of my updated code, as shown in openledger when linked to my local testnet (though manually entered via cli_wallet). Notice how every trade is perfectly rounded off, and the sizes received was always exactly what I, as a trader, would expect them to be. Note in this case I was buying/selling back to a single account "nathan". However, in my test case I was using a buyer and seller on both sides, and it did not appear to trigger an assertion in verify_asset_supplies(db):

[abitmore]

1. We need to define "sell" and "buy". In BitShares core there was no "buy" but only "sell", so every order has an amount_to_sell field and a min_to_receive field. I guess if we want to implement "buy", we need a new operation, with fields amount_to_buy and max_to_pay, so it can have different behavior, and we'll need to change the limit_order data structure and a lot of related code, and need work on UI.
2. Never use double or float in consensus code. Otherwise it will lead to unintended behavior. For example, if( (a/b).to_real() > x ) can be changed to if( a > b*x ).

[pmconrad]

Was about to suggest the same.

[alexpmorris]

I used to_real() to extract the rounding error. It also seemed to work very well to identify a buy order from a sell order of the non-core asset, because all buy orders entered resulted in (real_order_price > 1), and all the sell orders resulted in (real_order_price < 1).

This makes perfect sense to me, because how else would one determine the side of the book to place an order (for both the UI and for order matching), which by extension, also enabled me to extrapolate "amount_to_sell" versus "amount_to_buy". And while this also seemed consistent throughout my testing, are you saying this may not always be the case?

Also, if there's a better way to extract both of these values using the template primitives versus using to_real() as you described, that should be a relatively minor adjustment to make.

[pmconrad]

Trying to distinguish a buy from a sell by looking at the price doesn't make sense at all. What happens to your logic if BTS goes above 1 USD, for example?
@abitmore is right, we need an explicit buy-operation. We'll never be able to reliably second-guess the traders intentions, so we must provide him with a means to tell us what he wants.

[alexpmorris]

That was my first thought as well, except that internally within each order object, base and core are maintained as total quantities to exchange versus each other, along with which side is "for_sale", which implicitly should contain all the information we need. And of course, there must still exist a consistent way that the front-end and the matching engine always knows which side to target (bids and offers).

Furthermore, every test case I've tried seems to verify this. I also gave examples where BTS was trading below 1, above 1, and where the matching even took place through 1. Here are all the test cases, along with a few screenshots as well. Again, all these test cases behaved exactly as I would have expected:

sell_asset nathan 250 BTS 1000 TEST 100000 false true <-- BUY 1000 TEST @ 0.25
sell_asset nathan 1000 TEST 250 BTS 100000 false true <-- SELL 1000 TEST @ 0.25

sell_asset nathan 1000 BTS 250 TEST 100000 false true <-- BUY 250 TEST @ 4
sell_asset nathan 250 TEST 1000 BTS 100000 false true <-- SELL 250 TEST @ 4

TAKER SELLS (below 1 / above 1)

sell_asset nathan 25 BTS 100 TEST 100000 false true <-- BUY 100 TEST @ 0.25 (bts)
sell_asset nathan 50 BTS 100 TEST 100000 false true <-- BUY 100 TEST @ 0.50
sell_asset nathan 300 TEST 50 BTS 100000 false true <-- SELL 300 TEST @ 0.16667
result: 100 TEST filled @0.50, 100 TEST filled @0.25, remainder: 100 TEST offered @0.16667

sell_asset nathan 400 BTS 100 TEST 100000 false true <-- BUY 100 TEST @ 4 (bts)
sell_asset nathan 300 BTS 100 TEST 100000 false true <-- BUY 100 TEST @ 3
sell_asset nathan 300 TEST 600 BTS 100000 false true <-- SELL 300 TEST @ 2
result: 100 TEST filled @4, 100 TEST filled @3, remainder: 100 TEST offered @2.00000

TAKER BUYS (below 1 / above 1)

sell_asset nathan 100 TEST 25 BTS 100000 false true <-- SELL 100 TEST @ 0.25 (bts)
sell_asset nathan 100 TEST 50 BTS 100000 false true <-- SELL 100 TEST @ 0.50
sell_asset nathan 300 BTS 300 TEST 100000 false true <-- BUY 300 TEST @ 1
result: 100 TEST filled @0.25, 100 TEST filled @0.50, remainder: 100 TEST bid @1.00000

sell_asset nathan 100 TEST 400 BTS 100000 false true <-- SELL 100 TEST @ 4 (bts)
sell_asset nathan 100 TEST 300 BTS 100000 false true <-- SELL 100 TEST @ 3
sell_asset nathan 1500 BTS 300 TEST 100000 false true <-- BUY 300 TEST @ 5
result: 100 TEST filled @3, 100 TEST filled @4, remainder: 100 TEST bid @5.00000

TAKER SELLS (above 1 through below 1)

sell_asset nathan 125 BTS 100 TEST 100000 false true <-- BUY 100 TEST @ 1.25 (bts)
sell_asset nathan 80 BTS 100 TEST 100000 false true <-- BUY 100 TEST @ 0.80
sell_asset nathan 300 TEST 150 BTS 100000 false true <-- SELL 300 TEST @ 0.50
result: 100 TEST filled @1.25, 100 TEST filled @0.80, remainder: 100 TEST offered @0.50000

TAKER BUYS (below 1 through above 1)

sell_asset nathan 100 TEST 80 BTS 100000 false true <-- SELL 100 TEST @ 0.80 (bts)
sell_asset nathan 100 TEST 125 BTS 100000 false true <-- SELL 100 TEST @ 1.25
sell_asset nathan 450 BTS 300 TEST 100000 false true <-- BUY 300 TEST @ 1.50
result: 100 TEST filled @0.80, 100 TEST filled @1.25, remainder: 100 TEST bid @1.50000

And finally...

TAKER SELLS small lot too low
sell_asset nathan 150 BTS 100 TEST 100000 false true <-- BUY 100 TEST @ 1.50 (bts)
sell_asset nathan 11 TEST 5 BTS 100000 false true <-- SELL 11 TEST @ 0.454545
result: 11 TEST sold / filled @1.5

TAKER BUYS small lot too high
sell_asset nathan 100 TEST 80 BTS 100000 false true <-- SELL 100 TEST @ 0.80 (bts)
sell_asset nathan 10 BTS 11 TEST 100000 false true <-- BUY 11 TEST @ 0.90909
result: 11 TEST bought / filled @0.80

Note, if you would like to try reproducing these results, every example I gave should work directly in the cli_wallet (just leave off the <-- comment). I also used:

get_limit_orders TEST BTS 100
cancel_order 1.7.8 true

between test sessions to retrieve order ids and cancel orders for the next test.

[pmconrad]

What you didn't test is the case that the book contains more at a better price than the taker offers.

Like this (didn't test myself, I hope you get the idea):

sell_asset nathan 400 TEST 100 BTS 100000 false true <-- SELL 400 TEST @ 0.25 (bts)
sell_asset nathan 100 BTS 100 TEST 100000 false true <-- BUY 100 TEST @ 1

sell_asset nathan 400 TEST 1000 BTS 100000 false true <-- SELL 400 TEST @ 2.5 (bts)
sell_asset nathan 100 BTS 1000 TEST 100000 false true <-- BUY 100 TEST @ 10

In one of these cases the taker should buy 400 with your modifications, in the other case 100.

[alexpmorris]

sell_asset nathan 400 TEST 100 BTS 100000 false true <-- SELL 400 TEST @ 0.25 (bts)
sell_asset nathan 100 BTS 100 TEST 100000 false true <-- BUY 100 TEST @ 1
result: 100 TEST bought / filled @0.25000

sell_asset nathan 400 TEST 1000 BTS 100000 false true <-- SELL 400 TEST @ 2.5 (bts)
sell_asset nathan 100 BTS 1000 TEST 100000 false true <-- BUY 1000 TEST @ 0.10000 (I think you meant the line below)
sell_asset nathan 1000 BTS 100 TEST 100000 false true <-- BUY 100 TEST @ 10
result: 100 TEST bought / filled @2.50000

Again, isn't this exactly what should be expected?

[pmconrad]

sell_asset nathan 1000 BTS 100 TEST 100000 false true <-- BUY 100 TEST @ 10

Yup, that's what I meant. Thanks for noticing.

My first example was bad, because the taker price is exactly 1. What about

sell_asset nathan 400 TEST 100 BTS 100000 false true <-- SELL 400 TEST @ 0.25 (bts)
sell_asset nathan 100 BTS 125 TEST 100000 false true <-- BUY 100 TEST @ 0.8

I'm still struggling with the logic you have implemented there. Can you explain in simple terms the reasoning behind it? For example, most of the time core_min_counter_size should be equal to core_for_sale.amount, but I suspect due to your use of doubles and rounding it may not be. At the same time, usd_max_counter_size will always be <= usd_for_sale.amount, because otherwise the two orders would not be matched.

[alexpmorris]

sell_asset nathan 400 TEST 100 BTS 100000 false true <-- SELL 400 TEST @ 0.25 (bts)
sell_asset nathan 100 BTS 125 TEST 100000 false true <-- BUY 125 TEST @ 0.8 (I think you meant 125 here, not 100)
result: 125 TEST bought / filled @0.25000

in match():

• use_max_counter_size assures that the maximum non-core size received does not exceed the exact rounded amount
• use_min_counter_size assures that the minimum core size received is not below the exact rounded amount

Essentially, the logic assures that you are both receiving and paying at an exact satoshi increment (as @abitmore had described), and not above or below on each side of the matched order.

in fill-order():

• this serves only to refund any overpay (above the rounded increment) on the order, as well as to adjust the order accordingly for that overpay.
• I thought this may still pose an issue, but mostly if I didn't account for another possibility (ie. it didn't seem I needed logic for the reverse case).
• Also, if fill-order() is called elsewhere directly without calling match() first, that may require an extra parameter into the function such as adjustForRounding:

bool database::fill_order( const limit_order_object& order, const asset& pays, const asset& receives, bool cull_if_small, bool adjustForRounding = false) { ... }

[pmconrad]

Thanks, but I still don't get it. How/why does the real_order_price play a role there?

Are you sure the orders arrive on the blockchain exactly as you enter them in the GUI?

HOWEVER, it seems the test code anticipates that if you overpay, you will receive MORE at a lower price,

Yes, that's the current logic.
Can you adapt the existing unit tests to your expectations, and perhaps add all of the above tests? That would be helpful no matter what solution we choose to implement.

[alexpmorris]

Sorry for the delay in responding, but it turns out you both were right about the inversion issue. I'm actually a bit confused myself, given how they all seemed to show up correctly as you saw in the screenshots. @pmconrad, you asked if I was entering them into the GUI, which may somehow still have been compensating somehow to obfuscate the problem. However, all orders were entered directly into the cli_wallet, with openledger only used to monitor. Perhaps it was some combination of the GUI and/or cli_wallet that was compensating for the issue.

However, internally, upon further review, the issue you brought up was certainly there. I might have tried using openledger to enter orders as well, but I would have had to change the genesis chain_id to my private testnet, which seemed non-trivial at the time.

As such, I spent some time rethinking how this could possibly be implemented by:

• addressing the inversion issue
• avoid creating a whole new buy operation, as @abitmore suggested would be required

What I came up with is a bit of a "hack", but so far it does seem to work. However, it would still require a mod to the UIs to pass in above1 by targeting the little-used "expiration" field. This would, of course, require much further review, however, it should provide the additional information required to identify the target side for "adjustment". If this "flag" is not set, match() will revert to its default pattern of behavior.

const limit_order_object* database_fixture::create_sell_order_with_flag( const account_object& user, const asset& amount, const asset& recv, bool above1 ) {
...
 if (above1) buy_order.expiration = buy_order.expiration.maximum()-1000; else 
		buy_order.expiration = buy_order.expiration.maximum()-1001;
...
}

The information is added into each order via the less often used expiration field, which is not ideal, but should be "minimally invasive" as a sort of "hack", since it doesn't add many new methods or operations, or require any modification to objects that may be already serialized or encoded on the blockchain or elsewhere.

Further analysis would also be required to determine if this can become a target vector for manipulation, by either reversing the flag or leaving it out (again, partly because as described above, if this "flag" is not set, match() will revert to its default pattern of behavior).

I also created a whole set of test cases based on the examples we discussed in this thread, and so far (assuming I got all the test cases correct) the solution is passing them all. More test cases will likely be needed to really run this idea through the grinder.

The main changes are in an updated match() function, and a new fill_order_rounded() which adds a parameter pay_refund to refund order "overpayments". Also, for the new test cases, a function create_sell_order_with_flag() was added.

Link to code updates: https://github.com/alexpmorris/bitshares-core/commits/master

[abitmore]

Actually the expiration field is frequently used by trading bots, as well as the fill_or_kill field, so it's not a good idea to mess them up.

A "normal" fix would be: add a new optional flag to the extensions field of limit_order_create_operation to indicate different behavior, so the operation will keep the old behavior if flag is not presented. UI and 3rd-party applications may need to understand the new flag, but I think it's not a big deal if they don't. It's a hard fork change, so nodes will need to upgrade anyway, there will be no serialization issue. It will be also OK to add new fields to objects. This approach will be better than adding a new operation.

Avoid using real, then there will be no need to call round(), because "rounding down" is the default behavior of operator /() of integers. @alexpmorris: after you removed doubles from your code I'll review the logic. Thank you.

[alexpmorris]

That's great to hear @abitmore, as I agree the other options would be much better if it could easily be implemented without causing issues elsewhere. My idea of using expiration was more of a "worst-case scenario", in case no better option was available. I also cleaned up the code a bit, and removed the use of double and round().

[abitmore]

TBH the code is far from usable. I'm not sure if it compiles. For example, match is a template function, the parameter core maybe a limit_order or call_order or settle_order, but fill_order_rounded only accepts limit_order. And we won't hack the expiration field in the final fix.

Thanks for your efforts anyway. If you want your code to be merged, or be used by others to work upon, please at least follow the existing coding style/format/practice, avoid duplicate code blocks and etc. Otherwise it would be more efficient for others to redo the job from scratch.

I have a rough image of solution of this issue in my head, but don't have much time to code it right now. I'll work on it later when got time and if it's still not fixed.

[abitmore]

Once we have "buys", we can add more options/flags to UIA's which can be decided by the issuers, for example, define a market pair is "un-flip-able", so only accept "sells" from on side and "buys" from the other side, and we can add restrictions to the price struct in that pair, for example enforce quote.amount % base.amount == 0 or something similar, then the rounding issue will be killed entirely.

[alexpmorris]

https://github.com/alexpmorris/bitshares-core/tree/order-rounding-fix

With this latest revision, I believe the order matching problem is solved. I also combined almost all the code into the rounded_match() function, called from database::match() in db_market.cpp - this should enable the code to be accessed by any template parameter that also calls match().

I also created a barrage of test cases, all of which pass (assuming I got all the necessary test cases correct, of course). In addition, for full functionality all a limit order needs is the assignment of one additional optional flag, isCoreBuySell.

It turns out the problem wasn't differentiating a buy from a sell (or above/below 1), it was differentiating an inverted buy/sell (ie. isCoreBuySell versus isTestBuySell). If you think of openledger, we always know when an order is a buy or a sell. What we don't know is which LEG they're trying to buy and sell. Once the target leg is identified (explicitly or by default), any remainder that doesn't evenly match is simply discarded and refunded.

I tried to use references that make it easier to follow what's going on from a practical standpoint, hence the use of terms such as "isCoreBuySell" and "isTestBuySell", since that's really what we need to know: is the order BUYING TEST / SELLING TEST, or BUYING CORE / SELLING CORE. By default, it is currently set to BUY TEST / SELL TEST (ie. buy DOW with USD / sell DOW with USD). For most cases, I believe it is much less often the other way around.

Another interesting thing that I discovered is that while STEEMIT did clean up the code quite a bit, this problem affects ALL chains based on graphene 2.0 (bitshares, steem, golos, peerplays, even eos)! That includes the STEEMIT internal market as well. So, even better, if this fix solves the problem for one, it should solve the issue for all the other chains as well.

Finally, if you would like to see my test runs, or the version I used for debugging (including all the idump(()) calls), you can find that code here:

https://github.com/alexpmorris/crypto-playpen/tree/master/bitshares-core

[pmconrad]

I'm sorry, but I still don't see how comparing order_price to book_price can yield useful information. This only makes sense if you assume a certain market order, which is entirely the wrong approach.

[abitmore]

The order on the book might have a same flag set as well ( sell or buy, or say, want to get more or get a refund ), and should be checked as well. Besides that, call orders and settle orders can not be cancelled/refunded, so their behavior are simpler.

[alexpmorris]

https://github.com/alexpmorris/bitshares-core/tree/order-rounding-fix

You're right @pmconrad, that variable was still mislabeled. We already know it's a match ( as we're already in match() ). The template ( greater_than / less_than ) is comparing the size of the incoming order to the size of the sitting order, and based on that, the code goes on to adjust for the target leg. I've changed the variable name to reflect that.

As a trader, if I place a limit order, I don't want to receive a fill above (or below, for a sell) the price of a standing limit order, and comparing my order size ratio versus the book's order size ratio assures that I will evenly match that order before moving on to the next order on the book. This solution appears to accomplish that goal.

Keep in mind that all orders already on the book are properly rounded versus their available size, so all that's really necessary is to match the size of the incoming order to size that rounds evenly with the order that is already available. And again, any remainder that cannot be properly matched in the face of a standing order is simply discarded and refunded.

As @abitmore said, call and settle orders are "simpler", in that they can probably just be handled in the current fashion, since there is an incentive to "penalize" those orders anyway. As such, the default mode of operation is now set to "no action" (ie. isCoreBuySell is undefined -> isCoreBuySell == false, isTestBuySell == false).

I also made the other adjustments you both suggested, and added the limit_order_flags extension to the cli_wallet code. As discussed, this also seems amicable to any future extensions that may be added as well. We can now issue sell_asset requests as follows:

sell_asset nathan 103 TEST 300 BTS {} 100000 false true
sell_asset nathan 103 TEST 300 BTS {"isCoreBuySell":false} 100000 false true
sell_asset nathan 103 TEST 300 BTS {"isCoreBuySell":true} 100000 false true

[abitmore]

Done with #830. Closing.

[abitmore]

@alexpmorris if you have time, can you help verify it's fixed in testnet (https://testnet.bitshares.eu/)?

[alexpmorris]

@abitmore I tried matching a bunch of orders with extreme price and size combinations on the testnet, and while the size could still be greater than expected (as expected, since that was the premise of my proposed "isCoreBuySell" extension), all the match prices appear to be right in line with what I'd expect.

As such, definitely a step in the right direction. 👍

[abitmore]

@alexpmorris thank you!