Consider `u128` price representation

[alnoki]

Currently lot size and tick size are implemented to ensure appropriate pricing on a trade. However, these can be eliminated with the right price representation.

The problem is somewhat related to granularity and can be summarized via three scenarios that must be representable in the same format:

1. Represent a price of 1 A traded for HI_64 of B
2. Represent a price of 1 B traded for HI_64 of A
3. Represent a price of 1 A traded for 1 B

The format may include a u128 price representation, where scenario 1 corresponds to only bit 127 set, scenario 2 corresponds to only bit 0 set, and scenario 3 corresponds to only bit 63 set

Also related is that the fee associated with a fill may have to truncate unless it is enforced that, for example, one basis point is always an integer number of indivisible subunits

[alnoki]

Related: #72

[elliottdehn]

This implementation of a fixed point u128 might be interesting/relevant: https://docs.rs/fixed/latest/fixed/struct.FixedU128.html

[elliottdehn]

I figured out how to do this without truncation issues (well, minimal such) and not much code. We need to be able to do two things with our magical number representation:

• Compare it with itself so as to order it in say, a binary search tree.
• Multiply a u64 integer by it to scale that integer by the fraction.

We can do this with a structure that stores a numerator (u64) and denominator (u64). We are able to compare them easily using Least Common Denominator algorithm. This allows us to totally order by them such as in a tree.

Scaling an integer is also straightforward, we multiply the integer by the numerator (expanding to a u128) then divide the result by the denominator. This is where we get our truncation which I think is fine. The user loses at most 1 base subunit.

[alnoki]

Sample module:

module econia::price {

    #[test_only]
    use std::debug;

    /// Maximum possible price, where 1 base equals `HI_64` quote.
    /// Python: hex(int('1' * 64, 2) ** 2)
    const MAX_PRICE: u128 = 0xfffffffffffffffe0000000000000001;
    /// Price where 1 base equals one quote.
    /// Python: hex(int('1' * 64, 2))
    const UNITY: u128 = 0xffffffffffffffff;
    /// Max possible `u64`, where all bits are set.
    /// Python: hex(int('1' * 64, 2))
    const HI_64: u64 = 0xffffffffffffffff;

    const E_QUOTE_OVERFLOW: u64 = 0;
    const E_PRICE_TOO_LARGE: u64 = 1;
    const E_DIVIDE_BY_ZERO: u64 = 2;
    const E_BASE_OVERFLOW: u64 = 0;

    /// Condition 1: {base = HI_64, price = 1} returns 1
    /// HI_64 * 1 / UNITY = 1 ->
    /// UNITY = HI_64
    ///
    /// Condition 2: 1 {base = 1, price = MAX_PRICE} returns HI_64
    /// 1 * MAX_PRICE / UNITY = HI_64 ->
    /// MAX_PRICE = UNITY * HI_64 ->
    /// MAX_PRICE = HI_64 * HI_64
    public fun base_to_quote(base: u64, price: u128): u64 {
        assert!(price <= MAX_PRICE, E_PRICE_TOO_LARGE);
        let quote = ((base as u256) * (price as u256)) / (UNITY as u256);
        assert!(quote <= (HI_64 as u256), E_QUOTE_OVERFLOW);
        (quote as u64)
    }

    public fun price(base: u64, quote: u64): u128 {
        assert!(base != 0, E_DIVIDE_BY_ZERO);
        ((quote as u256) * (UNITY as u256) / (base as u256) as u128)
    }

    public fun quote_to_base(quote: u64, price: u128): u64 {
        assert!(price <= MAX_PRICE, E_PRICE_TOO_LARGE);
        let base = (quote as u256) * (UNITY as u256) / (price as u256);
        assert!(base <= (HI_64 as u256), E_BASE_OVERFLOW);
        (base as u64)
    }

    #[test]
    fun test_price_assorted() {
        assert!(base_to_quote(HI_64, 1) == 1, 0);
        assert!(base_to_quote(1, UNITY) == 1, 0);
        assert!(base_to_quote(HI_64, UNITY) == HI_64, 0);
        assert!(base_to_quote(100, UNITY) == 100, 0);
        assert!(base_to_quote(1, MAX_PRICE) == HI_64, 0);
        assert!(price(1, 1) == UNITY, 0);
        assert!(price(HI_64, HI_64) == UNITY, 0);
        assert!(price(1, HI_64) == MAX_PRICE, 0);
        assert!(price(HI_64, 1) == 1, 0);
        assert!(quote_to_base(1, 1) == HI_64, 0);
        assert!(quote_to_base(1, UNITY) == 1, 0);
        assert!(quote_to_base(HI_64, UNITY) == HI_64, 0);
        assert!(quote_to_base(100, UNITY) == 100, 0);
        assert!(quote_to_base(HI_64, MAX_PRICE) == 1, 0);
        debug::print(&price(1, 3));
        debug::print(&base_to_quote(1, price(1, 3)));
        debug::print(&base_to_quote(1000000000, price(1000000000, 3)));
        debug::print(&base_to_quote(1000000000, price(1000000000, 300)));
    }
}

Note that per @elliottdehn's prediction this introduces truncation issues (see the print statements at the end of the test), which appear limited to one subunit:

BUILDING Econia
Running Move unit tests
[debug] 55340232221128654845
[debug] 3
[debug] 2
[debug] 299

[alnoki]

Some issues:

• If someone calculates price for an expected base/quote trade amount (e.g. a view function return of price() in the above implementation, they may sell 1000000000 base and expect 300 quote but only get 299 (or analogously 299999999 etc.)
• Truncation can compound across multiple fills, meaning that the total trade volume is non-deterministic: e.g. 6 fills each of 49 quote, versus one fill of 299 (if someone places a limit order that crosses the spread then their trade volume can't be predicted based only on order inputs)

[alnoki]

Note also that the above reference implementation is based on powers of two, e.g. max price mapping 1 to HI_64, although an implementation based on powers of 10 could be more intuitive. Here, UNITY still maps 1-to-1, but base_to_quote(base = 1, price = MAX_PRICE) = n where n is the highest power of 10 less than HI_64. Similarly, base_to_quote(n, price = 1) = 1. This could reduce truncation errors for common trading situations, but not eliminate them entirely

As far as implementation details go, this essentially involves having UNITY set to the power of 10 n mentioned above

[alnoki]

Base-10 implementation (essentially decimalized price per #72:

module econia::price {

    #[test_only]
    use std::debug;

    /// Largest power of 10 that can fit in a `u64`.
    /// Python: hex(10 ** (int(math.log10(int('1' * 64, 2)))))
    const MAX_ASSET_AMOUNT: u64 = 0x8ac7230489e80000;
    /// Maximum possible price, 1 base equals `MAX_ASSET_AMOUNT` quote.
    /// Python: hex((10 ** (int(math.log10(int('1' * 64, 2))))) ** 2)
    const MAX_PRICE: u128 = 0x4b3b4ca85a86c47a098a224000000000;
    /// Price where 1 base equals one quote. Equals `MAX_ASSET_AMOUNT`.
    const UNITY: u128 = 0x8ac7230489e80000;

    const E_QUOTE_OVERFLOW: u64 = 0;
    const E_PRICE_TOO_LARGE: u64 = 1;
    const E_DIVIDE_BY_ZERO: u64 = 2;
    const E_BASE_OVERFLOW: u64 = 0;

    #[view]
    /// {base = 1, price = UNITY} returns 1
    /// 1 * UNITY / divisor = 1 ->
    /// UNITY = divisor
    ///
    /// {base = MAX_ASSET_AMOUNT, price = 1} returns 1
    /// MAX_ASSET_AMOUNT * 1 / UNITY = 1 ->
    /// UNITY = MAX_ASSET_AMOUNT
    ///
    /// {base = 1, price = MAX_PRICE} returns MAX_ASSET_AMOUNT
    /// 1 * MAX_PRICE / UNITY = MAX_ASSET_AMOUNT ->
    /// MAX_PRICE = UNITY * MAX_ASSET_AMOUNT ->
    /// MAX_PRICE = MAX_ASSET_AMOUNT * MAX_ASSET_AMOUNT
    public fun base_to_quote(base: u64, price: u128): u64 {
        assert!(base <= MAX_ASSET_AMOUNT, E_BASE_OVERFLOW);
        assert!(price <= MAX_PRICE, E_PRICE_TOO_LARGE);
        let quote = ((base as u256) * (price as u256)) / (UNITY as u256);
        assert!(quote <= (MAX_ASSET_AMOUNT as u256), E_QUOTE_OVERFLOW);
        (quote as u64)
    }

    #[view]
    public fun price(base: u64, quote: u64): u128 {
        assert!(base <= MAX_ASSET_AMOUNT, E_BASE_OVERFLOW);
        assert!(quote <= MAX_ASSET_AMOUNT, E_QUOTE_OVERFLOW);
        assert!(base != 0, E_DIVIDE_BY_ZERO);
        ((quote as u256) * (UNITY as u256) / (base as u256) as u128)
    }

    #[view]
    public fun quote_to_base(quote: u64, price: u128): u64 {
        assert!(quote <= MAX_ASSET_AMOUNT, E_QUOTE_OVERFLOW);
        assert!(price <= MAX_PRICE, E_PRICE_TOO_LARGE);
        let base = (quote as u256) * (UNITY as u256) / (price as u256);
        assert!(base <= (MAX_ASSET_AMOUNT as u256), E_BASE_OVERFLOW);
        (base as u64)
    }

    #[view]
    public fun base_to_quote_will_truncate(base: u64, price: u128): bool {
        assert!(base <= MAX_ASSET_AMOUNT, E_BASE_OVERFLOW);
        assert!(price <= MAX_PRICE, E_PRICE_TOO_LARGE);
        let numerator = (base as u256) * (price as u256);
        numerator % (UNITY as u256) > 0
    }

    #[view]
    public fun price_will_truncate(base: u64, quote: u64): bool {
        assert!(base <= MAX_ASSET_AMOUNT, E_BASE_OVERFLOW);
        assert!(quote <= MAX_ASSET_AMOUNT, E_QUOTE_OVERFLOW);
        assert!(base != 0, E_DIVIDE_BY_ZERO);
        let numerator = (quote as u256) * (UNITY as u256);
        numerator % (base as u256) > 0
    }

    #[view]
    public fun quote_to_base_will_truncate(quote: u64, price: u128): bool {
        assert!(quote <= MAX_ASSET_AMOUNT, E_QUOTE_OVERFLOW);
        assert!(price <= MAX_PRICE, E_PRICE_TOO_LARGE);
        let numerator = (quote as u256) * (UNITY as u256);
        numerator % (price as u256) > 0
    }

    #[test]
    fun test_price_assorted() {
        assert!(base_to_quote(MAX_ASSET_AMOUNT, 1) == 1, 0);
        assert!(base_to_quote(1, UNITY) == 1, 0);
        assert!(base_to_quote(MAX_ASSET_AMOUNT, UNITY) == MAX_ASSET_AMOUNT, 0);
        assert!(base_to_quote(100, UNITY) == 100, 0);
        assert!(base_to_quote(1, MAX_PRICE) == MAX_ASSET_AMOUNT, 0);
        assert!(price(1, 1) == UNITY, 0);
        assert!(price(MAX_ASSET_AMOUNT, MAX_ASSET_AMOUNT) == UNITY, 0);
        assert!(price(1, MAX_ASSET_AMOUNT) == MAX_PRICE, 0);
        assert!(price(MAX_ASSET_AMOUNT, 1) == 1, 0);
        assert!(quote_to_base(1, 1) == MAX_ASSET_AMOUNT, 0);
        assert!(quote_to_base(1, UNITY) == 1, 0);
        assert!(quote_to_base(MAX_ASSET_AMOUNT, UNITY) == MAX_ASSET_AMOUNT, 0);
        assert!(quote_to_base(100, UNITY) == 100, 0);
        assert!(quote_to_base(MAX_ASSET_AMOUNT, MAX_PRICE) == 1, 0);
        debug::print(&price(1, 3));
        debug::print(&base_to_quote(1, price(1, 3)));
        debug::print(&base_to_quote(1000000000, price(1000000000, 3)));
        debug::print(&base_to_quote(1000000000, price(1000000000, 300)));
    }

    #[test]
    fun test_will_truncate() {
        // Less than one quote subunit.
        debug::print(&base_to_quote_will_truncate(1, 10));
        // Price can't be represented as integer.
        debug::print(&price_will_truncate(3, 10));
        // Base can't be represented as integer.
        debug::print(&quote_to_base_will_truncate(1, 3));
    }
}

Here, there is no truncation for a typical trading scenario (test_price_assorted()), and the assorted will_x_truncate() helpers can be used to predict truncation scenarios:

Running Move unit tests
[debug] 30000000000000000000
[debug] 3
[debug] 3
[debug] 300
[ PASS    ] 0x0::price::test_price_assorted
[debug] true
[debug] true
[debug] true
[ PASS    ] 0x0::price::test_will_truncate

[elliottdehn]

@alnoki would using the numerator / denominator approach I described, rather than combining them into a calculated u128, allow to eliminate the concept of max asset from this process? Still takes up u128 bits but is a bit more organized and perhaps less restrictive?

[alnoki]

@alnoki would using the numerator / denominator approach I described, rather than combining them into a calculated u128, allow to eliminate the concept of max asset from this process? Still takes up u128 bits but is a bit more organized and perhaps less restrictive?

Potentially, although I don't know if it is necessarily problematic for resolution to exclude values above max asset amount (this is the largest power of 10 that can fit in a u64, which would be at least 10% of token supply in a single trade)

I think another advantage of the simple u128 representation is that it is straightforward and readable, with minimal operations

I believe the rust example you gave above still provides total order (e.g. can sort prices in ascending/descending sequence) but I suspect it requires more arithmetic operations and still doesn't fully eliminate the truncation issue

[bogberry]

@elliottdehn the numerator / denominator approach makes zero sense here. At the end of the day, these get converted to the values in CoinStore as defined by Aptos, and thus it makes no sense to allow values that would not be valid coin balances in the orderbook

The truncation issue also makes this solution unworkable. Any solution involving truncation would only be by one unit, so I'm not why you feel this is a more acceptable form of truncation. The problem is that these compound on top of each other, & the user should get exactly what they are owed in any case

[bogberry]

We are able to compare them easily using Least Common Denominator algorithm.

Not sure what you are referring to when you say Least Common Denominator algorithm, but if you mean when comparing $\frac{a}{b}$ and $\frac{c}{d}$ multiplying both by $lcm(b, d)$ there are faster ways of doing this

In any case, we should not have to do any calculations when we compare two levels in the orderbook as this is an extremely common operation and the cumulative gas increase of implementing something like this would be quite high

[bogberry]

@alnoki there is no representation for price that would allow you to eliminate lot size and tick size, or some comparable restriction on what values a user can submit for order size and price

The problem is somewhat related to granularity

The problem is granularity. Any size value multiplied by price value must be representable as a legal balance for the quote coin, and since quote coins can have different numbers of decimals, the enforcement will differ per market

and can be summarized via three scenarios that must be representable in the same format:

1. Represent a price of 1 A traded for HI_64 of B
2. Represent a price of 1 B traded for HI_64 of A
3. Represent a price of 1 A traded for 1 B

These three scenarios are in no way exhaustive of the cases you would need to test for in order to verify that any solution here is workable

[alnoki]

@bogberry @elliottdehn

In any case, we should not have to do any calculations when we compare two levels in the orderbook as this is an extremely common operation and the cumulative gas increase of implementing something like this would be quite high

Agreed on this, anything less efficient than an int compare is problematic

eliminate lot size and tick size, or some comparable restriction on what values a user can submit for order size and price

Yes unfortunately I don't know if there is any way to get around this, although I think that we can probably do with just a min size and tick size: min size to prevent a bunch of tiny orders on the book, and tick size to prevent wasteful adversarial dynamics where someone places an order at nominal price 15.000, someone places another at 15.00000001 just to get ahead of them, etc.

As far as truncation goes I don't think we can get around the issue of allowing some kind of truncation, at least at the fee level. Because if we enforce that even fees for a fill cannot undergo truncation then it seems like we would have to enforce that the most granular possible tick will be 0.01 USDC (corresponding to 0.000001 USDC for each basis point, a single indivisible subunit of USDC)

[bogberry]

No you absolutely do need lot size. As I said above, any quote amount that results from order size multiplied by order size in base coins must be representable as a valid amount according to the number of allowed decimals allowed for the quote coin.

There is no way to enforce this with just a tick size and a minimum size.

[bogberry]

As far as truncation goes I don't think we can get around the issue of allowing some kind of truncation, at least at the fee level.

No you achieve this by having the allowed fee rate be a function of these values, where setting larger values allows for more granularity in the fee rates you can set, and smaller values mean less granularity

[alnoki]

No you achieve this by having the allowed fee rate be a function of these values, where setting larger values allows for more granularity in the fee rates you can set, and smaller values mean less granularity

I believe one implication here is that the fee rate for a market will have to be set upon registration, and thus that for each lot size/tick size/min size tuple there could be multiple markets, each with a different fee rate. Noting here that this design choice provides more opportunities to fracture liquidity and I'll note that as a trade-off

As an example I'll consider that the market is registered with a simple 3 basis point fee. To avoid truncation this means that the mimimum increment in fees for a fill will be 0.000001 USDC. Hence the minimum quote volume increment for a fill would theoretically be $0.000001 / (0.03 * 0.01) = 0.00\bar3$, but this is not an integer and so we have to take a multiple: min quote volume increment for a fill is 0.01 USDC, and min fee increment for a fill is 0.000003 USDC.

Since quote volume is size times price, this means that the minimum increment in price is 0.01 USDC, and so now a minimum size increment (lot size) has to be chosen. At current market prices, if price can only be incremented by 0.01 USDC per lot, then the smallest reasonable lot size would be 1 APT per lot: if we went smaller to a lot size of 0.1 APT, at a price increment of 0.01 USDC per lot then the result would be that 1 APT (10 lots) could only be quoted in 0.1 USDC increments (7.70, 7.80, but not 7.75).

Hence my understanding:

1. If we insist of truncation prohibition either APT can't be priced with enough granularity, or we can't fill less than an integer multiple of 1 APT at a time.
2. If we allow truncation in fees then we can price APT with enough granularity and fill less than an integer multiple of 1 APT at a time

[alnoki]

Addressed at https://github.com/econia-labs/econia-v5/blob/cb8b990/doc/architecture-specification.md#units