structs.js

        

Mangrove Summary

  • The Mangrove holds order books for outbound_tkn,inbound_tkn pairs.
  • Offers are sorted in a doubly linked list.
  • Each offer promises outbound_tkn and requests inbound_tkn.
  • Each offer has an attached maker address.
  • In the normal operation mode (called Mangrove for Maker Mangrove), when an offer is executed, we:
    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.
  • There is an inverted operation mode (called InvertedMangrove for Taker Mangrove), the flashloan is reversed (from the maker to the taker).
  • Offer are just promises. They can fail.
  • If an offer fails to transfer the right amount back, the loan is reverted.
  • A penalty mechanism incentivizes keepers to keep the book clean of failing offers.
  • A penalty provision must be posted with each offer.
  • If the offer succeeds, the provision returns to the maker.
  • If the offer fails, the provision is given to the taker as penalty.
  • The penalty should overcompensate for the taker’s lost gas.

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


        

        

Preprocessing

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

structs = {
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>Packed by Solidity); here is a simplified version:

struct UniverseUnpacked {
uint serialnumber;
bool hospitable;
}

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

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

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

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

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

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

Then, in Solidity code, one can write:

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

        

Data stuctures


        

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. To make development easier, we use the preprocessor solpp and generate getters and setters for each struct we declare. The generation is defined in lib/preproc.js.

80
81
82
const preproc = require("./lib/preproc.js");

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.

84
85
86
87
88
89
90
91
92
93
94
95
96
const fields = {
  wants: { name: "wants", bits: 96, type: "uint" },
  gives: { name: "gives", bits: 96, type: "uint" },
  gasprice: { name: "gasprice", bits: 16, type: "uint" },
  gasreq: { name: "gasreq", bits: 24, type: "uint" },
  offer_gasbase: { name: "offer_gasbase", bits: 24, type: "uint" },
};

const id_field = (name) => {
  return { name, bits: 32, type: "uint" };
};

Structs


        

Offer


        

        

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


        
103
104
const structs = {
  offer: [
  • prev points to immediately better offer. The best offer’s prev is 0. 32 bits wide.
106
107
    id_field("prev"),
  • next points to the immediately worse offer. The worst offer’s next is 0. 32 bits wide.
109
    id_field("next"),
  • wants is the amount of inbound_tkn the offer wants in exchange for gives. 96 bits wide, so assuming the usual 18 decimals, amounts can only go up to 10 billions.
113
    fields.wants,
  • gives is the amount of outbound_tkn the offer will give if successfully executed. 96 bits wide, so assuming the usual 18 decimals, amounts can only go up to 10 billions.
117
118
119
    fields.gives,
  ],

OfferDetail


        

        

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

124
  offerDetail: [
  • maker is the address that created the offer. It will be called when the offer is executed, and later during the posthook phase.
126
    { name: "maker", bits: 160, type: "address" },
  • 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.
130
    fields.gasreq,
  • offer_gasbase represents the gas overhead used by processing the offer inside the Mangrove + the overhead of initiating an entire order.

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

  • gas consumed during the call to the offer
  • offer_gasbase

(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 wei is taken from the provision per unit of gas used. gasprice should approximate the average gas price at offer creation time.

offer_gasbase is 24 bits wide – note that if more room was needed, we could bring it down to 8 bits and have it represent 1k gas increments.

offer_gasbase is also the name of a local Mangrove parameters. When an offer is created, their current value is copied from the 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

where offer_gasbase and gasprice are the 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

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

166
    fields.offer_gasbase,
  • gasprice is in gwei/gas and 16 bits wide, which accomodates 1 to ~65k 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 the Mangrove’s global gasprice.
168
169
170
    fields.gasprice,
  ],

Configuration and state

Configuration information for a outbound_tkn,inbound_tkn pair is split between a global struct (common to all pairs) and a local struct specific to each pair. Configuration fields are:


        

Global Configuration

175
  global: [
  • The monitor can provide realtime values for gasprice and density to the dex, and receive liquidity events notifications.
177
    { name: "monitor", bits: 160, type: "address" },
  • If useOracle is true, the dex will use the monitor address as an oracle for gasprice and density, for every outbound_tkn/inbound_tkn pair.
179
    { name: "useOracle", bits: 8, type: "bool" },
  • If notify is true, the dex will notify the monitor address after every offer execution.
181
    { name: "notify", bits: 8, type: "bool" },
  • The gasprice is the amount of penalty paid by failed offers, in gwei per gas used. gasprice should approximate the average gas price and will be subject to regular updates.
183
    fields.gasprice,
  • 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.
186
    { name: "gasmax", bits: 24, type: "uint" },
  • dead dexes cannot be resurrected.
188
189
190
    { name: "dead", bits: 8, type: "bool" },
  ],

Local configuration

192
  local: [
  • A outbound_tkn,inbound_tkn pair is inactive by default, but may be activated/deactivated by governance.
194
    { name: "active", bits: 8, type: "bool" },
  • fee, in basis points, of outbound_tkn given to the taker. This fee is sent to the Mangrove. Fee is capped to 5%.
196
    { name: "fee", bits: 16, type: "uint" },
  • 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 == 10, offer_gasbase == 5000, an offer with gasreq == 30000 must promise at least 10 × (30000 + 5000) = 350000 outbound_tkn. 112 bits wide.
198
    { name: "density", bits: 112, type: "uint" },
  • offer_gasbase is an overapproximation of the gas overhead associated with processing one offer. The Mangrove considers that a failed offer has used at least offer_gasbase gas. Local to a pair 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.
200
    fields.offer_gasbase,
  • If lock is true, orders may not be added nor executed.

Reentrancy during offer execution is not considered safe:

  • during execution, an offer could consume other offers further up in the book, effectively frontrunning 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.
  • an offer insertion consumes an unbounded amount of gas (because it has to be correctly placed in the book).

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

210
    { name: "lock", bits: 8, type: "bool" },
  • best holds the current best offer id. Has size of an id field. Danger: reading best inside a lock may give you a stale value.
212
    id_field("best"),
  • last is a counter for offer ids, incremented every time a new offer is created. It can’t go above 23212^{32}-1.
214
215
216
217
218
    id_field("last"),
  ],
};

module.exports = preproc.structs_with_macros(structs);
MgvLib.sol

        

MgvLib.sol


        

This is free and unencumbered software released into the public domain.


        

Anyone is free to copy, modify, publish, use, compile, sell, or distribute this software, either in source code form or as a compiled binary, for any purpose, commercial or non-commercial, and by any means.


        

In jurisdictions that recognize copyright laws, the author or authors of this software dedicate any and all copyright interest in the software to the public domain. We make this dedication for the benefit of the public at large and to the detriment of our heirs and successors. We intend this dedication to be an overt act of relinquishment in perpetuity of all present and future rights to this software under copyright law.


        

THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.


        

For more information, please refer to https://unlicense.org/


        

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

16
17
18
19
20
21
22
pragma solidity ^0.8.10;

pragma abicoder v2;

import "./preprocessed/MgvStructs.post.sol" as MgvStructs;

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.

25
26
library MgvLib {

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 internalSnipes (and some of their nested functions) to avoid stack too deep errors.

32
33
34
35
36
  struct SingleOrder {
    address outbound_tkn;
    address inbound_tkn;
    uint offerId;
    MgvStructs.OfferPacked offer;

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

38
39
    uint wants;
    uint gives;

offerDetail is only populated when necessary.

41
42
43
44
45
    MgvStructs.OfferDetailPacked offerDetail;
    MgvStructs.GlobalPacked global;
    MgvStructs.LocalPacked local;
  }

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 the Mangrove encountered an error.

47
48
  struct OrderResult {

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

50
    bytes32 makerData;

mgvData is an internal Mangrove status code code.

52
53
54
55
    bytes32 mgvData;
  }
}

Events

The events emitted for use by bots are listed here:

58
contract HasMgvEvents {
  • Emitted at the creation of the new Mangrove contract on the pair (inbound_tkn, outbound_tkn)
60
61
  event NewMgv();

Mangrove adds or removes wei from maker’s account


        
  • Credit event occurs when an offer is removed from the Mangrove or when the fund function is called
64
  event Credit(address indexed maker, uint amount);
  • Debit event occurs when an offer is posted or when the withdraw function is called
66
67
  event Debit(address indexed maker, uint amount);
  • Mangrove reconfiguration
69
70
71
72
73
74
75
76
77
78
79
80
  event SetActive(address indexed outbound_tkn, address indexed inbound_tkn, bool value);
  event SetFee(address indexed outbound_tkn, address indexed inbound_tkn, uint value);
  event SetGasbase(address indexed outbound_tkn, address indexed inbound_tkn, uint offer_gasbase);
  event SetGovernance(address value);
  event SetMonitor(address value);
  event SetVault(address value);
  event SetUseOracle(bool value);
  event SetNotify(bool value);
  event SetGasmax(uint value);
  event SetDensity(address indexed outbound_tkn, address indexed inbound_tkn, uint value);
  event SetGasprice(uint value);

Market order execution

82
83
84
85
86
87
88
89
90
91
92
  event OrderStart();
  event OrderComplete(
    address indexed outbound_tkn,
    address indexed inbound_tkn,
    address indexed taker,
    uint takerGot,
    uint takerGave,
    uint penalty,
    uint feePaid
  );
  • Offer execution
94
95
96
97
  event OfferSuccess(
    address indexed outbound_tkn,
    address indexed inbound_tkn,
    uint id,

maker is not logged because it can be retrieved from the state using (outbound_tkn,inbound_tkn,id).

99
100
101
102
103
    address taker,
    uint takerWants,
    uint takerGives
  );

Log information when a trade execution reverts or returns a non empty bytes32 word

105
106
107
108
  event OfferFail(
    address indexed outbound_tkn,
    address indexed inbound_tkn,
    uint id,

maker is not logged because it can be retrieved from the state using (outbound_tkn,inbound_tkn,id).

110
111
112
    address taker,
    uint takerWants,
    uint takerGives,

mgvData may only be "mgv/makerRevert", "mgv/makerTransferFail" or "mgv/makerReceiveFail"

114
115
116
    bytes32 mgvData
  );

Log information when a posthook reverts

118
119
  event PosthookFail(address indexed outbound_tkn, address indexed inbound_tkn, uint offerId, bytes32 posthookData);
  • After permit and approve
121
122
  event Approval(address indexed outbound_tkn, address indexed inbound_tkn, address owner, address spender, uint value);
  • Mangrove closure
124
125
  event Kill();
  • An offer was created or updated. A few words about why we include a prev field, and why we don’t include a next field: in theory clients should need neither prev nor a next field. They could just 1. Read the order book state at a given block b. 2. On every event, update a local copy of the orderbook. But in practice, we do not want to force clients to keep a copy of the entire orderbook. There may be a long tail of spam. Now if they only start with the first NN offers and receive a new offer that goes to the end of the book, they cannot tell if there are missing offers between the new offer and the end of the local copy of the book.

So we add a prev pointer so clients with only a prefix of the book can receive out-of-prefix offers and know what to do with them. The next pointer is an optimization useful in Solidity (we traverse fewer memory locations) but useless in client code.

142
143
144
145
146
147
148
149
150
151
152
153
  event OfferWrite(
    address indexed outbound_tkn,
    address indexed inbound_tkn,
    address maker,
    uint wants,
    uint gives,
    uint gasprice,
    uint gasreq,
    uint id,
    uint prev
  );
  • offerId was present and is now removed from the book.
155
156
157
  event OfferRetract(address indexed outbound_tkn, address indexed inbound_tkn, uint id);
}

IMaker interface

159
interface IMaker {

Called upon offer execution.

  • If the call fails, Mangrove will not try to transfer funds.
  • If the call succeeds but returndata’s first 32 bytes are not 0, Mangrove will not try to transfer funds either.
  • If the call succeeds and returndata’s first 32 bytes are 0, Mangrove will try to transfer funds. In other words, you may declare failure by reverting or by returning nonzero data. In both cases, those 32 first bytes will be passed back to you during the call to makerPosthook in the result.mgvData field.
function tradeRevert(bytes32 data) internal pure {
  bytes memory revData = new bytes(32);
    assembly {
      mstore(add(revData, 32), data)
      revert(add(revData, 32), 32)
    }
}
175
176
  function makerExecute(MgvLib.SingleOrder calldata order) external returns (bytes32);

Called after all offers of an order have been executed. Posthook of the last executed order is called first and full reentrancy into the 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)

178
179
180
  function makerPosthook(MgvLib.SingleOrder calldata order, MgvLib.OrderResult calldata result) external;
}

ITaker interface

182
interface ITaker {

Inverted mangrove only: call to taker after loans went through

184
185
186
  function takerTrade(
    address outbound_tkn,
    address inbound_tkn,

total amount of outbound_tkn token that was flashloaned to the taker

188
    uint totalGot,

total amount of inbound_tkn token that should be made available

190
191
192
193
    uint totalGives
  ) external;
}

Monitor interface

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

196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
interface IMgvMonitor {
  function notifySuccess(MgvLib.SingleOrder calldata sor, address taker) external;

  function notifyFail(MgvLib.SingleOrder calldata sor, address taker) external;

  function read(address outbound_tkn, address inbound_tkn) external view returns (uint gasprice, uint density);
}

interface IERC20 {
  function totalSupply() external view returns (uint);

  function balanceOf(address account) external view returns (uint);

  function transfer(address recipient, uint amount) external returns (bool);

  function allowance(address owner, address spender) external view returns (uint);

  function approve(address spender, uint amount) external returns (bool);

  function transferFrom(address sender, address recipient, uint amount) external returns (bool);

  function symbol() external view returns (string memory);

  event Transfer(address indexed from, address indexed to, uint value);
  event Approval(address indexed owner, address indexed spender, uint value);

/ for wETH contract

223
224
  function decimals() external view returns (uint8);
}
MgvRoot.sol

        

MgvRoot.sol


        

Copyright © 2021 Giry SAS.


        

        

This program is free software: you can redistribute it and/or modify


        

it under the terms of the GNU Affero General Public License as published


        

by the Free Software Foundation, either version 3 of the License, or


        

(at your option) any later version.


        

        

This program is distributed in the hope that it will be useful,


        

but WITHOUT ANY WARRANTY; without even the implied warranty of


        

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


        

GNU Affero General Public License for more details.


        

        

You should have received a copy of the GNU Affero General Public License


        

along with this program. If not, see https://www.gnu.org/licenses/.


        

MgvRoot and its descendants describe an orderbook-based exchange (“the Mangrove”) where market makers do not have to provision their offer. See structs.js for a longer introduction. In a nutshell: each offer created by a maker specifies an address (maker) to call upon offer execution by a taker. In the normal mode of operation, the 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.

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

The interaction map between the different actors is as follows:

The sequence diagram of a market order is as follows:

There is a secondary mode of operation in which the maker flashloans the sold amount to the taker.

The Mangrove contract is abstract and accomodates both modes. Two contracts, Mangrove and InvertedMangrove inherit from it, one per mode of operation.

The contract structure is as follows:

37
38
39
40
41
42
43
pragma solidity ^0.8.10;

pragma abicoder v2;

import {MgvLib, HasMgvEvents, IMgvMonitor, MgvStructs} from "./MgvLib.sol";

MgvRoot contains state variables used everywhere in the operation of the Mangrove and their related function.

45
contract MgvRoot is HasMgvEvents {

State variables


        

        

The vault address. If a pair has fees >0, those fees are sent to the vault.

49
50
  address public vault;

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

52
  MgvStructs.GlobalPacked internal internal_global;

Configuration mapping for each token pair of the form outbound_tkn => inbound_tkn => MgvStructs.LocalPacked. The structure of each MgvStructs.LocalPacked value is detailed in structs.js. It fits in one word.

54
55
  mapping(address => mapping(address => MgvStructs.LocalPacked)) internal locals;

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

57
58
59
60
61
62
  function checkDensity(uint density) internal pure returns (bool) {
    unchecked {
      return uint112(density) == density;
    }
  }

Checking the size of gasprice is necessary to prevent a) data loss when gasprice is copied to an OfferDetail struct, and b) overflow when gasprice is used in calculations.

64
65
66
67
68
69
  function checkGasprice(uint gasprice) internal pure returns (bool) {
    unchecked {
      return uint16(gasprice) == gasprice;
    }
  }

Configuration Reads


        

Reading the configuration for a pair involves reading the config global to all pairs and the local one. In addition, a global parameter (gasprice) and a local one (density) may be read from the oracle.

72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
  function config(address outbound_tkn, address inbound_tkn)
    public
    view
    returns (MgvStructs.GlobalPacked _global, MgvStructs.LocalPacked _local)
  {
    unchecked {
      _global = internal_global;
      _local = locals[outbound_tkn][inbound_tkn];
      if (_global.useOracle()) {
        (uint gasprice, uint density) = IMgvMonitor(_global.monitor()).read(outbound_tkn, inbound_tkn);
        if (checkGasprice(gasprice)) {
          _global = _global.gasprice(gasprice);
        }
        if (checkDensity(density)) {
          _local = _local.density(density);
        }
      }
    }
  }

Returns the configuration in an ABI-compatible struct. Should not be called internally, would be a huge memory copying waste. Use config instead.

93
94
95
96
97
98
99
100
101
102
103
104
  function configInfo(address outbound_tkn, address inbound_tkn)
    external
    view
    returns (MgvStructs.GlobalUnpacked memory global, MgvStructs.LocalUnpacked memory local)
  {
    unchecked {
      (MgvStructs.GlobalPacked _global, MgvStructs.LocalPacked _local) = config(outbound_tkn, inbound_tkn);
      global = _global.to_struct();
      local = _local.to_struct();
    }
  }

Convenience function to check whether given pair is locked

106
107
108
109
110
  function locked(address outbound_tkn, address inbound_tkn) external view returns (bool) {
    MgvStructs.LocalPacked local = locals[outbound_tkn][inbound_tkn];
    return local.lock();
  }

Gatekeeping

Gatekeeping functions are safety checks called in various places.


        

unlockedMarketOnly protects modifying the market 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 market.

118
119
120
121
  function unlockedMarketOnly(MgvStructs.LocalPacked local) internal pure {
    require(!local.lock(), "mgv/reentrancyLocked");
  }

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

  • Executing an offer
  • Sending ETH to the Mangrove the normal way. Usual shenanigans are possible.
  • Creating a new offer
128
129
130
131
  function liveMgvOnly(MgvStructs.GlobalPacked _global) internal pure {
    require(!_global.dead(), "mgv/dead");
  }

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

133
134
135
136
137
  function activeMarketOnly(MgvStructs.GlobalPacked _global, MgvStructs.LocalPacked _local) internal pure {
    liveMgvOnly(_global);
    require(_local.active(), "mgv/inactive");
  }
}
MgvHasOffers.sol

        

MgvHasOffers.sol


        

Copyright © 2021 Giry SAS.


        

        

This program is free software: you can redistribute it and/or modify


        

it under the terms of the GNU Affero General Public License as published


        

by the Free Software Foundation, either version 3 of the License, or


        

(at your option) any later version.


        

        

This program is distributed in the hope that it will be useful,


        

but WITHOUT ANY WARRANTY; without even the implied warranty of


        

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


        

GNU Affero General Public License for more details.


        

        

You should have received a copy of the GNU Affero General Public License


        

along with this program. If not, see https://www.gnu.org/licenses/.

19
20
21
22
23
24
25
pragma solidity ^0.8.10;

pragma abicoder v2;

import {MgvLib, HasMgvEvents, IMgvMonitor, MgvStructs} from "./MgvLib.sol";
import {MgvRoot} from "./MgvRoot.sol";

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.

27
contract MgvHasOffers is MgvRoot {

State variables


        

Given a outbound_tkn,inbound_tkn pair, the mappings offers and offerDetails associate two 256 bits words to each offer id. Those words encode information detailed in structs.js.

The mappings are outbound_tkn => inbound_tkn => offerId => MgvStructs.OfferPacked|MgvStructs.OfferDetailPacked.

33
34
35
  mapping(address => mapping(address => mapping(uint => MgvStructs.OfferPacked))) public offers;
  mapping(address => mapping(address => mapping(uint => MgvStructs.OfferDetailPacked))) public offerDetails;

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 a penalty, which depends on their gasreq and on the pair’s offer_gasbase. This provision is deducted from their balanceOf. If an offer fails, part of that provision is given to the taker, as retribution. The exact amount depends on the gas used by the offer before failing.

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

42
43
  mapping(address => uint) public balanceOf;

Read functions


        

Convenience function to get best offer of the given pair

46
47
48
49
50
51
52
  function best(address outbound_tkn, address inbound_tkn) external view returns (uint) {
    unchecked {
      MgvStructs.LocalPacked local = locals[outbound_tkn][inbound_tkn];
      return local.best();
    }
  }

Returns information about an offer in ABI-compatible structs. Do not use internally, would be a huge memory-copying waste. Use offers[outbound_tkn][inbound_tkn] and offerDetails[outbound_tkn][inbound_tkn] instead.

54
55
56
57
58
59
60
61
62
63
64
65
66
67
  function offerInfo(address outbound_tkn, address inbound_tkn, uint offerId)
    external
    view
    returns (MgvStructs.OfferUnpacked memory offer, MgvStructs.OfferDetailUnpacked memory offerDetail)
  {
    unchecked {
      MgvStructs.OfferPacked _offer = offers[outbound_tkn][inbound_tkn][offerId];
      offer = _offer.to_struct();

      MgvStructs.OfferDetailPacked _offerDetail = offerDetails[outbound_tkn][inbound_tkn][offerId];
      offerDetail = _offerDetail.to_struct();
    }
  }

Provision debit/credit utility functions


        

balanceOf is in wei of ETH.

70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
  function debitWei(address maker, uint amount) internal {
    unchecked {
      uint makerBalance = balanceOf[maker];
      require(makerBalance >= amount, "mgv/insufficientProvision");
      balanceOf[maker] = makerBalance - amount;
      emit Debit(maker, amount);
    }
  }

  function creditWei(address maker, uint amount) internal {
    unchecked {
      balanceOf[maker] += amount;
      emit Credit(maker, amount);
    }
  }

Misc. low-level functions


        

Offer deletion


        

When an offer is deleted, it is marked as such by setting gives to 0. Note that provision accounting in the Mangrove aims to minimize writes. Each maker funds the 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 * (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).

93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
  function dirtyDeleteOffer(
    address outbound_tkn,
    address inbound_tkn,
    uint offerId,
    MgvStructs.OfferPacked offer,
    MgvStructs.OfferDetailPacked offerDetail,
    bool deprovision
  ) internal {
    unchecked {
      offer = offer.gives(0);
      if (deprovision) {
        offerDetail = offerDetail.gasprice(0);
      }
      offers[outbound_tkn][inbound_tkn][offerId] = offer;
      offerDetails[outbound_tkn][inbound_tkn][offerId] = offerDetail;
    }
  }

Stitching the orderbook


        

Connect the offers betterId and worseId through their next/prev pointers. For more on the book structure, see structs.js. Used after executing an offer (or a segment of offers), after removing an offer, or moving an offer.

Warning: calling with betterId = 0 will set worseId as the best. So with betterId = 0 and worseId = 0, it sets the book to empty and loses track of existing offers.

Warning: may make memory copy of local.best stale. Returns new local.

118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
  function stitchOffers(
    address outbound_tkn,
    address inbound_tkn,
    uint betterId,
    uint worseId,
    MgvStructs.LocalPacked local
  ) internal returns (MgvStructs.LocalPacked) {
    unchecked {
      if (betterId != 0) {
        offers[outbound_tkn][inbound_tkn][betterId] = offers[outbound_tkn][inbound_tkn][betterId].next(worseId);
      } else {
        local = local.best(worseId);
      }

      if (worseId != 0) {
        offers[outbound_tkn][inbound_tkn][worseId] = offers[outbound_tkn][inbound_tkn][worseId].prev(betterId);
      }

      return local;
    }
  }

Check offer is live


        

Check whether an offer is ‘live’, that is: inserted in the order book. The Mangrove holds a outbound_tkn => inbound_tkn => id => MgvStructs.OfferPacked mapping in storage. Offer ids that are not yet assigned or that point to since-deleted offer will point to an offer with gives field at 0.

142
143
144
145
146
147
  function isLive(MgvStructs.OfferPacked offer) public pure returns (bool) {
    unchecked {
      return offer.gives() > 0;
    }
  }
}
MgvOfferMaking.sol

        

MgvOfferMaking.sol


        

Copyright © 2021 Giry SAS.


        

        

This program is free software: you can redistribute it and/or modify


        

it under the terms of the GNU Affero General Public License as published


        

by the Free Software Foundation, either version 3 of the License, or


        

(at your option) any later version.


        

        

This program is distributed in the hope that it will be useful,


        

but WITHOUT ANY WARRANTY; without even the implied warranty of


        

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


        

GNU Affero General Public License for more details.


        

        

You should have received a copy of the GNU Affero General Public License


        

along with this program. If not, see https://www.gnu.org/licenses/.

19
20
21
22
23
24
25
pragma solidity ^0.8.10;

pragma abicoder v2;

import {IMaker, HasMgvEvents, MgvStructs} from "./MgvLib.sol";
import {MgvHasOffers} from "./MgvHasOffers.sol";

MgvOfferMaking contains market-making-related functions.

27
contract MgvOfferMaking is MgvHasOffers {

Public Maker operations

New Offer


        

        

In the 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.

36
37
38
39
40
41
42
43
44
45
46
  struct OfferPack {
    address outbound_tkn;
    address inbound_tkn;
    uint wants;
    uint gives;
    uint id;
    uint gasreq;
    uint gasprice;
    uint pivotId;
    MgvStructs.GlobalPacked global;
    MgvStructs.LocalPacked local;

used on update only

48
49
50
    MgvStructs.OfferPacked oldOffer;
  }

The function newOffer is for market makers only; no match with the existing book is done. A maker specifies how much inbound_tkn it wants and how much outbound_tkn it gives.

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

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

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

Offers are always inserted at the correct place in the book. This requires walking through offers to find the correct insertion point. As in Oasis, the maker should find the id of an offer close to its own and provide it as pivotId.

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

No more than 23212^{32}-1 offers can ever be created for one outbound_tkn,inbound_tkn pair.

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

67
68
69
70
71
72
73
74
75
76
  function newOffer(
    address outbound_tkn,
    address inbound_tkn,
    uint wants,
    uint gives,
    uint gasreq,
    uint gasprice,
    uint pivotId
  ) external payable returns (uint) {
    unchecked {

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

78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
      OfferPack memory ofp;
      (ofp.global, ofp.local) = config(outbound_tkn, inbound_tkn);
      unlockedMarketOnly(ofp.local);
      activeMarketOnly(ofp.global, ofp.local);
      if (msg.value > 0) {
        creditWei(msg.sender, msg.value);
      }

      ofp.id = 1 + ofp.local.last();
      require(uint32(ofp.id) == ofp.id, "mgv/offerIdOverflow");

      ofp.local = ofp.local.last(ofp.id);

      ofp.outbound_tkn = outbound_tkn;
      ofp.inbound_tkn = inbound_tkn;
      ofp.wants = wants;
      ofp.gives = gives;
      ofp.gasreq = gasreq;
      ofp.gasprice = gasprice;
      ofp.pivotId = pivotId;

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

100
101
      writeOffer(ofp, false);

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 current best offer.

103
104
105
106
107
      locals[ofp.outbound_tkn][ofp.inbound_tkn] = ofp.local;
      return ofp.id;
    }
  }

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.

A pivotId should still be given to minimise reads in the order book. It is OK to give the offers’ own id as a pivot.

Gas use is minimal when:

  1. The offer does not move in the book
  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 the Mangrove’s gasprice estimation
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
  function updateOffer(
    address outbound_tkn,
    address inbound_tkn,
    uint wants,
    uint gives,
    uint gasreq,
    uint gasprice,
    uint pivotId,
    uint offerId
  ) external payable {
    unchecked {
      OfferPack memory ofp;
      (ofp.global, ofp.local) = config(outbound_tkn, inbound_tkn);
      unlockedMarketOnly(ofp.local);
      activeMarketOnly(ofp.global, ofp.local);
      if (msg.value > 0) {
        creditWei(msg.sender, msg.value);
      }
      ofp.outbound_tkn = outbound_tkn;
      ofp.inbound_tkn = inbound_tkn;
      ofp.wants = wants;
      ofp.gives = gives;
      ofp.id = offerId;
      ofp.gasreq = gasreq;
      ofp.gasprice = gasprice;
      ofp.pivotId = pivotId;
      ofp.oldOffer = offers[outbound_tkn][inbound_tkn][offerId];

Save local config

150
      MgvStructs.LocalPacked oldLocal = ofp.local;

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

152
      writeOffer(ofp, true);

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

154
155
156
157
158
159
      if (!oldLocal.eq(ofp.local)) {
        locals[ofp.outbound_tkn][ofp.inbound_tkn] = ofp.local;
      }
    }
  }

Retract Offer


        

        

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

163
164
165
166
167
168
169
170
171
172
173
  function retractOffer(address outbound_tkn, address inbound_tkn, uint offerId, bool deprovision)
    external
    returns (uint provision)
  {
    unchecked {
      (, MgvStructs.LocalPacked local) = config(outbound_tkn, inbound_tkn);
      unlockedMarketOnly(local);
      MgvStructs.OfferPacked offer = offers[outbound_tkn][inbound_tkn][offerId];
      MgvStructs.OfferDetailPacked offerDetail = offerDetails[outbound_tkn][inbound_tkn][offerId];
      require(msg.sender == offerDetail.maker(), "mgv/retractOffer/unauthorized");

Here, we are about to un-live an offer, so we start by taking it out of the book by stitching together its previous and next offers. Note that unconditionally calling stitchOffers would break the book since it would connect offers that may have since moved.

175
176
177
      if (isLive(offer)) {
        MgvStructs.LocalPacked oldLocal = local;
        local = stitchOffers(outbound_tkn, inbound_tkn, offer.prev(), offer.next(), local);

If calling stitchOffers has changed the current best offer, we update the storage.

179
180
181
182
        if (!oldLocal.eq(local)) {
          locals[outbound_tkn][inbound_tkn] = local;
        }
      }

Set gives to 0. Moreover, the last argument depends on whether the user wishes to get their provision back (if true, gasprice will be set to 0 as well).

184
185
      dirtyDeleteOffer(outbound_tkn, inbound_tkn, offerId, offer, offerDetail, deprovision);

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

187
188
189
      if (deprovision) {
        provision = 10 ** 9 * offerDetail.gasprice() //gasprice is 0 if offer was deprovisioned
          * (offerDetail.gasreq() + offerDetail.offer_gasbase());

credit balanceOf and log transfer

191
192
193
194
195
196
        creditWei(msg.sender, provision);
      }
      emit OfferRetract(outbound_tkn, inbound_tkn, offerId);
    }
  }

Provisioning

Market makers must have enough provisions for possible penalties. These provisions are in ETH. 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.

206
207
208
209
210
211
212
213
214
215
216
217
218
219
  function fund(address maker) public payable {
    unchecked {
      (MgvStructs.GlobalPacked _global,) = config(address(0), address(0));
      liveMgvOnly(_global);
      creditWei(maker, msg.value);
    }
  }

  function fund() external payable {
    unchecked {
      fund(msg.sender);
    }
  }

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

221
222
223
224
225
226
  receive() external payable {
    unchecked {
      fund(msg.sender);
    }
  }

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

228
229
  function withdraw(uint amount) external returns (bool noRevert) {
    unchecked {

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.

231
232
233
234
235
      debitWei(msg.sender, amount);
      (noRevert,) = msg.sender.call{value: amount}("");
    }
  }

Low-level Maker functions


        

Write Offer

239
240
241
  function writeOffer(OfferPack memory ofp, bool update) internal {
    unchecked {

gasprice’s floor is Mangrove’s own gasprice estimate, ofp.global.gasprice. We first check that gasprice fits in 16 bits. Otherwise it could be that uint16(gasprice) < global_gasprice < gasprice, and the actual value we store is uint16(gasprice).

243
244
245
246
247
248
      require(checkGasprice(ofp.gasprice), "mgv/writeOffer/gasprice/16bits");

      if (ofp.gasprice < ofp.global.gasprice()) {
        ofp.gasprice = ofp.global.gasprice();
      }
  • Check gasreq below limit. Implies gasreq at most 24 bits wide, which ensures no overflow in computation of provision (see below).
250
      require(ofp.gasreq <= ofp.global.gasmax(), "mgv/writeOffer/gasreq/tooHigh");
  • Make sure gives > 0 – division by 0 would throw in several places otherwise, and isLive relies on it.
252
      require(ofp.gives > 0, "mgv/writeOffer/gives/tooLow");
  • 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.
254
255
256
257
      require(
        ofp.gives >= (ofp.gasreq + ofp.local.offer_gasbase()) * ofp.local.density(), "mgv/writeOffer/density/tooLow"
      );

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

259
260
261
      require(uint96(ofp.gives) == ofp.gives, "mgv/writeOffer/gives/96bits");
      require(uint96(ofp.wants) == ofp.wants, "mgv/writeOffer/wants/96bits");

The position of the new or updated offer is found using findPosition. If the offer is the best one, prev == 0, and if it’s the last in the book, next == 0.

findPosition is only ever called here, but exists as a separate function to make the code easier to read.

Warning: findPosition will call better, which may read the offer’s offerDetails. So it is important to find the offer position before we update its offerDetail in storage. We waste 1 (hot) read in that case but we deem that the code would get too ugly if we passed the old offerDetail as argument to findPosition and to better, just to save 1 hot read in that specific case.

267
268
      (uint prev, uint next) = findPosition(ofp);

Log the write offer event.

270
271
272
273
      emit OfferWrite(
        ofp.outbound_tkn, ofp.inbound_tkn, msg.sender, ofp.wants, ofp.gives, ofp.gasprice, ofp.gasreq, ofp.id, prev
        );

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

275
276
277
278
279
280
281
282
      uint oldProvision;
      {
        MgvStructs.OfferDetailPacked offerDetail = offerDetails[ofp.outbound_tkn][ofp.inbound_tkn][ofp.id];
        if (update) {
          require(msg.sender == offerDetail.maker(), "mgv/updateOffer/unauthorized");
          oldProvision = 10 ** 9 * offerDetail.gasprice() * (offerDetail.gasreq() + offerDetail.offer_gasbase());
        }

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

284
285
286
287
288
289
290
291
292
293
294
295
296
297
        if (
          !update || offerDetail.gasreq() != ofp.gasreq || offerDetail.gasprice() != ofp.gasprice
            || offerDetail.offer_gasbase() != ofp.local.offer_gasbase()
        ) {
          uint offer_gasbase = ofp.local.offer_gasbase();
          offerDetails[ofp.outbound_tkn][ofp.inbound_tkn][ofp.id] = MgvStructs.OfferDetail.pack({
            __maker: msg.sender,
            __gasreq: ofp.gasreq,
            __offer_gasbase: offer_gasbase,
            __gasprice: ofp.gasprice
          });
        }
      }

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.

299
300
301
302
303
304
305
306
      {
        uint provision = (ofp.gasreq + ofp.local.offer_gasbase()) * ofp.gasprice * 10 ** 9;
        if (provision > oldProvision) {
          debitWei(msg.sender, provision - oldProvision);
        } else if (provision < oldProvision) {
          creditWei(msg.sender, oldProvision - provision);
        }
      }

We now place the offer in the book at the position found by findPosition.


        

First, we test if the offer has moved in the book or is not currently in the book. If !isLive(ofp.oldOffer), we must update its prev/next. If it is live but its prev has changed, we must also update them. Note that checking both prev = oldPrev and next == oldNext would be redundant. If either is true, then the updated offer has not changed position and there is nothing to update.

As a note for future changes, there is a tricky edge case where prev == oldPrev yet the prev/next should be changed: a previously-used offer being brought back in the book, and ending with the same prev it had when it was in the book. In that case, the neighbor is currently pointing to another offer, and thus must be updated. With the current code structure, this is taken care of as a side-effect of checking !isLive, but should be kept in mind. The same goes in the next == oldNext case.

312
      if (!isLive(ofp.oldOffer) || prev != ofp.oldOffer.prev()) {
  • If the offer is not the best one, we update its predecessor; otherwise we update the best value.
314
315
316
317
318
319
        if (prev != 0) {
          offers[ofp.outbound_tkn][ofp.inbound_tkn][prev] = offers[ofp.outbound_tkn][ofp.inbound_tkn][prev].next(ofp.id);
        } else {
          ofp.local = ofp.local.best(ofp.id);
        }
  • If the offer is not the last one, we update its successor.
321
322
323
324
        if (next != 0) {
          offers[ofp.outbound_tkn][ofp.inbound_tkn][next] = offers[ofp.outbound_tkn][ofp.inbound_tkn][next].prev(ofp.id);
        }
  • Recall that in this branch, the offer has changed location, or is not currently in the book. If the offer is not new and already in the book, we must remove it from its previous location by stitching its previous prev/next.
326
327
328
329
330
331
        if (update && isLive(ofp.oldOffer)) {
          ofp.local =
            stitchOffers(ofp.outbound_tkn, ofp.inbound_tkn, ofp.oldOffer.prev(), ofp.oldOffer.next(), ofp.local);
        }
      }

With the prev/next in hand, we finally store the offer in the offers map.

333
334
335
336
337
338
      MgvStructs.OfferPacked ofr =
        MgvStructs.Offer.pack({__prev: prev, __next: next, __wants: ofp.wants, __gives: ofp.gives});
      offers[ofp.outbound_tkn][ofp.inbound_tkn][ofp.id] = ofr;
    }
  }

Find Position


        

findPosition takes a price in the form of a (ofp.wants,ofp.gives) pair, an offer id (ofp.pivotId) and walks the book from that offer (backward or forward) until the right position for the price is found. The position is returned as a (prev,next) pair, with prev or next at 0 to mark the beginning/end of the book (no offer ever has id 0).

If prices are equal, findPosition will put the newest offer last.

343
344
345
346
347
  function findPosition(OfferPack memory ofp) internal view returns (uint, uint) {
    unchecked {
      uint prevId;
      uint nextId;
      uint pivotId = ofp.pivotId;

Get pivot, optimizing for the case where pivot info is already known

349
350
351
      MgvStructs.OfferPacked pivot =
        pivotId == ofp.id ? ofp.oldOffer : offers[ofp.outbound_tkn][ofp.inbound_tkn][pivotId];

In case pivotId is not an active offer, it is unusable (since it is out of the book). We default to the current best offer. If the book is empty pivot will be 0. That is handled through a test in the better comparison function.

353
354
355
356
357
      if (!isLive(pivot)) {
        pivotId = ofp.local.best();
        pivot = offers[ofp.outbound_tkn][ofp.inbound_tkn][pivotId];
      }
  • Pivot is better than wants/gives, we follow next.
359
360
361
362
363
364
365
366
367
368
369
370
      if (better(ofp, pivot, pivotId)) {
        MgvStructs.OfferPacked pivotNext;
        while (pivot.next() != 0) {
          uint pivotNextId = pivot.next();
          pivotNext = offers[ofp.outbound_tkn][ofp.inbound_tkn][pivotNextId];
          if (better(ofp, pivotNext, pivotNextId)) {
            pivotId = pivotNextId;
            pivot = pivotNext;
          } else {
            break;
          }
        }

gets here on empty book

372
373
        (prevId, nextId) = (pivotId, pivot.next());
  • Pivot is strictly worse than wants/gives, we follow prev.
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
      } else {
        MgvStructs.OfferPacked pivotPrev;
        while (pivot.prev() != 0) {
          uint pivotPrevId = pivot.prev();
          pivotPrev = offers[ofp.outbound_tkn][ofp.inbound_tkn][pivotPrevId];
          if (better(ofp, pivotPrev, pivotPrevId)) {
            break;
          } else {
            pivotId = pivotPrevId;
            pivot = pivotPrev;
          }
        }

        (prevId, nextId) = (pivot.prev(), pivotId);
      }

      return (prevId == ofp.id ? ofp.oldOffer.prev() : prevId, nextId == ofp.id ? ofp.oldOffer.next() : nextId);
    }
  }

Better


        

The utility method better takes an offer represented by ofp and another represented by offer1. It returns true iff offer1 is better or as good as ofp. “better” is defined on the lexicographic order price×lexdensity1\textrm{price} \times_{\textrm{lex}} \textrm{density}^{-1}. This means that for the same price, offers that deliver more volume per gas are taken first.

In addition to offer1, we also provide its id, offerId1 in order to save gas. If necessary (ie. if the prices wants1/gives1 and wants2/gives2 are the same), we read storage to get gasreq1 at `offerDetails[…][offerId1].

400
401
402
  function better(OfferPack memory ofp, MgvStructs.OfferPacked offer1, uint offerId1) internal view returns (bool) {
    unchecked {
      if (offerId1 == 0) {

Happens on empty book. Returning false would work as well due to specifics of findPosition but true is more consistent. Here we just want to avoid reading offerDetail[...][0] for nothing.

404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
        return true;
      }
      uint wants1 = offer1.wants();
      uint gives1 = offer1.gives();
      uint wants2 = ofp.wants;
      uint gives2 = ofp.gives;
      uint weight1 = wants1 * gives2;
      uint weight2 = wants2 * gives1;
      if (weight1 == weight2) {
        uint gasreq1 = offerDetails[ofp.outbound_tkn][ofp.inbound_tkn][offerId1].gasreq();
        uint gasreq2 = ofp.gasreq;
        return (gives1 * gasreq2 >= gives2 * gasreq1);
      } else {
        return weight1 < weight2;
      }
    }
  }
}
MgvOfferTaking.sol

        

MgvOfferTaking.sol


        

Copyright © 2021 Giry SAS.


        

        

This program is free software: you can redistribute it and/or modify


        

it under the terms of the GNU Affero General Public License as published


        

by the Free Software Foundation, either version 3 of the License, or


        

(at your option) any later version.


        

        

This program is distributed in the hope that it will be useful,


        

but WITHOUT ANY WARRANTY; without even the implied warranty of


        

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


        

GNU Affero General Public License for more details.


        

        

You should have received a copy of the GNU Affero General Public License


        

along with this program. If not, see https://www.gnu.org/licenses/.

19
20
21
22
23
24
25
26
pragma solidity ^0.8.10;

pragma abicoder v2;

import {IERC20, HasMgvEvents, IMaker, IMgvMonitor, MgvLib, MgvStructs} from "./MgvLib.sol";
import {MgvHasOffers} from "./MgvHasOffers.sol";

abstract contract MgvOfferTaking is MgvHasOffers {

MultiOrder struct


        

The MultiOrder struct is used by market orders and snipes. Some of its fields are only used by market orders (initialWants, initialGives). We need a common data structure for both since low-level calls are shared between market orders and snipes. The struct is helpful in decreasing stack use.

29
30
31
32
33
34
35
36
37
38
39
  struct MultiOrder {
    uint initialWants; // used globally by market order, not used by snipes
    uint initialGives; // used globally by market order, not used by snipes
    uint totalGot; // used globally by market order, per-offer by snipes
    uint totalGave; // used globally by market order, per-offer by snipes
    uint totalPenalty; // used globally
    address taker; // used globally
    bool fillWants; // used globally
    uint feePaid; // used globally
  }

Market Orders


        

Market Order


        

        

A market order specifies a (outbound_tkn,inbound_tkn) pair, a desired total amount of outbound_tkn (takerWants), and an available total amount of inbound_tkn (takerGives). It returns four uints: the total amount of outbound_tkn received, the total amount of inbound_tkn spent, the penalty received by msg.sender (in wei), and the fee paid by the taker (in wei).

The takerGives/takerWants ratio induces a maximum average price that the taker is ready to pay across all offers that will be executed during the market order. It is thus possible to execute an offer with a price worse than the initial (takerGives/takerWants) ratio given as argument to marketOrder if some cheaper offers were executed earlier in the market order.

The market order stops when the price has become too high, or when the end of the book has been reached, or:

  • If fillWants is true, the market order stops when takerWants units of outbound_tkn have been obtained. With fillWants set to true, to buy a specific volume of outbound_tkn at any price, set takerWants to the amount desired and takerGives to 216012^{160}-1.
  • If fillWants is false, the taker is filling gives instead: the market order stops when takerGives units of inbound_tkn have been sold. With fillWants set to false, to sell a specific volume of inbound_tkn at any price, set takerGives to the amount desired and takerWants to 00.
52
53
54
55
56
57
58
59
60
  function marketOrder(address outbound_tkn, address inbound_tkn, uint takerWants, uint takerGives, bool fillWants)
    external
    returns (uint, uint, uint, uint)
  {
    unchecked {
      return generalMarketOrder(outbound_tkn, inbound_tkn, takerWants, takerGives, fillWants, msg.sender);
    }
  }

General Market Order


        

        

General market orders set up the market order with a given taker (msg.sender in the most common case). Returns (totalGot, totalGave, penaltyReceived, feePaid). Note that the taker can be anyone. This is safe when taker == msg.sender, but generalMarketOrder must not be called with taker != msg.sender unless a security check is done after (see MgvOfferTakingWithPermit`.

65
66
67
68
69
70
71
72
73
  function generalMarketOrder(
    address outbound_tkn,
    address inbound_tkn,
    uint takerWants,
    uint takerGives,
    bool fillWants,
    address taker
  ) internal returns (uint, uint, uint, uint) {
    unchecked {

Since amounts stored in offers are 96 bits wide, checking that takerWants and takerGives fit in 160 bits prevents overflow during the main market order loop.

75
76
77
      require(uint160(takerWants) == takerWants, "mgv/mOrder/takerWants/160bits");
      require(uint160(takerGives) == takerGives, "mgv/mOrder/takerGives/160bits");

SingleOrder is defined in MgvLib.sol and holds information for ordering the execution of one offer.

79
80
81
82
      MgvLib.SingleOrder memory sor;
      sor.outbound_tkn = outbound_tkn;
      sor.inbound_tkn = inbound_tkn;
      (sor.global, sor.local) = config(outbound_tkn, inbound_tkn);

Throughout the execution of the market order, the sor’s offer id and other parameters will change. We start with the current best offer id (0 if the book is empty).

84
85
      sor.offerId = sor.local.best();
      sor.offer = offers[outbound_tkn][inbound_tkn][sor.offerId];

sor.wants and sor.gives may evolve, but they are initially however much remains in the market order.

87
88
89
      sor.wants = takerWants;
      sor.gives = takerGives;

MultiOrder (defined above) maintains information related to the entire market order. During the order, initial wants/gives values minus the accumulated amounts traded so far give the amounts that remain to be traded.

91
92
93
94
95
96
      MultiOrder memory mor;
      mor.initialWants = takerWants;
      mor.initialGives = takerGives;
      mor.taker = taker;
      mor.fillWants = fillWants;

For the market order to even start, the market needs to be both active, and not currently protected from reentrancy.

98
99
100
      activeMarketOnly(sor.global, sor.local);
      unlockedMarketOnly(sor.local);

Initialization


        

The market order will operate as follows : it will go through offers from best to worse, starting from offerId, and:


        
  • will maintain remaining takerWants and takerGives values. The initial takerGives/takerWants ratio is the average price the taker will accept. Better prices may be found early in the book, and worse ones later.
  • will not set prev/next pointers to their correct locations at each offer taken (this is an optimization enabled by forbidding reentrancy).
  • after consuming a segment of offers, will update the current best offer to be the best remaining offer on the book.

        

We start be enabling the reentrancy lock for this (outbound_tkn,inbound_tkn) pair.

108
109
110
111
112
      sor.local = sor.local.lock(true);
      locals[outbound_tkn][inbound_tkn] = sor.local;

      emit OrderStart();

Call recursive internalMarketOrder function.

114
115
      internalMarketOrder(mor, sor, true);

Over the course of the market order, a penalty reserved for msg.sender has accumulated in mor.totalPenalty. No actual transfers have occured yet – all the ethers given by the makers as provision are owned by the Mangrove. sendPenalty finally gives the accumulated penalty to msg.sender.

117
118
119
120
      sendPenalty(mor.totalPenalty);

      emit OrderComplete(outbound_tkn, inbound_tkn, taker, mor.totalGot, mor.totalGave, mor.totalPenalty, mor.feePaid);
122
123
124
125
      return (mor.totalGot, mor.totalGave, mor.totalPenalty, mor.feePaid);
    }
  }

Internal market order


        

        

internalMarketOrder works recursively. Going downward, each successive offer is executed until the market order stops (due to: volume exhausted, bad price, or empty book). Then the reentrancy lock is lifted. Going upward, each offer’s maker contract is called again with its remaining gas and given the chance to update its offers on the book.

The last argument is a boolean named proceed. If an offer was not executed, it means the price has become too high. In that case, we notify the next recursive call that the market order should end. In this initial call, no offer has been executed yet so proceed is true.

131
132
  function internalMarketOrder(MultiOrder memory mor, MgvLib.SingleOrder memory sor, bool proceed) internal {
    unchecked {

Case 1 : End of order


        

We execute the offer currently stored in sor.

135
136
137
138
      if (proceed && (mor.fillWants ? sor.wants > 0 : sor.gives > 0) && sor.offerId > 0) {
        uint gasused; // gas used by `makerExecute`
        bytes32 makerData; // data returned by maker

mgvData is an internal Mangrove status code. It may appear in an OrderResult. Its possible values are:

  • "mgv/notExecuted": offer was not executed.
  • "mgv/tradeSuccess": offer execution succeeded. Will appear in OrderResult.
  • "mgv/notEnoughGasForMakerTrade": cannot give maker close enough to gasreq. Triggers a revert of the entire order.
  • "mgv/makerRevert": execution of makerExecute reverted. Will appear in OrderResult.
  • "mgv/makerTransferFail": maker could not send outbound_tkn tokens. Will appear in OrderResult.
  • "mgv/makerReceiveFail": maker could not receive inbound_tkn tokens. Will appear in OrderResult.
  • "mgv/takerTransferFail": taker could not send inbound_tkn tokens. Triggers a revert of the entire order.

mgvData should not be exploitable by the maker!

149
150
        bytes32 mgvData;

Load additional information about the offer. We don’t do it earlier to save one storage read in case proceed was false.

152
153
        sor.offerDetail = offerDetails[sor.outbound_tkn][sor.inbound_tkn][sor.offerId];

execute will adjust sor.wants,sor.gives, and may attempt to execute the offer if its price is low enough. It is crucial that an error due to taker triggers a revert. That way, mgvData not in ["mgv/notExecuted","mgv/tradeSuccess"] means the failure is the maker’s fault.


        

Post-execution, sor.wants/sor.gives reflect how much was sent/taken by the offer. We will need it after the recursive call, so we save it in local variables. Same goes for offerId, sor.offer and sor.offerDetail.

156
157
158
        (gasused, makerData, mgvData) = execute(mor, sor);

Keep cached copy of current sor values.

160
161
162
163
164
165
        uint takerWants = sor.wants;
        uint takerGives = sor.gives;
        uint offerId = sor.offerId;
        MgvStructs.OfferPacked offer = sor.offer;
        MgvStructs.OfferDetailPacked offerDetail = sor.offerDetail;

If an execution was attempted, we move sor to the next offer. Note that the current state is inconsistent, since we have not yet updated sor.offerDetails.

167
168
        if (mgvData != "mgv/notExecuted") {
          sor.wants = mor.initialWants > mor.totalGot ? mor.initialWants - mor.totalGot : 0;

It is known statically that mor.initialGives - mor.totalGave does not underflow since

  1. mor.totalGave was increased by sor.gives during execute,
  2. sor.gives was at most mor.initialGives - mor.totalGave from earlier step,
  3. sor.gives may have been clamped down during execute (to “offer.wants” if the offer is entirely consumed, or to makerWouldWant, cf. code of execute).
174
175
176
177
178
          sor.gives = mor.initialGives - mor.totalGave;
          sor.offerId = sor.offer.next();
          sor.offer = offers[sor.outbound_tkn][sor.inbound_tkn][sor.offerId];
        }

note that internalMarketOrder may be called twice with same offerId, but in that case proceed will be false!

180
181
182
        internalMarketOrder(
          mor,
          sor,

proceed value for next call. Currently, when an offer did not execute, it’s because the offer’s price was too high. In that case we interrupt the loop and let the taker leave with less than they asked for (but at a correct price). We could also revert instead of breaking; this could be a configurable flag for the taker to pick.

184
185
186
          mgvData != "mgv/notExecuted"
        );

Restore sor values from to before recursive call

188
189
190
191
192
193
        sor.offerId = offerId;
        sor.wants = takerWants;
        sor.gives = takerGives;
        sor.offer = offer;
        sor.offerDetail = offerDetail;

After an offer execution, we may run callbacks and increase the total penalty. As that part is common to market orders and snipes, it lives in its own postExecute function.

195
196
197
198
        if (mgvData != "mgv/notExecuted") {
          postExecute(mor, sor, gasused, makerData, mgvData);
        }

Case 2 : End of market order


        

If proceed is false, the taker has gotten its requested volume, or we have reached the end of the book, we conclude the market order.

201
      } else {

During the market order, all executed offers have been removed from the book. We end by stitching together the best offer pointer and the new best offer.

203
        sor.local = stitchOffers(sor.outbound_tkn, sor.inbound_tkn, 0, sor.offerId, sor.local);

Now that the market order is over, we can lift the lock on the book. In the same operation we

  • lift the reentrancy lock, and
  • update the storage

so we are free from out of order storage writes.

211
212
213
        sor.local = sor.local.lock(false);
        locals[sor.outbound_tkn][sor.inbound_tkn] = sor.local;

payTakerMinusFees sends the fee to the vault, proportional to the amount purchased, and gives the rest to the taker

215
216
        payTakerMinusFees(mor, sor);

In an inverted Mangrove, amounts have been lent by each offer’s maker to the taker. We now call the taker. This is a noop in a normal Mangrove.

218
219
220
221
222
        executeEnd(mor, sor);
      }
    }
  }

Sniping


        

Snipes


        

        

snipes executes multiple offers. It takes a uint[4][] as penultimate argument, with each array element of the form [offerId,takerWants,takerGives,offerGasreq]. The return parameters are of the form (successes,snipesGot,snipesGave,bounty,feePaid). Note that we do not distinguish further between mismatched arguments/offer fields on the one hand, and an execution failure on the other. Still, a failed offer has to pay a penalty, and ultimately transaction logs explicitly mention execution failures (see MgvLib.sol).

229
230
231
232
233
234
235
236
237
  function snipes(address outbound_tkn, address inbound_tkn, uint[4][] calldata targets, bool fillWants)
    external
    returns (uint, uint, uint, uint, uint)
  {
    unchecked {
      return generalSnipes(outbound_tkn, inbound_tkn, targets, fillWants, msg.sender);
    }
  }

From an array of n [offerId, takerWants,takerGives,gasreq] elements, execute each snipe in sequence. Returns (successes, takerGot, takerGave, bounty, feePaid).

Note that if this function is not internal, anyone can make anyone use Mangrove. Note that unlike general market order, the returned total values are not mor.totalGot and mor.totalGave, since those are reset at every iteration of the targets array. Instead, accumulators snipesGot and snipesGave are used.

243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
  function generalSnipes(
    address outbound_tkn,
    address inbound_tkn,
    uint[4][] calldata targets,
    bool fillWants,
    address taker
  ) internal returns (uint successCount, uint snipesGot, uint snipesGave, uint totalPenalty, uint feePaid) {
    unchecked {
      MgvLib.SingleOrder memory sor;
      sor.outbound_tkn = outbound_tkn;
      sor.inbound_tkn = inbound_tkn;
      (sor.global, sor.local) = config(outbound_tkn, inbound_tkn);

      MultiOrder memory mor;
      mor.taker = taker;
      mor.fillWants = fillWants;

For the snipes to even start, the market needs to be both active and not currently protected from reentrancy.

261
262
263
264
265
      activeMarketOnly(sor.global, sor.local);
      unlockedMarketOnly(sor.local);

      emit OrderStart();

Main loop


        

        

Call internalSnipes function.

270
271
      (successCount, snipesGot, snipesGave) = internalSnipes(mor, sor, targets);

Over the course of the snipes order, a penalty reserved for msg.sender has accumulated in mor.totalPenalty. No actual transfers have occured yet – all the ethers given by the makers as provision are owned by the Mangrove. sendPenalty finally gives the accumulated penalty to msg.sender.

273
      sendPenalty(mor.totalPenalty);
275
276
277
278
279
280
281
      emit OrderComplete(sor.outbound_tkn, sor.inbound_tkn, taker, snipesGot, snipesGave, mor.totalPenalty, mor.feePaid);
      totalPenalty = mor.totalPenalty;
      feePaid = mor.feePaid;
    }
  }

Internal snipes


        

        

internalSnipes works by looping over targets. Each successive offer is executed under a reentrancy lock, then its posthook is called. Going upward, each offer’s maker contract is called again with its remaining gas and given the chance to update its offers on the book.

285
286
287
288
289
290
  function internalSnipes(MultiOrder memory mor, MgvLib.SingleOrder memory sor, uint[4][] calldata targets)
    internal
    returns (uint successCount, uint snipesGot, uint snipesGave)
  {
    unchecked {
      for (uint i = 0; i < targets.length; i++) {

Reset these amounts since every snipe is treated individually. Only the total penalty is sent at the end of all snipes.

292
293
294
        mor.totalGot = 0;
        mor.totalGave = 0;

Initialize single order struct.

296
297
298
299
        sor.offerId = targets[i][0];
        sor.offer = offers[sor.outbound_tkn][sor.inbound_tkn][sor.offerId];
        sor.offerDetail = offerDetails[sor.outbound_tkn][sor.inbound_tkn][sor.offerId];

If we removed the isLive conditional, a single expired or nonexistent offer in targets would revert the entire transaction (by the division by offer.gives below since offer.gives would be 0). We also check that gasreq is not worse than specified. A taker who does not care about gasreq can specify any amount larger than 22412^{24}-1. A mismatched price will be detected by execute.

301
        if (!isLive(sor.offer) || sor.offerDetail.gasreq() > targets[i][3]) {

We move on to the next offer in the array.

303
304
305
306
307
308
309
          continue;
        } else {
          require(uint96(targets[i][1]) == targets[i][1], "mgv/snipes/takerWants/96bits");
          require(uint96(targets[i][2]) == targets[i][2], "mgv/snipes/takerGives/96bits");
          sor.wants = targets[i][1];
          sor.gives = targets[i][2];

We start be enabling the reentrancy lock for this (outbound_tkn,inbound_tkn) pair.

311
312
313
          sor.local = sor.local.lock(true);
          locals[sor.outbound_tkn][sor.inbound_tkn] = sor.local;

execute will adjust sor.wants,sor.gives, and may attempt to execute the offer if its price is low enough. It is crucial that an error due to taker triggers a revert. That way mgvData not in ["mgv/tradeSuccess","mgv/notExecuted"] means the failure is the maker’s fault.


        

Post-execution, sor.wants/sor.gives reflect how much was sent/taken by the offer.

316
317
318
319
320
321
          (uint gasused, bytes32 makerData, bytes32 mgvData) = execute(mor, sor);

          if (mgvData == "mgv/tradeSuccess") {
            successCount += 1;
          }

In the market order, we were able to avoid stitching back offers after every execute since we knew a continuous segment starting at best would be consumed. Here, we cannot do this optimisation since offers in the targets array may be anywhere in the book. So we stitch together offers immediately after each execute.

323
324
325
326
          if (mgvData != "mgv/notExecuted") {
            sor.local = stitchOffers(sor.outbound_tkn, sor.inbound_tkn, sor.offer.prev(), sor.offer.next(), sor.local);
          }

Now that the current snipe is over, we can lift the lock on the book. In the same operation we

  • lift the reentrancy lock, and
  • update the storage

so we are free from out of order storage writes.

333
334
335
          sor.local = sor.local.lock(false);
          locals[sor.outbound_tkn][sor.inbound_tkn] = sor.local;

payTakerMinusFees sends the fee to the vault, proportional to the amount purchased, and gives the rest to the taker

337
338
          payTakerMinusFees(mor, sor);

In an inverted Mangrove, amounts have been lent by each offer’s maker to the taker. We now call the taker. This is a noop in a normal Mangrove.

340
341
          executeEnd(mor, sor);

After an offer execution, we may run callbacks and increase the total penalty. As that part is common to market orders and snipes, it lives in its own postExecute function.

343
344
345
346
347
348
349
350
351
352
353
          if (mgvData != "mgv/notExecuted") {
            postExecute(mor, sor, gasused, makerData, mgvData);
          }

          snipesGot += mor.totalGot;
          snipesGave += mor.totalGave;
        }
      }
    }
  }

General execution


        

During a market order or a snipes, offers get executed. The following code takes care of executing a single offer with parameters given by a SingleOrder within a larger context given by a MultiOrder.


        

Execute


        

This function will compare sor.wants sor.gives with sor.offer.wants and sor.offer.gives. If the price of the offer is low enough, an execution will be attempted (with volume limited by the offer’s advertised volume).

Summary of the meaning of the return values:

  • gasused is the gas consumed by the execution
  • makerData is the data returned after executing the offer
  • mgvData is an internal Mangrove status code.
365
366
367
368
369
  function execute(MultiOrder memory mor, MgvLib.SingleOrder memory sor)
    internal
    returns (uint gasused, bytes32 makerData, bytes32 mgvData)
  {
    unchecked {

Price comparison


        

        

The current offer has a price p = offerWants ÷ offerGives and the taker is ready to accept a price up to p' = takerGives ÷ takerWants. Comparing offerWants * takerWants and offerGives * takerGives tels us whether p < p'.

374
375
376
377
378
      {
        uint offerWants = sor.offer.wants();
        uint offerGives = sor.offer.gives();
        uint takerWants = sor.wants;
        uint takerGives = sor.gives;

If the price is too high, we return early.

Otherwise we now know we’ll execute the offer.

382
383
384
385
        if (offerWants * takerWants > offerGives * takerGives) {
          return (0, bytes32(0), "mgv/notExecuted");
        }

Specification of value transfers:

Let owo_w be offerWants, ogo_g be offerGives, twt_w be takerWants, tgt_g be takerGives, and f ∈ {w,g} be ww if fillWants is true, gg otherwise.

Let got\textrm{got} be the amount that the taker will receive, and gave\textrm{gave} be the amount that the taker will pay.

Case f=wf = w

If f=wf = w, let got=min(og,tw)\textrm{got} = \min(o_g,t_w), and let gave=owgotog\textrm{gave} = \left\lceil\dfrac{o_w \textrm{got}}{o_g}\right\rceil. This is well-defined since, for live offers, og>0o_g > 0.

In plain english, we only give to the taker up to what they wanted (or what the offer has to give), and follow the offer price to determine what the taker will give.

Since gave\textrm{gave} is rounded up, the price might be overevaluated. Still, we cannot spend more than what the taker specified as takerGives. At this point we know that owtwogtgo_w t_w \leq o_g t_g, so since tgt_g is an integer we have

tgowtwogowgotog=gavet_g \geq \left\lceil\dfrac{o_w t_w}{o_g}\right\rceil \geq \left\lceil\dfrac{o_w \textrm{got}}{o_g}\right\rceil = \textrm{gave}.

Case f=gf = g

If f=gf = g, let gave=min(ow,tg)\textrm{gave} = \min(o_w,t_g), and got=og\textrm{got} = o_g if ow=0o_w = 0, got=oggaveow\textrm{got} = \left\lfloor\dfrac{o_g \textrm{gave}}{o_w}\right\rfloor otherwise.

In plain english, we spend up to what the taker agreed to pay (or what the offer wants), and follow the offer price to determine what the taker will get. This may exceed twt_w.

Price adjustment

Prices are rounded up to ensure maker is not drained on small amounts. It’s economically unlikely, but density protects the taker from being drained anyway so it is better to default towards protecting the maker here.


        

Implementation

First we check the cases (f=wog<tw)(fgow<tg)(f=w \wedge o_g < t_w)\vee(f_g \wedge o_w < t_g), in which case the above spec simplifies to got=og,gave=ow\textrm{got} = o_g, \textrm{gave} = o_w.

Otherwise the offer may be partially consumed.

In the case f=wf=w we don’t touch got\textrm{got} (which was initialized to twt_w) and compute gave=owtwog\textrm{gave} = \left\lceil\dfrac{o_w t_w}{o_g}\right\rceil. As shown above we have gavetg\textrm{gave} \leq t_g.

In the case f=gf=g we don’t touch gave\textrm{gave} (which was initialized to tgt_g) and compute got=og\textrm{got} = o_g if ow=0o_w = 0, and got=ogtgow\textrm{got} = \left\lfloor\dfrac{o_g t_g}{o_w}\right\rfloor otherwise.

425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
        if ((mor.fillWants && offerGives < takerWants) || (!mor.fillWants && offerWants < takerGives)) {
          sor.wants = offerGives;
          sor.gives = offerWants;
        } else {
          if (mor.fillWants) {
            uint product = offerWants * takerWants;
            sor.gives = product / offerGives + (product % offerGives == 0 ? 0 : 1);
          } else {
            if (offerWants == 0) {
              sor.wants = offerGives;
            } else {
              sor.wants = (offerGives * takerGives) / offerWants;
            }
          }
        }
      }

The flashloan is executed by call to flashloan. If the call reverts, it means the maker failed to send back sor.wants outbound_tkn to the taker. Notes :

  • msg.sender is the Mangrove itself in those calls – all operations related to the actual caller should be done outside of this call.
  • any spurious exception due to an error in Mangrove code will be falsely blamed on the Maker, and its provision for the offer will be unfairly taken away.
445
446
447
      (bool success, bytes memory retdata) =
        address(this).call(abi.encodeWithSelector(this.flashloan.selector, sor, mor.taker));

success is true: trade is complete

449
      if (success) {

In case of success, retdata encodes the gas used by the offer.

451
        gasused = abi.decode(retdata, (uint));

mgvData indicates trade success

453
454
455
        mgvData = bytes32("mgv/tradeSuccess");
        emit OfferSuccess(sor.outbound_tkn, sor.inbound_tkn, sor.offerId, mor.taker, sor.wants, sor.gives);

If configured to do so, the Mangrove notifies an external contract that a successful trade has taken place.

457
458
459
460
        if (sor.global.notify()) {
          IMgvMonitor(sor.global.monitor()).notifySuccess(sor, mor.taker);
        }

We update the totals in the multiorder based on the adjusted sor.wants/sor.gives.


        

overflow: sor.{wants,gives} are on 96bits, sor.total{Got,Gave} are on 256 bits.

463
464
465
        mor.totalGot += sor.wants;
        mor.totalGave += sor.gives;
      } else {

In case of failure, retdata encodes a short status code, the gas used by the offer, and an arbitrary 256 bits word sent by the maker.

467
        (mgvData, gasused, makerData) = innerDecode(retdata);

Note that in the ifs, the literals are bytes32 (stack values), while as revert arguments, they are strings (memory pointers).

469
470
471
        if (mgvData == "mgv/makerRevert" || mgvData == "mgv/makerTransferFail" || mgvData == "mgv/makerReceiveFail") {
          emit OfferFail(sor.outbound_tkn, sor.inbound_tkn, sor.offerId, mor.taker, sor.wants, sor.gives, mgvData);

If configured to do so, the Mangrove notifies an external contract that a failed trade has taken place.

473
474
475
          if (sor.global.notify()) {
            IMgvMonitor(sor.global.monitor()).notifyFail(sor, mor.taker);
          }

It is crucial that any error code which indicates an error caused by the taker triggers a revert, because functions that call execute consider that mgvData not in ["mgv/notExecuted","mgv/tradeSuccess"] should be blamed on the maker.

477
478
479
480
481
        } else if (mgvData == "mgv/notEnoughGasForMakerTrade") {
          revert("mgv/notEnoughGasForMakerTrade");
        } else if (mgvData == "mgv/takerTransferFail") {
          revert("mgv/takerTransferFail");
        } else {

This code must be unreachable. Danger: if a well-crafted offer/maker pair can force a revert of flashloan, the Mangrove will be stuck.

483
484
485
486
          revert("mgv/swapError");
        }
      }

Delete the offer. The last argument indicates whether the offer should be stripped of its provision (yes if execution failed, no otherwise). We cannot partially strip an offer provision (for instance, remove only the penalty from a failing offer and leave the rest) since the provision associated with an offer is always deduced from the (gasprice,gasbase,gasreq) parameters and not stored independently. We delete offers whether the amount remaining on offer is > density or not for the sake of uniformity (code is much simpler). We also expect prices to move often enough that the maker will want to update their price anyway. To simulate leaving the remaining volume in the offer, the maker can program their makerPosthook to updateOffer and put the remaining volume back in.

488
489
490
491
492
493
      dirtyDeleteOffer(
        sor.outbound_tkn, sor.inbound_tkn, sor.offerId, sor.offer, sor.offerDetail, mgvData != "mgv/tradeSuccess"
      );
    }
  }

flashloan (abstract)


        

Externally called by execute, flashloan lends money (from the taker to the maker, or from the maker to the taker, depending on the implementation) then calls makerExecute to run the maker liquidity fetching code. If makerExecute is unsuccessful, flashloan reverts (but the larger orderbook traversal will continue).

All flashloan implementations must require(msg.sender) == address(this)).

498
499
  function flashloan(MgvLib.SingleOrder calldata sor, address taker) external virtual returns (uint gasused);

Maker Execute


        

Called by flashloan, makerExecute runs the maker code and checks that it can safely send the desired assets to the taker.

502
503
504
505
506
507
508
509
  function makerExecute(MgvLib.SingleOrder calldata sor) internal returns (uint gasused) {
    unchecked {
      bytes memory cd = abi.encodeWithSelector(IMaker.makerExecute.selector, sor);

      uint gasreq = sor.offerDetail.gasreq();
      address maker = sor.offerDetail.maker();
      uint oldGas = gasleft();

We let the maker pay for the overhead of checking remaining gas and making the call, as well as handling the return data (constant gas since only the first 32 bytes of return data are read). So the require below is just an approximation: if the overhead of (require + cost of CALL) is hh, the maker will receive at worst gasreq63h64\textrm{gasreq} - \frac{63h}{64} gas.


        

Note : as a possible future feature, we could stop an order when there’s not enough gas left to continue processing offers. This could be done safely by checking, as soon as we start processing an offer, whether 63/64(gasleft-offer_gasbase) > gasreq. If no, we could stop and know by induction that there is enough gas left to apply fees, stitch offers, etc for the offers already executed.

512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
      if (!(oldGas - oldGas / 64 >= gasreq)) {
        innerRevert([bytes32("mgv/notEnoughGasForMakerTrade"), "", ""]);
      }

      (bool callSuccess, bytes32 makerData) = controlledCall(maker, gasreq, cd);

      gasused = oldGas - gasleft();

      if (!callSuccess) {
        innerRevert([bytes32("mgv/makerRevert"), bytes32(gasused), makerData]);
      }

      bool transferSuccess = transferTokenFrom(sor.outbound_tkn, maker, address(this), sor.wants);

      if (!transferSuccess) {
        innerRevert([bytes32("mgv/makerTransferFail"), bytes32(gasused), makerData]);
      }
    }
  }

executeEnd (abstract)


        

Called by internalSnipes and internalMarketOrder, executeEnd may run implementation-specific code after all makers have been called once. In InvertedMangrove, the function calls the taker once so they can act on their flashloan. In [Mangrove], it does nothing.

534
535
  function executeEnd(MultiOrder memory mor, MgvLib.SingleOrder memory sor) internal virtual;

Post execute


        

At this point, we know mgvData != "mgv/notExecuted". After executing an offer (whether in a market order or in snipes), we

  1. Call the maker’s posthook and sum the total gas used.
  2. If offer failed: sum total penalty due to msg.sender and give remainder to maker.
541
542
543
544
545
546
547
548
549
550
551
552
553
554
  function postExecute(
    MultiOrder memory mor,
    MgvLib.SingleOrder memory sor,
    uint gasused,
    bytes32 makerData,
    bytes32 mgvData
  ) internal {
    unchecked {
      if (mgvData == "mgv/tradeSuccess") {
        beforePosthook(sor);
      }

      uint gasreq = sor.offerDetail.gasreq();

We are about to call back the maker, giving it its unused gas (gasreq - gasused). Since the gas used so far may exceed gasreq, we prevent underflow in the subtraction below by bounding gasused above with gasreq. We could have decided not to call back the maker at all when there is no gas left, but we do it for uniformity.

556
557
558
559
560
561
562
563
564
565
566
567
      if (gasused > gasreq) {
        gasused = gasreq;
      }

      gasused = gasused + makerPosthook(sor, gasreq - gasused, makerData, mgvData);

      if (mgvData != "mgv/tradeSuccess") {
        mor.totalPenalty += applyPenalty(sor, gasused);
      }
    }
  }

beforePosthook (abstract)


        

Called by makerPosthook, this function can run implementation-specific code before calling the maker has been called a second time. In InvertedMangrove, all makers are called once so the taker gets all of its money in one shot. Then makers are traversed again and the money is sent back to each taker using beforePosthook. In Mangrove, beforePosthook does nothing.

570
571
572
  function beforePosthook(MgvLib.SingleOrder memory sor) internal virtual;

Maker Posthook

574
575
576
577
578
  function makerPosthook(MgvLib.SingleOrder memory sor, uint gasLeft, bytes32 makerData, bytes32 mgvData)
    internal
    returns (uint gasused)
  {
    unchecked {

At this point, mgvData can only be "mgv/tradeSuccess", "mgv/makerRevert", "mgv/makerTransferFail" or "mgv/makerReceiveFail"

580
581
582
583
584
585
586
      bytes memory cd = abi.encodeWithSelector(
        IMaker.makerPosthook.selector, sor, MgvLib.OrderResult({makerData: makerData, mgvData: mgvData})
      );

      address maker = sor.offerDetail.maker();

      uint oldGas = gasleft();

We let the maker pay for the overhead of checking remaining gas and making the call. So the require below is just an approximation: if the overhead of (require + cost of CALL) is hh, the maker will receive at worst gasreq63h64\textrm{gasreq} - \frac{63h}{64} gas.

588
589
590
591
592
593
594
595
596
597
598
599
600
601
      if (!(oldGas - oldGas / 64 >= gasLeft)) {
        revert("mgv/notEnoughGasForMakerPosthook");
      }

      (bool callSuccess, bytes32 posthookData) = controlledCall(maker, gasLeft, cd);

      gasused = oldGas - gasleft();

      if (!callSuccess) {
        emit PosthookFail(sor.outbound_tkn, sor.inbound_tkn, sor.offerId, posthookData);
      }
    }
  }

controlledCall


        

Calls an external function with controlled gas expense. A direct call of the form (,bytes memory retdata) = maker.call{gas}(selector,...args) enables a griefing attack: the maker uses half its gas to write in its memory, then reverts with that memory segment as argument. After a low-level call, solidity automaticaly copies returndatasize bytes of returndata into memory. So the total gas consumed to execute a failing offer could exceed gasreq + offer_gasbase where n is the number of failing offers. In case of success, we read the first 32 bytes of returndata (the signature of makerExecute is bytes32). Otherwise, for compatibility with most errors that bubble up from contract calls and Solidity’s require, we read 32 bytes of returndata starting from the 69th (4 bytes of method sig + 32 bytes of offset + 32 bytes of string length).

604
605
606
607
  function controlledCall(address callee, uint gasreq, bytes memory cd) internal returns (bool success, bytes32 data) {
    unchecked {
      bytes32[4] memory retdata;

if success, read returned bytes 1…32, otherwise read returned bytes 69…100.

609
610
611
612
613
614
615
      assembly {
        success := call(gasreq, callee, 0, add(cd, 32), mload(cd), retdata, 100)
        data := mload(add(mul(iszero(success), 68), retdata))
      }
    }
  }

Penalties


        

Offers are just promises. They can fail. Penalty provisioning discourages from failing too much: we ask makers to provision more ETH than the expected gas cost of executing their offer and penalize them accoridng to wasted gas.

Under normal circumstances, we should expect to see bots with a profit expectation dry-running offers locally and executing snipe on failing offers, collecting the penalty. The result should be a mostly clean book for actual takers (i.e. a book with only successful offers).

Incentive issue: if the gas price increases enough after an offer has been created, there may not be an immediately profitable way to remove the fake offers. In that case, we count on 3 factors to keep the book clean:

  1. Gas price eventually comes down.
  2. Other market makers want to keep the Mangrove attractive and maintain their offer flow.
  3. Mangrove governance (who may collect a fee) wants to keep the Mangrove attractive and maximize exchange volume.

        

        

After an offer failed, part of its provision is given back to the maker and the rest is stored to be sent to the taker after the entire order completes. In applyPenalty, we only credit the maker with its excess provision. So it looks like the maker is gaining something. In fact they’re just getting back a fraction of what they provisioned earlier.


        

Penalty application summary:

  • If the transaction was a success, we entirely refund the maker and send nothing to the taker.
  • Otherwise, the maker loses the cost of gasused + offer_gasbase gas. The gas price is estimated by gasprice.
  • To create the offer, the maker had to provision for gasreq + offer_gasbase gas at a price of offerDetail.gasprice.
  • We do not consider the tx.gasprice.
  • offerDetail.gasbase and offerDetail.gasprice are the values of the Mangrove parameters config.offer_gasbase and config.gasprice when the offer was created. Without caching those values, the provision set aside could end up insufficient to reimburse the maker (or to retribute the taker).
637
638
639
640
641
642
  function applyPenalty(MgvLib.SingleOrder memory sor, uint gasused) internal returns (uint) {
    unchecked {
      uint gasreq = sor.offerDetail.gasreq();

      uint provision = 10 ** 9 * sor.offerDetail.gasprice() * (gasreq + sor.offerDetail.offer_gasbase());

We set gasused = min(gasused,gasreq) since gasreq < gasused is possible e.g. with gasreq = 0 (all calls consume nonzero gas).

644
645
646
647
      if (gasused > gasreq) {
        gasused = gasreq;
      }

As an invariant, applyPenalty is only called when mgvData is not in ["mgv/notExecuted","mgv/tradeSuccess"]

649
650
651
652
653
654
      uint penalty = 10 ** 9 * sor.global.gasprice() * (gasused + sor.local.offer_gasbase());

      if (penalty > provision) {
        penalty = provision;
      }

Here we write to storage the new maker balance. This occurs after possible reentrant calls. How do we know we’re not crediting twice the same amounts? Because the offer’s provision was set to 0 in storage (through dirtyDeleteOffer) before the reentrant calls. In this function, we are working with cached copies of the offer as it was before it was consumed.

656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
      creditWei(sor.offerDetail.maker(), provision - penalty);

      return penalty;
    }
  }

  function sendPenalty(uint amount) internal {
    unchecked {
      if (amount > 0) {
        (bool noRevert,) = msg.sender.call{value: amount}("");
        require(noRevert, "mgv/sendPenaltyReverted");
      }
    }
  }

Post-trade, payTakerMinusFees sends what’s due to the taker and the rest (the fees) to the vault. Routing through the Mangrove like that also deals with blacklisting issues (separates the maker-blacklisted and the taker-blacklisted cases).

672
673
  function payTakerMinusFees(MultiOrder memory mor, MgvLib.SingleOrder memory sor) internal {
    unchecked {

Should be statically provable that the 2 transfers below cannot return false under well-behaved ERC20s and a non-blacklisted, non-0 target.

675
676
677
678
679
680
681
682
683
684
685
686
687
      uint concreteFee = (mor.totalGot * sor.local.fee()) / 10_000;
      if (concreteFee > 0) {
        mor.totalGot -= concreteFee;
        mor.feePaid = concreteFee;
        require(transferToken(sor.outbound_tkn, vault, concreteFee), "mgv/feeTransferFail");
      }
      if (mor.totalGot > 0) {
        require(transferToken(sor.outbound_tkn, mor.taker, mor.totalGot), "mgv/MgvFailToPayTaker");
      }
    }
  }

Misc. functions


        

Regular solidity reverts prepend the string argument with a function signature. Since we wish to transfer data through a revert, the innerRevert function does a low-level revert with only the required data. innerCode decodes this data.

691
692
  function innerDecode(bytes memory data) internal pure returns (bytes32 mgvData, uint gasused, bytes32 makerData) {
    unchecked {

The data pointer is of the form [mgvData,gasused,makerData] where each array element is contiguous and has size 256 bits.

694
695
696
697
698
699
700
701
      assembly {
        mgvData := mload(add(data, 32))
        gasused := mload(add(data, 64))
        makerData := mload(add(data, 96))
      }
    }
  }

innerRevert reverts a raw triple of values to be interpreted by innerDecode.

703
704
705
706
707
708
709
710
  function innerRevert(bytes32[3] memory data) internal pure {
    unchecked {
      assembly {
        revert(data, 96)
      }
    }
  }

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.

716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
  function transferTokenFrom(address tokenAddress, address from, address to, uint value) internal returns (bool) {
    unchecked {
      bytes memory cd = abi.encodeWithSelector(IERC20.transferFrom.selector, from, to, value);
      (bool noRevert, bytes memory data) = tokenAddress.call(cd);
      return (noRevert && (data.length == 0 || abi.decode(data, (bool))));
    }
  }

  function transferToken(address tokenAddress, address to, uint value) internal returns (bool) {
    unchecked {
      bytes memory cd = abi.encodeWithSelector(IERC20.transfer.selector, to, value);
      (bool noRevert, bytes memory data) = tokenAddress.call(cd);
      return (noRevert && (data.length == 0 || abi.decode(data, (bool))));
    }
  }
}
MgvOfferTakingWithPermit.sol

        

MgvOfferTakingWithPermit.sol


        

Copyright © 2021 Giry SAS.


        

        

This program is free software: you can redistribute it and/or modify


        

it under the terms of the GNU Affero General Public License as published


        

by the Free Software Foundation, either version 3 of the License, or


        

(at your option) any later version.


        

        

This program is distributed in the hope that it will be useful,


        

but WITHOUT ANY WARRANTY; without even the implied warranty of


        

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


        

GNU Affero General Public License for more details.


        

        

You should have received a copy of the GNU Affero General Public License


        

along with this program. If not, see https://www.gnu.org/licenses/.

19
20
21
22
23
24
25
26
27
28
pragma solidity ^0.8.10;

pragma abicoder v2;

import {HasMgvEvents} from "./MgvLib.sol";

import {MgvOfferTaking} from "./MgvOfferTaking.sol";

abstract contract MgvOfferTakingWithPermit is MgvOfferTaking {

Takers may provide allowances on specific pairs, 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

32
  mapping(address => mapping(address => mapping(address => mapping(address => uint)))) public allowances;

Storing nonces avoids replay attacks.

34
  mapping(address => uint) public nonces;

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.

36
  bytes32 public constant PERMIT_TYPEHASH = 0xb7bf278e51ab1478b10530c0300f911d9ed3562fc93ab5e6593368fe23c077a2;

Initialized in the constructor, DOMAIN_SEPARATOR avoids cross-application permit reuse.

38
39
40
  bytes32 public immutable DOMAIN_SEPARATOR;

  constructor(string memory contractName) {

Initialize EIP712 DOMAIN_SEPARATOR.

42
43
44
45
46
47
48
49
50
51
52
    DOMAIN_SEPARATOR = keccak256(
      abi.encode(
        keccak256("EIP712Domain(string name,string version,uint256 chainId,address verifyingContract)"),
        keccak256(bytes(contractName)),
        keccak256(bytes("1")),
        block.chainid,
        address(this)
      )
    );
  }

Delegation public functions


        

Adapted from Uniswap v2 contract

56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
  function permit(
    address outbound_tkn,
    address inbound_tkn,
    address owner,
    address spender,
    uint value,
    uint deadline,
    uint8 v,
    bytes32 r,
    bytes32 s
  ) external {
    unchecked {
      require(deadline >= block.timestamp, "mgv/permit/expired");

      uint nonce = nonces[owner]++;
      bytes32 digest = keccak256(
        abi.encodePacked(
          "\x19\x01",
          DOMAIN_SEPARATOR,
          keccak256(abi.encode(PERMIT_TYPEHASH, outbound_tkn, inbound_tkn, owner, spender, value, nonce, deadline))
        )
      );
      address recoveredAddress = ecrecover(digest, v, r, s);
      require(recoveredAddress != address(0) && recoveredAddress == owner, "mgv/permit/invalidSignature");

      allowances[outbound_tkn][inbound_tkn][owner][spender] = value;
      emit Approval(outbound_tkn, inbound_tkn, owner, spender, value);
    }
  }

  function approve(address outbound_tkn, address inbound_tkn, address spender, uint value) external returns (bool) {
    unchecked {
      allowances[outbound_tkn][inbound_tkn][msg.sender][spender] = value;
      emit Approval(outbound_tkn, inbound_tkn, msg.sender, spender, value);
      return true;
    }
  }

The delegate version of marketOrder is marketOrderFor, which takes a taker address as additional argument. Penalties incurred by failed offers will still be sent to msg.sender, but exchanged amounts will be transferred from and to the taker. If the msg.sender’s allowance for the given outbound_tkn,inbound_tkn and taker are strictly less than the total amount eventually spent by taker, the call will fail.


        

Note: marketOrderFor and snipesFor may emit ERC20 Transfer events of value 0 from taker, but that’s already the case with common ERC20 implementations.

97
98
99
100
101
102
103
104
105
106
107
  function marketOrderFor(
    address outbound_tkn,
    address inbound_tkn,
    uint takerWants,
    uint takerGives,
    bool fillWants,
    address taker
  ) external returns (uint takerGot, uint takerGave, uint bounty, uint feePaid) {
    unchecked {
      (takerGot, takerGave, bounty, feePaid) =
        generalMarketOrder(outbound_tkn, inbound_tkn, takerWants, takerGives, fillWants, taker);

The sender’s allowance is verified after the order complete so that takerGave rather than takerGives is checked against the allowance. The former may be lower.

109
110
111
112
      deductSenderAllowance(outbound_tkn, inbound_tkn, taker, takerGave);
    }
  }

The delegate version of snipes is snipesFor, which takes a taker address as additional argument.

114
115
116
117
118
119
120
121
122
123
  function snipesFor(
    address outbound_tkn,
    address inbound_tkn,
    uint[4][] calldata targets,
    bool fillWants,
    address taker
  ) external returns (uint successes, uint takerGot, uint takerGave, uint bounty, uint feePaid) {
    unchecked {
      (successes, takerGot, takerGave, bounty, feePaid) =
        generalSnipes(outbound_tkn, inbound_tkn, targets, fillWants, taker);

The sender’s allowance is verified after the order complete so that the actual amounts are checked against the allowance, instead of the declared takerGives. The former may be lower.

An immediate consequence is that any funds available to Mangrove through approve can be used to clean offers. After a snipesFor where all offers have failed, all token transfers have been reverted, so takerGave=0 and the check will succeed – but the sender will still have received the bounty of the failing offers.

127
128
129
130
      deductSenderAllowance(outbound_tkn, inbound_tkn, taker, takerGave);
    }
  }

Misc. low-level functions


        

Used by *For functions, its both checks that msg.sender was allowed to use the taker’s funds, and decreases the former’s allowance.

134
135
136
137
138
139
140
141
142
143
  function deductSenderAllowance(address outbound_tkn, address inbound_tkn, address owner, uint amount) internal {
    unchecked {
      uint allowed = allowances[outbound_tkn][inbound_tkn][owner][msg.sender];
      require(allowed >= amount, "mgv/lowAllowance");
      allowances[outbound_tkn][inbound_tkn][owner][msg.sender] = allowed - amount;

      emit Approval(outbound_tkn, inbound_tkn, owner, msg.sender, allowed - amount);
    }
  }
}
MgvGovernable.sol

        

MgvGovernable.sol


        

Copyright © 2021 Giry SAS.


        

        

This program is free software: you can redistribute it and/or modify


        

it under the terms of the GNU Affero General Public License as published


        

by the Free Software Foundation, either version 3 of the License, or


        

(at your option) any later version.


        

        

This program is distributed in the hope that it will be useful,


        

but WITHOUT ANY WARRANTY; without even the implied warranty of


        

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


        

GNU Affero General Public License for more details.


        

        

You should have received a copy of the GNU Affero General Public License


        

along with this program. If not, see https://www.gnu.org/licenses/.

19
20
21
22
23
24
25
26
pragma solidity ^0.8.10;

pragma abicoder v2;

import {HasMgvEvents, MgvStructs} from "./MgvLib.sol";
import {MgvRoot} from "./MgvRoot.sol";

contract MgvGovernable is MgvRoot {

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

28
29
30
31
32
33
  address public governance;

  constructor(address _governance, uint _gasprice, uint gasmax) MgvRoot() {
    unchecked {
      emit NewMgv();

Initially, governance is open to anyone.


        

Initialize vault to governance address, and set initial gasprice and gasmax.

37
38
39
      setVault(_governance);
      setGasprice(_gasprice);
      setGasmax(gasmax);

Initialize governance to _governance after parameter setting.

41
42
43
44
      setGovernance(_governance);
    }
  }

authOnly check

46
47
48
49
50
51
52
  function authOnly() internal view {
    unchecked {
      require(msg.sender == governance || msg.sender == address(this) || governance == address(0), "mgv/unauthorized");
    }
  }

Set configuration and Mangrove state


        

Locals


        

active

57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
  function activate(address outbound_tkn, address inbound_tkn, uint fee, uint density, uint offer_gasbase) public {
    unchecked {
      authOnly();
      locals[outbound_tkn][inbound_tkn] = locals[outbound_tkn][inbound_tkn].active(true);
      emit SetActive(outbound_tkn, inbound_tkn, true);
      setFee(outbound_tkn, inbound_tkn, fee);
      setDensity(outbound_tkn, inbound_tkn, density);
      setGasbase(outbound_tkn, inbound_tkn, offer_gasbase);
    }
  }

  function deactivate(address outbound_tkn, address inbound_tkn) public {
    authOnly();
    locals[outbound_tkn][inbound_tkn] = locals[outbound_tkn][inbound_tkn].active(false);
    emit SetActive(outbound_tkn, inbound_tkn, false);
  }

fee

75
76
77
  function setFee(address outbound_tkn, address inbound_tkn, uint fee) public {
    unchecked {
      authOnly();

fee is in basis points, i.e. in percents of a percent.

79
80
81
82
83
84
      require(fee <= 500, "mgv/config/fee/<=500"); // at most 5%
      locals[outbound_tkn][inbound_tkn] = locals[outbound_tkn][inbound_tkn].fee(fee);
      emit SetFee(outbound_tkn, inbound_tkn, fee);
    }
  }

density


        

Useless if global.useOracle != 0

87
88
89
90
91
  function setDensity(address outbound_tkn, address inbound_tkn, uint density) public {
    unchecked {
      authOnly();

      require(checkDensity(density), "mgv/config/density/112bits");
93
94
95
96
97
      locals[outbound_tkn][inbound_tkn] = locals[outbound_tkn][inbound_tkn].density(density);
      emit SetDensity(outbound_tkn, inbound_tkn, density);
    }
  }

gasbase

99
100
101
  function setGasbase(address outbound_tkn, address inbound_tkn, uint offer_gasbase) public {
    unchecked {
      authOnly();

Checking the size of offer_gasbase is necessary to prevent a) data loss when copied to an OfferDetail struct, and b) overflow when used in calculations.

103
      require(uint24(offer_gasbase) == offer_gasbase, "mgv/config/offer_gasbase/24bits");
105
106
107
108
109
      locals[outbound_tkn][inbound_tkn] = locals[outbound_tkn][inbound_tkn].offer_gasbase(offer_gasbase);
      emit SetGasbase(outbound_tkn, inbound_tkn, offer_gasbase);
    }
  }

Globals


        

kill

112
113
114
115
116
117
118
119
  function kill() public {
    unchecked {
      authOnly();
      internal_global = internal_global.dead(true);
      emit Kill();
    }
  }

gasprice


        

Useless if global.useOracle is != 0

122
123
124
125
126
  function setGasprice(uint gasprice) public {
    unchecked {
      authOnly();
      require(checkGasprice(gasprice), "mgv/config/gasprice/16bits");
128
129
130
131
132
133
      internal_global = internal_global.gasprice(gasprice);
      emit SetGasprice(gasprice);
    }
  }

gasmax

135
136
137
  function setGasmax(uint gasmax) public {
    unchecked {
      authOnly();

Since any new gasreq is bounded above by config.gasmax, this check implies that all offers’ gasreq is 24 bits wide at most.

139
      require(uint24(gasmax) == gasmax, "mgv/config/gasmax/24bits");
141
142
143
144
145
      internal_global = internal_global.gasmax(gasmax);
      emit SetGasmax(gasmax);
    }
  }

governance

147
148
149
150
151
152
153
154
155
  function setGovernance(address governanceAddress) public {
    unchecked {
      authOnly();
      require(governanceAddress != address(0), "mgv/config/gov/not0");
      governance = governanceAddress;
      emit SetGovernance(governanceAddress);
    }
  }

vault

157
158
159
160
161
162
163
164
  function setVault(address vaultAddress) public {
    unchecked {
      authOnly();
      vault = vaultAddress;
      emit SetVault(vaultAddress);
    }
  }

monitor

166
167
168
169
170
171
172
173
  function setMonitor(address monitor) public {
    unchecked {
      authOnly();
      internal_global = internal_global.monitor(monitor);
      emit SetMonitor(monitor);
    }
  }

useOracle

175
176
177
178
179
180
181
182
  function setUseOracle(bool useOracle) public {
    unchecked {
      authOnly();
      internal_global = internal_global.useOracle(useOracle);
      emit SetUseOracle(useOracle);
    }
  }

notify

184
185
186
187
188
189
190
191
  function setNotify(bool notify) public {
    unchecked {
      authOnly();
      internal_global = internal_global.notify(notify);
      emit SetNotify(notify);
    }
  }
}
AbstractMangrove.sol

        

AbstractMangrove.sol


        

Copyright © 2021 Giry SAS.


        

        

This program is free software: you can redistribute it and/or modify


        

it under the terms of the GNU Affero General Public License as published


        

by the Free Software Foundation, either version 3 of the License, or


        

(at your option) any later version.


        

        

This program is distributed in the hope that it will be useful,


        

but WITHOUT ANY WARRANTY; without even the implied warranty of


        

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


        

GNU Affero General Public License for more details.


        

        

You should have received a copy of the GNU Affero General Public License


        

along with this program. If not, see https://www.gnu.org/licenses/.

19
20
21
22
23
24
25
26
27
28
pragma solidity ^0.8.10;

pragma abicoder v2;

import {MgvLib} from "./MgvLib.sol";

import {MgvOfferMaking} from "./MgvOfferMaking.sol";
import {MgvOfferTakingWithPermit} from "./MgvOfferTakingWithPermit.sol";
import {MgvGovernable} from "./MgvGovernable.sol";

AbstractMangrove inherits the three contracts that implement generic Mangrove functionality (MgvGovernable,MgvOfferTakingWithPermit and MgvOfferMaking) but does not implement the abstract functions.

30
31
32
33
34
35
abstract contract AbstractMangrove is MgvGovernable, MgvOfferTakingWithPermit, MgvOfferMaking {
  constructor(address governance, uint gasprice, uint gasmax, string memory contractName)
    MgvOfferTakingWithPermit(contractName)
    MgvGovernable(governance, gasprice, gasmax)
  {}
}
Mangrove.sol

        

Mangrove.sol


        

Copyright © 2021 Giry SAS.


        

        

This program is free software: you can redistribute it and/or modify


        

it under the terms of the GNU Affero General Public License as published


        

by the Free Software Foundation, either version 3 of the License, or


        

(at your option) any later version.


        

        

This program is distributed in the hope that it will be useful,


        

but WITHOUT ANY WARRANTY; without even the implied warranty of


        

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


        

GNU Affero General Public License for more details.


        

        

You should have received a copy of the GNU Affero General Public License


        

along with this program. If not, see https://www.gnu.org/licenses/.

19
20
21
22
23
24
25
26
pragma solidity ^0.8.10;

pragma abicoder v2;

import {MgvLib, MgvStructs} from "./MgvLib.sol";

import {AbstractMangrove} from "./AbstractMangrove.sol";

The Mangrove contract implements the “normal” version of Mangrove, where the taker flashloans the desired amount to each maker. Each time, makers are called after the loan. When the order is complete, each maker is called once again (with the orderbook unlocked).

28
29
30
31
32
33
34
35
36
contract Mangrove is AbstractMangrove {
  constructor(address governance, uint gasprice, uint gasmax)
    AbstractMangrove(governance, gasprice, gasmax, "Mangrove")
  {}

  function executeEnd(MultiOrder memory mor, MgvLib.SingleOrder memory sor) internal override {}

  function beforePosthook(MgvLib.SingleOrder memory sor) internal override {}

Flashloan


        

flashloan is for the ‘normal’ mode of operation. It:

  1. Flashloans takerGives inbound_tkn from the taker to the maker and returns false if the loan fails.
  2. Runs offerDetail.maker’s execute function.
  3. Returns the result of the operations, with optional makerData to help the maker debug.
44
45
  function flashloan(MgvLib.SingleOrder calldata sor, address taker) external override returns (uint gasused) {
    unchecked {

flashloan must be used with a call (hence the external modifier) so its effect can be reverted. But a call from the outside would be fatal.

47
      require(msg.sender == address(this), "mgv/flashloan/protected");

The transfer taker -> maker is in 2 steps. First, taker->mgv. Then mgv->maker. With a direct taker->maker transfer, if one of taker/maker is blacklisted, we can’t tell which one. We need to know which one: if we incorrectly blame the taker, a blacklisted maker can block a pair forever; if we incorrectly blame the maker, a blacklisted taker can unfairly make makers fail all the time. Of course we assume that Mangrove is not blacklisted. This 2-step transfer is incompatible with tokens that have transfer fees (more accurately, it uselessly incurs fees twice).

52
53
54
55
56
57
58
59
60
61
62
63
      if (transferTokenFrom(sor.inbound_tkn, taker, address(this), sor.gives)) {
        if (transferToken(sor.inbound_tkn, sor.offerDetail.maker(), sor.gives)) {
          gasused = makerExecute(sor);
        } else {
          innerRevert([bytes32("mgv/makerReceiveFail"), bytes32(0), ""]);
        }
      } else {
        innerRevert([bytes32("mgv/takerTransferFail"), "", ""]);
      }
    }
  }
}
InvertedMangrove.sol

        

InvertedMangrove.sol


        

Copyright © 2021 Giry SAS.


        

        

This program is free software: you can redistribute it and/or modify


        

it under the terms of the GNU Affero General Public License as published


        

by the Free Software Foundation, either version 3 of the License, or


        

(at your option) any later version.


        

        

This program is distributed in the hope that it will be useful,


        

but WITHOUT ANY WARRANTY; without even the implied warranty of


        

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


        

GNU Affero General Public License for more details.


        

        

You should have received a copy of the GNU Affero General Public License


        

along with this program. If not, see https://www.gnu.org/licenses/.

19
20
21
22
23
24
25
26
pragma solidity ^0.8.10;

pragma abicoder v2;

import {ITaker, MgvLib, MgvStructs} from "./MgvLib.sol";

import {AbstractMangrove} from "./AbstractMangrove.sol";

The InvertedMangrove contract implements the “inverted” version of Mangrove, where each maker loans money to the taker. The taker is then called, and finally each maker is sent its payment and called again (with the orderbook unlocked).

28
29
30
31
32
contract InvertedMangrove is AbstractMangrove {
  constructor(address governance, uint gasprice, uint gasmax)
    AbstractMangrove(governance, gasprice, gasmax, "InvertedMangrove")
  {}

execute taker trade

34
35
36
37
38
39
40
41
  function executeEnd(MultiOrder memory mor, MgvLib.SingleOrder memory sor) internal override {
    unchecked {
      ITaker(mor.taker).takerTrade(sor.outbound_tkn, sor.inbound_tkn, mor.totalGot, mor.totalGave);
      bool success = transferTokenFrom(sor.inbound_tkn, mor.taker, address(this), mor.totalGave);
      require(success, "mgv/takerFailToPayTotal");
    }
  }

We use transferFrom with takers (instead of checking balanceOf before/after the call) for the following reason we want the taker to be awaken after all loans have been made, so either

  1. The taker gets a list of all makers and loops through them to pay back, or
  2. we call a new taker method “payback” after returning from each maker call, or
  3. we call transferFrom after returning from each maker call

So :

  1. Would mean accumulating a list of all makers, which would make the market order code too complex
  2. Is OK, but has an extra CALL cost on top of the token transfer, one for each maker. This is unavoidable anyway when calling makerExecute (since the maker must be able to execute arbitrary code at that moment), but we can skip it here.
  3. Is the cheapest, but it has the drawbacks of transferFrom: money must end up owned by the taker, and taker needs to approve Mangrove
52
53
  function beforePosthook(MgvLib.SingleOrder memory sor) internal override {
    unchecked {

If transferToken returns false here, we’re in a special (and bad) situation. The taker is returning part of their total loan to a maker, but the maker can’t receive the tokens. Only case we can see: maker is blacklisted. In that case, we send the tokens to the vault, so things have a chance of getting sorted out later (Mangrove is a token black hole).

55
      if (!transferToken(sor.inbound_tkn, sor.offerDetail.maker(), sor.gives)) {

If that transfer fails there’s nothing we can do – reverting would punish the taker for the maker’s blacklisting.

57
58
59
60
61
        transferToken(sor.inbound_tkn, vault, sor.gives);
      }
    }
  }

Flashloans


        

        

Inverted Flashloan


        

invertedFlashloan is for the ‘arbitrage’ mode of operation. It: 0. Calls the maker’s execute function. If successful (tokens have been sent to taker): 2. Runs taker’s execute function. 4. Returns the results ofthe operations, with optional makerData to help the maker debug.

There are two ways to do the flashloan:

  1. balanceOf before/after
  2. run transferFrom ourselves.

balanceOf pros:

  • maker may transferFrom another address they control; saves gas compared to Mangrove’s transferFrom
  • maker does not need to approve Mangrove

balanceOf cons

  • if the ERC20 transfer method has a callback to receiver, the method does not work (the receiver can set its balance to 0 during the callback)
  • if the taker is malicious, they can analyze the maker code. If the maker goes on any Mangrove2, they may execute code provided by the taker. This would reduce the taker balance and make the maker fail. So the taker could steal the maker’s balance.

We choose transferFrom.

85
86
87
  function flashloan(MgvLib.SingleOrder calldata sor, address) external override returns (uint gasused) {
    unchecked {

invertedFlashloan must be used with a call (hence the external modifier) so its effect can be reverted. But a call from the outside would be fatal.

89
90
91
92
93
      require(msg.sender == address(this), "mgv/invertedFlashloan/protected");
      gasused = makerExecute(sor);
    }
  }
}