Mangrove Summary

• Mangrove holds offer lists for outbound_tkn,inbound_tkn pairs with a given tickSpacing.
• Offers are sorted in a tree (the “tick tree”) where each available price point (a bin) holds a doubly linked list of offers.
• Each offer promises outbound_tkn and requests inbound_tkn.
• Each offer has an attached maker address.
• When an offer is executed, Mangrove does the following:
  1. Flashloan some inbound_tkn to the offer’s maker.
  2. Call an arbitrary execute function on that address.
  3. Transfer back some outbound_tkn.
  4. Call back the maker so they can update their offers.

Let the devs know about any error, typo etc, by contacting devs@mangrove.exchange

More documentation / discussions can be found at https://docs.mangrove.exchange/.

There is one Mangrove contract that manages all tradeable offer lists. This reduces deployment costs for new offer lists and lets market makers have all their provision for all offer lists in the same place.

The interaction map between the different actors is as follows:

The sequence diagram of a market order is as follows:

Ratio and price

In the comments, we use the word ‘price’ to refer to the ratio between the amount promised by an offer and the amount it requests in return. In the code however, we use the generic word ratio to avoid confusion with notions of price based on concepts such as ‘quote’ and ‘base’ tokens, etc.

The unit of price (and ratio) is inbound_tkn/outbound_tkn.

tickSpacing

The granularity of available price points in an offer list is controlled by the tickSpacing parameter. With a high tickSpacing, fewer price points are available, but the gas cost of market orders is lower since a smaller part of the tick tree has to be explored.

The available prices in an offer list are 1.0001^i for all MIN_TICK <= i <= MAX_TICK such that i % tickSpacing = 0.

Tree storage

Offers are stored in a tree we call a “tick tree”. Thanks to this tree structure, offer operations (insert, update, and retract) take constant time (the height of the tree is fixed).

Bins

Below the bottom of the tree are bins. A bin is a doubly linked list of offers. All offers in a bin have the same tick. During a market order, offers in a bin are executed in order, from the first to the last. Inserted offers are always appended at the end of a bin.

Bins are laid in sequence. In the context of an offer list, each bin has an associated tick (and a tick determines a price). If a bin has tick t, the following bin has tick t+tickSpacing.

Bins are identified by their index in the bin sequence, from the first (MIN_BIN) to the last (MAX_BIN). The number of available bins is larger than the number of available ticks, so some bins will never be used.

Tree structure

The structure of the tick tree is as follows:

At the bottom of the tree, leaves contain information about 4 bins: their first and last offer. Offer ids use 32 bits, so leaves use 256 bits.

When a market order runs, execution starts with the first offer of the lowest-numbered nonempty bin and continues from there.

Once all the offers in the smallest bin have been executed, the next non-empty bin is found. If the leaf of the current bin now only has empty bins, the tree must be searched for the next non-empty bin, starting at the node above the leaf:

A non-leaf node contains a bit field with information about all its children: if the ith bit of the node is set, its ith child has at least one non-empty bin. Otherwise, its ith child only has empty bins.

To find the next non-empty bin, it may be necessary to keep going up the tree until the root is reached. At each level above, the bit field rule applies similarly: the ith bit of a node is set iff its ith child has at least one set bit.

Once a node with a set bit is found, its rightmost nonempty child is examined, and so on until the next nonempty bin is reached, and the first offer of that bin gets executed.

Caching

At any time, if there is at least one offer in the offer list, the best offer is the first offer of the bin containing the cheapest offers; and that bin is the best bin. Its parent is the best level3, whose parent is the best level2, and whose parent is the best level1 (whose parent is the root).

The root, the best level1, the best level2, and the best level3 are always stored in local. The position of the best bin in the best leaf is also stored in local.

This data is useful for two things:

• Read and modify the tree branch of the best offer without additional storage reads and writes (except for modifying the best leaf).
• Know the price of the best offer without an additional storage read (it can be computed using the set bit positions in each level, the position of the best bin in the best leaf, and the value of tickSpacing).

The structure of the local config is as follows:

This caching means that as the price oscillates within a more restricted range, fewer additional storage read/writes have to be performed (as most of the information is available in local) when there is a market order or an offer insertion/update.

Some numbers

Here are some useful numbers, for reference:

Preprocessing

The current file (structs.js) is used in Structs.pre.sol (not shown here) to generate the libraries in Struct.pre.sol. Here is an example of js struct specification and of a generated library:

struct_defs = {
universe: [
 {name: "serialnumber", bits: 16, type: "uint"},
 {name: "hospitable",bits: 8, type:"bool"}
]
}

The generated file will store all data in a single EVM stack slot (seen as an abstract type <TypeName> by Solidity); here is a simplified version:

struct UniverseUnpacked {
uint serialnumber;
bool hospitable;
}

library Library {
// use Solidity 0.8* custom types
type Universe is uint;

// test word equality
function eq(Universe ,Universe) returns (bool);

// word <-> struct conversion
function to_struct(Universe) returns (UniverseUnpacked memory);
function t_of_struct(UniverseUnpacked memory) returns (Universe);

// arguments <-> word conversion
function unpack(Universe) returns (uint serialnumber, bool hospitable);
function pack(uint serialnumber, bool hospitable) returns(Universe);

// read and write first property
function serialnumber(Universe) returns (uint);
function serialnumber(Universe,uint) returns (Universe);

// read and write second property
function hospitable(Universe) returns (bool);
function hospitable(Universe,bool) returns (Universe);
}

Then, in Solidity code, one can write:

Universe uni = UniverseLib.pack(32,false);
uint num = uni.serialnumber();
uni.hospitable(true);

Data structures

Struct-like data structures are stored in storage and memory as 256 bits words. We avoid using structs due to significant gas savings gained by extracting data from words only when needed. This is exacerbated by the fact that Mangrove uses one recursive call per executed offer; it is much cheaper to accumulate used stack space than memory space throughout the recursive calls.

The generation is defined in lib/preproc.ts.

Struct fields that are common to multiple structs are factored here. Multiple field names refer to offer identifiers, so the id_field is a function that takes a name as argument and returns a field with the right size & type.

Structs

Offer

Offers hold doubly linked list pointers to their prev and next offers, as well as price and volume information. 256 bits wide, so one storage read is enough. They have the following fields:

• prev points to immediately better offer at the same price point, if any, and 0 if there is none. 32 bits wide.

• next points to immediately worse offer at the same price point, if any, and 0 if there is none. 32 bits wide.

• tick is the log base 1.0001 of the price of the offer. 21 bits wide.

• gives is the amount of outbound_tkn the offer will give if successfully executed. 127 bits wide.

OfferDetail

OfferDetails hold the maker’s address and provision/penalty-related information. They have the following fields:

• maker is the address that created the offer. It will be called when the offer is executed and later during the posthook phase.

• gasreq gas will be provided to execute. 24 bits wide, i.e. around 16M gas. Note that if more room was needed, we could bring it down to 16 bits and have it represent 1k gas increments.

• kilo_offer_gasbase represents the gas overhead used by processing the offer inside Mangrove + the overhead of initiating an entire order, in 1k gas increments.

The gas considered ‘used’ by an offer is the sum of

• gas consumed during the call to the offer
• kilo_offer_gasbase * 1e3

(There is an inefficiency here. The overhead could be split into an “offer-local overhead” and a “general overhead”. That general overhead gas penalty could be spread between all offers executed during an order, or all failing offers. It would still be possible for a cleaner to execute a failing offer alone and make them pay the entire general gas overhead. For the sake of simplicity we keep only one “offer overhead” value.)

If an offer fails, gasprice Mwei is taken from the provision per unit of gas used. gasprice should approximate the average gas price at offer creation time.

kilo_offer_gasbase is the actual field name, is 9 bits wide, and represents 1k gas increments. The accessor offer_gasbase returns kilo_offer_gasbase * 1e3.

kilo_offer_gasbase is also the name of a local Mangrove parameter. When an offer is created, its current value is copied from Mangrove local configuration. The maker does not choose it.

So, when an offer is created, the maker is asked to provision the following amount of wei:

(gasreq + offer_gasbase) * gasprice * 1e6

where offer_gasbase and gasprice are Mangrove’s current configuration values (or a higher value for gasprice if specified by the maker).

When an offer fails, the following amount is given to the taker as compensation:

(gasused + offer_gasbase) * gasprice * 1e6

where offer_gasbase and gasprice are Mangrove’s current configuration values. The rest is given back to the maker.

• gasprice is in Mwei/gas and 26 bits wide, which accommodates 0.001 to ~67k gwei / gas. gasprice is also the name of a global Mangrove parameter. When an offer is created, the offer’s gasprice is set to the max of the user-specified gasprice and Mangrove’s global gasprice.

Global Configuration

Configuration information for an offer list is split between a global struct (common to all offer lists) and a local struct specific to each offer list. Global configuration fields are:

• The monitor can provide real-time values for gasprice and density to Mangrove. It can also receive liquidity event notifications.

• If useOracle is true, Mangrove will use the monitor address as an oracle for gasprice and density, for every outbound_tkn/inbound_tkn pair, except if the oracle-provided values do not pass a check performed by Mangrove. In that case the oracle values are ignored.

• If notify is true, Mangrove will notify the monitor address after every offer execution.

• The gasprice is the amount of penalty paid by failed offers, in Mwei per gas used. gasprice should approximate the average gas price and will be subject to regular updates.

• gasmax specifies how much gas an offer may ask for at execution time. An offer which asks for more gas than the block limit would live forever on the book. Nobody could take it or remove it, except its creator (who could cancel it). In practice, we will set this parameter to a reasonable limit taking into account both practical transaction sizes and the complexity of maker contracts.

• dead: if necessary, Mangrove can be entirely deactivated by governance (offers can still be retracted and provisions can still be withdrawn). Once killed, Mangrove must be redeployed; It cannot be resurrected.

• maxRecursionDepth is the maximum number of times a market order can recursively execute offers. This is a protection against stack overflows.

• maxGasreqForFailingOffers is the maximum gasreq failing offers can consume in total. This is used in a protection against failing offers collectively consuming the block gas limit in a market order. Setting it too high would make it possible for successive failing offers to consume up to that limit then trigger a revert (thus the failing offer would not be removed). During a market order, Mangrove keeps a running sum of the gasreq of the failing offers it has executed and stops the market order when that sum exceeds maxGasreqForFailingOffers.

Local configuration

• An offer list is not active by default, but may be activated/deactivated by governance.

• fee, in basis points, of outbound_tkn given to the taker. This fee is sent to Mangrove. Fee is capped to ~2.5%.

• density is similar to a ‘dust’ parameter. We prevent spamming of low-volume offers by asking for a minimum ‘density’ in outbound_tkn per gas requested. For instance, if density is worth 10, offer_gasbase == 5000, an offer with gasreq == 30000 must promise at least 10 × (30000 + 5000) = 350000 outbound_tkn. 9 bits wide.

We store the density as a float with 2 bits for the mantissa, 7 for the exponent, and an exponent bias of 32, so that density ranges from $2^{-32}$ to $1.75 \times 2^{95}$. For more information, see DensityLib.

To save gas, Mangrove caches the entire tick tree branch of the bin that contains the best offer in each offer list’s local parameter. Taken together, binPosInLeaf, level3, level2, level1, and root provide the following info:

• What the current bin is (see BinLib.bestBinFromLocal)
• When a leaf is emptied and the next offer must be fetched, the information in the fields level3, level2, level1 and root avoid multiple storage reads

• offer_gasbase represents the gas overhead used by processing the offer inside Mangrove + the overhead of initiating an entire order. Mangrove considers that a failed offer has used at least offer_gasbase gas. The actual field name is kilo_offer_gasbase and the accessor offer_gasbase returns kilo_offer_gasbase*1e3. Local to an offer list, because the costs of calling outbound_tkn and inbound_tkn’s transferFrom are part of offer_gasbase. Should only be updated when ERC20 contracts change or when opcode prices change.

• If lock is true, orders may not be added nor executed, nor the offer list read by external contracts.

Reentrancy during offer execution is not considered safe:

• during execution, an offer could consume other offers further up in the list, effectively front-running the taker currently executing the offer.
• it could also cancel other offers, creating a discrepancy between the advertised and actual market price at no cost to the maker.
• a maker could potentially distinguish between a clean and a market order based on the current state of the offer list

Note: An optimization in the marketOrder function relies on reentrancy being forbidden.

• last is a counter for offer ids, incremented every time a new offer is created. It can’t go above $2^{32}-1$.

Import additional libraries for Local and LocalExtra.

Globally enable global.method(…)

The constants below are written as literals to optimize gas. For all the relevant constants here, the non-literal expression that computes them is checked in Constants.t.sol.

sizes must match field sizes in structs.ts where relevant

Number of bits used to represent a tick

Number of bits used to represent an offer id

Maximum possible size of a field – protects against wrong code changes. Constraint given by BitLib.ctz64.

X_SIZE_BITS is 1+log2 of the size of X, where size is the number of elements it holds.In a field, an element is a bit; in a leaf, an element is a pair of offer ids. For LEVELs and ROOT, the value must be exact, so only power-of-2 sizes are allowed.

X_SIZE is 2**X_SIZE_BITS

X_SIZE_MASK is 0...01...1 where the number of 1s is X_SIZE_BITS

0...01...1 with OFFER_BITS 1s at the end

Same as ROOT_SIZE

Same as NUM_LEVEL1 * LEVEL_SIZE

Same as NUM_LEVEL2 * LEVEL_SIZE

Same as NUM_LEVEL3 * LEVEL_SIZE

Same as NUM_LEAFS * LEAF

min and max bins are defined like min and max int.

The tick range is the largest such that the mantissa of 1.0001^MAX_TICK fits on 128 bits (and thus can be multiplied by volumes).

These are reference values for what the function tickFromRatio function will return, not the most possible accurate values for the min and max tick.

MANTISSA_BITS is the number of bits used in the mantissa of normalized floats that represent ratios. 128 means we can multiply all allowed volumes by the mantissa and not overflow.

With |tick|<=887272 and normalized mantissas on 128 bits, the maximum possible mantissa is 340282295208261841796968287475569060645, so the maximum safe volume before overflow is NO_OVERFLOW_AMOUNT = 340282438633630198193436196978374475856 (slightly above 2**128).

For ease of use, we could pick a simpler, slightly smaller max safe volume: (1<<128)-1.

However the *ByVolume functions get a price by (abstractly) performing outboundAmount/inboundAmount. If we limit all volumes to NO_OVERFLOW_AMOUNT but aren’t more restrictive than that, since type(uint128).max > 1.0001**MAX_TICK, we will get ratios that are outside the price boundaries.

We thus pick a uniform, easy to remember constraint on volumes that works everywhere: (1<<127)-1

When a market order consumes offers, the implementation uses recursion consumes additional EVM stack space at each new offer. To avoid reverting due to stack overflow, Mangrove keeps a counter and stops the market order when it reaches a maximum recursion depth. INITIAL_MAX_RECURSION_DEPTH is the maximum recursion depth given at deployment time.

See maxRecursionDepth in structs.ts

Without optimizer enabled it fails above 79. With optimizer and 200 runs it fails above 80. Set default a bit lower to be safe.

When a market order consumes offers, it may use gas on offers that fail to deliver. To avoid reverts after a string of failing offers that consumes more gas than is available in a block, Mangrove stops a market order after it has gone through failing offers such that their cumulative gasreq is greater than the global maxGasreqForFailingOffers parameter. At deployment, maxGasreqForFailingOffers is set to:

INITIAL_MAX_GASREQ_FOR_FAILING_OFFERS_MULTIPLIER * gasmax

Those two constants are used in TickLib.ratioFromTick to convert a log base 1.0001 to a log base 2.

MgvLib contains data structures returned by external calls to Mangrove and the interfaces it uses for its own external calls.

OLKey (for “OfferListKey”) contains the information that characterizes an offer list:

• outbound_tkn, token that goes from the maker to the taker (to remember the direction, imagine the token as going out of the Mangrove offer, towards the taker)
• inbound_tkn, token that goes from the taker to the maker (to remember the direction, imagine the token as going into Mangrove from the taker)
• tickSpacing, how many ticks should be jumped between available price points. More volatile outbound/inbound pairs should have a larger tickSpacing.

Globally enable olKey.method(...)

The id of an OLKey should be keccak256(abi.encode(olKey)) To save gas, id() directly hashes the memory (which matches the ABI encoding; there is a fuzz test on that). If the memory layout changes, this function must be updated.

Creates a flipped copy of the olKey with same tickSpacing.

Convert tick to bin according to olKey.tickSpacing

Convert bin to tick according to olKey.tickSpacing

Structs

The structs defined in structs.js have their counterpart as solidity structs that are easy to manipulate for outside contracts / callers of view functions.

Some miscellaneous data types useful to Mangrove and external contracts

SingleOrder holds data about an order-offer match in a struct. Used by marketOrder (and some of its nested functions) to avoid stack too deep errors. It is used in market order and cleaning.

The offer given to the maker will be cleaned of prev/next pointers.

takerWants/takerGives mutate over execution. Initially the wants/gives from the taker’s pov, then actual wants/gives adjusted by offer’s price and volume.

offerDetail is only populated when necessary.

The local given to the maker will be cleaned of tick tree information.

OrderResult holds additional data for the maker and is given to them after they fulfilled an offer. It gives them their own returned data from the previous call and an mgvData specifying whether Mangrove encountered an error.

makerData holds a message that was either returned by the maker or passed as revert message at the end of the trade execution

mgvData is an internal Mangrove status code code.

CleanTarget holds data about an offer that should be cleaned, i.e. made to fail by executing it with the specified volume. It is used in MgvOfferTaking.cleanByImpersonation.

Events

The events emitted are listed here:

Events in solidity is a hard thing to do in a optimal way. If you look at it as a purely gas efficient issue, you want to emit as few events as possible and with as few fields as possible. But as events also has to be usable for an off chain user, then doing this is not always the best solution.

We tried to list the main forces that drive which events and data to emit:

1. Use as little gas as possible.
2. An indexer should be able to keep track of the state of Mangrove.
3. Doing RPC calls directly, should be able to find offers and other information based on offer list, maker, taker, offer id, etc.

These forces are in conflict and it is impossible to find a solution that is optimal for all three. The following events are therefore an attempt to balance the trade-offs.

Mangrove Creation

Emitted at the creation of the new Mangrove contract

Mangrove adds or removes wei from maker’s account

• Credit event occurs when an offer is removed from Mangrove or when the fund function is called This is emitted when a user’s account on Mangrove is credited with some native funds, to be used as provision for offers.

It emits the maker’s address and the amount credited

The maker address is indexed so that we can filter on it when doing RPC calls.

These are the scenarios where it can happen:

• Fund Mangrove directly
• Fund Mangrove when posting an offer
• When updating an offer
  • Funding Mangrove or
  • the updated offer needs less provision, than it already has. Meaning the user gets credited the difference.
• When retracting an offer and deprovisioning it. Meaning the user gets credited the provision that was locked by the offer.
• When an offer fails. The remaining provision gets credited back to the maker

A challenge for an indexer is to know how much provision each offer locks. With the current events, an indexer is going to have to know the liveness, gasreq and gasprice of the offer. If the offer is not live, then also know if it has been deprovisioned. And know what the gasbase of the offer list was when the offer was posted. With this information an indexer can calculate the exact provision locked by the offer.

The indexer also cannot deduce what scenario the credit event happened. E.g., we don’t know if the credit event happened because an offer failed or because the user simply funded Mangrove.

• Debit event occurs when an offer is posted or when the withdraw function is called This is emitted when a user’s account on Mangrove is debited with some native funds.

It emits the maker’s address and the amount debited.

The maker address is indexed so that we can filter on it when doing RPC calls.

These are the scenarios where it can happen:

• Withdraw funds from Mangrove directly
• When posting an offer. The user gets debited the provision that the offer locks.
• When updating an offer and it requires more provision that it already has. Meaning the user gets debited the difference.

Same challenges as for Credit

Mangrove reconfiguration

This event is emitted when an offer list is activated or deactivated. Meaning one half of a market is opened.

It emits the olKeyHash and the boolean value. By emitting this, an indexer will be able to keep track of what offer lists are active and what their hash is.

The olKeyHash and both token addresses are indexed, so that we can filter on it when doing RPC calls.

This event is emitted when the fee of an offer list is changed.

It emits the olKeyHash and the value. By emitting this, an indexer will be able to keep track of what fee each offer list has.

The olKeyHash is indexed, so that we can filter on it when doing RPC calls.

This event is emitted when the gasbase of an offer list is changed.

It emits the olKeyHash and the offer_gasbase. By emitting this, an indexer will be able to keep track of what gasbase each offer list has.

The olKeyHash is indexed, so that we can filter on it when doing RPC calls.

This event is emitted when the governance of Mangrove is set.

It emits the governance address. By emitting this, an indexer will be able to keep track of what governance address Mangrove has.

No fields are indexed as there is no need for RPC calls to filter on this.

This event is emitted when the monitor address of Mangrove is set. Be aware that the address for Monitor is also the address for the oracle.

It emits the monitor / oracle address. By emitting this, an indexer will be able to keep track of what monitor/oracle address Mangrove use.

No fields are indexed as there is no need for RPC calls to filter on this.

This event is emitted when the configuration for whether to use an oracle or not is set.

It emits the useOracle, which is a boolean value, that controls whether or not Mangrove reads its gasprice and density from an oracle or uses its own local values. By emitting this, an indexer will be able to keep track of if Mangrove is using an oracle.

No fields are indexed as there is no need for RPC calls to filter on this.

This event is emitted when the configuration for notify on Mangrove is set.

It emits a boolean value, to tell whether or not notify is active. By emitting this, an indexer will be able to keep track of whether or not Mangrove notifies the Monitor/Oracle when and offer is taken, either successfully or not.

No fields are indexed as there is no need for RPC calls to filter on this.

This event is emitted when the gasmax of Mangrove is set.

It emits the gasmax. By emitting this, an indexer will be able to keep track of what gasmax Mangrove has. Read more about Mangroves gasmax on docs.mangrove.exchange

No fields are indexed as there is no need for RPC calls to filter on this.

This event is emitted when the density of an offer list is changed.

It emits the olKeyHash and the density. By emitting this, an indexer will be able to keep track of what density each offer list has.

The olKeyHash is indexed, so that we can filter on it when doing RPC calls.

This event is emitted when the max recursion depth of Mangrove is set.

It emits the max depth value. By emitting this, an indexer will be able to keep track of what max recursion depth Mangrove has. Read more about Mangroves max recursion depth on docs.mangrove.exchange

This event is emitted when the max gasreq for failing offers of Mangrove is set.

It emits the max gasreq for failing offers value. By emitting this, an indexer will be able to keep track of what max gasreq for failing offers Mangrove has. Read more about Mangroves max gasreq for failing offers on docs.mangrove.exchange

This event is emitted when the gasprice of Mangrove is set.

It emits the gasprice. By emitting this, an indexer will be able to keep track of what gasprice Mangrove has. Read more about Mangroves gasprice on docs.mangrove.exchange

No fields are indexed as there is no need for RPC calls to filter on this.

Clean order execution

This event is emitted when a user tries to clean offers on Mangrove, using the build in clean functionality.

It emits the olKeyHash, the taker address and offersToBeCleaned, which is the number of offers that should be cleaned. By emitting this event, an indexer can save what offer list the user is trying to clean and what taker is being used. This way it can keep a context for the following events being emitted (Just like OrderStart). The offersToBeCleaned is emitted so that an indexer can keep track of how many offers the user tried to clean. Combining this with the amount of OfferFail events emitted, then an indexer can know how many offers the user actually managed to clean. This could be used for analytics.

The fields olKeyHash and taker are indexed, so that we can filter on them when doing RPC calls.

This event is emitted when a Clean operation is completed.

It does not emit any fields. This event is only needed in order to know that the clean operation is completed. This way an indexer can know exactly in what context we are in. It could emit the total bounty received, but in order to know who got the bounty, an indexer would still be needed or we would have to emit the taker address as well, in order for an RPC call to find the data. But an indexer would still be able to find this info, by collecting all the previous events. So we do not emit the bounty.

Market order execution

This event is emitted when a market order is started on Mangrove.

It emits the olKeyHash, the taker, the maxTick, fillVolume and fillWants.

The fields olKeyHash and taker are indexed, so that we can filter on them when doing RPC calls.

By emitting this an indexer can keep track of what context the current market order is in. E.g. if a user starts a market order and one of the offers taken also starts a market order, then we can in an indexer have a stack of started market orders and thereby know exactly what offer list the order is running on and the taker.

By emitting maxTick, fillVolume and fillWants, we can now also know how much of the market order was filled and if it matches the price given. See OrderComplete for more.

This event is emitted when a market order is finished.

It emits olKeyHash, the taker and the total fee paid. We need this event, in order to know that a market order is completed. This way an indexer can know exactly in what context we are in. The total fee paid for that market order, is needed, as we do not emit this any other places. The fields olKeyHash and taker is not needed for an indexer, but they are emitted and indexed in order for RPC calls to filter and find the fee.

Offer execution

This event is emitted when an offer is successfully taken. Meaning both maker and taker has gotten their funds.

It emits the olKeyHash, taker address, the offerId and the takerWants and takerGives that the offer was taken at. Just as for OfferFail, the olKeyHash and taker are not needed for an indexer to work, but are needed for RPC calls. olKeyHash taker and id are indexed so that we can filter on them when doing RPC calls. As maker can be a strategy and not the actual owner, then we chose not to emit it here and to mark the field id indexed, the strat should emit the relation between maker and offerId. This way you can still by RPC calls find the relevant offer successes So they are emitted and indexed for that reason. Just like OfferFail this event is emitted during posthook end, so it is emitted in reverse order compared to what order they are taken. This event could be emitted at offer execution, but for consistency we emit it at posthook end.

If the posthook of the offer fails. Then we emit OfferSuccessWithPosthookData instead of just OfferSuccess. This event has one extra field, which is the reason for the posthook failure. By emitting the posthook data, an indexer can keep track of the reason posthook fails, this could for example be used for analytics.

By emitting offerId, wants and gives, an indexer can keep track of whether the offer was partially or fully taken, by looking at the what the offer was posted at.

This event is emitted when an offer fails, because of a maker error.

It emits olKeyHash, taker, the offerId, the offers takerWants, takerGives, penalty and the reason for failure. olKeyHash and taker are all fields that we do not need, in order for an indexer to work, as an indexer will be able the get that info from the former OrderStart and OfferWrite events. But in order for RPC call to filter on this, we need to emit them. olKeyHash taker and id are indexed so that we can filter on them when doing RPC calls. As maker can be a strategy and not the actual owner, then we chose to not emit it here and to mark the field id indexed, the strat should emit the relation between maker and offerId. This way you can still by RPC calls find the relevant offer successes

If the posthook of the offer fails. Then we emit OfferFailWithPosthookData instead of just OfferFail. This event has one extra field, which is the reason for the posthook failure. By emitting the posthook data, an indexer can keep track of the reason posthook fails, this could for example be used for analytics.

This event is emitted during posthook end, we wait to emit this event to the end, because we need the information of penalty, which is only available at the end of the posthook. This means that OfferFail events are emitted in reverse order, compared to what order they are taken. This is due to the way we handle posthooks. The same goes for OfferSuccess.

By emitting this event, an indexer can keep track of, if an offer failed and thereby if the offer is live. By emitting the takerWants and takerGives that the offer was taken with, then an indexer can keep track of these amounts, which could be useful for e.g. strategy manager, to know if their offers fail at a certain amount.

After permit and approve

This is emitted when a user permits another address to use a certain amount of its funds to do market orders, or when a user revokes another address to use a certain amount of its funds.

Approvals are based on the pair of outbound and inbound token. Be aware that it is not offer list bases, as an offer list also holds the tick spacing.

We emit outbound token, inbound token, owner, msg.sender (spender), value. Where owner is the one who owns the funds, spender is the one who is allowed to use the funds and value is the amount of funds that is allowed to be used.

Outbound, inbound and owner is indexed, this way one can filter on these fields when doing RPC calls. If we could somehow combine outbound and inbound into one field, then we could also index the spender.

Mangrove closure

An offer was created or updated.

This event is emitted when an offer is posted on Mangrove.

It emits the olKeyHash, the maker address, the tick, the gives, the gasprice, gasreq and the offers id.

By emitting the olKeyHash and id, an indexer will be able to keep track of each offer, because offer list and id together create a unique id for the offer. By emitting the maker address, we are able to keep track of who has posted what offer. The tick and gives, enables an indexer to know exactly how much an offer is willing to give and at what price, this could for example be used to calculate a return. The gasprice and gasreq, enables an indexer to calculate how much provision is locked by the offer, see Credit for more information.

The fields olKeyHash and maker are indexed, so that we can filter on them when doing RPC calls.

This event is emitted when a user retracts his offer.

It emits the olKeyHash, the maker address, offerId and whether or not the user chose to deprovision the offer.

By emitting this event an indexer knows whether or not an offer is live. And whether or not an offer is deprovisioned. This is important because we need to know this, when we try to calculate how much an offer locks in provision. See the description of Credit for more info.

The maker is not needed for an indexer to work, but is needed for RPC calls, so it is emitted and indexed for that reason. The olKeyHash is only indexed because it is needed for RPC calls.

IMaker interface

Called upon offer execution.

• If the call throws, Mangrove will not try to transfer funds and the first 32 bytes of revert reason are passed to makerPosthook as makerData
• If the call returns normally, returnData is passed to makerPosthook as makerData and Mangrove will attempt to transfer the funds.

Called after all offers of an order have been executed. Posthook of the last executed order is called first and full reentrancy into Mangrove is enabled at this time. order recalls key arguments of the order that was processed and result recalls important information for updating the current offer. (see above)

Monitor interface

If enabled, the monitor receives notification after each offer execution and is read for each offer list’s gasprice and density.

MgvCommon and its descendants describe an orderbook-based exchange (“Mangrove”) where market makers do not have to provision their offer. In a nutshell: each offer created by a maker specifies an address (maker) to call upon offer execution by a taker. When an offer is executed, Mangrove transfers the amount to be paid by the taker to the maker, calls the maker, attempts to transfer the amount promised by the maker to the taker, and reverts if it cannot.

MgvCommon contains state variables used everywhere in the operation of Mangrove and related gatekeeping functions. The main Mangrove contract inherits from MgvCommon, and the auxiliary MgvAppendix contract inherits from MgvCommon as well. This way, when Mangrove delegatecalls to MgvAppendix, the storage slots match.

State variables

The governance address. Governance is the only address that can configure parameters.

Global mgv configuration, encoded in a 256 bits word. The information encoded is detailed in structs.js.

OfferData contains all the information related to an offer. Each field contains packed information such as the volumes and the gas required. See structs.js for more information.

OfferList contains all data specific to an offer list.

local is the Mangrove configuration specific to the outbound,inbound,tickSpacing offer list. It contains e.g. the minimum offer density. It contains packed information, see structs.js for more.

level1s maps a level1 index to a (dirty) field. Each field holds 64 bits marking the (non)empty state of 64 level2 fields.

level2s maps a level2 index to a (dirty) field. Each field holds 64 bits marking the (non)empty state of 64 level3 fields.

level3s maps a level3 index to a (dirty) field. Each field holds 64 bits marking the (non)empty state of 64 leaves.

leafs (intentionally not leaves for clarity) maps a leaf index to a leaf. Each leaf holds the first&last offer id of 4 bins.

OfferData maps an offer id to a struct that holds the two storage words where the packed offer information resides. For more information see Offer and OfferDetail.

OLKeys (see MgvLib.sol) are hashed to a bytes32 OLKey identifier, which get mapped to an OfferList struct. Having a single mapping instead of one mapping per field in OfferList means we can pass around a storage reference to that struct.

For convenience, and to enable future functions that access offer lists by directly supplying an OLKey identifier, Mangrove maintains an inverse id -> key mapping.

Makers provision their possible penalties in the balanceOf mapping.

Offers specify the amount of gas they require for successful execution (gasreq). To minimize book spamming, market makers must provision an amount of native tokens that depends on their gasreq and on the offer list’s offer_gasbase. This provision is deducted from their balanceOf. If an offer fails, part of that provision is given to the taker as a penalty. The exact amount depends on the gas used by the offer before failing and during the execution of its posthook.

Mangrove keeps track of available balances in the balanceOf map, which is decremented every time a maker creates a new offer, and may be modified on offer updates/cancellations/takings.

Gatekeeping

Gatekeeping functions are safety checks called in various places.

unlockedOfferListOnly protects modifying the offer list while an order is in progress. Since external contracts are called during orders, allowing reentrancy would, for instance, let a market maker replace offers currently on the book with worse ones. Note that the external contracts will be called again after the order is complete, this time without any lock on the offer list.

In case of emergency, Mangrove can be killed. It cannot be resurrected. When a Mangrove is dead, the following operations are disabled :

• Executing an offer
• Sending ETH to Mangrove the normal way. Usual shenanigans are possible.
• Creating a new offer

When Mangrove is deployed, all offer lists are inactive by default (since locals[outbound_tkn][inbound_tkn] is 0 by default). Offers on inactive offer lists cannot be taken or created. They can be updated and retracted.

_config is the lower-level variant which opportunistically returns a pointer to the storage offer list induced by (outbound_tkn,inbound_tkn,tickSpacing).

Gas gasprice can be ignored by making sure the oracle’s set gasprice does not pass the check below.

Oracle density can be ignored by making sure the oracle’s set density does not pass the checks below.

Checking the size of density is necessary to prevent overflow when density is used in calculations.

Token transfer functions

transferTokenFrom is adapted from existing code and in particular avoids the “no return value” bug. It never throws and returns true iff the transfer was successful according to tokenAddress.

Note that any spurious exception due to an error in Mangrove code will be falsely blamed on from.

Permit-related functionality

Takers may provide allowances on specific offer lists, so other addresses can execute orders in their name. Allowance may be set using the usual approve function, or through an EIP712 permit.

The mapping is outbound_tkn => inbound_tkn => owner => spender => allowance. There is no tickSpacing specified since we assume the natural semantics of a permit are “spender has the right to trade token A against token B at any tickSpacing”.

Storing nonces avoids replay attacks.

Following EIP712, structured data signing has keccak256("Permit(address outbound_tkn,address inbound_tkn,address owner,address spender,uint256 value,uint256 nonce,uint256 deadline)") in its prefix.

If you are looking for DOMAIN_SEPARATOR, it is defined in MgvOfferTakingWithPermit.

If you define an immutable C, you must initialize it in the constructor of C, unless you use solidity >= 0.8.21. Then you can initialize it in the constructor of a contract that inherits from C. At the time of the writing 0.8.21 is too recent so we move DOMAIN_SEPARATOR to MgvOfferTakingWithPermit, which has a constructor and also initializes DOMAIN_SEPARATOR.

MgvHasOffers contains the state variables and functions common to both market-maker operations and market-taker operations. Mostly: storing offers, removing them, updating market makers’ provisions.

Provision debit/credit utility functions

balanceOf is in wei of ETH.

Misc. low-level functions

Offer deletion

When an offer is deleted, it is marked as such by setting gives to 0 and leaving other fields intact. Note that provision accounting in Mangrove aims to minimize writes. Each maker funds Mangrove to increase its balance. When an offer is created/updated, we compute how much should be reserved to pay for possible penalties. That amount can always be recomputed with

offerDetail.gasprice * 1e6 * (offerDetail.gasreq + offerDetail.offer_gasbase)

The balance is updated to reflect the remaining available ethers.

Now, when an offer is deleted, the offer can stay provisioned, or be deprovisioned. In the latter case, we set gasprice to 0, which induces a provision of 0. All code calling dirtyDeleteOffer with deprovision set to true must be careful to correctly account for where that provision is going (back to the maker’s balanceOf, or sent to a taker as compensation).

Removing an offer from the tick tree

To remove an offer from the tick tree, we do the following:

• Remove the offer from the bin
• If the bin is now empty, mark it as empty in its leaf
• If the leaf is now empty, mark it as empty in its level3
• If the level3 is now empty, mark it as empty in its level2
  • If the level2 is now empty, mark it as empty in its level1
    • If the level1 is now empty, mark it as empty in the root
      • If the root is now empty, return
• Once we are done marking leaves/fields as empty, if the removed offer was the best there is at least one remaining offer, and if the caller requested it by setting shouldUpdateBranch=true, go down the tree and find the new best offer.

Each step must take into account the fact that the branch of the best offer is cached in local and that loading a new best offer requires caching a different branch in local.

The reason why the caller might set shouldUpdateBranch=false is that it is itself about to insert an offer better than the current best offer. In that case, it will take care of caching the branch of the new best offer after calling dislodgeOffer.

The new updated local is returned, along with whether the branch in local ended up being updated.

Only load offer’s leaf if the offer leaf must be updated. If offer is in the middle of a bin’s linked list, the bin’s first&last offers will not change, so the leaf does not have to be loaded.

Update the forward pointer to offer (either in a leaf or in an offer’s next pointer)

If offer was its bin’s first offer, the new first offer is nextId (may be 0).

Otherwise, the next pointer of offer’s prev becomes nextId.

Update the backward pointer to offer (either in a leaf or in an offer’s prev pointer)

If offer was its bin’s last offer, the new last offer is prevId (may be 0).

Otherwise, the prev pointer of offer’s next becomes prevId.

If previous pointer updates only updated offer pointers, offer’s leaf has not changed and we can return early

Only plan on updating the branch if the caller requested it and if offer is the best.

Since offer was the first or last of its bin, its leaf must be updated

If the leaf is now empty, flip off its bit in offer’s level3

We reuse the same index variable for all 3 level indices and for the leaf index.

We reuse the same field variable for all 3 level indices.

Local cache management conditional

If offer’s level3 is cached, update it in local.

If shouldUpdateBranch=true and the level3 is now empty, another level3 may take its place. We immediately evict the empty value of level3 to storage. (If the level3 is not empty, then the new best offer will use that level3, so no eviction necessary).

Clean/dirty management. ifs are nested to avoid a useless SLOAD.

If offer’s level3 is not cached, update it in storage.

If offer’s level3 is now empty, flip off its bit in the removed offer’s level2

Local cache management conditional

If offer’s level2 is cached, update it in local.

If shouldUpdateBranch=true and the level2 is now empty, another level2 may take its place. We immediately evict the empty value of level2 to storage. (If the level2 is not empty, then the new best offer will use that level2, so no eviction necessary).

Clean/dirty management. Ifs are nested to avoid a useless SLOAD.

If offer’s level2 is not cached, update it in storage.

If offer’s level2 is now empty, flip off its bit in offer’s level1

Local cache management conditional

If offer’s level1 is cached, update it in local.

If shouldUpdateBranch=true and the level1 is now empty, another level1 may take its place. We immediately evict the empty value of level1 to storage. (If the level1 is not empty, then the new best offer will use that level1, so no eviction necessary).

Unlike with level3 and level2, level1 cannot be CLEAN_EMPTY (it gets dirtied in activate)

If offer’s level1 is not cached, update it in storage.

If offer’s level1 is now empty, flip off its bit in the root field.

root is always in local

If the root is now empty, return the updated local

Since offer’s level1 became empty, if we have to update the branch, load the level1 containing the new best offer in local.

Since offer’s level2 became empty, if we have to update the branch, load the level2 containing the new best offer in local.

Since offer’s level3 became empty, if we have to update the branch, load the level3 containing the new best offer in local.

Since offer’s leaf became empty, if we have to update the branch, load the leaf containing the new best offer in leaf (so that we can find the position of the first non-empty bin in the leaf).

Since offer’s bin became empty if we have to update the branch, load the position of the first non-empty bin in the current leaf in local.

MgvOfferMaking contains market-making-related functions.

Public Maker operations

New Offer

In Mangrove, makers and takers call separate functions. Market makers call newOffer to fill the book, and takers call functions such as marketOrder to consume it.

The following structs holds offer creation/update parameters in memory. This frees up stack space for local variables.

The function newOffer is for market makers only; no match with the existing offer list is done. The maker specifies how much olKey.outbound_tkn token it gives and at which tick (which induces the price 1.0001^tick). The actual tick of the offer will be the smallest tick offerTick > tick that satisfies offerTick % tickSpacing == 0.

It also specify with gasreq how much gas should be given when executing their offer.

gasprice indicates an upper bound on the gasprice (in Mwei) at which the maker is ready to be penalised if their offer fails. Any value below Mangrove’s internal gasprice configuration value will be ignored.

gasreq, together with gasprice, will contribute to determining the penalty provision set aside by Mangrove from the market maker’s balanceOf balance.

An offer cannot be inserted in a closed market, nor when a reentrancy lock for outbound_tkn,inbound_tkn is on.

No more than $2^{32}-1$ offers can ever be created for one (outbound,inbound, tickSpacing) offer list.

The actual contents of the function is in writeOffer, which is called by both newOffer and updateOffer.

In preparation for calling writeOffer, we read the outbound_tkn,inbound_tkn, tickSpacing offer list configuration, check for reentrancy and offer list liveness, fill the OfferPack struct and increment the offer list’s last.

The last parameter to writeOffer indicates that we are creating a new offer, not updating an existing one.

Since we locally modified a field of the local configuration (last), we save the change to storage. Note that writeOffer may have further modified the local configuration by updating the currently cached tick tree branch.

There is a ByVolume variant where the maker specifies how much inbound_tkn it wants and how much outbound_tkn it gives. Volumes should fit on 127 bits.

Update Offer

Very similar to newOffer, updateOffer prepares an OfferPack for writeOffer. Makers should use it for updating live offers, but also to save on gas by reusing old, already consumed offers.

Gas use is minimal when:

1. The offer does not move in the offer list
2. The offer does not change its gasreq
3. The (outbound_tkn,inbound_tkn)'s offer_gasbase has not changed since the offer was last written
4. gasprice has not changed since the offer was last written
5. gasprice is greater than Mangrove’s gasprice estimation

The second argument indicates that we are updating an existing offer, not creating a new one.

We saved the current offer list’s local configuration before calling writeOffer, since that function may update it. We now check for any change to the configuration and update it if needed.

Retract Offer

retractOffer takes the offer offerId out of the book. However, deprovision == true also refunds the provision associated with the offer.

Here, we are about to un-live an offer, so we start by taking it out of the tick tree. Note that unconditionally calling dislodgeOffer even if the offer is not live would break the offer list since it would connect offers that may have since moved.

If calling dislodgeOffer has changed the current best offer, we update local.

Set offer.gives to 0 (which is encodes the fact that the offer is dead). The deprovision argument indicates whether the maker wishes to get their provision back (if true, offer.gasprice will be set to 0 as well).

If the user wants to get their provision back, we compute it from the offer’s gasprice, offer_gasbase and gasreq.

Provisioning

Market makers must have enough provisions for possible penalties. These provisions are in native tokens. Every time a new offer is created or an offer is updated, balanceOf is adjusted to provision the offer’s maximum possible penalty (gasprice * (gasreq + offer_gasbase)).

For instance, if the current balanceOf of a maker is 1 ether and they create an offer that requires a provision of 0.01 ethers, their balanceOf will be reduced to 0.99 ethers. No ethers will move; this is just an internal accounting movement to make sure the maker cannot withdraw the provisioned amounts.

Fund should be called with a nonzero value (hence the payable modifier). The provision will be given to maker, not msg.sender.

A transfer with enough gas to Mangrove will increase the caller’s available balanceOf balance. You should send enough gas to execute this function when sending money to Mangrove.

Any provision not currently held to secure an offer’s possible penalty is available for withdrawal.

Since we only ever send money to the caller, we do not need to provide any particular amount of gas, the caller should manage this herself.

Low-level Maker functions

Write Offer

Used by updateOfferBy* and newOfferBy*, this function optionally removes an offer then (re)inserts it in the tick tree. The update argument indicates whether the call comes from updateOfferBy* or newOfferBy*.

gasprice’s floor is Mangrove’s own gasprice estimate, ofp.global.gasprice. We first check that gasprice fits in 26 bits. Otherwise it could be that uint26(gasprice) < global_gasprice < gasprice and the actual value we store is uint26(gasprice) (using pseudocode here since the type uint26 does not exist).

• Check gasreq below limit. Implies gasreq at most 24 bits wide, which ensures no overflow in computation of provision (see below).

• Make sure gives > 0 – division by 0 would throw in several places otherwise, and isLive relies on it.

• Make sure that the maker is posting a ‘dense enough’ offer: the ratio of outbound_tkn offered per gas consumed must be high enough. The actual gas cost paid by the taker is overapproximated by adding offer_gasbase to gasreq.

The following checks are for the maker’s convenience only.

Derive bin from given tick, then normalize the tick: available ticks in an offer list are those who are equal to 0 modulo tickSpacing.

Log the write offer event.

We now write the new offerDetails and remember the previous provision (0 by default, for new offers) to balance out maker’s balanceOf.

If the offer is new, has a new gasprice, gasreq, or if Mangrove’s offer_gasbase configuration parameter has changed, we also update offerDetails.

With every change to an offer, a maker may deduct provisions from its balanceOf balance. It may also get provisions back if the updated offer requires fewer provisions than before.

We now cache the current best bin in a stack variable. Since the current best bin is derived from ofp.local, and since ofp.local may change as a new branch is cached in local, not caching that value means potentially losing access to it.

If the tick tree is empty, we consider the current best bin to be the bin of the written offer. This makes later comparisons between them pick the right conditional branch every time.

If the tick tree is currently not empty, we cache the current best bin.

If the written offer is currently stored in the tick tree, it must be removed.

If the insertion bin of the offer is better than the current best bin, the later call to dislodgeOffer does not need to update the cached branch in local since we (writeOffer) will take care of updating the branch as part of insertion the offer in its new bin. Otherwise, we may need dislodgeOffer to take care of updating the cached branch in local. However, that is only th the case if the written offer is currently the best offer of the tick tree. dislodgeOffer will make that determination.

local is updated, and shouldUpdateBranch now means “did update branch”.

If dislodgeOffer did update the information in local, it means the cached best bin may be stale – the best offer may now be in a different bin. So we update it.

A call to bestBin() is invalid when the branch cached in local is for an empty tick tree. In that case, as we did earlier if the tick tree was already empty, we set the current best bin to the bin of the written offer.

We will now insert the offer to its new position in the tick tree. If the offer is now the best offer, we update the cached “bin position in leaf” information in local.

Next, we load the leaf of the offer to check whether it needs updating.

If the written offer’s leaf was empty, the level3 above it needs updating.

We reuse the same field variable for all 3 level indices.

We reuse the same insertionIndex and currentIndex variables for all 3 level indices and for the leaf index.

If the written offer’s level3 is the cached level3, we load the written offer’s level3 from local.

Otherwise we load the written offer’s level3 from storage.

If the written offer’s level3 is strictly better than the cached level3, we evict the cached level3.