search

econia-labs / econia

Hyper-parallelized on-chain order book for the Aptos blockchain
https://econia.dev
Other
134 stars 46 forks source link

Add asset agnosticism #13

Closed alnoki closed 2 years ago

alnoki commented 2 years ago

Motivations

Presently, Econia supports spot trading for assets of type aptos_framework::coin::Coin, but this approach is insufficient for certain applications, for example perpetual futures and other contract exchanges. In the interest of abstraction and modularity, an asset-agnostic approach is proposed, whereby Econia's bookkeeping functionality is only optionally combined with collateral management.

Data structures

/// Information about a trading pair
struct TradingPairInfo has copy, drop, store {
    /// Base asset type
    base_type: type_info::TypeInfo,
    /// Quote asset type
    quote_type: type_info::TypeInfo,
    /// Number of base units exchanged per lot
    lot_size: u64,
    /// Number of quote units exchanged per lot
    tick_size: u64,
    /// `true` if base asset is `aptos_framework::coin::Coin` type
    base_is_coin: bool,
    /// `true` if quote asset is `aptos_framework::coin::Coin` type
    quote_is_coin: bool,
    /// ID of custodian capability required to withdraw/deposit
    /// collateral in the case of an agnostic order book
    custodian_id: u64,
}

/// Unique identifier for a market
struct MarketInfo has copy, drop, store {
    /// Trading pair parameters
    trading_pair_info: TradingPairInfo,
    /// Account hosting corresponding `OrderBook`
    host: address,
}

/// Container for core tracking information
struct Registry has key {
    /// Map from trading pair to order book host address
    hosts: table::Table<TradingPairInfo, address>,
    /// List of all available markets
    markets: vector<MarketInfo>,
    /// Number of custodians who have registered
    n_custodians: u64
}

/// An order book for the given market
struct OrderBook<phantom BaseType, phantom QuoteType> has key {
    /// Number of base units exchanged per lot
    lot_size: u64,
    /// Number of quote units exchanged per lot
    tick_size: u64,
    /// Asks tree
    asks: CritBitTree<Order>,
    /// Bids tree
    bids: CritBitTree<Order>,
    /// Order ID of minimum ask, per price-time priority. The ask
    /// side "spread maker".
    min_ask: u128,
    /// Order ID of maximum bid, per price-time priority. The bid
    /// side "spread maker".
    max_bid: u128,
    /// Strictly increasing counter for number of limit orders placed on
    /// book
    counter: u64
    /// `true` if base asset is `aptos_framework::coin::Coin` type
    base_is_coin: bool,
    /// `true` if quote asset is `aptos_framework::coin::Coin` type
    quote_is_coin: bool,
    /// ID of custodian capability required to withdraw/deposit
    /// collateral in the case of an agnostic order book
    custodian_id: u64,
}

Here, a custodian capability is required for collateral withdraw/deposit on an asset agnostic order book (one having either base_is_coin or quote_is_coin set to false), because the corresponding custodian is required to validate that withdraws and deposits are accounted for as the correct size. This is in contrast to an order book where both assets are Coin types, because the underlying Coin.value field can be used to verify withdraw and deposit sizes.

When either base_is_coin or quote_is_coin is true, then a corresponding collateral container (Collateral<CoinType>) will be set up and managed per the current implementation. Otherwise collateral will be ignored for the given MarketAccount

Considerations

Market registration will require verifying that base_is_coin and quote_is_coin are accounted for correctly. In the case of an agnostic order book, the custodian_id field of an Order will become irrelevant - this could potentially be used as a general level metadata field. Pending future suggestions, asset-agnostic order books trades can be placed by users, but collateral management will only be available to the designated custodian for the given order book, who can validate deposit and withdraw amounts. Pending the implementation of a fee model, it may be necessary to enforce that the quote_is_coin is always true.

alnoki commented 2 years ago

Simplifications

OrderBook does not need to include custodian_id as no collateral transfer happens book-side

alnoki commented 2 years ago

Integration support

In the case of asset-agnostic markets, the above implementation still requires that calling functions submit unique type arguments for each asset-agnostic market. But this approach requires integrators to declare unique types for each asset-agnostic market they wish to trade on, which is unfeasible. Instead, generic agnostic type flags are proposed as follows, for the following registry.move data structures:


/// When both base and quote assets are coins
const PURE_COIN_PAIR: u64 = 0;

/// Type flag for generic asset
struct GenericAsset{}

/// Unique identifier for a market
struct MarketInfo has copy, drop, store {
    /// Account hosting corresponding `OrderBook`
    host: address,
    /// Trading pair parameters
    trading_pair_info: TradingPairInfo
    /// Serial ID for the corresponding market
    market_id: u64
}

/// Container for core registration information
struct Registry has key {
    /// Map from trading pair to order book host address
    hosts: table::Table<TradingPairInfo, address>,
    /// List of all available markets
    markets: vector<MarketInfo>,
    /// Number of registered custodians
    n_custodians: u64,
    /// Number of registered markets
    n_markets: u64,
}

/// Information about a trading pair
struct TradingPairInfo has copy, drop, store {
    /// Base asset type info. When trading an
    /// `aptos_framework::coin::Coin`, corresponds to the phantom
    /// `CoinType`, for instance `MyCoin` rather than
    /// `Coin<MyCoin>`. Corresponds to `GenericAsset` otherwise.
    base_type_info: type_info::TypeInfo,
    /// Quote asset type info. When trading an
    /// `aptos_framework::coin::Coin`, corresponds to the phantom
    /// `CoinType`, for instance `MyCoin` rather than
    /// `Coin<MyCoin>`. Corresponds to `GenericAsset` otheriwse.
    quote_type_info: type_info::TypeInfo,
    /// Number of base units exchanged per lot
    lot_size: u64,
    /// Number of quote units exchanged per lot
    tick_size: u64,
    /// ID of custodian capability required to withdraw/deposit
    /// collateral for an asset that is not a coin. A "market-wide"
    /// collateral transfer custodian ID, required to verify deposit
    /// and withdraw amounts for asset-agnostic markets. Marked as
    /// `PURE_COIN_PAIR` when base and quote types are both coins.
    custodian_id: u64,
    /// Serial ID for a given base/quote combination in the case of
    /// a generic asset on either side. Allows third-parties to
    /// register multiple asset-agnostic order books. Marked as
    /// `PURE_COIN_PAIR` when base and quote types are both coins.
    agnostic_id: u64
}

User-side

Here, a user's MarketAccount need only store the corresponding market_id:

/// Unique ID describing a market and a user-specific custodian
struct MarketAccountInfo has copy, drop, store {
    /// Serial ID of the market that a user is trading on
    market_id: u64,
    /// Serial ID of registered account custodian, set to 0 when
    /// given account does not have an authorized custodian
    user_level_custodian_id: u64
    /// ID of custodian capability required to withdraw/deposit
    /// collateral for an asset that is not a coin. A "market-wide"
    /// collateral transfer custodian ID, required to verify deposit
    /// and withdraw amounts for asset-agnostic markets. Marked as
    /// `PURE_COIN_PAIR` when base and quote types are both coins.
    market_level_custodian_id: u64
}

/// Market account map for all of a user's `MarketAccount`s
struct MarketAccounts has key {
    /// Map from `MarketAccountInfo` to `MarketAccount`. Separated
    /// into different table entries to reduce transaction
    /// collisions across markets
    map: open_table::OpenTable<MarketAccountInfo, MarketAccount>
}

/// Represents a user's open orders and available assets for a given
///`MarketAccountInfo`
struct MarketAccount has store {
    /// Base asset type info. When trading an
    /// `aptos_framework::coin::Coin`, corresponds to the phantom
    /// `CoinType`, for instance `MyCoin` rather than
    /// `Coin<MyCoin>`. Corresponds to `GenericAsset` otherwise.
    base_type_info: type_info::TypeInfo,
    /// Quote asset type info. When trading an
    /// `aptos_framework::coin::Coin`, corresponds to the phantom
    /// `CoinType`, for instance `MyCoin` rather than
    /// `Coin<MyCoin>`. Corresponds to `GenericAsset` otheriwse.
    quote_type_info: type_info::TypeInfo,
    /// Map from order ID to size of outstanding order, measured in
    /// lots lefts to fill
    asks: CritBitTree<u64>,
    /// Map from order ID to size of outstanding order, measured in
    /// lots lefts to fill
    bids: CritBitTree<u64>,
    /// Total base asset units held as collateral
    base_total: u64,
    /// Base asset units available for withdraw
    base_available: u64,
    /// Total quote asset units held as collateral
    quote_total: u64,
    /// Quote asset units available for withdraw
    quote_available: u64
}

Base types, quote types, and market-level custodian IDs are included as a parallelism optimization - such that user-side operations do not conflict with market-wide registration operations.

alnoki commented 2 years ago

Book side

On the book side, type arguments can then be eliminated per a map approach, whereby a host stores multiple order books, indexed by market ID:

/// An order book for the given market
struct OrderBook has store {
    /// Base asset type info. When trading an
    /// `aptos_framework::coin::Coin`, corresponds to the phantom
    /// `CoinType`, for instance `MyCoin` rather than
    /// `Coin<MyCoin>`. Corresponds to `GenericAsset` otherwise.
    base_type_info: type_info::TypeInfo,
    /// Quote asset type info. When trading an
    /// `aptos_framework::coin::Coin`, corresponds to the phantom
    /// `CoinType`, for instance `MyCoin` rather than
    /// `Coin<MyCoin>`. Corresponds to `GenericAsset` otheriwse.
    quote_type_info: type_info::TypeInfo,
    /// Number of base units exchanged per lot
    lot_size: u64,
    /// Number of quote units exchanged per lot
    tick_size: u64,
    /// Asks tree
    asks: CritBitTree<Order>,
    /// Bids tree
    bids: CritBitTree<Order>,
    /// Order ID of minimum ask, per price-time priority. The ask
    /// side "spread maker".
    min_ask: u128,
    /// Order ID of maximum bid, per price-time priority. The bid
    /// side "spread maker".
    max_bid: u128,
    /// Number of limit orders placed on book
    counter: u64
}

/// Order book map for all of a host's `OrderBook`s
struct OrderBooks has key {
    /// Map from market ID to the corresponding order book
    map: open_table::OpenTable<u64, OrderBook>
}

Here, lot size and tick side are included as lookup optimizations for internal integer arithmetic, and base/quote types are included to reduce queries on the registry when filling swaps directly against the book