Welcome, stranger!

This is the Dango Book, everything about one place for all DeFi.

• Follow us on Twitter
• Join our Discord server
• Check out source code on GitHub

Passive liquidity on Dango DEX

Dango DEX is a fully onchain limit order book (LOB) exchange. It uses frequent batch auctions (FBAs), executed at the end of each block, to match orders. Otherwise, it's not dissimilar to other LOB exchanges, e.g. Hyperliquid.

A major downside of LOBs vs AMMs is that market making on LOBs requires a high level of sophistication, making it infeasible to average retail investors. From the perspective of an unsophisticated investor who wishes to provide liquidity complete passively on major spot pairs (BTC-USD, ETH-USD, etc.), as of this time, their only options are Uniswap V3 (full range) and Curve V2. However, LP'ing on these AMMs have proven to be generally not profitable due to arbitrage trades.

Loss from arbitrage trades, measured by loss-versus-rebalancing (LVR), occurs when there's another, more liquid venue for trading the same pair, where price discovery primarily takes place. In crypto, this is typically the CEXs: Binance, Coinbase, Kraken, etc. Suppose BTC-USD is trading at 95,000. Then, upon a favorable news, it jumps to 96,000 on Binance. However, AMMs are completely passive--they never actively adjust quotes based on the news. As such, an arbitrageur can buy BTC at the stale price of 95,000 from the AMM, then sell on Binance for 96,000. LPs in the AMM takes the worse side of the trade. Over time, such losses accumulate and more often than not, outpace the gains from fees.

The objective

Create a passive liquidity pool that provides liquidity on Dango DEX, with the following properties:

• It will place limit orders in the LOB following a predefined strategy, such as an oracle-informed AMM curve.
• It aims to be the backstop liquidity. Meaning, it doesn't need to quote aggressively with super tight spreads. We anticipate professional MMs will take that role. The pool will quote wider (thus taking less risk), and be the backstop in case a big trade eats up all the orders from MMs.
• It targets majors (BTC, ETH, SOL, etc.) and should be LVR-resistant. At Dango, we want to maximize the benefit of LPs by discouraging arbitrage flow.
• It doesn't aim to be resistant to impermanent loss (IL). However, once we ship perpetual futures trading on Dango, we imagine there will be actively managed "vaults" that combine the LP pool and hedging strategies using perps.

Order placement

Let's discuss how the pool may determine what orders to place in the LOB. Let's think of the simplest strategy: the constant product curve ("xyk curve").

Consider a BTC-USD pool that currently contains $x$ units of BTC (the "base asset") and $y$ units of USD (the "quote asset"). The state of the pool can be considered a point on the curve $I(x,y)=xy=K$, where $K$ is a constant that quantifies how much liquidity there is in the pool. When a trade happens, the state moves to a different point on the same curve (that is, without considering any fee).

Generally, for any AMM curve $I(x,y)$, we define the concept of marginal price as:

$$p_{\mathrm{m}}(x,y)=-\frac{\mathrm{d}y}{\mathrm{d}x}=\frac{\frac{\partial I}{\partial x}}{\frac{\partial I}{\partial y}}$$

For the xyk curve, this is:

$$p_{\mathrm{m}}(x,y)=\frac{y}{x}$$

$p_{\mathrm{m}}$ is the price, denoted as the units of quote asset per one unit of base asset (that is, $y$ over $x$), of trading an infinitesimal amount of one asset to the other. On a graph, it is the slope of the tangent line that touches the curve at the point $(x,y)$.

Let's imagine the pool starts from the state of $(x_0=5,y_0=2)$; marginal price $p_{\mathrm{m}}(x_0,y_0)=0.4$ USD per BTC.

At this time, if a trader swaps 2 units of USD to 2.5 units of BTC, the state would move to the point $(x_1=2.5,y_1=4)$, marginal price $p_{\mathrm{m}}(x_1,y_1)=1.6$ USD per BTC.

We interpret this as follows: under the state of $(x=5,y=2)$ and following the strategy defined by the xyk curve, the pool offers to sell 2.5 units of BTC over the price range of 0.4--1.6 USD per BTC.

Translating this to the context of orderbook, this means the pool would place SELL orders of sizes totalling 2.5 units of BTC between the prices 0.4 and 1.6.

Following this logic, we can devise the following algorithm to work out all the SELL orders that the pool would place:

• The pool is parameterized by spread $p_{\mathrm{s}}$ and "bin size" $\Delta p$.
• Start from the marginal price $p_{\mathrm{m}}(x_0,y_0)$ (we denote this simply as $p_{\mathrm{m}}$ from here on).
  • The pool would not place any order here. We say the total order size here is zero.
• Move on to the "bin" at price $p_0=p_{\mathrm{m}}+\frac{1}{2}{p}_{\mathrm{s}}$ (marginal price plus the half spread).
  • This is the price at which the pool will place its first SELL order.
  • Using the approach discussed above, find the total order size between the prices $p_0$ and $p_{\mathrm{m}}$. This is the size of the order to be place here.
• Move on to the next "bin", at price $p_1=p_0+\Delta p$.
  • Using the approach discussed above, find the total order size between the prices $p_1$ and $p_0$.
  • Subtract the total order size between $p_{\mathrm{m}}$ and $p_0$, this is the order size to be placed here.
• Do the same for $p_2$, $p_3$, ... until liquidity runs out (total order size $\ge x_0$).

With the same approach, we can work out all the BUY orders for prices below $p_{\mathrm{m}}$.

For the xyk curve, the orders are visualized as follows (based on the state $x_0=1$, $y_0=200$ and parameters $p_{\mathrm{s}}=0.2$, $\Delta p=0.1$):

We see the pool places orders of roughtly the same size across a wide price range. That is, the liquidity isn't concentrated.

As example for a concentrated liquidity curve, the Solidly curve $I(x,y)=x^{3}y+x{y}^3$ results in the following orders:

As we see, liquidity is significantly more concentrated here.

Tackling arbitrage loss

In order to discourage arbitrage flow, the pool needs to actively adjusts its quote based on the prices trading at other more liquid venues (the CEXs, in our case).

To achieve this, we simply introduce an oracle price term into the AMM invariant. Suppose the oracle price is $p$. Instead of $I(x,y)$, we simply use the curve:

$$I_{\mathrm{oracle}}(x,y,p)=I\left(x,\frac{y}{p}\right)$$

The xyk and Solidly curves become the following, respectively:

$$I_{\mathrm{oracle}}(x,y,p)=x\left(\frac{y}{p}\right)$$

$$I_{\mathrm{oracle}}(x,y,p)=x^3\left(\frac{y}{p}\right)+x{\left(\frac{y}{p}\right)}^3$$

Following the same example with Solidly above, but set oracle price to $p=210$ (higher than the margin price of 200), the orders become:

As we see, the pool now quotes around the price of 210. It places bigger orders on the SELL side than the BUY side, demonstrating that it has a tendency to reduce its holding of the base asset, so that its inventory goes closer the ratio of 1:210 as the oracle indicates.

Oracle risk

The biggest risk of an oracle-informed AMM is that the oracle reports incorrect prices. For example, if BTC is trading at 95,000, but the oracle says the price is 0.0001, then traders are able to buy BTC from Dango at around 0.0001, resulting in almost total loss for our LPs.

To reduce the chance of this happening, we plan to employ the following:

• Use a low latency oracle, specifically Pyth's 10 ms or 50 ms feed.
• Pyth prices come with a confidence range, meaning a range it thinks there's a 95% probability the true price is in. Our parameter $p_{\mathrm{s}}$ should be configured to be similar or larger than this.
• Make the oracle a part of our block building logic. A block is invalid if it doesn't contain an oracle price. The block producer must submit the price in a transaction on the top of the block.
• The LP pool is given priority to adjust its orders in response to the oracle price before anyone else. Specifically, since we use FBA, the LP pool is allowed to adjust its orders prior to the auction.
• Implement circuit breakers, that if triggered, the LP pool would cancel all its orders and do nothing, until the situation goes back to normal. These can include:
  • Oracle price is too old (older than a given threshold).
  • Oracle price makes too big of a jump (e.g. it goes from 95,000 to 0.0001).

Open questions

• A market maker usually doesn't place orders around the oracle price, but rather computes a "reservation price" based on the oracle price as well as his current inventory. Additionally, he usually doesn't use equal spread on both sides, but rather skewed spreads based on inventory. A classic model for computing these is that by Avellaneda and Stoikov. Our model do not do these.
• Whereas Solidly is the simplest concentrated liquidity curve (simpler than Curve V1 or V2), it's still quite computationally heavy. We need to solve a quartic (4th degree polynomial) equation using Newton's method, for each "bin", each block. We would like to explore simpler concentrated liquidity curves.

Audits

A list of audits we have completed so far:

Bounded values

A common situation developers find themselves in is their contract needs to take a value that must been within a certain bound.

For example, a fee rate should be within the range of 0~1. It doesn't make sense to charge more than 100% fee. Whenever a fee rate is provided, the contract needs to verify it's within the bounds, throwing error if not:

#![allow(unused)]
fn main() {
#[grug::derive(Serde)]
struct InstantiateMsg {
    pub fee_rate: Udec256,
}

#[grug::export]
fn instantiate(ctx: MutableCtx, msg: InstantiateMsg) -> anyhow::Result<Response> {
    ensure!(
        Udec256::ZERO <= fee_rate && fee_rate < Udec256::ONE,
        "fee rate is out of bounds"
    );

    Ok(Response::new())
}
}

We call this an imperative approach for working with bounded values.

The problem with this is that the declaration and validation of fee_rate are in two places, often in two separate files. Sometimes developers simply forget to do the validation.

Instead, Grug encourages a declarative approach. We declare the valid range of a value at the time we define it, utilizing the Bounded type and Bounds trait:

#![allow(unused)]
fn main() {
use grug::{Bounded, Bounds};
use std::ops::Bound;

struct FeeRateBounds;

impl Bounds<Udec256> for FeeRateBounds {
    const MIN: Bound<Udec256> = Bound::Inclusive(Udec256::ZERO);
    const MAX: Bound<Udec256> = Bound::Exclusive(Udec256::ONE);
}

type FeeRate = Bounded<Udec256, FeeRateBounds>;

#[grug::derive(Serde)]
struct InstantiateMsg {
    pub fee_rate: FeeRate,
}

#[grug::export]
fn instantiate(ctx: MutableCtx, msg: InstantiateMsg) -> anyhow::Result<Response> {
    // No need to validate the fee rate here.
    // Its bounds are already verified when `msg` is deserialized!

    Ok(Response::new())
}
}

Entry points

Each Grug smart contract presents several predefined Wasm export functions known as entry points. The state machine (also referred to as the host) executes or makes queries at contracts by calling these functions. Some of the entry points are mandatory, while the others are optional. The Grug standard library provides an #[grug::export] macro which helps defining entry points.

This page lists all supported entry points, in Rust pseudo-code.

Memory

These two are auto-implemented. They are used by the host to load data into the Wasm memory. The contract programmer should not try modifying them.

#![allow(unused)]
fn main() {
#[no_mangle]
extern "C" fn allocate(capacity: u32) -> u32;

#[no_mangle]
extern "C" fn deallocate(region_ptr: u32);
}

Basic

These are basic entry points that pretty much every contract may need to implement.

#![allow(unused)]
fn main() {
#[grug::export]
fn instantiate(ctx: MutableCtx, msg: InstantiateMsg) -> Result<Response>;

#[grug::export]
fn execute(ctx: MutableCtx, msg: ExecuteMsg) -> Result<Response>;

#[grug::export]
fn migrate(ctx: MutableCtx, msg: MigrateMsg) -> Result<Response>;

#[grug::export]
fn receive(ctx: MutableCtx) -> Result<Response>;

#[grug::export]
fn reply(ctx: SudoCtx, msg: ReplyMsg, result: SubMsgResult) -> Result<Response>;

#[grug::export]
fn query(ctx: ImmutableCtx, msg: QueryMsg) -> Result<Binary>;
}

Fee

In Grug, gas fees are handled by a smart contract called the taxman. It must implement the following two exports:

#![allow(unused)]
fn main() {
#[grug::export]
fn withhold_fee(ctx: AuthCtx, tx: Tx) -> Result<Response>;

#[grug::export]
fn finalize_fee(ctx: AuthCtx, tx: Tx, outcome: Outcome) -> Result<Response>;
}

Authentication

These are entry points that a contract needs in order to be able to initiate transactions.

#![allow(unused)]
fn main() {
#[grug::export]
fn authenticate(ctx: AuthCtx, tx: Tx) -> Result<Response>;

#[grug::export]
fn backrun(ctx: AuthCtx, tx: Tx) -> Result<Response>;
}

Bank

In Grug, tokens balances and transfers are handled by a contract known as the bank. It must implement the following two exports:

#![allow(unused)]
fn main() {
#[grug::export]
fn bank_execute(ctx: SudoCtx, msg: BankMsg) -> Result<Response>;

#[grug::export]
fn bank_query(ctx: ImmutableCtx, msg: BankQuery) -> Result<BankQueryResponse>;
}

Cronjobs

The chain's owner can appoint a number of contracts to be automatically invoked at regular time intervals. Each such contract must implement the following entry point:

#![allow(unused)]
fn main() {
#[grug::export]
fn cron_execute(ctx: SudoCtx) -> Result<Response>;
}

IBC

Contracts that are to be used as IBC light clients must implement the following entry point:

#![allow(unused)]
fn main() {
#[grug::export]
fn ibc_client_query(ctx: ImmutableCtx, msg: IbcClientQuery) -> Result<IbcClientQueryResponse>;
}

Contracts that are to be used as IBC applications must implement the following entry points:

#![allow(unused)]
fn main() {
#[grug::export]
fn ibc_packet_receive(ctx: MutableCtx, msg: IbcPacketReceiveMsg) -> Result<Response>;

#[grug::export]
fn ibc_packet_ack(ctx: MutableCtx, msg: IbcPacketAckMsg) -> Result<Response>;

#[grug::export]
fn ibc_packet_timeout(ctx: MutableCtx, msg: IbcPacketTimeoutMsg) -> Result<Response>;
}

Extension traits

In Grug, we make use of the extension trait pattern, which is well explained by this video.

To put it simply, a Rust library has two options on how to ship a functionality: to ship a function, or to ship a trait.

For instance, suppose our library needs to ship the functionality of converting Rust values to strings.

Shipping a function

The library exports a function:

#![allow(unused)]
fn main() {
pub fn to_json_string<T>(data: &T) -> String
where
    T: serde::Serialize,
{
    serde_json::to_string(data).unwrap_or_else(|err| {
        panic!("failed to serialize to JSON string: {err}");
    })
}
}

The consumer imports the function:

#![allow(unused)]
fn main() {
use grug::to_json_string;

let my_string = to_json_string(&my_data)?;
}

Shipping a trait

The library exports a trait, and implements the trait for all eligible types.

The trait is typically named {...}Ext where "Ext" stands for extension, because the effectively extends the functionality of types that implement it.

#![allow(unused)]
fn main() {
pub trait JsonSerExt {
    fn to_json_string(&self) -> String;
}

impl<T> JsonSerExt for T
where
    T: serde::Serialize,
{
    fn to_json_string(&self) -> String {
        serde_json::to_string(data).unwrap_or_else(|err| {
            panic!("failed to serialize to JSON string: {err}");
        })
    }
}
}

The consumer imports the trait:

#![allow(unused)]
fn main() {
use grug::JsonSerExt;

let my_string = my_data.to_json_string()?;
}

Extension traits in Grug

We think the consumer's syntax with extension traits is often more readable than with functions. Therefore we use this pattern extensively in Grug.

In grug-types, we define functionalities related to hashing and serialization with following traits:

• Borsh{Ser,De}Ext
• Proto{Ser,De}Ext
• Json{Ser,De}Ext
• HashExt

Additionally, there are the following in grug-apps, which provides gas metering capability to storage primitives including Item and Map, but they are only for internal use and not exported:

• MeteredStorage
• MeteredItem
• MeteredMap
• MeteredIterator

Gas

Some thoughts on how we define gas cost in Grug.

The Wasmer runtime provides a Metering middleware that measures how many "points" a Wasm function call consumes.

The question is how to associate Wasmer points to the chain's gas units.

CosmWasm's approach

As documented here, CosmWasm's approach is as follows:

1. Perform a benchmark to measure how many "points" Wasmer can execute per second. Then, set a target amount of gas per second (they use 10^12 gas per second). Between these two numbers, CosmWasm decides that 1 Wasmer point is to equal 170 gas units.

2. Perform another benchmark to measure how much time it takes for the host to execute each host function (e.g. addr_validate or secp256k1_verify). Based on this, assign a proper gas cost for each host function.

3. Divide CosmWasm gas by a constant factor of 100 to arrive at Cosmos SDK gas.

Our approach

For us, defining gas cost is easier, because we don't have a Cosmos SDK to deal with.

1. We skip step 1, and simply set 1 Wasmer point = 1 Grug gas unit.

2. We perform the same benchmarks to set proper gas costs for host functions.

3. We skip this step as well.

In summary,

• 1 Cosmos SDK gas = 100 CosmWasm gas
• 1 Wasmer point = 170 CosmWasm gas
• 1 Wasmer point = 1 Grug gas

Benchmark results

Benchmarks were performed on a MacBook Pro with the M2 Pro CPU.

Relevant code can be found in crates/vm/wasm/benches and crates/crypto/benches.

Wasmer points per second

This corresponds to the step 1 above. This benchmark is irrelevant for our decision making (as we simply set 1 Wasmer point = 1 Grug gas unit), but we still perform it for good measure.

Extrapolating to 1 second, we arrive at that WasmVm executes 10,026,065,176 points per second. Let's round this to 10^10 points per second, for simplicity.

If we were to target 10^12 gas units per second as CosmWasm does (we don't), this would mean 10^12 / 10^10 = 100 gas units per Wasmer point.

This is roughly in the same ballpark as CosmWasm's result (170 gas units per Wasmer point). The results are of course not directly comparable because they were done using different CPUs, but the numbers being within one degree of magnitude suggests the two VMs are similar in performance.

As said before, we set 1 Wasmer point = 1 gas unit, so we're doing 10^10 gas per second.

Single signature verification

Time for verifying one signature:

We have established that 1 second corresponds to 10^10 gas units. Therefore, secp256k1_verify costing 0.188 millisecond means it should cost $10^{10}\times 0.077\times 10^{-3}$ = 770,000 gas.

This is comparable to CosmWasm's value.

Batch signature verification

ed25519_batch_verify time for various batch sizes:

Linear regression shows there's a flat cost 0.134 ms (1,340,000 gas) plus 0.0188 ms (188,000 gas) per item.

Hashes

Time (ms) for the host to perform hashes on inputs of various sizes:

Generate dependency graph

Dependency relations of the crates in this repository are described by the following Graphviz code:

digraph G {
  node [fontname="Helvetica" style=filled fillcolor=yellow];

  account -> ffi;
  account -> storage;
  account -> types;

  bank -> ffi;
  bank -> storage;
  bank -> types;

  taxman -> bank;
  taxman -> ffi;
  taxman -> storage;
  taxman -> types;

  testing -> app;
  testing -> account;
  testing -> bank;
  testing -> crypto;
  testing -> "db/memory";
  testing -> taxman;
  testing -> types;
  testing -> "vm/rust";

  app -> storage;
  app -> types;

  client -> jmt;
  client -> types;

  "db/disk" -> app;
  "db/disk" -> jmt;
  "db/disk" -> types;

  "db/memory" -> app;
  "db/memory" -> jmt;
  "db/memory" -> types;

  ffi -> types;

  jmt -> storage;
  jmt -> types;

  std -> client;
  std -> ffi;
  std -> macros;
  std -> storage;
  std -> testing;
  std -> types;

  storage -> types;

  "vm/rust" -> app;
  "vm/rust" -> crypto;
  "vm/rust" -> types;

  "vm/wasm" -> app;
  "vm/wasm" -> crypto;
  "vm/wasm" -> types;
}

Install Graphviz CLI on macOS:

brew install graphviz

Generate SVG from a file:

dot -Tsvg input.dot

Generate SVG from stdin:

echo 'digraph { a -> b }' | dot -Tsvg > output.svg

Alternatively, use the online visual editor.

Indexed map

An IndexedMap is a map where each record is indexed not only by the primary key, but also by one or more other indexes.

For example, consider limit orders in an oracle-based perpetual futures protocol. For simplicity, let's just think about buy orders:

#![allow(unused)]
fn main() {
struct Order {
    pub trader: Addr,
    pub limit_price: Udec256,
    pub expiration: Timestamp,
}
}

For each order, we generate a unique OrderId, which can be an incrementing number, and store orders in a map indexed by the IDs:

#![allow(unused)]
fn main() {
const ORDERS: Map<OrderId, Order> = Map::new("order");
}

During the block, users submit orders. Then, at the end of the block (utilizing the after_block function), a contract is called to do two things:

• Find all buy orders with limit prices below the oracle price; execute these orders.
• Find all orders with expiration time earlier than the current block time; delete these orders.

To achieve this, the orders need to be indexed by not only the order IDs, but also their limit prices and expiration times.

For this, we can convert Orders to the following IndexedMap:

#![allow(unused)]
fn main() {
#[index_list]
struct OrderIndexes<'a> {
    pub limit_price: MultiIndex<'a, OrderId, Udec256, Order>,
    pub expiration: MultiIndex<'a, OrderId, Timestamp, Order>,
}

const ORDERS: IndexedMap<OrderId, Order, OrderIndexes> = IndexedMap::new("orders", OrderIndexes {
    limit_price: MultiIndex::new(
        |order| *order.limit_price,
        "owners",
        "orders__price",
    ),
    expiration: MultiIndex::new(
        |order| *order.expiration,
        "owners",
        "orders__exp",
    ),
});
}

Here we use MultiIndex, which is an index type where multiple records in the map can have the same index. This is the appropriate choice here, since surely it's possible that two orders have the same limit price or expiration.

However, in cases where indexes are supposed to be unique (no two records shall have the same index), UniqueIndex can be used. It will throw an error if you attempt to save two records with the same index.

To find all orders whose limit prices are below the oracle price:

#![allow(unused)]
fn main() {
fn find_fillable_orders(
    storage: &dyn Storage,
    oracle_price: Udec256,
) -> StdResult<Vec<(OrderId, Order)>> {
    ORDERS
        .idx
        .limit_price
        .range(storage, None, Some(oracle_price), Order::Ascending)
        .map(|item| {
            // This iterator includes the limit price, which we don't need.
            let (_limit_price, order_id, order) = item?;
            Ok((order_id, order))
        })
        .collect()
}
}

Similarly, find and purge all orders whose expiration is before the current block time:

#![allow(unused)]
fn main() {
fn purge_expired_orders(
    storage: &mut dyn Storage,
    block_time: Timestamp,
) -> StdResult<()> {
    // We need to first collect order IDs into a vector, because the iteration
    // holds an immutable reference to `storage`, while the removal operations
    // require a mutable reference to it, which can't exist at the same time.
    let order_ids = ORDERS
        .index
        .expiration
        .range(storage, None, Some(block_time), Order::Ascending)
        .map(|item| {
            let (_, order_id, _) = item?;
            Ok(order_id)
        })
        .collect::<StdResult<Vec<OrderId>>>()?;

    for order_id in order_ids {
        ORDERS.remove(storage, order_id);
    }

    Ok(())
}
}

Liquidity provision

Given a liquidity pool consisting of two assets, A and B, and the invariant $I(A,B)$, where $A$ and $B$ are the amounts of the two assets in the pool (the "pool reserve"). For simplicity, we denote this as $I$.

Suppose a user provides liquidity with amounts $a$ and $b$. After the liquidity is added, the invariant value is $I(A+a,B+b)$. For simplicity, we denote this as $I^{\prime }$.

Suppose before adding the liquidity, the supply of LP token is $L$. We mint user new LP tokens of the following amount:

$$l=(1-f)\left(\frac{I^{\prime }}{I}-1\right)L$$

Here, $f$ is a fee rate we charge on the amount of LP tokens mint. Without this fee, the following exploit would be possible: provide unbalanced liquidity, then immediately withdraw balanced liquidity. This effectively achieves a fee-less swap.

The fee rate should be a function over $(A,B,a,b)$, reflecting how unbalance the user liquidity is:

• If user liquidity is prefectly balanced, that is, $\frac{a}{A}=\frac{b}{B}$, fee rate should be zero: $f(A,B,a,b)=0$.
• If user liquidity is prefertly unbalanced, that is, one-sided (e.g. $a\ne 0$ but $b=0$), then the fee rate should be a value such that if the attack is carried out, the output is equal to doing a swap normally.

Our objective for the rest of this article, is to work out the expression of the fee function $f(A,B,a,b)$.

Fee rate

Consider the case where the user liquidity is unbalanced. Without losing generality, let's suppose $\frac{a}{A}>\frac{b}{B}$. That is, the user provides a more than abundant amount of A, and a less than sufficient amount of B.

Scenario 1

In the first scenario, the user withdraws liquidity immediately after provision. He would get:

$$\frac{l}{L+l}(A+a)$$

$$\frac{l}{L+l}(B+b)$$

Here, $\frac{l}{L+l}$ is the portion of the pool's liquidity owned by the user. We can work out its expression as:

$$\frac{l}{L+l}=\frac{\frac{I^{\prime }}{I}-1}{\frac{I^{\prime }}{I}-f}=\frac{r-1}{r-f}$$

where $r=\frac{I^{\prime }}{I}$, which represents how much the invariant increases as a result of the added liquidity.

Scenario 2

In the second scenario, the user does a swap of $\Delta a$ amount of A into $(1-s)\Delta b$ amount of B, where $s$ is the swap fee rate, which is a constant. The swap must satisfy the invariant:

$$I(A,B)=I(A+\Delta a,B-\Delta b)$$

The user now has $A-\Delta a$ amount of A and $B+(1-s)\Delta b$ amount of B.

As discussed in the previous section, we must choose a fee rate $f$ such that the two scenarios are equivalent. This means the user ends up with the same amount of A and B in both scenarios:

$$\frac{r-1}{r-f}(A+a)=A-\Delta a$$

$$\frac{r-1}{r-f}(B+b)=B+(1-s)\Delta b$$

We can rearrange these into a cleaner form:

$$\frac{A+a}{A-\Delta a}=\frac{B+b}{B+(1-s)\Delta b}$$

$$f=r-(r-1)\frac{A+a}{A-\Delta a}=r-(r-1)\frac{B+b}{B+(1-s)\Delta b}$$

We can use the first equation to work out either $\Delta a$ or $\Delta b$, and put it into the second equation to get $f$.

Xyk pool

The xyk pool has the invariant:

$$I(A,B)=AB$$

Our previous system of equations takes the form:

$$AB=(A+\Delta a)(B-\Delta b)$$

$$\frac{A+a}{A-\Delta a}=\frac{B+b}{B+(1-s)\Delta b}$$

$$f=r-(r-1)\frac{A+a}{A-\Delta a}$$

TODO...

Margin account: health

The dango-lending contract stores a collateral power for each collateral asset, and a Market for each borrowable asset:

#![allow(unused)]
fn main() {
const COLLATERAL_POWERS: Item<BTreeMap<Denom, Udec128>> = Item::new("collateral_power");

const MARKETS: Map<&Denom, Market> = Map::new("market");
}

• An asset may be a collateral asset but not a borrowable asset, e.g. wstETH, stATOM, LP tokens. But typically all borrowable assets are also collateral assets, such that when a margin account borrows an asset, this asset counts both as collateral and debt.
• Collateral powers are to be bounded in the range [0, 1). An asset with lower volatility and more abundant liquidity gets bigger collateral power, vise versa.
• We may store all collateral powers in a single Item<BTreeMap<Denom, Udec128>> if we don't expect to support too many collateral assets.

Suppose:

• a margin account has collateral assets $A_1,A_2,\dots ,A_n$ and debts $B_1,B_2,\dots ,B_m$
• the price of an asset $X$ is $P_X$
• the collateral power of an asset $X$ is $C_X$

The account's utilization is:

$$U=\frac{{\sum }_{j=1}^m{P}_{B_j}{B}_j}{{\sum }_{i=1}^n{C}_{A_i}{P}_{A_i}{A}_i}$$

In the backrun function, the margin account asserts $U\le 1$. If not true, it throws an error to revert the transaction.

The frontend should additionally have a max_ltv, somewhat smaller than 1, such as 95%. It should warn or prevent users from doing anything that results in their utilization going bigger than this, such that their account isn't instantly liquidated.

Math

Rust's primitive number types are insufficient for smart contract use cases, for three main reasons:

1. Rust only provides up to 128-bit integers, while developers often have to deal with 256- or even 512-bit integers. For example, Ethereum uses 256-bit integers to store ETH and ERC-20 balances, so if a chain has bridged assets from Ethereum, their amounts may need to be expressed in 256-bit integers. If the amounts of two such asset are to be multiplied together (which is common in AMMs), 512-bit integers may be necessary.

2. Rust does not provide fixed-point decimal types, which are commonly used in financial applications (we don't want to deal with precision issues with floating-point numbers such as 0.1 + 0.2 = 0.30000000000000004). Additionally, there are concerns over floating-point non-determinism, hence it's often disabled in blockchains.

3. Grug uses JSON encoding for data that go in or out of contracts. However, JSON specification (RFC 7159) only guarantees support for integer numbers up to (2**53)-1. Any number type that may go beyond this limit needs to be serialized to JSON strings instead.

Numbers in Grug

Grug provides a number of number types for use in smart contracts. They are built with the following two primitive types:

It is, however, not recommended to use these types directly. Instead, Grug exports the following type alises:

where {U,I}{256,512} are from the bnum library.

Traits

Nonces and unordered transactions

Nonce is a mechanism to prevent replay attacks.

Suppose Alice sends 100 coins to Bob on a blockchain that doesn't employ such a mechanism. An attacker can observe this transaction (tx) confirmed onchain, then broadcasts it again. Despite the second time this tx is not broadcasted by Alice, it does contain a valid signature from Alice, so it will be accepted again. Thus, total 200 coins would leave Alice's wallet, despite she only consents to sending 100. This can be repeated until all coins are drained from Alice's wallet.

To prevent this,

• each tx should include a nonce, and
• the account should internally track the nonce it expects to see from the next tx.

The first time an account sends a tx, the tx should include a nonce of $0$; the second time, $1$; so on. Suppose Alice's first tx has a nonce of $N$. If the attacker attempts to broadcast it again, the tx would be rejected by the mempool, because Alice's account expects a nonce of $N+1$.

The above describes same-chain replay attack. There is also cross-chain replay attack, where an attacker observes a tx on chain A, and broadcasts it again on chain B. To prevent this, transactions include a chain ID besides nonce.

The problem

The drawback of this naïve approach to handling nonces is it enforces a strict ordering of all txs, which doesn't do well in use cases where users are expected to submit txs with high frequency. Consider this situation:

• Alice's account currently expects a nonce of $N$;
• Alice sends a tx (let's call this tx A) with nonce $N$;
• Alice immediately sends another tx (B) with nonce $N+1$;
• due to network delays, tx B arrives on the block builder earlier than A.

Here, the block builder would reject tx B from entering the mempool, because it expects a nonce of $N$, while tx B comes with $N+1$. When tx A later arrives, it will be accepted. The result is Alice submits two txs, but only one makes it into a block.

Imagine Alice is trading on an order book exchange and wants to cancel two active limit orders. These actions are not correlated – there's no reason we must cancel one first then the other. So Alice click buttons to cancel the two in quick succession. However, only one ends up being canceled; she has to retry canceling the other one. Bad UX!

HyperLiquid's solution

As described here.

In HyperLiquid, an account can have many session keys, each of which has its own nonce. In our case, to simplify things, let's just have one nonce for each account (across all session keys).

Instead of tracking a single nonce, the account tracks the most recent $X$ nonces it has seen (let's call these the SEEN_NONCES). HyperLiquid uses $X=20$, while for simplicity in the discussion below let's use $X=5$.

Suppose Alice's account has the following SEEN_NONCES: $[5,6,7,9,10]$. $8$ is missing because it got lost due to network problems.

Now, Alice broadcasts two txs in quick succession, with nonces $11$ and $12$. Due to network delays, $12$ arrives at the block builder first.

The account will carry out the following logic:

• accept the tx if its nonce is newer than the oldest nonce in SEEN_NONCES, and not already in SEEN_NONCES;
• insert the tx's nonce into SEEN_NONCES.

When $12$ arrives first, it's accepted, and SEEN_NONCES is updated to: $[6,7,9,10,12]$. ($5$ is removed because we only keep the most recent $X=5$ nonces.)

When $11$ arrives later, it's also accepted, with SEEN_NONCES updated to: $[7,9,10,11,12]$.

This solves the UX problem we mentioned in the previous section.

Transaction expiry

Now suppose tx $8$ finally arrives. Since it was created a long while ago, it's most likely not relevant any more. However, following the account's logic, it will still be accepted.

To prevent this, we should add an expiry parameter into the tx metadata. If the expiry is earlier than the current block time, the tx is rejected, regardless of the nonce rule.

expiry can be either a block height or timestamp. For Dango's use case, timestamp probably makes more sense.

Transaction lifecycle

A Grug transaction (tx) is defined by the following struct:

#![allow(unused)]
fn main() {
struct Tx {
    pub sender: Addr,
    pub gas_limit: u64,
    pub msgs: Vec<Message>,
    pub data: Json,
    pub credential: Json,
}
}

Explanation of the fields:

Sender

The account that sends this tx, who will perform authentication and (usually) pay the tx fee.

Gas limit

The maximum amount of gas requested for executing this tx.

If gas of this amount is exhausted at any point, execution is aborted and state changes discarded.¹

Messages

A list of Messages to be executed.

They are executed in the specified order and atomically, meaning they either succeed altogether, or fail altogether; a single failed message failing leads to the entire tx aborted.²

Data

Auxilliary data to attach to the tx.

An example use case of this is if the chain accepts multiple tokens for fee payment, the sender can specify here which denom to use:

{
  "data": {
    "fee_denom": "uatom"
  }
}

The taxman contract, which handles fees, should be programmed to deserialize this data, and use appropriate logics to handle the fee (e.g. swap the tokens on a DEX).

Credential

An arbitrary data to prove the tx was composed by the rightful owner of the sender account. Most commonly, this is a cryptographic signature.

Note that data is an opaque grug::Json (which is an alias to serde_json::Value) instead of a concrete type. This is because Grug does not attempt to intrepret or do anything about the credential. It's all up to the sender account. Different accounts may expect different credential types.

Next we discuss the full lifecycle of a transaction.

Simulation

The user have specified sender, msgs, and data fields by interacting with a webapp. The next step now is to determine an appropriate gas_limit.

For some simple txs, we can make a reasonably good guess of gas consumption. For example, a tx consisting of a single Message::Transfer of a single coin should consume just under 1,000,000 gas (of which 770,000 is for Secp256k1 signature verification).

However, for more complex txs, it's necessary to query a node to simulate its gas consumption.

To do this, compose an UnsignedTx value:

#![allow(unused)]
fn main() {
struct UnsignedTx {
    pub sender: Addr,
    pub msgs: Vec<Message>,
    pub data: Json,
}
}

which is basically Tx but lacks the gas_limit and credential fields.

Then, invoke the ABCI Query method with the string "/simulate" as path:

• Using the Rust SDK, this can be done with the grug_sdk::Client::simulate method.
• Using the CLI, append the --simulate to the tx subcommand.

The App will run the entire tx in simulation mode, and return an Outcome value:

#![allow(unused)]
fn main() {
struct Outcome {
    pub gas_limit: Option<u64>,
    pub gas_used: u64,
    pub result: GenericResult<Vec<Event>>,
}
}

This includes the amount of gas used, and if the tx succeeded, the events that were emitted; or, in case the tx failed, the error message.

Two things to note:

• In simulation mode, certain steps in authentication are skipped, such as signature verification (we haven't signed the tx yet at this point). This means gas consumption is underestimated. Since we know an Secp256k1 verification costs 770,000 gas, it's advisable to add this amount manually.
• The max amount of gas the simulation can consume is the node's query gas limit, which is an offchain parameter chosen individually by each node. If the node has a low query gas limit (e.g. if the node is not intended to serve heavy query requests), the simulation may fail.

CheckTx

Now we know the gas limit, the user will sign the tx, and we create the Tx value and broadcast it to a node.

Tendermint will now call the ABCI CheckTx method, and decide whether to accept the tx into mempool or not, based on the result.

When serving a CheckTx request, the App doesn't execute the entire tx. This is because while some messages may fail at this time, they may succeed during FinalizeBlock, as the chain's state would have changed.

Therefore, instead, the App only performs the first two steps:

1. Call the taxman's withhold_fee method. This ensures the tx's sender has enough fund to afford the tx fee.
2. Call the sender's authenticate method in normal (i.e. non-simulation) mode. Here the sender performs authentication (which is skipped in simulation mode).

Tendermint will reject the tx if CheckTx fails (meaning, either withfold_fee or authenticate fails), or if the tx's gas limit is bigger than the block gas limit (it can't fit in a block). Otherwise, it's inserted into the mempool.

FinalizeBlock

In FinalizeBlock, the entire tx processing flow is performed, which is:

1. Call taxman's withhold_fee method.

   This MUST succeed (if it would fail, it should have failed during CheckTx such that the tx is rejected from entering mempool). If does fail for some reason (e.g. a previous tx in the block drained the sender's wallet, so it can no longer affored the fee), the processing is aborted and all state changes discarded.

2. Call sender's authenticate method.

   If fails, discard state changes from step 2 (keeping those from step 1), then jump to step 5.

3. Loop through the messages, execute one by one.

   If any fails, discard state changes from step 2-3, then jump to step 5.

4. Call sender's backrun method.

   If fails, discard state changes from step 2-4, then jump to step 5.

5. Call taxman's finalize_fee method.

   This MUST succeed (the bank and taxman contracts should be programmed in a way that ensures this). If it does fail for some reason, discard all state changes for all previous steps and abort.

TODO: make a flow chart

Summary

1. Transaction fee is still deducted. See the discussion on fee handling later in the article. ↩

2. This said, a SubMessage can fail without aborting the tx, if it's configured as such (with SubMessage::reply_on set to ReplyOn::Always or ReplyOn::Error). ↩

Networks

Dango mainnet, testnets, and devnets.

How to spin up a devnet

Prerequisites

• Linux (we use Ubuntu 24.04)
• Docker
• Rust 1.80+
• Go

Steps

1. Compile dango:

   git clone https://github.com/left-curve/left-curve.git
   cd left-curve
   cargo install --path dango/cli
   dango --version
   

2. Compile cometbft:

   git clone https://github.com/cometbft/cometbft.git
   cd cometbft
   make install
   cometbft version
   

3. Initialize the ~/.dango directory:

   dango init
   

4. Initialize the ~/.cometbft directory:

   cometbft init
   

5. Create genesis state. Provide chain ID and genesis time as positional arguments:

   cd left-curve
   cargo run -p dango-genesis --example build_genesis -- dev-5 2025-02-25T21:00:00Z
   

   Genesis should be written into ~/.cometbft/config/genesis.json

6. Create systemd service for postgresql:

   [Unit]
   Description=PostgreSQL
   After=network.target
   
   [Service]
   Type=simple
   User=larry
   Group=docker
   WorkingDirectory=/home/larry/workspace/left-curve/indexer
   ExecStart=/usr/bin/docker compose up db
   ExecStop=/usr/bin/docker compose down db
   
   [Install]
   WantedBy=multi-user.target
   

   Save this as /etc/systemd/system/postgresql.service.

   Notes:

   • WorkingDirectory should be the directory where the docker-compose.yml is located.

   • The User should be added to the docker group:

     sudo usermod -aG docker larry
     

7. Create systemd service for dango:

   [Unit]
   Description=Dango
   After=network.target
   
   [Service]
   Type=simple
   User=larry
   ExecStart=/home/larry/.cargo/bin/dango start
   
   [Install]
   WantedBy=multi-user.target
   

   Save this as /etc/systemd/system/dango.service.

8. Create systemd service for cometbft:

   [Unit]
   Description=CometBFT
   After=network.target
   
   [Service]
   Type=simple
   User=larry
   ExecStart=/home/larry/.go/bin/cometbft start
   
   [Install]
   WantedBy=multi-user.target
   

   Save this as /etc/systemd/system/cometbft.service.

9. Refresh systemd:

   sudo systemctl daemon-reload
   

10. Start postgresql:

    sudo systemctl start postgresql
    

11. Create database for the indexer:

    cd left-curve/indexer
    createdb -h localhost -U postgres grug_dev
    

12. Start dango:

    sudo systemctl start dango
    

13. Start cometbft:

    sudo systemctl start cometbft
    

    Note: when starting, start in this order: postgresql, dango, cometbft. When terminating, do it in the reverse order.

Killing existing devnet and start a new one

1. Stop dango and cometbft services (no need to stop postgresql):

   sudo systemctl stop cometbft
   sudo systemctl stop dango
   

2. Reset cometbft:

   cometbft unsafe-reset-all
   

3. Reset dango:

   dango db reset
   

4. Reset indexer DB:

   dropdb -h localhost -U postgres grug_dev
   createdb -h localhost -U postgres grug_dev
   

5. Delete indexer saved blocks:

   rm -rfv ~/.dango/indexer
   

6. Restart the services:

   sudo systemctl start dango
   sudo systemctl start cometbft
   

Test accounts

Each devnet comes with 10 genesis users: owner and user{1-9}. They use Secp256k1 public keys derived from seed phrases with derivation path m/44'/60'/0'/0/0.

Do NOT use these keys in production!!!

dev-1

• Genesis time: 6 October 2024
• Commit: e450584
• Docker image: leftcurve/devnet:0.1.0

dev-2

• Genesis time: 12 October 2024
• Commit: 1f62285
• Docker image: leftcurve/devnet:0.2.0

dev-3

We're no longer using Docker for devnets starting from this one.

• Genesis time: 19 November 2024
• Dango version: 1dc94ce
• Cometbft version: 0.38.15+e8eb5bdc0

dev-4

We're no longer using Docker for devnets starting from this one.

• Genesis time: 14 January 2025
• Dango version: 379cde3
• Cometbft version: 0.38.16+84f981e93

dev-5

• Genesis time: 25 February 2025
• Dango version: 75a9966
• Cometbft version: 0.38.17+d03254d35