Developing a Privacy-Focused Decentralized Order Book Exchange on Polygon Miden

Published in

Sprkfi

4 min readJul 29, 2024

In recent weeks, our team has dedicated significant efforts to learning and developing smart contracts on Polygon Miden, a ZK-STARK-based Virtual Machine designed to serve as a layer two rollup for Ethereum. This initiative is part of our endeavor to create Spark, a decentralized, privacy-preserving order book exchange on the Miden blockchain.

Why Polygon Miden?

Polygon Miden addresses significant challenges faced by Ethereum, notably scalability and privacy. By integrating unspent transaction outputs (UTXOs) from Bitcoin with programmable smart contracts from Ethereum, Polygon Miden offers a high-performance and privacy-focused blockchain solution.

Scalability

Ethereum’s model of storing all transaction data on-chain is not scalable for mass adoption in decentralized finance. Miden mitigates this issue using ZK-STARKs, which enable storing only the hash of a smart contract or account, reducing the data footprint to just 32 bytes. This allows Miden to handle large smart contracts efficiently. Miden also supports client-side proving, enabling users to generate transaction proofs locally, which reduces node load and allows concurrent transaction processing, unlike Ethereum’s thread-blocking model.

Privacy

While all Ethereum transactions are public, Miden offers users the option of transaction privacy at the blockchain level. Initially, Miden will provide privacy similar to web2 platforms like PayPal, with the operator seeing all transaction data. In the future, Miden aims to enhance privacy further, potentially eliminating the need for transaction senders to be visible.

Differences from Ethereum

Miden’s architecture includes “notes,” which are unspent transaction outputs containing scripts defining conditions for their consumption. Notes can hold assets or data, ensuring that smart contracts consuming these notes can trust the validity of the data.

Building an Order Book Exchange on Miden

An order book records buy and sell orders, sorted by price. In this context, traders creating orders are “Makers,” and those filling orders are “Takers.”

Partially Fillable SWAP Notes (SWAPp)

To implement an order book exchange, our team utilized SWAPp notes, which act like cryptographic cashier’s checks. These notes allow partial deposits of offered liquidity, contingent on issuing two new checks: one with the requested asset for the SWAPp creator and another with the remaining liquidity.

Example Scenario

Trader 1 wants to exchange 10 tokens of Asset A for 10 tokens of Asset B. Trader 2, lacking enough tokens B, can partially fill Trader 1’s order, creating a new SWAPp note with the remaining liquidity. This process continues until Trader 1’s liquidity is fully consumed.

Order Book Depth and Buy/Sell Limit Orders

SWAPp notes support buy/sell limit orders:
- Buy Limit Order: Placed when a trader expects the asset price to fall.
- Sell Limit Order: Placed when a trader expects the asset price to rise.

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 ensures fixed-point precision and avoids overflow, crucial for handling large values.

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

Implementing the Partial SWAP (SWAPp) Note in Miden Assembly

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 SWAPp note requires nine stack elements as inputs and follows specific steps to manage liquidity and create new notes. The SWAPp note also includes mechanisms to allow the original creator to reclaim their order and future implementations will add expiration times.

Mitigating Race Conditions

Race conditions occur when multiple users compete to consume a SWAPp note first. Addressing this requires strategies to prevent exclusion of market participants, akin to mitigating miner extractable value (MEV) on Ethereum.

Conclusion

The Spark order book exchange on Polygon Miden demonstrates the innovative architecture of Miden, offering scalability, privacy, and expressive smart contracts. By leveraging ZK-STARKs, Polygon Miden enhances transaction efficiency and scalability, paving the way for advanced decentralized financial applications.