---
# System prepended metadata

title: KEOM exchange (Polygon Miden)

---

# KEOM decentralized limit order book exchange 
This document aims to describe the possible design of the KEOM decentralized limit order book. The main venue for crypto asset exchange are central limit order books (CLOB). Traditional blockchains are too slow to reflect sub-second order updates or onchain matching. That is the reason why most exchanges are centralized and custodial and are therefore prone to fraud or follow the AMM design. 

## Goal of the design
With Polygon Miden, KEOM is able to build a non-custodial onchain order book exchange with sub-second price updates. Secondary goals are provable regulatory compliance and different levels of privacy. We can provide five specific sub-goals.

1) on-chain order book exchange 
    * orders are defined by spend conditions whose commitments live on-chain
    * CLOB providers merely compete on holding the most accurate set of spend conditions and creating fast efficient routing for market takers
2) non-custodial
    * funds should be held by user-controlled notes at all times
    * note spend conditions should be unilaterally revokable by owners without depending on interactiosn with the CLOB UI provider
3) sub-second price updates (Garry speaks ab 40ms latency)
    * orders matching should not rely on block settlement
4) privacy for traders 
    * user-controlled release of partial spending condition information
5) provable regulatory compliance
    * best execution
    * FiFo

(ToDo: all terms must be properly defined, eg, the current design is not 100% onchain, which compliance must be proven, ...)

## The design
KEOM can use the Polygon Miden protocol to achieve most of the goals. In Miden, there are accounts and notes, see [here](https://polygon.technology/blog/polygon-miden-transaction-model-2). 

Notes carry assets and their scripts must be executed by the consuming account. Simply put, if an account wants to receive the assets from a note, it must execute the note script. 

### Orders: Notes represent orders
The following depicts an order (using the Note Tag KEOM). The sender wants to trade y ETH (out of a total Y ETH held on the note) for a certain amount x of DAI. The note script is defined such that the sender account can update x and y.

In this case, the note can only be consumed (hence the order and the price be accepted) by a taker account iff two conditions are true

1. taker must know a message signed by the sender 
2. (OPTIONAL) taker must be able to prove statements about their identity (KYC compliance / PolygonID)

![image](https://hackmd.io/_uploads/BJdj4wkVp.png) 

The message `m = s(x, block_height)` is a signed tuple by the sender with 

- x being the amount of DAI the sender wants in exchange for the ETH present in the Note
- block_height being the timestamp until this message is valid. With that the sender, e.g., market maker, has the ability to put a timelock on a specific order (not 100% thought through yet)

Open questions:
- do we need to check the signature or can we work with a) a cryptographic secret (like HTLC) or b) by revealing sub-MAST roots as described [here](https://github.com/0xPolygonMiden/examples/discussions/138)
- we must think about the block_height problem hence note consumption is asynchronous in Miden and people can simply use an older block_height when executing locally
- we can add more complex spend conditions like a nonce to gain additional features
- Can operations targeting a given note be aggregated at the sequencer level such that the note is consumed only at the end. 
- Can notes be consumed into new versions with identical spending scripts?
- If I submit a tx to consume a note that creates a new one, can I already submit the transaction referencing the new note BEFORE the next block reaches consensus? This could allow operation aggregations.

### Orders: Creating orders
Notes must be present in the Miden Notes DB to be consumable. That means creating a new note requires an on-chain operation. But notes can represent many different orders with the same asset pair by using different messages `m`.

![image](https://hackmd.io/_uploads/Skgts524T.png)

This design ensures that the exchange works non-custdially, see goal 2). The exchange operator (KEOM) does not have access to the funds on a note. KEOM merely aid users in constructing a note with spend conditions of their choosing.

Open questions: 
- What are the trust assumptions on the Miden Operator here?

### Orders: Updating orders
Updating a note only requires that the sender publishes a new signed message `m` anywhere. This must not be onchain and can in theory happen in any whisper or chat protocol. It is in the sender's interested to publish the new message widely as it represents a new price. 

~This however does not need to be true, as is the case of special spend conditions to be made available privately (ex: OTC deals). The order book in this model becomes the abstract snapshot of all spend conditions as revealed to the KEOM service.~

![image](https://hackmd.io/_uploads/r1ypTPJEp.png)

Updating the note's spend condition off-chain provides goal 3).

(ToDo: We should test how fast this can be done, inclusive of the PolygonID verification step, to show a quantifiable comparison with a hypothetical equivalent EVM operation.)

### Orders: 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 if possible. 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. If an order cannot be filled, it needs to be added to the order book to be filled when the order book changes. These operations are performed by KEOM or any other exchange operator competing with us. 

To ensure "best execution", we need to ensure that any order `O` with a given Order Book at state at t `S(order_book, time)` is being executed in the most favorable way for the user. In the KEOM design, the Order Book State is partially on-chain (notes), and for the most part off-chain, the messages `m`. The KEOM operator and in the frontend the whole state is known and shown. The whole state `S(order_book, time)` could be logged, stored and expressed in a single hash `h(S(order_book, time))`. Let's assume the order book is always sorted, e.g., using a red-black-binary tree that is computed at the KEOM operator.

Matching could then happen in a simple Miden VM program, where 

- public inputs: `(order, h(S(order_book, time)))` whereas only the specific price pair, not the whole order book is of interest
- advice provider: `order_book`
- program: (1) check correct sorting, (2) try to fill (if true -> return notes to be consumed, if false -> do nothing)

If the order can not be filled, the insertion into the order book happens outside the VM at the KEOM operator. Correctness will be checked by checking correct sorting at the next try to fill. 

That way we always get a proof that a given tupel `(order, order_book_state)` is being executed accoring to the defined rules in the program (could be FiFo, Pro-Rata). This provides almost 5). 

Maybe the off-chain information must be stored somewhere - maybe for 2 years? - to be able to reconstruct the prove to show to authorities. In fact it should be sufficient without storing if the authorities accept zkProofs ...

ToDo: Depending on the size of an orderbook this could be too slow, we need to run some tests. But assuming there are 5k order of a given price pair, we should get this done in <10k cycles which should be a matter of ms.

Open Questions:
- We might not even need FiFo or Pro-Rate because all liquidity is public anyway and users can match any orders they like. Or there can be aggregators. In this scenario, best execution is enforced by open market competition among exchange operators.

### Orders: Settling orders
Consuming a note or taking an order requires another on-chain operation. Which provides decentralized settlement and almost goal 1). Almost, because the whole exchange design is not fully on-chain.

In order to prevent race conditions, we might need to introduce a KEOM DEX account. Oders could be settled by executing public transactions against this account. The transaction could always simply send one leg of the order to the sender (e.g. 100 ETH) and on leg of the order to the receiver and executor (10.000 DAI). That way, every note can only be settled once. Using a KEOM DEX Account / Smart contract is also the place where we can allow or prevent MEV. 


### Orders: Recalling orders
Market makers might want to cancel an order quite quickly. As note creators can always re-consume their own notes, market makers can re-call orders. However, they might need to wait for the next block, because settlement happens on-chain. This might take up to 4 seconds. 

They could send a message to the frontend operator to take any order down immediately even before reconsumption is confirmed by the blockchain. However, this might have any security implications. 

Open Questions:

- Order messages could also specify a version number, allowing market makers to void a specific version.
- Order aggregation, discussed in the previous sections, could significantly help here

(ToDo: I thought we had a solution for this?)

### 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](https://polygon.technology/blog/polygon-miden-transaction-model-2) and [here](https://polygon.technology/blog/polygon-miden-state-model?utm_source=twitter&utm_medium=social&utm_content=miden-state-model)): 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):

![image](https://github.com/0xPolygonMiden/examples/assets/35031754/43df9c67-20ad-4e0c-a684-d0b24f27b4a5)

- 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. 

## Open Questions
- Do we get sub-second latency in order updates?
- Do we get sub-second latency in order settlement? (unrealistic)
- How do we prevent race conditions? Do we need a CLOB account against which all settling tx are being executed?
- Is an obfuscator even required? Can't the note simply publicize a hash commitment to the spending script only? The user than has the freedom to selectively publish however much information of their spending script as they please.
- Aggregating txs that spend the same  note at the sequencer level? 
- Having malleable NoteID referecnes for streamed execution of multiple txs whose spends are consistent with each other? 
- Garry: How would orderes be logged and how can we make those logs accesible, say, 2 years down the line for compliance purposes. (Centralized or not/immutable)


## Competitive advantages
- We don't need to collect liquidity but only the spend.
- The typical question we get from liquidity providers is: how do you plan to attract liquidity? Miden offers a simple answer: WE DON'T NEED TO! 
- Running a CLOB simply evolves into an open market competition over the collection of the most extensive set of spend conditions.
- There is no exchange that can do CLOB onchain, is private and provably compliant

## Next steps (what, by whom)
- How can Polygon sustainably support KEOM?
- ...
- 
