pair.gno
14.84 Kb · 478 lines
1// Package pair is the whole behaviour of one constant-product AMM pair, as a
2// pure package, so that a realm holding a single pair can be twenty lines of
3// glue.
4//
5// It is the shared half of the instance-per-realm pattern: deploy this once,
6// then deploy one tiny realm per token couple, each owning its own state, its
7// own funds and its own storage deposit, all running this identical code. The
8// Ethereum shape it copies (a factory spawning one UniswapV2Pair per couple)
9// needs EIP-1167 clones to make the duplication affordable; an import makes it
10// free.
11//
12// # How an instance uses it
13//
14// var p *pair.Pair
15//
16// func init(cur realm) {
17// p = pair.New(keyA, keyB, grc20reg.MustGet(keyA), grc20reg.MustGet(keyB))
18// pairreg.Register(cross(cur), p)
19// }
20//
21// func Swap(cur realm, keyIn string, amountIn, minOut int64) int64 {
22// return p.Swap(0, cur, keyIn, amountIn, minOut)
23// }
24//
25// # Why the methods look like that
26//
27// Every state-changing method is shaped (_ int, rlm realm, ...). The leading
28// dummy is mandatory: gno rejects a function whose FIRST parameter is realm
29// when it is declared in a pure package ("crossing function declared in
30// non-realm package"), and the parameter cannot be named cur either. Same
31// reason grc20's tellers are Transfer(_ int, rlm realm, ...). The realm value
32// arrives non-crossing, which is exactly what is wanted: the frame stays the
33// instance realm, so funds move to and from the INSTANCE's address, and
34// rlm.IsCurrent() still holds for grc20's spoof check.
35//
36// A pure package also cannot import a realm at all, so this package never
37// resolves a token by path. The instance passes *grc20.Token handles in.
38//
39// # The economics, unchanged from the single-realm design
40//
41// Constant product x*y=k with a 30 bps fee kept by the pool, reserves stored
42// and never derived from BalanceOf (so a direct transfer to the realm is
43// inert, and permanently stuck), first deposit minting shares equal to the
44// token-A amount with no sqrt and no MINIMUM_LIQUIDITY burn, and every reserve
45// capped so the int64 arithmetic cannot overflow. The reasoning behind each of
46// those is in https://github.com/moul/gno-contracts/issues/135 and is not
47// repeated here; this package is that design with one pool per realm instead
48// of many pools in one realm.
49//
50// Consequence worth repeating, because it bites: with a 1000x fee denominator
51// on int64 amounts, this is unusable with 18-decimal tokens. Six to nine
52// decimals is the practical band.
53package pair
54
55import (
56 "chain"
57 "math"
58 "math/bits"
59 "strconv"
60
61 "gno.land/p/nt/avl/v0"
62 "gno.land/p/nt/grc20/v0"
63 "gno.land/p/nt/ufmt/v0"
64)
65
66const (
67 // feeNum/feeDen is the swap fee kept by the pool: 997/1000, i.e. 30 bps.
68 feeNum = 997
69 feeDen = 1000
70
71 // maxReserve is the largest reserve a pair will hold, in base units.
72 //
73 // Pricing computes den = reserveIn*feeDen + amountIn*feeNum in plain
74 // int64 before handing off to the 128-bit mulDiv. Capping every reserve,
75 // and every post-swap reserve, at MaxInt64/feeDen makes that sum provably
76 // safe:
77 //
78 // den < (reserveIn + amountIn) * feeDen <= maxReserve * feeDen
79 // = 9223372036854775000 <= MaxInt64 = 9223372036854775807
80 MaxReserve = math.MaxInt64 / feeDen // 9223372036854775
81)
82
83// Pair is one token couple and its liquidity. Fields are concrete by design:
84// the registry realm holds a live pointer to this struct and reads it while
85// rendering, so an interface or a func field here would let a hostile
86// instance hand foreign code to the registry's frame.
87//
88// keyA < keyB always holds; New canonicalises.
89type Pair struct {
90 keyA, keyB string
91 tokA, tokB *grc20.Token
92 resA, resB int64
93 totalShares int64
94 shares *avl.Tree // address string -> int64
95}
96
97// New builds an empty pair from two grc20reg keys and the matching token
98// handles, in canonical order. The caller (the instance realm) is responsible
99// for resolving the handles, because a pure package cannot import the
100// registry realm that holds them.
101func New(keyA, keyB string, tokA, tokB *grc20.Token) *Pair {
102 if keyA == "" || keyB == "" {
103 panic("pair: empty token key")
104 }
105 if keyA == keyB {
106 panic("pair: a pair needs two different tokens")
107 }
108 if tokA == nil || tokB == nil {
109 panic("pair: nil token")
110 }
111 if keyA > keyB {
112 keyA, keyB = keyB, keyA
113 tokA, tokB = tokB, tokA
114 }
115 return &Pair{keyA: keyA, keyB: keyB, tokA: tokA, tokB: tokB, shares: avl.NewTree()}
116}
117
118//
119// Writes. Each one takes the instance realm's own cur, forwarded.
120//
121
122// AddLiquidity deposits up to maxA of token A and maxB of token B and mints LP
123// shares to the caller. On an existing pair the deposit is trimmed to the
124// current reserve ratio, so pass the amounts you are willing to spend, not the
125// amounts you insist on spending.
126//
127// The caller must first Approve the INSTANCE realm's address on both tokens.
128// Returns the shares minted.
129func (p *Pair) AddLiquidity(_ int, rlm realm, maxA, maxB int64) int64 {
130 if maxA <= 0 || maxB <= 0 {
131 panic("pair: both deposit amounts must be > 0")
132 }
133 amtA, amtB := maxA, maxB
134
135 var minted int64
136 if p.totalShares == 0 {
137 // First position: the depositor sets the price and the share unit is
138 // token A at seed time. No sqrt, no MINIMUM_LIQUIDITY burn.
139 minted = amtA
140 } else {
141 // Trim to the current ratio, then mint from whichever side is scarcer.
142 // Both divisions floor, and taking the minimum means an off-ratio
143 // deposit is rounded against the depositor, never against the pool.
144 if want := mulDiv(amtA, p.resB, p.resA); want <= amtB {
145 amtB = want
146 } else {
147 amtA = mulDiv(amtB, p.resA, p.resB)
148 }
149 if amtA <= 0 || amtB <= 0 {
150 panic("pair: deposit too small for the current ratio")
151 }
152 minted = min64(
153 mulDiv(amtA, p.totalShares, p.resA),
154 mulDiv(amtB, p.totalShares, p.resB),
155 )
156 }
157 if minted <= 0 {
158 panic("pair: deposit mints zero shares")
159 }
160 if p.resA+amtA > MaxReserve || p.resB+amtB > MaxReserve {
161 panic("pair: reserve cap exceeded")
162 }
163
164 provider := rlm.Previous().Address()
165 self := rlm.Address()
166 pull(0, rlm, p.tokA, provider, self, amtA)
167 pull(0, rlm, p.tokB, provider, self, amtB)
168
169 p.resA += amtA
170 p.resB += amtB
171 p.totalShares += minted
172 p.setShares(provider, p.SharesOf(provider)+minted)
173
174 chain.Emit("AddLiquidity",
175 "pair", p.ID(),
176 "provider", provider.String(),
177 "amountA", itoa(amtA),
178 "amountB", itoa(amtB),
179 "shares", itoa(minted),
180 )
181 return minted
182}
183
184// RemoveLiquidity burns shares held by the caller and returns the
185// proportional amounts of both tokens, in (A, B) order.
186//
187// Burning the entire share supply pays out the whole reserve, so the last
188// provider out leaves nothing unclaimable behind and the pair can be reseeded
189// at a fresh price.
190func (p *Pair) RemoveLiquidity(_ int, rlm realm, shares int64) (int64, int64) {
191 if shares <= 0 {
192 panic("pair: shares must be > 0")
193 }
194 owner := rlm.Previous().Address()
195 held := p.SharesOf(owner)
196 if held < shares {
197 panic("pair: insufficient shares")
198 }
199
200 var amtA, amtB int64
201 if shares == p.totalShares {
202 amtA, amtB = p.resA, p.resB
203 } else {
204 amtA = mulDiv(shares, p.resA, p.totalShares)
205 amtB = mulDiv(shares, p.resB, p.totalShares)
206 }
207 if amtA <= 0 || amtB <= 0 {
208 panic("pair: burn would return nothing on one side")
209 }
210
211 p.resA -= amtA
212 p.resB -= amtB
213 p.totalShares -= shares
214 p.setShares(owner, held-shares)
215
216 push(0, rlm, p.tokA, owner, amtA)
217 push(0, rlm, p.tokB, owner, amtB)
218
219 chain.Emit("RemoveLiquidity",
220 "pair", p.ID(),
221 "provider", owner.String(),
222 "amountA", itoa(amtA),
223 "amountB", itoa(amtB),
224 "shares", itoa(shares),
225 )
226 return amtA, amtB
227}
228
229// Swap sells amountIn of keyIn for the other token and aborts unless at least
230// minOut comes back. The caller must first Approve the instance realm's
231// address on keyIn.
232//
233// minOut is the only protection against being sandwiched or against the pair
234// moving between quoting and execution. Pass a real bound; passing 0 means
235// accepting any price at all.
236func (p *Pair) Swap(_ int, rlm realm, keyIn string, amountIn, minOut int64) int64 {
237 if amountIn <= 0 {
238 panic("pair: amountIn must be > 0")
239 }
240 if minOut < 0 {
241 panic("pair: minOut must be >= 0")
242 }
243 flipped := p.mustSide(keyIn)
244
245 resIn, resOut := p.resA, p.resB
246 tokIn, tokOut := p.tokA, p.tokB
247 if flipped {
248 resIn, resOut = p.resB, p.resA
249 tokIn, tokOut = p.tokB, p.tokA
250 }
251
252 out := AmountOut(amountIn, resIn, resOut)
253 if out <= 0 {
254 panic("pair: output rounds to zero")
255 }
256 if out < minOut {
257 panic("pair: slippage, output below minOut")
258 }
259
260 trader := rlm.Previous().Address()
261 pull(0, rlm, tokIn, trader, rlm.Address(), amountIn)
262
263 newIn, newOut := resIn+amountIn, resOut-out
264 // The invariant holds by construction (out is floored), so this can only
265 // fire if the pricing above is ever edited into being wrong. It is exact:
266 // both products are compared in 128 bits.
267 if cmpProd(newIn, newOut, resIn, resOut) < 0 {
268 panic("pair: constant product regression")
269 }
270 if flipped {
271 p.resB, p.resA = newIn, newOut
272 } else {
273 p.resA, p.resB = newIn, newOut
274 }
275
276 push(0, rlm, tokOut, trader, out)
277
278 chain.Emit("Swap",
279 "pair", p.ID(),
280 "trader", trader.String(),
281 "tokenIn", tokIn.GetSymbol(),
282 "amountIn", itoa(amountIn),
283 "amountOut", itoa(out),
284 )
285 return out
286}
287
288//
289// Reads. Safe for the registry realm to call on another realm's Pair.
290//
291
292// AmountOut is the pricing function, fee included, as a pure function of the
293// two reserves. Exported so a caller can quote off chain against reserves it
294// already holds, and so the arithmetic is testable on its own.
295func AmountOut(amountIn, reserveIn, reserveOut int64) int64 {
296 if amountIn <= 0 {
297 panic("pair: amountIn must be > 0")
298 }
299 if reserveIn <= 0 || reserveOut <= 0 {
300 panic("pair: pair has an empty reserve")
301 }
302 if reserveIn > MaxReserve || reserveOut > MaxReserve {
303 panic("pair: reserve above cap")
304 }
305 if amountIn > MaxReserve-reserveIn {
306 panic("pair: reserve cap exceeded")
307 }
308 inFee := amountIn * feeNum
309 den := reserveIn*feeDen + inFee
310 return mulDiv(inFee, reserveOut, den)
311}
312
313// Quote prices amountIn of keyIn against the live reserves. It is the number
314// Swap would return right now, which is not a promise about the next block.
315func (p *Pair) Quote(keyIn string, amountIn int64) int64 {
316 if p.totalShares == 0 {
317 return 0
318 }
319 if p.mustSide(keyIn) {
320 return AmountOut(amountIn, p.resB, p.resA)
321 }
322 return AmountOut(amountIn, p.resA, p.resB)
323}
324
325// Keys returns the two grc20reg keys in canonical order.
326func (p *Pair) Keys() (string, string) { return p.keyA, p.keyB }
327
328// Symbols returns the two token symbols in canonical order.
329func (p *Pair) Symbols() (string, string) { return p.tokA.GetSymbol(), p.tokB.GetSymbol() }
330
331// ID is the canonical identifier of the couple, "keyA~keyB". The separator is
332// "~" and not "|": a "|" inside a markdown table cell breaks the row.
333func (p *Pair) ID() string { return p.keyA + "~" + p.keyB }
334
335// Reserves returns the two reserves in canonical order.
336func (p *Pair) Reserves() (int64, int64) { return p.resA, p.resB }
337
338// TotalShares returns the LP share supply.
339func (p *Pair) TotalShares() int64 { return p.totalShares }
340
341// Providers returns how many addresses hold shares.
342func (p *Pair) Providers() int { return p.shares.Size() }
343
344// SharesOf returns owner's LP shares.
345func (p *Pair) SharesOf(owner address) int64 {
346 v := p.shares.Get(owner.String())
347 if v == nil {
348 return 0
349 }
350 return v.(int64)
351}
352
353// Render is the instance realm's whole page: what the couple is, what it
354// holds, and how to trade it.
355func (p *Pair) Render(path string) string {
356 symA, symB := p.Symbols()
357 out := "# " + symA + " / " + symB + "\n\n"
358 out += "One constant-product pair, `x*y=k`, 30 bps to the liquidity providers. "
359 out += "Logic lives in [p/moul/x/pair/v0](/p/moul/x/pair/v0); this realm is the instance.\n\n"
360
361 if p.totalShares == 0 {
362 out += "_Empty. The first `AddLiquidity` sets the price._\n\n"
363 } else {
364 out += ufmt.Sprintf("| side | reserve | key |\n|---|---|---|\n| %s | %d | `%s` |\n| %s | %d | `%s` |\n\n",
365 symA, p.resA, p.keyA, symB, p.resB, p.keyB)
366 out += ufmt.Sprintf("- LP shares: **%d** across %d provider(s)\n",
367 p.totalShares, p.shares.Size())
368 out += ufmt.Sprintf("- Spot: 1 %s buys ~%d %s (before fee and slippage)\n\n",
369 symA, p.spot(), symB)
370 }
371 out += "Approve this realm's address on the token you are selling, then call `Swap`.\n"
372 return out
373}
374
375//
376// Internals.
377//
378
379// spot is the display-only mid price, floor(resB/resA). Never price anything
380// off it: it is a spot reserve ratio that any trader can move in one tx.
381func (p *Pair) spot() int64 {
382 if p.resA == 0 {
383 return 0
384 }
385 return p.resB / p.resA
386}
387
388// mustSide reports whether key is the B side, and panics if it is neither.
389func (p *Pair) mustSide(key string) bool {
390 switch key {
391 case p.keyA:
392 return false
393 case p.keyB:
394 return true
395 }
396 panic("pair: " + key + " is not in this pair")
397}
398
399func (p *Pair) setShares(owner address, n int64) {
400 if n == 0 {
401 p.shares.Remove(owner.String())
402 return
403 }
404 p.shares.Set(owner.String(), n)
405}
406
407// pull moves amount of tok from `from` into the instance realm, spending the
408// allowance `from` granted to the instance realm's address.
409//
410// Non-crossing on purpose: `_ int, rlm realm` is the only shape a pure
411// package can declare, and it keeps rlm the instance's own live frame.
412// RealmTeller binds the spender eagerly to rlm.Address(), which is therefore
413// the instance, not this package (a pure package has no address at all).
414func pull(_ int, rlm realm, tok *grc20.Token, from, to address, amount int64) {
415 err := tok.RealmTeller(0, rlm).TransferFrom(0, rlm, from, to, amount)
416 if err != nil {
417 panic("pair: cannot take " + tok.GetSymbol() + ": " + err.Error())
418 }
419}
420
421// push sends amount of tok from the instance realm to `to`.
422func push(_ int, rlm realm, tok *grc20.Token, to address, amount int64) {
423 err := tok.RealmTeller(0, rlm).Transfer(0, rlm, to, amount)
424 if err != nil {
425 panic("pair: cannot send " + tok.GetSymbol() + ": " + err.Error())
426 }
427}
428
429// mulDiv returns floor(a*b/c) through a 128-bit intermediate, which plain
430// int64 arithmetic cannot do: a*b is routinely wider than 63 bits here even
431// when the quotient is small.
432func mulDiv(a, b, c int64) int64 {
433 if a < 0 || b < 0 {
434 panic("pair: negative operand")
435 }
436 if c <= 0 {
437 panic("pair: division by a non-positive value")
438 }
439 hi, lo := bits.Mul64(uint64(a), uint64(b))
440 // bits.Div64 panics for y <= hi; refusing here turns that into a named
441 // abort and also covers every quotient that would not fit in 64 bits.
442 if hi >= uint64(c) {
443 panic("pair: quotient overflows int64")
444 }
445 q, _ := bits.Div64(hi, lo, uint64(c))
446 if q > uint64(math.MaxInt64) {
447 panic("pair: quotient overflows int64")
448 }
449 return int64(q)
450}
451
452// cmpProd compares a*b with c*d exactly, in 128 bits, and returns -1, 0 or 1.
453func cmpProd(a, b, c, d int64) int {
454 h1, l1 := bits.Mul64(uint64(a), uint64(b))
455 h2, l2 := bits.Mul64(uint64(c), uint64(d))
456 if h1 != h2 {
457 if h1 < h2 {
458 return -1
459 }
460 return 1
461 }
462 if l1 != l2 {
463 if l1 < l2 {
464 return -1
465 }
466 return 1
467 }
468 return 0
469}
470
471func min64(a, b int64) int64 {
472 if a < b {
473 return a
474 }
475 return b
476}
477
478func itoa(v int64) string { return strconv.FormatInt(v, 10) }
