Building a Scalable Cairo-Based Automated Market Maker (AMM)

A Step-By-Step Guide

We recently released the alpha version of SHARP – our Shared Prover that allows anyone to send programs to be STARK-proved (currently on Goerli), and it’s a good opportunity to talk about how you can build an end-to-end Cairo-powered dApp. Seeing how Automated Market Makers (or AMMs) have been getting a lot of attention lately, we figured it would be useful to have a detailed guide on how to write and deploy a scalable Cairo-based Automated Market Maker. 

Be warned –  this post is considerably longer than what we usually write, but you will come up on the other end of it with a ready-to-use-and-improve Cairo-based AMM. So yay. 

What is an AMM?

Automated Market Maker, as you might have guessed from the name, is a mechanism that allows a simple way for market-making. In an AMM we have two types of users: Traders and Liquidity Providers.

Traders perform trades against liquidity pools. Every liquidity pool supports two or more assets, and allows trading according to some predetermined formula. This means that for every quantity of some asset that you want to buy, you can compute exactly how much you’d have to pay to receive it (given the current state of the pool).

Unlike the regular order book matching, it’s very easy to write and run AMM logic. So easy that it can be fully deployed on Ethereum and still provide efficient, inexpensive trading. The user interface is extremely simple – you only need to specify the quantity of the assets you want to trade, and you know you’ll get a fair rate. An AMM is also very friendly for the Liquidity Providers – anyone can easily provide liquidity (invest money) and potentially profit by doing so.

To learn more about AMM, take a look at the Uniswap docs.

Building Blocks

Let’s take a look at the system components:

  1. A Cairo program that knows how to create a STARK-provable statement that we moved from State A to State B validly and with the approval of the users.
  2. The SHARP On-Chain Smart Contract that verifies the STARK proof attesting to the validity of the Cairo run and issues a corresponding Fact (read more about how SHARP works with Facts here) 
  3. The dApp Smart Contract that holds the current state and knows how to transition from State A to State B, ensuring that the SHARP contract approved this state transition. 
  4. An Off-Chain Backend that takes many transactions, batches them and sends them to the off-chain SHARP prover. Once the proof is accepted, it triggers the dApp smart contract to execute the state transition. For the purpose of this demo, we are not using a “real” backend, but a script that simulates what a backend would do.

Let’s Start

Before we start, make sure your development environment is properly configured.

First, install the cairo-lang pip package on a new python virtual environment:

python3.7 -m venv ~/cairo_venv
source ~/cairo_venv/bin/activate
python3.7 -m pip install cairo-lang

Installing this package installs the Cairo developer toolchain and the SHARP client, which are used by this AMM demo.

Then, clone the cairo-lang repository:

git clone [email protected]:starkware-libs/cairo-lang.git

This repository includes the AMM demo code (in addition to the Cairo developer toolchain code, which we installed in the previous phase).

Step 1: Write The Cairo Program

The Cairo program holds the business logic we are going to use. In this case we are implementing an AMM. 

Follow the Simple Automated Market Maker tutorial we’ve prepared and once you’re finished – check that your code is correct by comparing it to this complete code. 

Step 2: Run the AMM Demo

The AMM Demo package holds all the building blocks described above – a script simulating a backend, the dApp solidity smart contract, and the complete Cairo code, similar to the code you implemented in Step 1. 

Initialization 

To start the demo, run the following commands:

cd cairo-lang/src/
python3.7 -m demo.amm_demo.demo

The scripts starts with 3 simple steps to initialize the backend: 

1.

Please provide an RPC URL to communicate with an Ethereum node on Goerli: https://goerli.infura.io/v3/XXX


Provide a Goerli RPC URL. If you’re unfamiliar with Ethereum nodes, we recommend using https://infura.io or https://www.alchemyapi.io for easy setup.

2.

Please enter an operator private key, or press Enter to generate a new private key:

Provide the operator’s (this is you) private key (it expects a hexadecimal number, e.g. 777abc) – or simply press enter and the script will create one for you.

3.

Please send funds (at least 0.1 Goerli ETH) to XXX and press enter.
Funds not received yet...
Funds not received yet...

Send some Goerli ETH to cover gas costs. 

Compiling the AMM demo smart contract…Deploying the AMM demo smart contract…Transaction built and signed.
Transaction sent. tx_hash=0xbbda073436b045f678994afee2221605a3844e20fbe59b0741a3c1df5f5e518e .
Transaction successfully mined.
AMM demo smart contract successfully deployed to address 0x2734a0744452Eb0Ec69eba47337c59797b33f922. 
You can track the contract state through this link https://goerli.etherscan.io/address/0x2734a0744452Eb0Ec69eba47337c59797b33f922 . Press enter to continue.

The script generates a preliminary state for you to work with (consisting of user accounts and balances, and how much money is in the AMM pool). For the purpose of this demo we are using 2 token types: Token A and Token B, so all balances will be of these tokens. It will also deploy the AMM contract on Goerli. You can read the contract’s code here, and if you’d like a deep dive – continue reading, we’ll get there. 

AMM Simulation

Let’s take a look at the entire system, and better understand its moving parts. 

First, you have the AMM Demo package – which is what you’ve just initialized. This is your backend.  The backend holds the state, and executes the business logic of the Cairo program you wrote in Step 1. This part is completely off-chain. 

Next, you have the SHARP component – the off-chain prover and the on-chain verifier.

And finally, you have the AMM smart contract on-chain. 

1 :  Generate A Batch

This step is executed in the backend. 

Sending batch to SHARP…
Swap: Account 3 gave 635 tokens of type token_a and received 173 tokens of type token_b.
Swap: Account 4 gave 783 tokens of type token_a and received 213 tokens of type token_b.
Swap: Account 1 gave 197 tokens of type token_a and received 53 tokens of type token_b.
Swap: Account 1 gave 106 tokens of type token_a and received 28 tokens of type token_b.
Swap: Account 1 gave 289 tokens of type token_a and received 78 tokens of type token_b.
Swap: Account 2 gave 105 tokens of type token_a and received 28 tokens of type token_b.
Swap: Account 3 gave 310 tokens of type token_a and received 84 tokens of type token_b.
Swap: Account 1 gave 52 tokens of type token_a and received 14 tokens of type token_b.
Swap: Account 4 gave 57 tokens of type token_a and received 15 tokens of type token_b.
Swap: Account 3 gave 30 tokens of type token_a and received 8 tokens of type token_b.
  1. The script generates some random AMM transactions. 
  2. Now, the backend updates the off-chain state by running the business logic (as defined in the Cairo program) on the state using the transactions it received. The new state consists of the new AMM balances and new traders account balances. 
  3. Now it sends this batch and the Cairo Trace to the  SHARP Prover (you can see the full code here). 
2: Prove State Transition Validity 

The SHARP Prover receives the Cairo Trace and generates a STARK proof of the validity of the run. This proof is sent, as usual, on-chain to the SHARP Verifier, that verifies it and writes a Fact attesting to the validity of this state transition. 

To refresh your memory on how this works, read our Cairo for Blockchain Developers post. 

3: Update the On-Chain State

Once the Fact is registered on-chain, the backend sends a transaction to the on-chain dApp Smart Contract asking it to update its current state to the new state. 

Before we go into what the dApp Smart Contract does with this information, let’s take a step back and look at the Smart Contract’s code. The full code of the Smart Contract is available here.

   /*
     Initializes the contract state.
   */
   constructor(
       uint256 accountTreeRoot,
       uint256 amountTokenA,
       uint256 amountTokenB,
       uint256 cairoProgramHash,
       address cairoVerifier)
       public
   {
       accountTreeRoot_ = accountTreeRoot;
       amountTokenA_ = amountTokenA;
       amountTokenB_ = amountTokenB;
       cairoProgramHash_ = cairoProgramHash;
       cairoVerifier_ = IFactRegistry(cairoVerifier);
   }

The Smart Contract holds information about the state: the balances of the tokens in the AMM pool and the commitment to the trader account balances on L2 in the form of a Merkle root. It’s also initialized with two things that allows it to verify the validity of the system update request: the hash of the Cairo program, and the address of the SHARP verifier contract (that holds the validated Facts). Both these parameters cannot be changed and they provide the security of the system. Think about it like this: holding a commitment to the Cairo program, means that the Smart Contract can make sure the business logic that was supposed to be executed is indeed the one executed. Similarly, holding the verifier address ensures the integrity of state updates.

Now let’s look at how the Smart Contract handles the state transition. 

function updateState(uint256[] memory programOutput)
       public
   {
       // Ensure that a corresponding proof was verified.
       bytes32 outputHash = keccak256(abi.encodePacked(programOutput));
       bytes32 fact = keccak256(abi.encodePacked(cairoProgramHash_, outputHash));
       require(cairoVerifier_.isValid(fact), "MISSING_CAIRO_PROOF");
 
       // Ensure the output consistency with current system state.
       require(programOutput.length == 6, "INVALID_PROGRAM_OUTPUT");
       require(accountTreeRoot_ == programOutput[4], "ACCOUNT_TREE_ROOT_MISMATCH");
       require(amountTokenA_ == programOutput[0], "TOKEN_A_MISMATCH");
       require(amountTokenB_ == programOutput[1], "TOKEN_B_MISMATCH");
 
       // Update system state.
       accountTreeRoot_ = programOutput[5];
       amountTokenA_ = programOutput[2];
       amountTokenB_ = programOutput[3];
   }

As you recall, several outputs were created when we generated the batch: the previous and new AMM balances, and the Merkle roots of the previous and new state of trader balances. All these outputs are sent to the updateState() function. 

The Smart Contract does two things: 

  1. checks with the SHARP Fact Registry contract that there is indeed a Fact attesting this state transition is valid and follows the expected business logic. It does that by computing the expected value of the Fact, using the hash of the Cairo program (cairoProgramHash) and a hash of the outputs it received from the backend. Once it sees that the Fact exists in the Fact Registry Contract, it knows it can safely update the state. 
  2. makes sure the previous state it got from the backend indeed matches the stored state. 

Once these two things are done, the Smart Contract goes ahead and updates the token balances and the Merkle root representing the state of the traders accounts balances. 

And… that’s all folks!

Recap

In this post we took you step by step through the process of building a scalable Cairo-based Automated Market Maker . You wrote the business logic and Cairo and then ran a backend and an AMM Solidity Smart Contract on Goerli. 

What happens next is up to you – you now have the beginning of a working AMM that, thanks to the Cairo code at its heart, the SHARP infrastructure and the scaling offered by STARK proofs, can handle massive scale. What’s left for you to do is to improve it: add features, make a frontend, think about new ways it can serve your users. If you do – share the results with us. 

And if you have ideas for other stuff you want to build with Cairo – let us know! The Cairo Devs discord server is where you can share ideas, ask questions and get help. Join now 🙂 

Tags: