Multiplication Overflow

[fleupold]

The following solution (batch 5294170) caused a

SafeMath: multiplication overflow

in the smart contract: https://gnosis-dev-dfusion.s3.amazonaws.com/data/mainnet/open-solver/results/2020-04-30/instance_5294170_2020-04-30T12%3A57%3A18.258176793%2B00%3A00/06_solution_int_valid.json

The payload sent to the contract is:

'{"jsonrpc":"2.0","method":"eth_call","params":[{"data":"0x2e4c83bd000000000000000000000000000000000000000000000000000000000050c85a0288df0cac5b3f5dc83cd4e930288df0cac5b3f5dc83cd4e930288df0cac5b3f00000000000000000000000000000000000000000000000000000000000000e000000000000000000000000000000000000000000000000000000000000003000000000000000000000000000000000000000000000000000000000000000520000000000000000000000000000000000000000000000000000000000000074000000000000000000000000000000000000000000000000000000000000007800000000000000000000000000000000000000000000000000000000000000010000000000000000000000000deaddd02b449bc6b3b253ccb08da83ca5c4433260000000000000000000000007129f869845e854afa805170a6e42ce42a543b3d00000000000000000000000063bff26aee9db95f67676b1b2c1c0fdc841db58f000000000000000000000000ba7dd58e6f294d6e26f22e267a62bb671ee2b297000000000000000000000000077b3b2dd6c0a0004d1ea775d8983bd2e4cbbb6700000000000000000000000043a734e3b6db49e20362f2a1ebb76df436a9b0f40000000000000000000000002661a8d2a2de9bb48d0aa8c41ad0b7fd9ea04035000000000000000000000000a5821acf51177f8b827709e4863154fb59d6ea6a0000000000000000000000006a79d177b8ab7e6cd84a4e36210be3e174a20fd10000000000000000000000004f3a6729d0570f61e9b2f5c3277f6cb969183a76000000000000000000000000607adf506deba187ca0233b410773d0dd583e1d4000000000000000000000000077b3b2dd6c0a0004d1ea775d8983bd2e4cbbb67000000000000000000000000b9e4f6b7cfc5f40e7ba40806e0be8726ecf034f0000000000000000000000000deaddd02b449bc6b3b253ccb08da83ca5c443326000000000000000000000000459c7f5562787b665da29a59f6ad5821594872fc000000000000000000000000068183e2057651a1c124c994489236447f9a50300000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000200000000000000000000000000000000000000000000000000000000000000020000000000000000000000000000000000000000000000000000000000000002000000000000000000000000000000000000000000000000000000000000000200000000000000000000000000000000000000000000000000000000000000020000000000000000000000000000000000000000000000000000000000000002000000000000000000000000000000000000000000000000000000000000000200000000000000000000000000000000000000000000000000000000000000020000000000000000000000000000000000000000000000000000000000000002000000000000000000000000000000000000000000000000000000000000000200000000000000000000000000000000000000000000000000000000000000020000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000200000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000002000000000000000000000000000000000000000000000000000000000000000200000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000a572010214cd0000000000000000000000000000000000000000000000000000cb129e9609b600000000000000000000000000000000000000000000000e33d4500c2864431a0000000000000000000000000000000000000000000000000000cb129e9609b60000000000000000000000000000000000000000000000000000a57200f7d5100000000000000000000000000000000000000000000000000000a571fcc34a0d0000000000000000000000000000000000000000000000000000cb129e9609b60000000000000000000000000000000000000000000000000000cb129e9609b60000000000000000000000000000000000000000000000000000cb129e9609b60000000000000000000000000000000000000000000000000000cb129e9609b60000000000000000000000000000000000000000000000000000cb129e9609b600000000000000000000000000000000000000000000000fb2a3a80ee7688dd60000000000000000000000000000000000000000000000000000cb129e9609b600000000000000000000000000000000000000000000001408d452718620dd9900000000000000000000000000000000000000000000002a46856d6eb208e2f600000000000000000000000000000000000000000000002a46856d6eb205e1a3000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000026647b11836b0bc900000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000007","from":"0x453ad119f26128034d3b5c2b6179b8b7f63ae1c7","to":"0x6f400810b62df8e13fded51be75ff5393eaa841f"},"latest"],"id":19849}'

[marcovc]

Thanks Felix. I was trying to use tenderly again. How do you know the block number corresponding to this transaction?

[fleupold]

We don't know for sure (as we are using the "latest" block at the time). The error was thrown at 10:57:45 UTC, the latest blocknumber at that time according to etherscan was probably https://etherscan.io/block/9973513

[marcovc]

Using that block number in tenderly fails on:

require(acceptingSolutions(batchId), "Solutions are no longer accepted for this batch");

Does this mean that I should try lower numbers?

[marcovc]

From https://etherscan.io/address/0x6f400810b62df8e13fded51be75ff5393eaa841f?fromaddress=0x453ad119f26128034d3b5c2b6179b8b7f63ae1c7 (filtered on the from address above), seems there is a failed transaction about 4.5 hours ago. That would be block 9973323, but it also fails with the error message above.

[fleupold]

Sorry, I messed up the timestamps (they were already in UTC), so we are looking at 12:57 which is block https://etherscan.io/block/9974043

Note that "Solutions are no longer accepted for this batch" can also mean "Solutions are not yet accepted for this batch"

[marcovc]

That worked, thanks. Unfortunately I ran out of free simulations (10). They are now asking me to upgrade to tenderly pro :(

EDIT: Apparently I still have a trial phase of 15 days, yay!

[marcovc]

After investigation using tenderly, it seems the multiplication overflow happens when computing the disregarded utility of an order. I double checked and it matches perfectly what I'm doing in python (except python has no limitations on multiplication). The contract throws when doing the multiplication on this line:

return leftoverSellAmount.mul(limitTerm).div(order.priceDenominator);

With:

leftoverSellAmount=369571105569092197786
limitTerm=370683784331598768882711983787539765449898669456698019911

If you multiply them together and take the log2 you get 256.24, and that's why it fail.

Now, how should we handle this on the solver side? Should we send the trivial solution whenever some multiplication/division can't fit in 256 bits?

[fleupold]

That's very unfortunate. It basically means the user has too much balance/remaining amount left. So his order can only be fulfilled fully - not partially (at least at these prices). Is this a very esotheric example or can this easily happen again?

We should be able to multiply to a product of up to 10**111, which should allow in sum 57 digits (111 - 18 (price_a) - 18 (price_b) - 18 (amount)

We should be able to multiply to a product of up to 10**77, which should allow in sum 23 digits (77 - 18 (price_a) - 18 (price_b) - 18 (amount)

[marcovc]

Here is the order details:

order.priceNumerator: 340282366920938463463374607431768211455
order.priceDenominator: 257116982223191571130725490665975709695
executedBuyAmount: 181909061768397
executedSellAmount: 65820725211753
getRemainingAmount(order): 257116982223191571130725424845250497942
getBalance(user, tokenIdToAddressMap(order.sellToken)) : 369571105569092197786
currentPrices[order.buyToken]: 1000000000000000000
currentPrices[order.sellToken]: 2766471386261818313
leftoverSellAmount: 369571105569092197786

[fleupold]

So the problem is the huge priceDenominator/Numerator.

cc @josojo for the discussion. This seems to be an OWL liquidity provision order. Because it has unlimited amount the numerator and denominator are extremely large (128 bit) which might limit their ability to be use in trades.

[fleupold]

Should we send the trivial solution whenever some multiplication/division can't fit in 256 bits?

Given the open solver can touch more then one order per side, can we just exclude the offending orders and try to solve again?

[marcovc]

I see. I supose in the smart contract we could have an alternative association in case it doesn't fit the current way?

For example this gives a pretty close value:

return leftoverSellAmount.mul((limitTerm.div(order.priceDenominator))

[marcovc]

Given the open solver can touch more then one order per side, can we just exclude the offending orders and try to solve again?

Yes that is always possible. It would be a bit inefficient though since we would have to remove one at a time, interleaving with solving, until everything fits. Unless we come up with a good heuristic to remove these orders at preprocessing.

[josojo]

Yes, I agree that this is an issue with the smart contract, which we should have thought of before. Hence, I made an issue in dex-contracts: gnosis/dex-contracts#708. We should tackle it in the next version.

Given the open solver can touch more then one order per side, can we just exclude the offending orders and try to solve again?

Yes that is always possible. It would be a bit inefficient though since we would have to remove one at a time, interleaving with solving, until everything fits. Unless we come up with a good heuristic to remove these orders at preprocessing.

For right now, I also can not come up with a better solution. Probably, we should go this way for the open-solver, although it is very inefficient.

But most likely the standard solver would also run into the same problem?

We should also think about deploying the bracket-strategy without this huge magic numbers.

[bh2smith]

Just in case anyone would like more information regarding the offending order:

{
    "accountID": "0xdeaddd02b449bc6b3b253ccb08da83ca5c443326",
    "sellToken": "T0007",
    "buyToken": "T0000",
    "sellAmount": "257116982223191571130725490665975709695",
    "buyAmount": "340282366920938463463374607431768211455",
    "orderID": 2,
    "execSellAmount": "65820725211753",
    "execBuyAmount": "181909061768397"
},

with balances

"0xdeaddd02b449bc6b3b253ccb08da83ca5c443326": {
    "T0000": "181909061768436",
    "T0007": "369571105569092197786"
},

Since up until now we have been missing the sellToken, accountId and orderId.

It is probably also worth pointing out here that this offending order is not "selling" OWL, but "buying" it. Something that has not yet been made clear in our discussions.

Also, although I don't suspect it is immediately relevant to the overflow, it might be worth mentioning that this trader was about to trade with themselves;

{
    "accountID": "0xdeaddd02b449bc6b3b253ccb08da83ca5c443326",
    "sellToken": "T0000",
    "buyToken": "T0007",
    "sellAmount": "340282366920938463463374607431768211455",
    "buyAmount": "114166553649801920510883669194393518079",
    "orderID": 1,
    "execSellAmount": "1023431320066105399961",
    "execBuyAmount": "369571105569092197785"
},

[bh2smith]

Some other observations made about the "geometry" of this trade was that the trade occurred between two tokens (token0 and token7 - OWL and DAI). We see that 16 trades were matched (14 selling DAI and 2 selling OWL). Furthermore, every single order matched in this solution was of "unlimited" type.

[marcovc]

Trying to reply to:

Why wasn’t the OWL order matched at its limit price?

Attached is the chart corresponding to the market where the overflow occurred.

multiplication_overflow.pdf

The green dashed lines are the limit prices of the 14 orders buying fee with non zero account balance. These orders, sorted by execution order are:

 order.sellAmount / order.buyAmount             order.sellAmount
----------------------------------------------------------------------------------
0.974845012937283	80790401783153
0.9503227992486911	80790401783153
0.926417441528185	80790401783153
0.9031134227718678	80790401783153
0.880395616305875	80790401783153
0.8582492759676278	80790401783153
0.8366600265340756	80790401783153
0.8156138543907182	80790401783153
0.7950970984353467	65820699440551
0.7750964412106015	65820724968719
0.7555989002595905	65820725211754
0.7365918196989572	94796341543530881811
0.7180628620039264	282173699143880591120
0.7	282173699143880519858

The orange dashed lines are the limit prices of the 11 orders selling fee with non zero account balance. These orders, sorted by execution order are:

order.buyAmount / order.sellAmount              order.sellAmount
----------------------------------------------------------------------------------
0.3355053471704794	1023431320066105400000
0.3611098256649219	1023431320066105400000
0.3886683395406223	66111358443395530000
0.73834	199299507028286
0.7383500000000011	2
0.7498	322322154097275
0.749999	61004200917281908698
0.75	8786702349374525822969
0.75075	45000104297288971368
0.8	10000000016395
0.85	336147265512751679002

I think I'm likely missing the point, because everything seems normal to me: The first two orders selling fee are two very large market orders, and they make the price (the value of the objective function is optimal there).

[fleupold]

I think it's really important to see the volumes that we left untouched as well.

The first two orders selling fee are two very large market orders, and they make the price

In that case I would have expected all orders buying the fee to be executed completely. However, we apparently left an order with >300$ remaining to be traded (the "high" remainingSellBalance caused the overflow). If the first two orders selling fee are smaller than that 300$ order I would instead expect the 300$ order to be making the price.

[marcovc]

This is fraction filled of every order buying fee, sorted by execution order:

0.9999999999999877
0.9999999999999877
0.9999999999999877
0.9999999999999877
0.9999999999999877
0.9999999999999877
0.9999999999999877
0.9999999999999877
0.9999999999999848
0.9999999999999848
0.9999999999999848
1.0
1.0
1.0
0.0
0.0

Note that is fraction is the executed sell amount over the max_sell_amount after capping by balance (i.e. the effective max sell amount).

The fact that sometimes it is not 1 exactly is because of rounding errors.

---- [EDITED] ---

The two less-priority orders buying fee were indeed not executed. Investigating.

[marcovc]

Clarifying, after taking the balance into account there are 16 orders buying fee with max_sell_amount > 10000 being considered. However, there are 2 whose limit price is below the 0.3355053471704794, which is the minimum price to be matched by any sell order. That is why you only see 14 green dashed vertical lines in the graph. All those 14 buy orders are fully filled.

[fleupold]

I see. So a major factor in this example is also that we are trading against ourselves. This makes it that despite our order being completely filled, we end up with remaining balance coming from the proceeds of trading on the other side at the same time.

To clarify, the solver thinks we have exhausted the orders to 100% and there is no more balance left. In the smart contract however we evaluate disregarded utility based on the final balance after settling all trades.
And since we also bought some of the sell token (trading with ourselves) remaining balance at that point is "relatively large".

My claim is that since the order size was unlimited, they could have theoretically been executed with much larger buy/sell amounts (leading to temporarily negative balances before the reverse trade is applied in the same batch). The executed amount should only be capped by the amount of fee we have to pay (bringing our balance to 0).

Is that correct? Is the punishing self-trade behaviour something that could be implemented?

[bh2smith]

Maybe here is a good place to include some of my construction attempts and failures:

Recall, we are trying to construct an example of a touched, unlimited order between two non-fee tokens that is fractionally filled by a very small percentage of the available balance.

I am beginning to think that we cannot make this happen between non-fee tokens. At least not with "market orders". This is because when a market order is filled, it is often filled completely. I suspect that the reason this can happen with the fee token is that it is a one-sided order in the sense that nobody needs to buy the OWL. Unfortunately the previous assumption does not fall in line with the example we have above since the offending order was actually buying OWL.

Conjecture: There are no optimal solutions containing two touched, unlimited order between two non-fee tokens that is fractionally filled by a very small percentage of the available balance.

I am not sure that I have proven this yet, but I below is a sketch proof that neither of the two orders can be "market orders" (i.e. willing to sell for whatever price). Essentially, I would say, if they are willing to sell at whatever price, then there is no reason they would be partially filled.

Fact; When there exist overlapping market orders, both orders should/could/would be fully executed and it does not matter at which price (within the overlapping price interval). Thus, overlapping market orders between non-fee tokens would/should/could not cause this overflow.

Assume now that there is an unlimited market order selling DAI for ETH with a “large” balance. The owner of the ETH has an
(i) unlimited or
(ii) limited

order selling a

(a) small or
(b) large

balance at a fixed appropriate limit price (since we have already considered market orders)

Note first, that large balance here is relative to the DAI owner’s balance (i.e. a balance of ETH that exceeds the DAI balance of the other trader according to the ETH seller’s valuation of their ETH) while small balance is the opposite of this (e.g. ETH owner has 1 ETH and DAI owner has 100K DAI at a valuation of 1 ETH = 100 DAI)

In both cases (b-i) and (b-ii) it would be feasible (optimal?) sell the entire small balance of ETH for all the DAI. This is undesired for other reasons, but shouldn’t overflow because dU vanishes on both orders.

In both (a-i) and (a-ii), if the relative ETH balance is much larger than that of DAI, then the price will be forced to the limit price specified by the seller of ETH and the market order selling DAI will be liquidated entirely and we are again in a scenario where dU vanishes (for different reasons) on both filled orders ETH gets their limit price and DAI sells their entire inventory.

[marcovc]

So a major factor in this example is also that we are trading against ourselves. This makes it that despite our order being completely filled, we end up with remaining balance coming from the proceeds of trading on the other side at the same time.

That makes sense.

The standard solver used to correctly handle this case. It was disabled at some point to solve some other problems that may happen when you can use balance that you don't have initially (@twalth3r should know). Currently it caps the max sell amounts to the initial balances, which is a very efficient way of satisfying the account balance constraint. This is what is done in the open solver as well.

[marcovc]

Conjecture: There are no optimal solutions containing two touched, unlimited order between two non-fee tokens that is fractionally filled by a very small percentage of the available balance.

I am not sure than when you say "balance" you are making the distinction between "max sell amount" and "account balance". Something I'm convinced of is that, there is no optimal solution for the token pair matching problem where there is more than one order that is partially filled.

[fleupold]

Something I'm convinced of is that, there is no optimal solution for the token pair matching problem where there is more than one order that is partially filled.

But this single partially filled order does not necessarily have to be matched close to its limit price? As in the price that at which it is matched could be significantly better than requested?
In that case it could have significant disregarded utility (since it would have both remaining balance and a significant surplus)

[bh2smith]

Something that was mentioned above but maybe not interpreted from the same angle is this fact that the offending order traded with themselves. This actually implies that the disregarded utility was calculated "incorrectly" for this account because of the fact that the contract adds all the balances of tokens obtained in the trade before subtracting. Since the disregarded utility is computed after the fact, the adjusted balances have both already been accounted for, so the individual disregarded utility for the trade itself is incorrect (i.e. using a different balance than it should). Of course it has no other way to know this. Furthermore, this would also go undetected by the solvers (in their current state) because they would not be computing dU with these balances.

I believe we have now started to isolate the exact scenario in which this overflow is expected to occur.

[marcovc]

But this single partially filled order does not necessarily have to be matched close to its limit price? As in the price that at which it is matched could be significantly better than requested?
In that case it could have significant disregarded utility (since it would have both remaining balance and a significant surplus)

The partial-filled order doesn't have to be matchd at its limit price. Here's an example with 1 order and 1 counter-order:

order1: {sellAmount: 4, buyAmount: 2 }
order2: {sellAmount: 2, buyAmount: 1 }

These orders get matched at:

order1: {execSellAmount: 3.17, execBuyAmount: 2 }
order2: {execSellAmount: 2, execBuyAmount: 3.17 }

The optimal exchange rate is more or less in the middle of both limit prices.

[marcovc]

because of the fact that the contract adds all the balances of tokens obtained in the trade before subtracting.

That's a good point. If I understood it correctly, the solvers are doing something similar: the du used in the objective function is computed using the initial token balance, and not the final (I believe that would be possible to do in the standard solver, but not sure how it would impact efficiency). Additionally, as said above, the solvers are also capping the max sell amounts to that initial token balance, which may also have an impact in this issue.

[twalth3r]

Additionally, as said above, the solvers are also capping the max sell amounts to that initial token balance, which may also have an impact in this issue.

One reason for this is that we can't have these huge numbers coming from the standing orders in the model for numerical reasons, so we have to cap sell amounts somewhere. We decided to cap them at the available balance, because otherwise it might screw people that accidentally trade with themselves into paying a lot of fees. On the downside, this prevents uncovered orders entirely.

[fleupold]

Here's an example with 1 order and 1 counter-order:
order1: {sellAmount: 4, buyAmount: 2 }
order2: {sellAmount: 2, buyAmount: 1 }
These orders get matched at:
order1: {execSellAmount: 3.17, execBuyAmount: 2 }
order2: {execSellAmount: 2, execBuyAmount: 3.17 }
The optimal exchange rate is more or less in the middle of both limit prices.

@marcovc I would have expected the following settlement:

order1: {execSellAmount: 4, execBuyAmount: 2 }
order2: {execSellAmount: 2, execBuyAmount: 4 }

Considering

u = (execBuyAmount - (execSellAmount * buyAmount / sellAmount)) * price_buy

In the solution you described I compute
u1 = (2 - (3.17 * 2 / 4)) * 2 ≈ 0.83
u2 = (3.17 - (2 * 1 / 2)) * 3.17 ≈ 6.8789

And some dU (left out here)

In the solution I expected I compute
u1 = 0
u2 = (4 - (2 * 1 / 2)) * 4 = 8

thus more than in the first solution. I'm probably messing up the prices somehow. Do you happen to have this computation in code somewhere?

[marcovc]

Lets call token1 the token bought by order1, and token2 the token bought by order2. Also lets consider that

xrate = p(token1)/p(token2) = execSellAmount(order1)/execSellAmount(order2)

For the solution I describe we have xrate ~ 1.58.

It seems above you assume that p(token1)=2 (which is fine, it can be whatever), and therefore p(token2) = 2/xrate = 1.26.

Therefore:
u1 = (2 - (3.17 * 2 / 4)) * 2 ≈ 0.83 (as you computed)
u2 = (3.17 - (2 * 1 / 2)) * 1.26 ~ 2.72 (different value)

In the solution you suggested we have xrate = 2, and therefore p(token2) = 1:
u1 = 0
u2 = (4 - (2 * 1 / 2)) * 1 = 3

I haven't checked what the disregarded utility would be, but perhaps this explains it?

You can use the code in this repo (although I believe we better try to sort this out independently since the code reflects my, possibly flawed, reasoning):

$ python -m src.match data/token_pair-1-1-1.json --logging=DEBUG token-pair token0 token1
DEBUG  ::solver     : === Order matching on token pair + fee token ===
DEBUG  ::solver     : b_buy_token       :       token0
DEBUG  ::solver     : s_buy_token       :       token1
DEBUG  ::solver     : fee_token         :       token0
DEBUG  ::solver     : 
DEBUG  ::solver     : === Solving token0 -- token1 (rational arithmetic) ===
DEBUG  ::xrate      : Exchange rate candidates for trivial solution:
DEBUG  ::xrate      :   roots[2] : (5.005e-01, -2.992e+17)
DEBUG  ::xrate      :   roots[1] : (1.998e+00, 1.497e+17)       [local optimum]
DEBUG  ::xrate      : Exchange rate candidates in interval xrate ∈ [5.005e-01, 1.998e+00]:
DEBUG  ::xrate      :   roots[4] : (1.581e+00, 1.671e+17)       [local optimum]
DEBUG  ::xrate      : Exchange rate candidates in interval xrate ∈ [5.005e-01, 1.998e+00]:
DEBUG  ::xrate      :   roots[4] : (1.581e+00, 1.671e+17)       [local optimum]
DEBUG  ::solver     : p(token0) / p(token1) = 1.581e+00 (precise arithmetic)
DEBUG  ::solver     : Adjusted xrate    :       1.581e+00

The relevant part are the lines starting with roots[i]. They have the following format:

roots[i]: (xrate, objective value at that xrate)

You can see that root 1, which corresponds to your suggestion, has lower objective value than the winning root (root 4).

Also when you're looking at the output above take into consideration that it also factors in the fees, both in the constraints and in the objective function.

[fleupold]

Thanks, that cleared things up for me. The dU of o2 is only ~0.23 and so the overall objective value in my proposed solution is less than in the one you found. This is a nice example of how our objective function does not favour a Walrasian Equilibrium even if we considered dU of all orders (I'm not sure if we already had an example for this cc @koeppelmann)

[marcovc]

Closing as this is a bug of the smart contract.