amm.gno
19.15 Kb · 589 lines
1// Package amm is a minimal constant-product automated market maker for GRC20
2// token pairs, in a single file.
3//
4// It holds many pools in one realm. A pool is created implicitly by its first
5// liquidity deposit and is addressed by the two tokens' grc20reg keys, in
6// either order. Swaps follow x*y=k with a 30 bps fee that stays in the pool
7// and therefore accrues to the liquidity providers.
8//
9// # What it is not
10//
11// Not an oracle: the reserve ratio is a spot price that any trader can move
12// within a single transaction. Nothing should price off this realm.
13// Not audited. Not a router: one hop, one pool, no path finding. Not a
14// place to park value.
15//
16// # Design notes worth knowing before calling it
17//
18// Reserves are stored fields and are NEVER derived from BalanceOf. That is
19// the single decision that removes Uniswap V2's MINIMUM_LIQUIDITY burn, its
20// skim/sync pair, and the first-depositor share-inflation attack in one go:
21// sending tokens straight to this realm's address changes no reserve, no
22// price and no share value. The price of that is blunt and worth stating:
23// tokens sent directly to the realm address are PERMANENTLY STUCK.
24//
25// The first deposit mints shares equal to the token-A amount rather than
26// sqrt(A*B). The geometric mean is cosmetic, every later operation uses only
27// ratios, and dropping it removes an integer square root over a 128-bit
28// product. Later deposits mint min(A-side, B-side) with floor division on
29// both, so an off-ratio deposit always rounds against the depositor.
30//
31// # v1 vs v0: LP shares are a real GRC20 token
32//
33// v0 tracks LP positions in a private avl ledger: smallest possible, but a
34// position can only be held by the address that opened it and is invisible to
35// every other contract. v1 mints one GRC20 token per pool instead, holds its
36// PrivateLedger, and registers it with grc20reg. A position is then an
37// ordinary fungible token: transferable, approvable, usable as collateral,
38// and readable by any realm that knows the registry key.
39//
40// The cost is honest and measurable. Pool creation now also mints a token and
41// writes a registry entry. Positions gain an allowance surface, and with it
42// the classic GRC20 approve race. And because MsgCall cannot pass a realm
43// argument, this realm has to re-export Transfer/Approve/TransferFrom/
44// Allowance wrappers over the LP token for signing users, four functions that
45// v0 does not need at all. Another REALM can skip them and move its own LP
46// balance through grc20reg directly.
47//
48// All amounts are int64, as GRC20 mandates, and there is no 256-bit type in
49// reach. Pricing therefore runs through a 128-bit mulDiv (math/bits), and
50// every reserve is capped at maxReserve so that the plain int64 parts of the
51// formula cannot overflow. See the comment on maxReserve for the arithmetic,
52// and note the consequence: this AMM is unusable with 18-decimal tokens.
53// Six to nine decimals is the practical band.
54//
55// Design study and full analysis: https://github.com/moul/gno-contracts/issues/135
56package amm
57
58import (
59 "chain"
60 "math"
61 "math/bits"
62 "strconv"
63
64 "gno.land/p/nt/avl/v0"
65 "gno.land/p/nt/grc20/v0"
66 "gno.land/p/nt/seqid/v0"
67 "gno.land/p/nt/ufmt/v0"
68 "gno.land/r/nt/grc20reg/v0"
69)
70
71const (
72 // feeNum/feeDen is the swap fee kept by the pool: 997/1000, i.e. 30 bps.
73 feeNum = 997
74 feeDen = 1000
75
76 // maxReserve is the largest reserve a pool will hold, in base units.
77 //
78 // Pricing computes den = reserveIn*feeDen + amountIn*feeNum in plain
79 // int64 before handing off to the 128-bit mulDiv. Capping every reserve,
80 // and every post-swap reserve, at MaxInt64/feeDen makes that sum provably
81 // safe:
82 //
83 // den < (reserveIn + amountIn) * feeDen <= maxReserve * feeDen
84 // = 9223372036854775000 <= MaxInt64 = 9223372036854775807
85 //
86 // AddLiquidity enforces the cap on the reserves themselves and Swap
87 // enforces it on reserveIn+amountIn, so a pool can never even enter the
88 // region where the formula would be unsafe.
89 maxReserve = math.MaxInt64 / feeDen // 9223372036854775
90)
91
92// pool is one token pair. keyA < keyB always holds: the pair is canonicalised
93// on the way in, so (X,Y) and (Y,X) address the same pool.
94type pool struct {
95 keyA, keyB string
96 tokA, tokB *grc20.Token
97 resA, resB int64
98
99 // lp is this pool's LP token: total supply is the share supply and a
100 // holder's balance is their position. lpLedger is the minting authority
101 // and MUST NOT leak out of this file. lpKey is lp's grc20reg key.
102 lp *grc20.Token
103 lpLedger *grc20.PrivateLedger
104 lpKey string
105}
106
107// pools maps the pool id "keyA~keyB" -> *pool. "~" cannot occur in a
108// grc20reg key, and unlike "|" it does not break a markdown table cell.
109var pools avl.Tree
110
111// lpSeq numbers the LP tokens. It is never reset, so a symbol is never reused
112// and grc20reg's one-token-per-realm-and-symbol rule is never tripped.
113var lpSeq seqid.ID
114
115//
116// Writes.
117//
118
119// AddLiquidity deposits up to maxA of keyA and maxB of keyB and mints LP
120// shares to the caller. It creates the pool if this is its first deposit, in
121// which case the caller's amounts set the starting price and the whole of
122// maxA and maxB is taken.
123//
124// On an existing pool the deposit is trimmed to the current reserve ratio:
125// only one side is consumed in full and the remainder of the richer side is
126// left untouched, so pass the amounts you are willing to spend, not the
127// amounts you insist on spending.
128//
129// The caller must first Approve this realm's address on BOTH tokens for at
130// least the amounts that will be taken. Returns the shares minted.
131func AddLiquidity(cur realm, keyA, keyB string, maxA, maxB int64) int64 {
132 a, b, flipped := canon(keyA, keyB)
133 amtA, amtB := maxA, maxB
134 if flipped {
135 amtA, amtB = maxB, maxA
136 }
137 if amtA <= 0 || amtB <= 0 {
138 panic("amm: both deposit amounts must be > 0")
139 }
140
141 p := getPool(a, b)
142 if p == nil {
143 p = newPool(0, cur, a, b)
144 pools.Set(poolID(a, b), p)
145 }
146
147 var minted int64
148 if p.lp.TotalSupply() == 0 {
149 // First position: the depositor sets the price and the share unit is
150 // token A at seed time. No sqrt, no MINIMUM_LIQUIDITY burn.
151 minted = amtA
152 } else {
153 // Trim to the current ratio, then mint from whichever side is scarcer.
154 // Both divisions floor, and taking the minimum means an off-ratio
155 // deposit is rounded against the depositor, never against the pool.
156 if want := mulDiv(amtA, p.resB, p.resA); want <= amtB {
157 amtB = want
158 } else {
159 amtA = mulDiv(amtB, p.resA, p.resB)
160 }
161 if amtA <= 0 || amtB <= 0 {
162 panic("amm: deposit too small for the current ratio")
163 }
164 supply := p.lp.TotalSupply()
165 minted = min64(
166 mulDiv(amtA, supply, p.resA),
167 mulDiv(amtB, supply, p.resB),
168 )
169 }
170 if minted <= 0 {
171 panic("amm: deposit mints zero shares")
172 }
173 if p.resA+amtA > maxReserve || p.resB+amtB > maxReserve {
174 panic("amm: reserve cap exceeded")
175 }
176
177 provider := cur.Previous().Address()
178 self := cur.Address()
179 pull(0, cur, p.tokA, provider, self, amtA)
180 pull(0, cur, p.tokB, provider, self, amtB)
181
182 p.resA += amtA
183 p.resB += amtB
184 if err := p.lpLedger.Mint(provider, minted); err != nil {
185 panic("amm: cannot mint LP shares: " + err.Error())
186 }
187
188 chain.Emit("AddLiquidity",
189 "pool", poolID(p.keyA, p.keyB),
190 "provider", provider.String(),
191 "amountA", itoa(amtA),
192 "amountB", itoa(amtB),
193 "shares", itoa(minted),
194 )
195 return minted
196}
197
198// RemoveLiquidity burns shares held by the caller and returns the proportional
199// amounts of both tokens, in the caller's (keyA, keyB) argument order.
200//
201// Burning the pool's entire share supply pays out the whole reserve, so the
202// last provider out leaves nothing unclaimable behind and the pool can be
203// reseeded at a fresh price.
204func RemoveLiquidity(cur realm, keyA, keyB string, shares int64) (int64, int64) {
205 if shares <= 0 {
206 panic("amm: shares must be > 0")
207 }
208 a, b, flipped := canon(keyA, keyB)
209 p := mustPool(a, b)
210
211 owner := cur.Previous().Address()
212 if p.lp.BalanceOf(owner) < shares {
213 panic("amm: insufficient shares")
214 }
215
216 supply := p.lp.TotalSupply()
217 var amtA, amtB int64
218 if shares == supply {
219 amtA, amtB = p.resA, p.resB
220 } else {
221 amtA = mulDiv(shares, p.resA, supply)
222 amtB = mulDiv(shares, p.resB, supply)
223 }
224 if amtA <= 0 || amtB <= 0 {
225 panic("amm: burn would return nothing on one side")
226 }
227
228 p.resA -= amtA
229 p.resB -= amtB
230 if err := p.lpLedger.Burn(owner, shares); err != nil {
231 panic("amm: cannot burn LP shares: " + err.Error())
232 }
233
234 push(0, cur, p.tokA, owner, amtA)
235 push(0, cur, p.tokB, owner, amtB)
236
237 chain.Emit("RemoveLiquidity",
238 "pool", poolID(p.keyA, p.keyB),
239 "provider", owner.String(),
240 "amountA", itoa(amtA),
241 "amountB", itoa(amtB),
242 "shares", itoa(shares),
243 )
244 if flipped {
245 return amtB, amtA
246 }
247 return amtA, amtB
248}
249
250// Swap sells amountIn of keyIn for keyOut and aborts unless at least minOut
251// comes back. The caller must first Approve this realm's address on keyIn.
252//
253// minOut is the only protection against being sandwiched or against the pool
254// moving between quoting and execution. Pass a real bound; passing 0 means
255// accepting any price at all.
256func Swap(cur realm, keyIn, keyOut string, amountIn, minOut int64) int64 {
257 if amountIn <= 0 {
258 panic("amm: amountIn must be > 0")
259 }
260 if minOut < 0 {
261 panic("amm: minOut must be >= 0")
262 }
263 a, b, flipped := canon(keyIn, keyOut)
264 p := mustPool(a, b)
265
266 resIn, resOut := p.resA, p.resB
267 tokIn, tokOut := p.tokA, p.tokB
268 if flipped {
269 resIn, resOut = p.resB, p.resA
270 tokIn, tokOut = p.tokB, p.tokA
271 }
272
273 out := AmountOut(amountIn, resIn, resOut)
274 if out <= 0 {
275 panic("amm: output rounds to zero")
276 }
277 if out < minOut {
278 panic("amm: slippage, output below minOut")
279 }
280
281 trader := cur.Previous().Address()
282 pull(0, cur, tokIn, trader, cur.Address(), amountIn)
283
284 newIn, newOut := resIn+amountIn, resOut-out
285 // The invariant holds by construction (out is floored), so this can only
286 // fire if the pricing above is ever edited into being wrong. It is exact:
287 // both products are compared in 128 bits.
288 if cmpProd(newIn, newOut, resIn, resOut) < 0 {
289 panic("amm: constant product regression")
290 }
291 if flipped {
292 p.resB, p.resA = newIn, newOut
293 } else {
294 p.resA, p.resB = newIn, newOut
295 }
296
297 push(0, cur, tokOut, trader, out)
298
299 chain.Emit("Swap",
300 "pool", poolID(p.keyA, p.keyB),
301 "trader", trader.String(),
302 "tokenIn", tokIn.GetSymbol(),
303 "amountIn", itoa(amountIn),
304 "amountOut", itoa(out),
305 )
306 return out
307}
308
309// TransferLP moves amount of the caller's LP position to `to`.
310//
311// The LP token lives in this realm, so a signing user cannot reach it through
312// the token's own entry points the way they would for any other GRC20: there
313// are none. These four wrappers are that entry point. A REALM holding LP does
314// not need them and can go through grc20reg instead:
315//
316// grc20reg.Transfer(0, cur, amm.LPToken(keyA, keyB), to, n)
317func TransferLP(cur realm, keyA, keyB string, to address, amount int64) {
318 a, b, _ := canon(keyA, keyB)
319 lpCheck(mustPool(a, b).lpLedger.CallerTeller().Transfer(0, cur, to, amount))
320}
321
322// ApproveLP lets spender move up to amount of the caller's LP position.
323//
324// Same approve race as any GRC20: an allowance changed from a non-zero value
325// can be spent at both the old and the new one if the holder is unlucky with
326// ordering. Set it to 0 first when lowering it.
327func ApproveLP(cur realm, keyA, keyB string, spender address, amount int64) {
328 a, b, _ := canon(keyA, keyB)
329 lpCheck(mustPool(a, b).lpLedger.CallerTeller().Approve(0, cur, spender, amount))
330}
331
332// TransferFromLP spends an allowance the owner granted to the caller.
333func TransferFromLP(cur realm, keyA, keyB string, from, to address, amount int64) {
334 a, b, _ := canon(keyA, keyB)
335 lpCheck(mustPool(a, b).lpLedger.CallerTeller().TransferFrom(0, cur, from, to, amount))
336}
337
338func lpCheck(err error) {
339 if err != nil {
340 panic("amm: LP token: " + err.Error())
341 }
342}
343
344//
345// Reads.
346//
347
348// AmountOut is the pricing function, fee included, as a pure function of the
349// two reserves. Exported so a caller can quote off-chain against reserves it
350// already holds, and so the arithmetic is testable on its own.
351func AmountOut(amountIn, reserveIn, reserveOut int64) int64 {
352 if amountIn <= 0 {
353 panic("amm: amountIn must be > 0")
354 }
355 if reserveIn <= 0 || reserveOut <= 0 {
356 panic("amm: pool has an empty reserve")
357 }
358 if reserveIn > maxReserve || reserveOut > maxReserve {
359 panic("amm: reserve above cap")
360 }
361 if amountIn > maxReserve-reserveIn {
362 panic("amm: reserve cap exceeded")
363 }
364 inFee := amountIn * feeNum
365 den := reserveIn*feeDen + inFee
366 return mulDiv(inFee, reserveOut, den)
367}
368
369// Quote prices amountIn of keyIn against the pool's live reserves. It is the
370// number Swap would return right now, which is not a promise about the next
371// block.
372func Quote(keyIn, keyOut string, amountIn int64) int64 {
373 a, b, flipped := canon(keyIn, keyOut)
374 p := mustPool(a, b)
375 if flipped {
376 return AmountOut(amountIn, p.resB, p.resA)
377 }
378 return AmountOut(amountIn, p.resA, p.resB)
379}
380
381// Reserves returns the two reserves in the caller's argument order.
382func Reserves(keyA, keyB string) (int64, int64) {
383 a, b, flipped := canon(keyA, keyB)
384 p := mustPool(a, b)
385 if flipped {
386 return p.resB, p.resA
387 }
388 return p.resA, p.resB
389}
390
391// SharesOf returns owner's LP shares, i.e. their LP token balance.
392func SharesOf(keyA, keyB string, owner address) int64 {
393 a, b, _ := canon(keyA, keyB)
394 return mustPool(a, b).lp.BalanceOf(owner)
395}
396
397// TotalShares returns the pool's LP token total supply.
398func TotalShares(keyA, keyB string) int64 {
399 a, b, _ := canon(keyA, keyB)
400 return mustPool(a, b).lp.TotalSupply()
401}
402
403// LPToken returns the grc20reg key of the pool's LP token. Hand it to any
404// realm that should read or move these positions without importing this one.
405func LPToken(keyA, keyB string) string {
406 a, b, _ := canon(keyA, keyB)
407 return mustPool(a, b).lpKey
408}
409
410// AllowanceLP reports how much of owner's LP position spender may move.
411func AllowanceLP(keyA, keyB string, owner, spender address) int64 {
412 a, b, _ := canon(keyA, keyB)
413 return mustPool(a, b).lp.Allowance(owner, spender)
414}
415
416// PoolCount returns how many pools exist.
417func PoolCount() int { return pools.Size() }
418
419// Render lists every pool, or one pool's detail when path is a "keyA~keyB"
420// pool id.
421func Render(path string) string {
422 if path != "" {
423 v := pools.Get(path)
424 if v == nil {
425 return "# 404\n\nNo pool `" + path + "`.\n"
426 }
427 p := v.(*pool)
428 out := "# " + p.tokA.GetSymbol() + " / " + p.tokB.GetSymbol() + "\n\n"
429 out += "- **" + p.tokA.GetSymbol() + "** reserve: " + itoa(p.resA) + " (`" + p.keyA + "`)\n"
430 out += "- **" + p.tokB.GetSymbol() + "** reserve: " + itoa(p.resB) + " (`" + p.keyB + "`)\n"
431 out += "- **LP token**: `" + p.lpKey + "` (" + p.lp.GetSymbol() + ")\n"
432 out += "- **LP shares**: " + itoa(p.lp.TotalSupply()) + " across " + strconv.Itoa(p.lp.KnownAccounts()) + " holder(s)\n"
433 return out
434 }
435
436 out := "# Minimal AMM\n\n"
437 out += "Constant product (`x*y=k`) with a 30 bps fee kept by the pool. Every position is a transferable GRC20 LP token. Reserves are stored, never read from balances, so sending tokens here directly does nothing and they cannot be recovered.\n\n"
438 if pools.Size() == 0 {
439 out += "_No pools yet. Call `AddLiquidity` with two `grc20reg` keys to open one._\n"
440 return out
441 }
442 out += "| pool | reserves | LP token | supply | holders |\n"
443 out += "|---|---|---|---|---|\n"
444 pools.Iterate("", "", func(key string, value any) bool {
445 p := value.(*pool)
446 out += ufmt.Sprintf("| [%s/%s](/r/moul/x/amm/v0:%s) | %d %s / %d %s | %s | %d | %d |\n",
447 p.tokA.GetSymbol(), p.tokB.GetSymbol(), key,
448 p.resA, p.tokA.GetSymbol(), p.resB, p.tokB.GetSymbol(),
449 p.lp.GetSymbol(), p.lp.TotalSupply(), p.lp.KnownAccounts())
450 return false
451 })
452 return out
453}
454
455//
456// Internals.
457//
458
459// canon sorts a caller's token pair into the pool's canonical order and
460// reports whether the caller's order was reversed.
461func canon(first, second string) (a, b string, flipped bool) {
462 if first == "" || second == "" {
463 panic("amm: empty token key")
464 }
465 if first == second {
466 panic("amm: a pool needs two different tokens")
467 }
468 if first > second {
469 return second, first, true
470 }
471 return first, second, false
472}
473
474// newPool resolves both tokens, mints this pool's LP token and registers it.
475//
476// Non-crossing (`_ int, rlm realm`): grc20.NewToken binds the token's
477// origRealm to rlm.PkgPath() under an IsCurrent assertion, and grc20reg
478// keys off the registering caller, so rlm has to stay AddLiquidity's own
479// live frame rather than a fresh one.
480//
481// The LP unit is token A at seed time, so the LP token mirrors token A's
482// decimals. The symbol is LP<n> because grc20 caps a symbol at 11 chars,
483// which "LP-" plus two 11-char symbols would blow past; the human-readable
484// pair lives in the name instead.
485func newPool(_ int, rlm realm, a, b string) *pool {
486 tokA, tokB := grc20reg.MustGet(a), grc20reg.MustGet(b)
487 id := lpSeq.Next()
488 lp, ledger := grc20.NewToken(
489 "AMM LP "+tokA.GetSymbol()+"/"+tokB.GetSymbol(),
490 "LP"+strconv.FormatUint(uint64(id), 10),
491 tokA.GetDecimals(),
492 id,
493 rlm,
494 )
495 p := &pool{keyA: a, keyB: b, tokA: tokA, tokB: tokB, lp: lp, lpLedger: ledger}
496 p.lpKey = grc20reg.Register(cross(rlm), lp, "")
497 return p
498}
499
500// poolID is the storage and render key for a canonicalised pair.
501func poolID(a, b string) string { return a + "~" + b }
502
503func getPool(a, b string) *pool {
504 v := pools.Get(poolID(a, b))
505 if v == nil {
506 return nil
507 }
508 return v.(*pool)
509}
510
511func mustPool(a, b string) *pool {
512 p := getPool(a, b)
513 if p == nil {
514 panic("amm: no such pool: " + poolID(a, b))
515 }
516 return p
517}
518
519// pull moves amount of tok from `from` into this realm, spending the
520// allowance `from` granted to this realm's address.
521//
522// Non-crossing on purpose: `_ int, rlm realm` is the only shape that keeps
523// rlm the caller's own live frame. RealmTeller binds the spender eagerly to
524// rlm.Address(), which is this realm.
525func pull(_ int, rlm realm, tok *grc20.Token, from, to address, amount int64) {
526 err := tok.RealmTeller(0, rlm).TransferFrom(0, rlm, from, to, amount)
527 if err != nil {
528 panic("amm: cannot take " + tok.GetSymbol() + ": " + err.Error())
529 }
530}
531
532// push sends amount of tok from this realm to `to`.
533func push(_ int, rlm realm, tok *grc20.Token, to address, amount int64) {
534 err := tok.RealmTeller(0, rlm).Transfer(0, rlm, to, amount)
535 if err != nil {
536 panic("amm: cannot send " + tok.GetSymbol() + ": " + err.Error())
537 }
538}
539
540// mulDiv returns floor(a*b/c) through a 128-bit intermediate, which plain
541// int64 arithmetic cannot do: a*b is routinely wider than 63 bits here even
542// when the quotient is small.
543func mulDiv(a, b, c int64) int64 {
544 if a < 0 || b < 0 {
545 panic("amm: negative operand")
546 }
547 if c <= 0 {
548 panic("amm: division by a non-positive value")
549 }
550 hi, lo := bits.Mul64(uint64(a), uint64(b))
551 // bits.Div64 panics for y <= hi; refusing here turns that into a named
552 // abort and also covers every quotient that would not fit in 64 bits.
553 if hi >= uint64(c) {
554 panic("amm: quotient overflows int64")
555 }
556 q, _ := bits.Div64(hi, lo, uint64(c))
557 if q > uint64(math.MaxInt64) {
558 panic("amm: quotient overflows int64")
559 }
560 return int64(q)
561}
562
563// cmpProd compares a*b with c*d exactly, in 128 bits, and returns -1, 0 or 1.
564func cmpProd(a, b, c, d int64) int {
565 h1, l1 := bits.Mul64(uint64(a), uint64(b))
566 h2, l2 := bits.Mul64(uint64(c), uint64(d))
567 if h1 != h2 {
568 if h1 < h2 {
569 return -1
570 }
571 return 1
572 }
573 if l1 != l2 {
574 if l1 < l2 {
575 return -1
576 }
577 return 1
578 }
579 return 0
580}
581
582func min64(a, b int64) int64 {
583 if a < b {
584 return a
585 }
586 return b
587}
588
589func itoa(v int64) string { return strconv.FormatInt(v, 10) }
