Building a Decentralized Privacy Preserving Order Book Exchange on Polygon Miden

11 min readJun 24, 2024

Introduction

Over the past several weeks, I’ve had the opportunity to work full-time learning how to build smart contracts on Polygon Miden, a ZK-STARK-based Virtual Machine that will be a layer two rollup for Ethereum.

Why have I been learning how to write smart contracts and UTXO scripts (Miden Notes) on Miden? Because I am working on building Spark, a decentralized privacy preserving order book exchange on the Miden blockchain!

Before I explain how I built an order book exchange in Miden Assembly and Rust, let me give you a brief introduction to why the Polygon Miden blockchain is so cool.

Why Polygon Miden?

Polygon Miden addresses several significant issues faced by Ethereum, particularly scalability and native privacy.

By integrating key concepts such as unspent transaction outputs (UTXOs) from Bitcoin and highly programmable expressive smart contracts from Ethereum, Polygon Miden creates a highly performant, privacy-preserving, smart-contract-enabled blockchain.

Super cool right?

Scalability

Ethereum stores all transaction data on-chain permanently, which is not scalable for onboarding billions of users in decentralized finance. Miden mitigates Ethereum’s state bloat problem through ZK-STARKs (Zero-Knowledge Scalable Transparent Arguments of Knowledge).

Instead of storing all transaction data as does Ethereum, Miden can reduce any smart contract or account to just its hash and store only that (account abstraction is supported by default on Miden). This means that even a huge smart contract with gigabytes of data can be represented on the Miden blockchain with just 32 bytes.

The Miden blockchain can either store:

The entire data of an account or smart contract on chain, like on Ethereum (for public accounts and notes)
Only commitments to that data (for private accounts and notes)

Additionally, Miden supports client-side proving, allowing users to generate transaction proofs locally before submitting them on-chain, further reducing load on nodes in the Miden network. This capability also enables concurrent transaction processing on Miden, unlike Ethereum, where transactions on L1 are essentially thread-blocking, leading to scalability issues.

Miden’s ability to handle transaction concurrency is comparable to other high-performance blockchains such as Solana and Sei. However, Miden’s support for local proof generation, and privacy-preserving transactions sets it apart.

As a bonus, because Miden’s core cryptography is based on ZK-STARKs, which are quantum secure, it is theoretically future-proof against quantum attacks.

Privacy

By default, all Ethereum transactions are public. As a result, privacy preserving projects like Tornado Cash have faced backlash from governments and even some web3 companies.

Miden offers users the choice of transaction privacy at the blockchain level. Initially, Miden will provide a level of privacy comparable to that of web2 platforms like PayPal, meaning the Miden operator will still see all transaction data for the first year after the mainnet launch. However, in the future, Miden aims to offer a whole new level of privacy, where, in theory, transaction notes won’t even need to have a sender.

While several privacy-preserving blockchains exist, few support expressive Turing-complete smart contracts.

Client-side proving, parallelized transactions, and native privacy make Miden a promising platform for privacy-preserving decentralized financial applications.

Differences From Ethereum

Although Miden and Ethereum both support smart contracts, Miden’s architecture diverges significantly with the concept of “notes”. Notes are unspent transaction outputs that contain a script, which defines the conditions from which a user can consume the note. Notes can contain assets or data. To create a note, an account must first generate a proof that the note was created.

I like to think of Miden Notes as cryptographic cashier’s checks. When someone writes a cashier’s check, the person depositing the check knows it won’t bounce.

Midjourney’s interpretation of a “cryptographic cashier’s check on Miden”

The same with Miden notes, the smart contract consuming the note knows the data inside of the note is valid.

The ability to pass data between smart contracts and for the smart contracts to be cryptographically certain that the data contained in the note was not tampered with is a feature of Miden that sets it apart from other blockchain projects. In a sense, Miden enables verifiable computation at the transaction level.

Currently, smart contracts and notes on Miden are written in an assembly language known as Miden Assembly (MASM).

Building an Order Book Exchange on Miden

An order book is a ubiquitous piece of financial architecture used in trading platforms to facilitate the buying and selling of assets. It records the buy and sell orders of traders, specifying the quantity and price of an asset.

The orders are sorted by price, allowing other traders to fill them based on their market strategies. In this context, the traders who create orders in the order book are known as “Makers,” while those who fill these orders are referred to as “Takers.”

Partially Fillable SWAP notes (SWAPp)

To implement the core functionality of an order book exchange, we need to create a mechanism for buy/sell orders using Miden notes. The SWAPp note can be thought of as cryptographic cashier’s check that allows partial deposits of the offered liquidity, contingent upon the trader “depositing” the cashier’s check issuing two new cashier’s checks:

A cashier’s check with the amount of the requested asset for the SWAPp creator (P2ID note).
A new buy/sell order cashier’s check (SWAPp note) with the remaining liquidity of the offered asset and the updated amount of the requested asset.

Example Scenario

Consider Trader 1, who wants to exchange 10 tokens of Asset A for 10 tokens of Asset B.
Trader 2 finds the price attractive but lacks sufficient tokens B to buy all of Trader 1’s tokens A.
Trader 1 is satisfied if they receive tokens B at the specified price, regardless of the amount.

This is where the Partially Fillable Swap Note (SWAPp) comes into play. Here’s a schema of how the SWAPp note works:

Trader 1 creates a SWAPp note with 10 tokens A and specifies a request for 10 tokens B.
Trader 2 consumes the SWAPp note, creates a note with tokens B for Trader 1, deposits 8 tokens A into their wallet, and creates a new SWAPp note with the remaining liquidity of Trader 1.
This process continues until the liquidity of Trader 1 is fully consumed.

Order Book Depth and Buy/Sell Limit Orders

The SWAPp note architecture inherently supports buy/sell limit orders.

Buy Limit Order: Placed when a trader believes the asset price will fall, specifying a price at which they wish to purchase the asset.
Sell Limit Order: Placed when a trader believes the asset price will rise, specifying a price at which they wish to sell the asset.

SWAPp notes can be aggregated and sorted by price, revealing the order book depth chart.

Example

Assume the spot price is 1:1 for tokens A and B.

To create a buy limit order, if the spot price is 1:1, a trader, Bob, would specify in their SWAPp script that they are offering 10 tokens B, for 12 tokens A. This implies that trader Bob thinks the value of token A will decrease, and the token A to token B exchange rate will drop to 0.83 B/A.

After being created, this buy limit order will not be consumed by rational market participants since the spot price is still 1:1.

Market participants who want to buy tokens B see that there are other orders with more favorable exchange rates, meaning a rational market participant would be incentivized to consume the SWAPp notes that have more favorable rates first, before consuming Bob’s open buy limit order. However, if the spot price declines to Bob’s specified exchange rate, Bob’s buy limit order will get filled.

Handling Fixed Point Precision Math in Miden Assembly

Below is a Miden Assembly procedure that calculates the amount of tokens A a SWAPp note will give if the consuming account sends a quantity of tokens B to the note creator. This calculation is akin to the x * y = k automated market maker formula but without slippage.

In Python, the SWAPp invariant formula looks like this:

def calculate_tokens_a_for_b(tokens_a, tokens_b, requested_tokens_b):
    # Scaling factor
    scaling_factor = 10**5
    
    # Check if tokens_a is smaller than tokens_b
    if tokens_a < tokens_b:
        # Scale the inverse ratio
        scaled_ratio = (tokens_b * scaling_factor) // tokens_a
        
        # Calculate the amout of tokens A out using integer arithmetic
        tokens_a_out = (requested_tokens_b * scaling_factor) // scaled_ratio
    else:
        # Scale the ratio
        scaled_ratio = (tokens_a * scaling_factor) // tokens_b

        # Calculate the amout of tokens A out using integer arithmetic
        tokens_a_out = (scaled_ratio * requested_tokens_b) // scaling_factor
    
    return tokens_a_out

In Miden Assembly, the equivalent procedure is as follows:

use.std::math::u64

const.AMT_TOKENS_A=0x0064
const.AMT_TOKENS_B=0x0065
const.AMT_TOKENS_B_IN=0x0066
const.RATIO=0x0067
  
const.FACTOR=0x000186A0 # 1e5
const.MAX_U32=0x0000000100000000
  
#! Inputs: [tokens_a, tokens_b, tokens_b_in]
#! Output: [tokens_a_out]
proc.calculate_tokens_a_for_b
  mem_store.AMT_TOKENS_A 
  mem_store.AMT_TOKENS_B 
  mem_store.AMT_TOKENS_B_IN 

  mem_load.AMT_TOKENS_B mem_load.AMT_TOKENS_A

  gt
  if.true
    mem_load.AMT_TOKENS_B
    u32split

    push.FACTOR
    u32split
            
    exec.u64::wrapping_mul

    mem_load.AMT_TOKENS_A
    u32split

    exec.u64::div
    push.MAX_U32 mul add

    mem_store.RATIO

    mem_load.AMT_TOKENS_B_IN
    u32split

    push.FACTOR
    u32split

    exec.u64::wrapping_mul

    mem_load.RATIO
    u32split

    exec.u64::div

    push.MAX_U32 mul add          

  else
    mem_load.AMT_TOKENS_A
    u32split

    push.FACTOR
    u32split
            
    exec.u64::wrapping_mul

    mem_load.AMT_TOKENS_B
    u32split

    exec.u64::div

    mem_load.AMT_TOKENS_B_IN
    u32split

    exec.u64::wrapping_mul

    push.FACTOR
    u32split

    exec.u64::div
    push.MAX_U32 mul add          

  end
end

The core of the calculate_tokens_a_for_b calculation is a straightforward division:

c = a / b

simple right?

However, to achieve fixed-point precision, the formula is adjusted to:

c = a * 10⁵ / b

To avoid overflow, particularly when a < b, the formula is modified as follows:

c1 = b * 10⁵ / a

c = 10⁵ / c1

Given that the maximum value within a stack element in the Miden VM is 2⁶⁴ — 2³², there is a limitation on the largest value a user can swap using the current implementation of the SWAPp note. Currently, the upper bound for values that the calculate_tokens_a_for_b procedure can handle is approximately 1,844,674 for a token with 8 decimal points or 184,467,440 for a token with 6 decimal points.

The plan is to implement the calculate_tokens_a_for_b procedure using u256 integers, which will effectively remove the current limitation on the maximum number of tokens a user can swap and will increase the fixed point decimal precision of the procedure.

Implementing the Partial SWAP (SWAPp) Note in Miden Assembly

This is where things start to get a bit technical, feel free to skip this part if you don’t care for the technical details :)

At a high level, these are the steps required to implement the partially fillable SWAP note (SWAPp) in Miden assembly.

The SWAPp note has the same number of inputs as the standard SWAP note in the miden-base repository. This means there are nine stack elements as inputs to the SWAPp note.

In the context of Miden, when describing the stack, capitalized words represent four stack elements. Four stack elements are referred to as words.

SWAPp note inputs:

Inputs: [PAYBACK_RECIPIENT, REQUESTED_ASSET, SWAPp_tag]

The PAYBACK_RECIPIENT is the RECIPIENT digest of the P2ID note addressed to the creator of the SWAPp note.

The RECIPIENT digest for all Miden notes is defined as:

hash(hash(hash(serial_num, [0; 4]), script_hash), input_hash)

Where, the serial_num is a unique number comprised of four stack elements.
Where, the script_hash is the Merkelized Abstract Syntax Tree (MAST) root of the given note script.
Where, the input_hash is the hash of the inputs to the note. The input to the P2ID note is the account id of the account that is allowed to consume the P2ID note.

We hash these values together to compute thePAYBACK_RECIPIENT which is the hash digest of the P2ID note.

For the SWAPp note inputs, theREQUESTED_ASSET is the faucet id and amount of the asset requested, and the SWAPp_tag is a value used to improve the discoverability of notes on the Miden blockchain.

In the steps below, “token A” refers to the offered asset, and “token B” refers to the requested asset in the SWAP note.

Push the amount_token_a contained as liquidity in the note to the stack.
Push the requested amount_token_b to the stack.
Push the amount of token B the consuming account wants to send to the SWAPp note creator, amount_token_b_in.
Using amount_token_b_in, calculate amount_token_a_out to send to the consuming account, using the calculate_tokens_a_for_b procedure.
Send amount_token_b_in to the SWAPp note creator via a P2ID note.
Send amount_token_a_out to the consuming account by calling the receive_asset procedure.
Update the amount of requested tokens B, amount_token_b’ for the new SWAPp note.
Create the new SWAPp note and add the remaining liquidity of token A, amount_token_a’.

Additionally, the SWAPp note checks if the currently consuming account is the original creator of the SWAPp note, and if so, the liquidity contained in the SWAPp note is sent to the owner. This is so that the original SWAPp note creator can reclaim their order after creation of the note.

In future implementations of the SWAPp note, the note will have an expiration time if not consumed within a certain time after being created.

You can check out the full implementation of the SWAPp note here: https://github.com/compolabs/spark-miden-v1

Mitigating Race Conditions

Currently, any user aware of a created SWAPp note can consume it. However, this can lead to potential issues, as multiple users may compete to generate and submit the proof first to the Miden node, resulting in a computational race. Addressing race conditions is challenging because initial solutions might inadvertently be exploited to exclude certain market participants from accessing the order book exchange.

I am currently researching potential strategies to mitigate the negative effects of race conditions. Notably, the issue of race conditions on Polygon Miden is analogous to the concept of miner extractable value (MEV) on Ethereum.

Conclusion

A decentralized privacy-preserving order book exchange on Polygon Miden is one of several DeFi applications that can take full advantage of the scalability, privacy, and expressive smart contracts that Polygon Miden enables.

By utilizing ZK-STARKs, Polygon Miden enables efficient transaction processing, significantly reduces on-chain data load, and enhances scalability through client-side proving.

The Spark order book exchange on Miden not only highlights the innovative architecture of Miden, but also paves the way for more advanced decentralized financial applications, addressing both scalability and privacy concerns in the DeFi space.