Implementation of Limit Order Book on Miden VM

[lzhabo]

Onchain Limit Order Book on Miden VM

Miden's Notes concept is applied to represent order entities. By utilizing Notes, each with a specific Tag corresponding to an order book, we can seamlessly organize and manage orders

Order Creation Configuration

users create orders by generating Notes specific to each asset. These Notes encapsulate various types of orders—Market, Limit, and Stop Limit, among others—through embedded parameters like PRICE, BASE_ASSET, and QUOTE_ASSET. Furthermore, we're exploring an innovative approach where a single Note might represent multiple user orders, aiming for a more consolidated and efficient order management system. This idea, while promising, requires deeper development and testing within the testnet environment to identify an optimal solution beyond the current one-order-per-Note strategy.

The description and pseudocode for the note logic, currently drafted in Rust, will be updated upon the release of Miden's Rust SDK. ⬇️

note;


//todo figure out how to validate inputs
inputs {
    MAKER: ADDRESS,
    BASE_ASSET: AssetId,
    QUOTE_ASSET: AssetId,
    PRICE: uint256,
    DIRECTION: String,
    
    PRICE_DECIMALS: u8 = 9, // optional
    MIN_FULFILL_AMOUNT0: u64 = 1, // optional
}

metadata {
    TAG: String
}

enum DIRECTION {
    BUY: (),
    SELL: ()
}

struct Arguments {
 amount: Option<uint256>,
}

fn main(arguments: Arguments){
    let caller = msg_sender();
    let payments = msg_payments();
    let (maker_payment_asset_id, taker_payment_asset_id) = if argumnts.direction == DIRECTION.SELL {
        (BASE_ASSET, QUOTE_ASSET)
    } else { 
        (QUOTE_ASSET, BASE_ASSET)
    };
    if caller == MAKER {
        //cancel order handler
        if arguments.amount.is_some() && arguments.amount.unwrap() > 0 && payments.len() == 0 {
            transfer_to_address(MAKER, maker_payment_asset_id, arguments.amount.unwrap());
        }
        //handler order expand
        if payments.get(0).is_some() && payments.get(0).unwrap() != maker_payment_asset_id {
            revert("invalid asset");
        }
    } else{
        //fulfill order handler
        check_fee(payments.get(1).unwrap());
        //todo fuigre out how to transfer fee to the matcher 

        let payment = payments.get(0).unwrap();
        if payment.asset_id == taker_payment_asset_id {
             if argumnts.direction == DIRECTION.SELL {
                //maker asset btc / taker asset usdc
                let trade_amount = min(
                    convert_quote_to_base(payment.amount), 
                    this_balance(BASE_ASSET)
                );
                transfer_to_address(MAKER, QUOTE_ASSET, convert_base_to_quote(trade_amount));
                transfer_to_address(caller, BASE_ASSET, trade_amount);
             }else{
                //maker asset usdc / taker asset btc
                let trade_amount = min(
                    payment.amount,
                    convert_quote_to_base(this_balance(maker_payment_asset_id))
                );
                transfer_to_address(MAKER, BASE_ASSET, trade_amount);
                transfer_to_address(caller, QUOTE_ASSET, convert_base_to_quote(trade_amount));
             }
        }
    }
}

fn convert_base_to_quote(base_amount: uint256) -> uint256{
    let base_asset_decimals = get_native_asset(BASE_ASSET).decimals;
    let quote_asset_decimals = get_native_asset(QUOTE_ASSET).decimals;
    base_amount * PRICE / 10.pow(base_asset_decimals + PRICE_DECIMALS - quote_asset_decimals)

}
fn convert_quote_to_base(quote_amount: uint256) -> uint256 {
    let base_asset_decimals = get_native_asset(BASE_ASSET).decimals;
    let quote_asset_decimals = get_native_asset(QUOTE_ASSET).decimals;
    quote_amount / PRICE * 10.pow(base_asset_decimals + PRICE_DECIMALS - quote_asset_decimals);
}

fn check_fee(payment: Payment){
    //todo fee check logic
}

• Limit Order: Allows users to specify the exact parameters for token exchange, defining the types of tokens desired and their quantities. Upon partial fulfillment, the original Note representing the order is consumed, and a new Note is created for the remaining amount. This ensures that the order can continue to be available for other takers until it's fully completed. The script for this operation might look like the following:

async function createLimitOrder() {
    const inputs = { 
        MAKER: midenSdk.getProvider().address,
        BASE_ASSET: assets.BTC.assetId,
        QUOTE_ASSET: assets.USDC.assetId,
        PRICE: 71000 * 1e9,
        DIRECTION: "SELL",
    }

    const payment = [
        {
            assetId: assets.BTC.assetId,
            amount: 1 * 1e8, //1btc
        },
        {
            assetId: assets.USDC.assetId,
            amount: sparkSdk.calculateFee(inputs)
        },
    ]

    const metadata = { tag: "SPARK" }
    
    const tx = midenSdk.produceNote("../path_to_stop_limit_note_code", inputs, payment, metadata)
    await midenSdk.send(tx)

}

create notes:
send(price: get.noteInputs * get.noteArgs, receiver: note.sender)  # Sends the agreed amount to the creator of the note
create_new_order(vault: 1 ETH * (1 - get.noteArgs), copy.noteInputs, ...)  # Creates a new order note with a reduced amount in the vault, copying the initial order's parameters...

• Market Order: Acts as a taker order, filling existing orders at a specific price. Market orders will be implemented as scripts that can consume various notes, possibly fulfilling orders partially or fully as needed. If the orders from the arguments are not enough to fully execute the market order, the remaining funds can be used to create a limit order or returned to the user, depending on the order settings.

async function createMarketOrder() {
    let inputs = {
        MAKER: midenSdk.getProvider().address,
        BASE_ASSET: assets.BTC.assetId,
        QUOTE_ASSET: assets.USDC.assetId,
        PRICE: 72000 * 1e9,
        DIRECTION: "BUY",
    }

    const payment = [
        {
            assetId: assets.BTC.assetId,
            amount: 36000 * 1e6, //0.5 btc
        },
        {
            assetId: assets.USDC.assetId,
            amount: sparkSdk.calculateFee(inputs)
        },
    ]

    const metadata = { tag: "SPARK" }

    const orderTx = midenSdk.produceNote("../path_to_stop_limit_note_code", inputs, payment, metadata)

    const orders = await indexerSdk.getMatchingOrdersIds(inputs, payment[0].amount);

    let matchTxs = sparkSdk.matchOrders(orders, [orderTx.noteId])

    await midenSdk.sendTogether([orderTx, ...matchTxs])
    //sparkSdk.matchOrders()
}

The taker could specify which amount he wants to consume and the note script specifies what should happen with the remaining amount. The remaining amount could be simply transferred to a copy of the original order note

• Stop Limit: Orders trigger a trade when the asset's market price drops below a specified level. The challenge lies in crafting a note script that adjusts the price for potential execution, initially encrypting inputs and later revealing them for execution. According to documentation (https://polygontechnology.notion.site/How-a-note-in-Miden-can-represent-different-orders-and-why-is-that-useful-ad094634d5a446a8a91863ce6c038136), implementing this off-chain is mentioned, yet the execution method remains unclear. It raises the question: Is an external service required to oversee price changes via an oracle, or can the entire process be managed on-chain without alterations? Ideally, leveraging only the note and node for this functionality would be optimal.

	// we are going to sell 1btc
	const inputs = { // configurables
		baseAsset: assets.BTC.assetId,
		quoteAsset: assets.USDC.assetId,
		tag: "SPARK",
		maker: provider.getAddress(),
        triggerPrice: 72000 * 1e9,
        price:  71000 * 1e9,
        direction: "SELL",
	}
	
	const payment = [
		{
			assetId: assets.BTC.assetId,
			amount: 1 * 1e8, //1btc
		},
		{
			assetId: assets.USDC.assetId,
			amount: sparkSdk.calculateFee(params)
		},
	]
        // code of note
	const note = midenSdk.buildNote("../path_to_stop_limit_note_code", inputs, params, payment)
	await midenSdk.produceNote(noteHash)

}

Order Cancellation

Mechanism: Users interact with a Note, specifying the amount and price (or ID) of the order to be canceled. The system verifies the request, ensuring it originates from the order's owner and that the cancellation does not exceed the order's total cost. Orders can be canceled in whole or in part, with remaining funds transferred to a new Note with identical parameters. But this would require on-chain transaction, maybe there is a way to define logic in script that would cancel this order by reviling the script code when time is up for instance.

aasync function cancelOrder() {
    const orderId = "<ORDER ID>"
    const order = await indexerSdk.getOrderDetails(orderId)

    const args = { amount: 0.5 * 1e8 }

    const tx = midenSdk.consumeNote(order.noteId, args)
    await midenSdk.send(tx)
}

For market makers, especially during high volatility, efficient order cancellation is crucial as it's a key component of their trading strategies.

Order Book Visualization

The order book, designed to list all Notes sharing the same Tag, will offer a comprehensive view of the market. Accessible through a SPA, it promises real-time updates and a user-friendly interface for traders. Unlike traditional models, this order book features a collection of orders represented by notes, which are not stored in smart contracts. This architecture enables any off-chain service to efficiently retrieve and match orders from the Notes database, thereby circumventing the limitations typically associated with smart contracts.

To effectively integrate TradingView charts, it's essential to implement an indexer that will supply comprehensive information about matched orders (trades).

Matching

To efficiently match orders in an order book, use a B-Tree structure to manage orders in a database can be highly effective, especially for financial applications like order books that require efficient, scalable, and rapid access to large datasets . Buy and sell orders are stored separately to streamline matching. An off-chain service, leveraging Miden's Note DB facilitating efficient order matching and execution. No need to store orders in contract because it would make orderbook slow.

Exploring three potential mechanisms for order matching:

• Direct Liquidity Provision: The matcher uses its liquidity to fulfill both sell and buy orders in one go.
• Matching account: The account acts as an intermediary, executing trades without holding actual assets. It verifies both parties' order terms, absorbing orders and ensuring fair execution with only commission considered. To maintain system trust, the engine's credibility and neutrality are ensured through oversight mechanisms and post-trade verification via zero-knowledge proofs, preventing manipulation.

Summarize design:

• There is no order book account / smart contract
• Users make, take and cancel orders using the Spark API
• Notes represent limit orders - market and stop limit orders are scripts
• Order book will list all notes sharing the same tag
• Matching is still being explored
• All information is on-chain