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.
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.
Further reading for learning Polygon Miden
If you want to learn more about Polygon Miden, how to write notes and accounts on Polygon Miden, here are a few of my favorite resources:
- Miden Research Repository. This is a repository I built to get up to speed learning how to write smart contracts on Polygon Miden: https://github.com/compolabs/miden-research
- Spark-Miden-v1. This is the current implementation of the Spark Order Book exchange on Polygon Miden, and contains the implementation of the SWAPp note: https://github.com/compolabs/miden-research
- Miden VM Documentation. This documentation is extremely useful for learning how to write scripts in Miden assembly: https://0xpolygonmiden.github.io/miden-vm/intro/main.html
- Miden Transaction Procedures Documentation. This is useful documentation for learning how to use transaction procedures and has a basic demo of how to use the Miden testnet: https://docs.polygon.technology/miden/miden-base/architecture/transactions/procedures/
- Miden Assembly Playground. This is extremely useful for learning how to write basic pure functions in Miden Assembly. https://0xpolygonmiden.github.io/examples/