amm.gno

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