Potential Onchain Order Book Exchange on Miden

[Dominik1999]

Potential Onchain Order Book Exchange on Miden

I want to discuss a PoC of an on-chain order book exchange on Polygon Miden. Miden is perfectly suitable for even a private on-chain order book exchange leveraging client-side proving, high throughput, updateable transactions, and the security of Ethereum.

What is an Order Book Exchange?

Order book refers to an electronic list of buy and sell orders for a specific security or financial instrument organized by price level. There are three parts to an order book: buy orders, sell orders, and order history. An order book is dynamic and constantly updated in real-time throughout the day. A key feature of order book models is allowing users to submit two types of orders: market or limit orders. Market orders mean a trader instantly buys or sells at the best price (highest bid, lowest ask). Limit orders are not instant and buy or sell at a specific price. Next to the order book, there also must be an order matching system following some rules of best execution to have an order book exchange.

Why is an Order Book Exchange important?

In crypto markets, the dominant venue for exchange has been centralized order book-based exchanges (CEX). There is high demand for on-chain order-book exchanges; see here 40 TPS only on dYdX. Onchain exchanges are mostly AMM-based exchanges that cannot provide quite the same benefits:

Order-book exchanges …
… provide price efficiency
… reduce the risk of slippage and have no impermanent loss
… are widely accepted by both institutional and retail traders alike
… are easier to use

Which features are needed for an on-chain order book exchange?

To run an on-chain order book, several features are needed {PLEASE ADD}

Needed:

1. High TPS - builders ask for 30-40 and some even more
2. Low finality - sub-second finality would be optimal
3. Quick and cheap order updates - Order updates should be almost instantaneously and for free, especially for Market Makers

Nice to have:

4. Privacy at the base layer - to not reveal a trading strategy
5. Matching engine - FIFO/Pro-Rata should also run on-chain to ensure "best execution"
6. MEV protection - to ensure "best execution"

(Are there more required features? Do we need to cancel the order quickly?)

Why is this hard to build on Ethereum?

Order-book exchanges on account-based blockchains are hard to implement. The algorithms of matching engines, commonly implemented in centralized exchanges (CEXs) based on the CLOB model, consume a large number of resources, making it challenging to deploy and run on the Ethereum blockchain, see here. Some DEXs have attempted to solve this issue by implementing matching engines and order books off-chain - dYdX (on StarkEX) or 0x. However, such solutions increase the risk of centralization (to a certain extent) and limit their ability to interact with other protocols, making it impossible to utilize or contribute to the open ecosystem of Ethereum effectively.

Why this can be done on Miden

Polygon Miden offers the required features (1-6) while simultaneously, computational integrity is secured by Ethereum, and liquidity is provided by Ethereum and the Polygon ecosystem.

Polygon Miden is designed to have high TPS sustainably. Orders can be updated for free and in no time using updateable transactions. Polygon Miden offers different levels of privacy at the base layer. Matching engines can run off-off-chain, but there can be a zk-proof of correct execution to be verified by the network.

For finality, we need to define what we mean by that.

Design ideas for a simple PoC

Let's collect ideas for implementing a private on-chain order book exchange on Miden. So given the Miden Architecture, we can design a simple onchain order book exchange.

In our simple example,

• users shall be able to place a limit order (buy or sell)
• users shall be able to place a market order (buy or sell)
• users shall be able to take any order
• users shall be able to cancel any order
• there shall be some form of best execution
• the order book shall be visible on any web2 interface like a homepage.

Notes represent orders

In Miden, there are Accounts and Notes, see here. Notes can be updated for free and in no time; therefore, Notes can represent an order.

All Notes with the same Tag can be listed in the same order book. Notes carry the asset to sell in their Vault - this cannot be updated, and in this example, it is 1 ETH. In addition, Notes have a single executable Script. This script is the root of a Miden program MAST. Here is where we can encode our order. For example, 0x1234 can mean

receive( 1 ETH )  # what is in the vault
send( 2000 DAI, note.sender ) # send to the creator of this note

Whoever wants to take this order needs to consume the above note and, in doing so, execute the script. Like this, we can pretty easily support limit orders, where limits can be updated nearly instantaneously in one direction.

All notes with the same tag are listed in the order book

The order book could now list all notes with the same Tag.

This will serve as our order book - which can be shown in a simple web2 interface/homepage. Now any user can take any order by simply consuming the respective note in a transaction - first come, first serve.

Notes in that order book must be public. That means everyone sees all the note's data and can compute the nullifier. That means whenever there is a nullifier in the Nullifier DB, the operator of the order book interface can delete the respective note.

Limit orders can be updated for free by revealing parts of the script

A limit order is a direction to buy or sell an asset for a specific price (limit) or better. We can update those limits by revealing new parts of the note script. The note's script can be partially hidden at the beginning, and whenever a user wants to update a limit order, a new leaf can be revealed in no time.

Now the user first reveals what A is. Then, what B is, and so on.

A = {receive 1 ETH && send 2000 DAI to sender}

If no one takes that order, the user reveals another part of the script.

B = {receive 1 ETH && send 1990 DAI to sender}

Market orders are slightly more complex

A market order is an order to buy or sell an asset immediately. This type of order guarantees that the order will be executed but does not guarantee the execution price.

A naive implementation would be to create a note having a script that queries the current market price. The script could be like receive( 1 ETH ), send( current_price, note.sender ). Whereas current_price must come from an oracle but it should be easy to compute given that all notes are public. However, there might be attack vectors for nonliquid markets.

So now, users can place limit and market orders by creating new notes. Those orders can be updated by simply revealing new parts of the script. Those updates don't need to happen on-chain, but, e.g., in any public forum or directly to the operator, and are therefore for free and can happen in no time. And anybody can take orders by simply consuming the respective notes.

Order canceling

In theory, any order can be canceled if the note's producer consumes the note himself. That would require an on-chain transaction, though. There might be a cheaper way by revealing a certain part of the script that makes the note unconsumable.

Order matching

We need some mechanism to match buy and sell orders. This mechanism should ensure/aim for "best execution".

A matching engine runs a matching algorithm, which fills an order. So if there are five sell orders of "200 A, 150 A, 50A, 100A, 100A" at slightly different prices and a limit buy order of "350 A" the algorithm chooses which sell to pick to fill the buy order. Iterating over many orders onchain on a traditional EVM blockchain would be quite gas intense. On Miden, this is different.

Option 1: No matching engine

Matching engines are a must in the centralized setting. In our simple case, users could decide which order to take. There could be a pool of notes - all with the same tag - and users pick the notes they want for consumption.

This way, best execution is ensured by the user, trades are the cheapest, and the implementation is super easy. However, it might be complicated to coordinate. Two users might want to consume the same note simultaneously, and only one would succeed.

Option 2: Matching account (normal account)

In Miden, every smart contract is an account. So trades could be executed by executing functions of the matching engines account. We can have functions for limit and functions for market orders. That way, we don't need an oracle, either. Traditional matching algorithms - FiFo or Pro Rata - could be implemented in the account. This account running the matching engine would need to be credibly neutral somehow. Or it should be possible to verify post-factum that the engine was credibly neutral using a zkProof. This approach would save a lot of gas, compared to traditional EVM blockchains.

This account would need an operator that executes all transactions within a certain time frame. The operator could get a fee for its service.

Option 3: Matching account (specialized account)

We have a single account, as in Option 2 above, but anyone can execute transactions against these accounts. This would mean that block producers would play a role of a "temporary exchange operator" (for the block they produce).

This option might be the most complex for a PoC.

Privacy

Privacy is actually a core feature of Polygon Miden, and it has many layers. The actual note that represents the order in this naive design must be stored publicly and cannot be private. However, users can easily use a proxy account and execute transactions locally against it to forward private orders or iceberg orders.

Let's reiterate (more details can be found here and here): On Miden transactions can be private when executed locally. Then the operator and all other users only see a commitment of the note that was created in a transaction. This note can also be consumed locally, and no one would know that a nullifier for this note exists but the users who have the full note data.

So to make a private order, we need the following flow (I am sure this can be optimized in several ways, but it's a PoC):

• we introduce a public account / smart contract that we call Obfuscator. Anyone can execute transactions against that account.
• tx 1: is executed by the user locally. The transaction produces Note 1 (private), and one branch of the note's script is the return address, which we will explain in more detail below.
• tx 2: is executed locally by the user against the Obfuscator account. The transaction consumes Note 1 and creates Note 2 (public). Note 2 is public and can be displayed by the DEX front end. The sender of Note 2 is now Obfuscator, but it basically copies Note 1, including the part of the script with the return address.
• tx 3: is the actual swap, and this must be a network transaction. It is executed by the DEX Operator. It consumes Note 2 and produces Note 3 (private). The private Note 3 carries the required DAI that the user wanted and can only be consumed by that user.

There can be several ways to ensure that Note 3 can only be consumed by the initiator of the trade while at the same time hiding the corresponding Account ID from everyone else. One easy way is to encode in Note 1 a secret that needs to be provided when Note 3 is consumed. Basically, Note 1 has a condition that reads like "Whenever you copy that note, also copy the condition: whenever you consume this note, you need to create another note carrying 100 DAI that can only be consumed by whoever knows x such that f(x) = a.

And for iceberg orders, there can be an Iceberg Obfuscator that breaks down large orders into several smaller ones.

Happy to discuss it; it should work, but maybe I am missing something.

---

The following point is specific questions that we got as feedback.

Cancellation censorship to pick off stale orders

So for our onchain order book exchange PoC, it could happen that the Operator would censor a certain to prevent him/her from canceling the order. This could be "rational" if there is a high misplaced order that the Operator wants to take itself.

So when orders are being obfuscated - as explained in Privacy above - the Operator might not know which user to block. However, if the Operator is also the Miden Operator, it could censor anyone who wants to consume a particular note that represents the stale order.

This could be prevented by having a built-in order expiry. So, every note representing an order could expire after 10 minutes in a way that it can only be consumed by the creator of the note. The 10 minutes can be any arbitrary number.

Race conditions for settlement

This is indeed an interesting point. A solution depends on the implementation of the DEX account. If there is no DEX account and users would pick the notes to consume - or an algorithm running locally for the user - then there are a lot of race conditions for settlement. However, if there is a DEX account, then it depends on the actual implementation and the interface between the frontend and the Miden chain.

That is something to think of when implementing.

MEV prevention or MEV extraction

To be defined

[bobbinth]

Excellent write up! A few preliminary thoughts/comments:

A key feature of order book models is allowing users to submit two types of orders: market or limit orders.

I think we can pretty easily support limit orders (where limits can be updated nearly instantaneously in one direction), but I'm not sure how we can support marker orders yet.

2. Low finality - sub-second finality would be optimal

As mentioned above, we can have near instantaneous updates for orders, but sub-second finality would be difficult. Currently, I'm thinking of block times between 3 and 6 seconds. So, even if we assume single-block finality, orders would be executed in this timeframe.

This script is the root of a Miden program MAST. Here is where we can encode our order.

We may be able to do this even more efficiently without changing the script root. Specifically, notes also take inputs. As one input we could provide a root of a Merkle tree which encodes various trades we may want to propose. Then, we'd reveal different leaves in this tree which would define asset/value pairs which we'd like to trade for the assets contained in the note. So, basically, we keep the script the same (which would make execution easier), but vary the inputs into the script.

In theory, we don't need a matching engine

I think we might run into issues with this. Specifically, when there are many open orders (and many participants), how do we ensure that people don't end up trying to fulfill the same order. For example, say there is an open order that both you and I like. We both submit a transaction to take the order - but only one of our transactions can go through. Two potential problems with this:

1. Someone (i.e., the operator) will need to decide which one of the conflicting transactions to take. To increase chances of their transactions being accepted, users may try to bribe the operator in some ways. This is probably undesirable.
2. In a highly contentious system, many attempts to take an order may be rejected (because someone else took it first). While sending transactions which get rejected comes at negligible cost, users may get frustrated that only a subset of their attempts go through.

So, we may still need to have a matching engine which minimizes conflicting attempts to take the same order. This engine would need to be credibly neutral somehow (or at least, it should be possible to verify post-factum that the engine was credibly neutral).

[Dominik1999]

Very nice point, thank you, Bobbin! I updated the above, given your input. I did not update the script part, and we dont take inputs yet. Maybe we can leave this as an optimization?

[bobbinth]

I did not update the script part, and we can take inputs yet. Maybe we can leave this as an optimization?

yep - that's fine.

[lenchik-ponchik]

Hey, looks nice!

• Canceling order is super important for Market Makers — they use this feature in times of high volatility
• "Batch" updates — updating multiple orders with one transaction / request
• Order edits (price or size) — must be done without updating order id or shifting order in the array of orders (if we speak about price nodes) for matching / execution

Two users might want to consume the same note simultaneously, and only one would succeed.

In this case there's special option for orders, like Fill or Kill (FOK) — directed to be executed immediately at a specified price or canceled if not filled. Otherwise, this limit order just goes into the order book.

create a note having a script that queries the current market price.

Current market price is not "current order book price" especially in low liquid market if I understand you correctly. One of the solution to this problem is to build a tree of price nodes. 1 price node is array of orders with same price sorted by time of creation — to ensure FIFO. It is also important to know that Taker side orders (mostly Market orders) cover more than half of the volume of all exchanges.

---

It would be interesting to read about:

• Fees implementation;
• Trigger orders;
• Good Till Date order option (basically auto expirable orders);
• Derivatives, where you don't have asset but have margin system + positions + contracts logic.

[Dominik1999]

Thanks for your comments! It's nice to have external contribution.

• I added a small section for canceling orders. That is possible, but in its naive implementation, it requires an onchain transaction.
• Batch updates should be easily possible if the notes/orders are created in the right way.
• Your point about order edits and maintaining the order of orders is interesting. That might depend how we implement the matching algorithm and we should have this as an requirement.
• Can you explain the point about "Current market price is not "current order book price" especially in low liquid market" a bit more? I may not be following. How would a market order be executed if not by taking the current order book price of the corresponding orders?
• Fees is a super important topic. We need to clarify that in miden-base first.

[medvedNick]

indeed a very nice PoC! Agreeing with the commenters above, I'll add a couple thoughts:

probably due to the Notes nature in Miden it is not stated explicitly, but the users of DEX order book should be able to withdraw their funds in any case, in contrary to CEX. I can see a few potential issues could rise with the intermediate exchange account (like direct access by order book owner or backdoor within the implementation). Probably simple note nullifying would work, but worth mentioning

there is also an opportunity to play with different private/public states/execution related to Miden model - you've mentioned a base privacy level, but I think this could evolve into multiple great features, something like trigger orders with hidden trigger price, which are not visible until the market price reached threshold (not sure if that would work exactly like I've described, but nevertheless)

[Dominik1999]

probably due to the Notes nature in Miden it is not stated explicitly, but the users of DEX order book should be able to withdraw their funds in any case, in contrary to CEX.

They indeed can do that. The notes script could entail a branch (part of the script) that allows the sender to consume it at any time.

there is also an opportunity to play with different private/public states/execution related to Miden model - you've mentioned a base privacy level, but I think this could evolve into multiple great features, something like trigger orders with hidden trigger price, which are not visible until the market price reached threshold (not sure if that would work exactly like I've described, but nevertheless)

Check out the new section about privacy, and let me know what you think

[TomDragonHunter]

thank you!

[BritvaBo]

thanks.interesting materials