Do not cap flows for unlimited orders to u128::MAX

[nlordell]

Fixes #1431

This PR removes the cap on transitive order "flows" for unlimited orders. The reasoning behind this is that for price estimates and transitive orderbook computations, unlimited orders with balances >> u128::MAX would generate too many transitive orders, as they would be capped to u128::MAX instead of the user's actual balance.

While the smart contract limits trades to u128::MAX, this is not required for price estimates, as the large balance would be repeatedly reduced over multiple iterations. Now they get reduced all at once :tada:.

Test Plan

New unit test added. By returning to the old behaviour, you can verify that this test indeed does cause the issue to happen:

diff --git a/pricegraph/src/orderbook/user.rs b/pricegraph/src/orderbook/user.rs
index 5bc11af..3ce06c4 100644
--- a/pricegraph/src/orderbook/user.rs
+++ b/pricegraph/src/orderbook/user.rs
@@ -24,7 +24,7 @@ impl User {
     /// Return's the user's balance for the specified token.
     /// Panics if the user doesn't have a balance.
     pub fn balance_of(&self, token: TokenId) -> U256 {
-        self.balances.get(&token).copied().unwrap_or_default()
+        self.balances.get(&token).copied().unwrap_or_default().min(u128::MAX.into())
     }

     /// Deducts an amount from the balance for the given token. Returns the new

Benchmarks were run to determine the impact of this issue and found no significant changes in performance:

Benchmarks

``` $ cargo bench -p pricegraph-bench -- --baseline master Finished bench [optimized] target(s) in 0.08s Running /var/home/nlordell/Developer/dex-services/target/release/deps/pricegraph-4889484856ca8c99 Gnuplot not found, using plotters backend Pricegraph::read time: [6.6880 ms 6.7900 ms 6.9124 ms] change: [-0.5615% +1.2319% +2.9784%] (p = 0.18 > 0.05) No change in performance detected. Found 37 outliers among 100 measurements (37.00%) 15 (15.00%) low severe 7 (7.00%) low mild 3 (3.00%) high mild 12 (12.00%) high severe Pricegraph::transitive_orderbook/5298183 time: [6.4790 ms 6.5226 ms 6.5801 ms] change: [-1.5986% +0.0589% +1.7140%] (p = 0.95 > 0.05) No change in performance detected. Pricegraph::estimate_limit_price/100000000000000000 time: [56.845 us 56.868 us 56.894 us] change: [-16.271% -13.153% -10.152%] (p = 0.00 < 0.05) Performance has improved. Found 5 outliers among 100 measurements (5.00%) 5 (5.00%) high mild Pricegraph::estimate_limit_price/1000000000000000000 time: [57.415 us 57.487 us 57.573 us] change: [-8.3413% -6.9433% -5.7976%] (p = 0.00 < 0.05) Performance has improved. Found 15 outliers among 100 measurements (15.00%) 2 (2.00%) high mild 13 (13.00%) high severe Pricegraph::estimate_limit_price/10000000000000000000 time: [117.59 us 118.09 us 118.63 us] change: [-3.5470% -1.2446% +0.7880%] (p = 0.29 > 0.05) No change in performance detected. Found 15 outliers among 100 measurements (15.00%) 11 (11.00%) low severe 1 (1.00%) high mild 3 (3.00%) high severe Pricegraph::estimate_limit_price/100000000000000000000 time: [215.75 us 216.30 us 217.25 us] change: [-8.9916% -8.1519% -7.3956%] (p = 0.00 < 0.05) Performance has improved. Found 11 outliers among 100 measurements (11.00%) 2 (2.00%) high mild 9 (9.00%) high severe Pricegraph::estimate_limit_price/1000000000000000000000 time: [573.01 us 573.86 us 574.77 us] change: [-10.082% -7.8667% -5.6236%] (p = 0.00 < 0.05) Performance has improved. Found 2 outliers among 100 measurements (2.00%) 1 (1.00%) low mild 1 (1.00%) high mild Pricegraph::order_for_limit_price/200 time: [49.420 us 49.463 us 49.517 us] change: [-11.154% -9.7598% -8.4945%] (p = 0.00 < 0.05) Performance has improved. Found 11 outliers among 100 measurements (11.00%) 2 (2.00%) high mild 9 (9.00%) high severe Pricegraph::order_for_limit_price/190 time: [147.28 us 147.81 us 148.66 us] change: [-1.9594% -0.6766% +0.5309%] (p = 0.30 > 0.05) No change in performance detected. Found 7 outliers among 100 measurements (7.00%) 1 (1.00%) low mild 2 (2.00%) high mild 4 (4.00%) high severe Pricegraph::order_for_limit_price/180 time: [252.07 us 253.42 us 255.20 us] change: [+1.3814% +1.8331% +2.4366%] (p = 0.00 < 0.05) Performance has regressed. Found 21 outliers among 100 measurements (21.00%) 1 (1.00%) low mild 9 (9.00%) high mild 11 (11.00%) high severe Pricegraph::order_for_limit_price/150 time: [547.37 us 547.84 us 548.42 us] change: [-4.3717% -2.6473% -0.9427%] (p = 0.00 < 0.05) Change within noise threshold. Found 10 outliers among 100 measurements (10.00%) 3 (3.00%) high mild 7 (7.00%) high severe Pricegraph::order_for_limit_price/100 time: [610.88 us 611.83 us 613.14 us] change: [-1.0885% +1.0080% +3.1165%] (p = 0.35 > 0.05) No change in performance detected. Found 6 outliers among 100 measurements (6.00%) 1 (1.00%) low mild 1 (1.00%) high mild 4 (4.00%) high severe ```

[nlordell]

I wonder if this PR can be used for a new attack on the price estimator.

I don't think its specific to this PR, since the behaviour hasn't changed, just that we reduce these cases faster.

Previously, this problem would still happen, as the price estimator had no limit on "trades" it can consider for getting a price.

[nlordell]

Maybe it makes sense to cap balances to u128::MAX, with the justification that the price estimator should only give prices that would be possible in a single batch.

Hmm... Maybe we should open an issue to discuss as this is a larger problem