exchange_book.gno
14.84 Kb · 513 lines
1package game29
2
3// ── P2P exchange: escrowed limit-order book (any coin pair) ──────────────────
4//
5// A maker escrows `give` and asks for `want` at their own price; takers fill
6// at the maker's price (fully or partly). Cancel or expiry refunds the
7// remaining escrow; the 2-grin posting fee is not refunded. No price bands.
8//
9// Storage (≈ 200 bytes per open order): no per-order tree node (one avl
10// insert costs ~2.1 KB of storage deposit). Each maker has ONE compact string
11// holding their ≤ 20 open orders, and each book side (want>give) is ONE
12// fixed-width string of sorted 76-byte entries (priceKey24 + id12 + maker40),
13// capped at maxSideOrders; when a side is full a new order must beat the
14// worst one, which is then refunded to its maker (evicted).
15
16import (
17 "math/bits"
18 "strconv"
19 "strings"
20 "time"
21
22 "chain"
23)
24
25type order struct {
26 id uint64
27 maker string
28 give, want string
29 remGive, remWant uint64
30 expiry int64
31 pk string // price key part of the book key
32}
33
34func padU(n uint64, w int) string {
35 s := strconv.FormatUint(n, 10)
36 for len(s) < w {
37 s = "0" + s
38 }
39 return s
40}
41
42const hexDigits = "0123456789abcdef"
43
44// priceKey = want-per-give × 1e12 as a fixed-width 24-hex-digit number
45// (96 bits; amounts ≤ 1e15 keep it < 2^90). Lexicographic = numeric order,
46// so ascending book keys are the cheapest asks first for takers.
47func priceKey(wantAmt, giveAmt uint64) string {
48 hi, lo := bits.Mul64(wantAmt, 1000000000000)
49 qhi := hi / giveAmt
50 qlo, _ := bits.Div64(hi%giveAmt, lo, giveAmt)
51 if qhi >= 1<<32 {
52 panic("price out of range")
53 }
54 b := make([]byte, 24)
55 for i := 7; i >= 0; i-- {
56 b[i] = hexDigits[qhi&15]
57 qhi >>= 4
58 }
59 for i := 23; i >= 8; i-- {
60 b[i] = hexDigits[qlo&15]
61 qlo >>= 4
62 }
63 return string(b)
64}
65
66const (
67 sideEntryLen = 76 // priceKey(24) + id(12) + maker address(40)
68 sideSortLen = 36 // entries sort by priceKey then id (FIFO within a price)
69 maxSideOrders = 256 // open orders per book side; bounds every string we rewrite
70)
71
72// maker record: id12|give|want|remGive|remWant|expiry|pk
73func encodeOrder(o *order) string {
74 return padU(o.id, 12) + "|" + o.give + "|" + o.want + "|" + u(o.remGive) + "|" + u(o.remWant) + "|" +
75 strconv.FormatInt(o.expiry, 10) + "|" + o.pk
76}
77
78func decodeOrder(maker, rec string) *order {
79 f := strings.Split(rec, "|")
80 if len(f) != 7 {
81 panic("corrupt order")
82 }
83 id, _ := strconv.ParseUint(f[0], 10, 64)
84 rg, _ := strconv.ParseUint(f[3], 10, 64)
85 rw, _ := strconv.ParseUint(f[4], 10, 64)
86 ex, _ := strconv.ParseInt(f[5], 10, 64)
87 return &order{id: id, maker: maker, give: f[1], want: f[2], remGive: rg, remWant: rw, expiry: ex, pk: f[6]}
88}
89
90func makerRecs(maker string) []string {
91 if !makerBooks.Has(maker) {
92 return nil
93 }
94 v := makerBooks.Get(maker).(string)
95 if v == "" {
96 return nil
97 }
98 return strings.Split(v, ";")
99}
100
101func setMakerRecs(maker string, recs []string) {
102 if len(recs) == 0 {
103 makerBooks.Remove(maker)
104 return
105 }
106 makerBooks.Set(maker, strings.Join(recs, ";"))
107}
108
109// loadOrderOf finds one of maker's open orders (≤ 20 records scanned).
110func loadOrderOf(maker string, id uint64) *order {
111 pre := padU(id, 12) + "|"
112 for _, r := range makerRecs(maker) {
113 if strings.HasPrefix(r, pre) {
114 return decodeOrder(maker, r)
115 }
116 }
117 return nil
118}
119
120func saveOrder(o *order) {
121 recs := makerRecs(o.maker)
122 pre := padU(o.id, 12) + "|"
123 for i, r := range recs {
124 if strings.HasPrefix(r, pre) {
125 recs[i] = encodeOrder(o)
126 setMakerRecs(o.maker, recs)
127 return
128 }
129 }
130 panic("invariant: order not found")
131}
132
133func sideKey(want, give string) string { return want + ">" + give }
134
135func sideEntry(o *order) string { return o.pk + padU(o.id, 12) + o.maker }
136
137func sideStr(k string) string {
138 if !sides.Has(k) {
139 return ""
140 }
141 return sides.Get(k).(string)
142}
143
144// sideSearch returns the index of the first entry whose sort key is ≥ key.
145func sideSearch(s, key string) int {
146 lo, hi := 0, len(s)/sideEntryLen
147 for lo < hi {
148 mid := (lo + hi) / 2
149 if s[mid*sideEntryLen:mid*sideEntryLen+sideSortLen] < key {
150 lo = mid + 1
151 } else {
152 hi = mid
153 }
154 }
155 return lo
156}
157
158func sideInsert(o *order) {
159 k := sideKey(o.want, o.give)
160 s := sideStr(k)
161 e := sideEntry(o)
162 i := sideSearch(s, e[:sideSortLen]) * sideEntryLen
163 sides.Set(k, s[:i]+e+s[i:])
164}
165
166func sideRemove(o *order) {
167 k := sideKey(o.want, o.give)
168 s := sideStr(k)
169 e := sideEntry(o)
170 i := sideSearch(s, e[:sideSortLen]) * sideEntryLen
171 if i+sideEntryLen > len(s) || s[i:i+sideEntryLen] != e {
172 panic("invariant: book entry missing")
173 }
174 s = s[:i] + s[i+sideEntryLen:]
175 if s == "" {
176 sides.Remove(k)
177 } else {
178 sides.Set(k, s)
179 }
180}
181
182// iterSide walks a taker's side (pays `pay`, gets `get`) best price first.
183func iterSide(pay, get string, fn func(maker string, id uint64) bool) {
184 s := sideStr(sideKey(pay, get))
185 for i := 0; i+sideEntryLen <= len(s); i += sideEntryLen {
186 e := s[i : i+sideEntryLen]
187 id, _ := strconv.ParseUint(e[24:36], 10, 64)
188 if fn(e[36:], id) {
189 return
190 }
191 }
192}
193
194func sideCount(pay, get string) int { return len(sideStr(sideKey(pay, get))) / sideEntryLen }
195
196// grinValueMilli = amt × reference value (milli-grin), saturating at 2^64-1.
197func grinValueMilli(coin string, amt uint64) uint64 {
198 hi, lo := bits.Mul64(amt, prefMilli[requireCoin(coin)])
199 if hi != 0 {
200 return ^uint64(0)
201 }
202 return lo
203}
204
205func openOrderCount(maker string) uint64 { return uint64(len(makerRecs(maker))) }
206
207// PlaceOrder escrows giveAmt of `give` and lists it for wantAmt of `want`
208// (any pair). Costs 2 grin (protocol fee, not refunded). Returns the id.
209// expirySecs 0 = 72 h; max 7 days.
210func PlaceOrder(cur realm, give string, giveAmt uint64, want string, wantAmt uint64, expirySecs int64) uint64 {
211 caller := exchangeCaller(cur)
212 requireMarketOpen(caller)
213 requireCoin(give)
214 requireCoin(want)
215 if give == want {
216 panic("give and want must differ")
217 }
218 requireAmount("giveAmt", giveAmt)
219 requireAmount("wantAmt", wantAmt)
220 if grinValueMilli(give, giveAmt) < minOrderGrinX1k {
221 panic("order too small: minimum is 50 grin of value")
222 }
223 if expirySecs == 0 {
224 expirySecs = defaultExpiry
225 }
226 if expirySecs < 60 || expirySecs > maxExpiry {
227 panic("expiry must be between 60 s and 7 days")
228 }
229 if openOrderCount(caller) >= maxOpenOrders {
230 panic("max 20 open orders")
231 }
232 if len(caller) != 40 {
233 panic("invalid maker address")
234 }
235 pk := priceKey(wantAmt, giveAmt)
236 nextId := addChk(nextOrderId, 1)
237 // A full side only takes an order that beats its worst one (which is then
238 // refunded to its maker): spam can't lock the book with absurd prices.
239 var evict *order
240 if sideCount(want, give) >= maxSideOrders {
241 s := sideStr(sideKey(want, give))
242 w := s[len(s)-sideEntryLen:]
243 if pk+padU(nextId, 12) >= w[:sideSortLen] {
244 panic("book side full: price must beat the worst open order")
245 }
246 wid, _ := strconv.ParseUint(w[24:36], 10, 64)
247 evict = loadOrderOf(w[36:], wid)
248 if evict == nil {
249 panic("invariant: book entry without order")
250 }
251 }
252 if give == hubCoin {
253 requireBalance(caller, hubCoin, addChk(giveAmt, postFeeGrin))
254 } else {
255 requireBalance(caller, hubCoin, postFeeGrin)
256 requireBalance(caller, give, giveAmt)
257 }
258 // ── all checks passed; writes start here ──
259 debitBal(caller, hubCoin, postFeeGrin)
260 accrueProtocolFee(hubCoin, postFeeGrin)
261 debitBal(caller, give, giveAmt) // escrow
262
263 if evict != nil {
264 closeOrder(evict, "evicted")
265 }
266 nextOrderId = nextId
267 o := &order{id: nextId, maker: caller, give: give, want: want, remGive: giveAmt, remWant: wantAmt,
268 expiry: time.Now().Unix() + expirySecs, pk: pk}
269 setMakerRecs(caller, append(makerRecs(caller), encodeOrder(o)))
270 sideInsert(o)
271 openOrderTotal = addChk(openOrderTotal, 1)
272 chain.Emit("OrderPlaced", "id", u(o.id), "maker", caller, "give", give, "giveAmt", u(giveAmt),
273 "want", want, "wantAmt", u(wantAmt), "expiry", strconv.FormatInt(o.expiry, 10))
274 return o.id
275}
276
277// closeOrder refunds the remaining escrow to the MAKER (never anyone else)
278// and deletes the order. Every close path goes through here.
279func closeOrder(o *order, reason string) {
280 refund := o.remGive
281 if refund > 0 {
282 creditBal(o.maker, o.give, refund)
283 o.remGive = 0
284 }
285 sideRemove(o)
286 recs := makerRecs(o.maker)
287 pre := padU(o.id, 12) + "|"
288 for i, r := range recs {
289 if strings.HasPrefix(r, pre) {
290 recs = append(recs[:i], recs[i+1:]...)
291 break
292 }
293 }
294 setMakerRecs(o.maker, recs)
295 openOrderTotal = subChk(openOrderTotal, 1)
296 chain.Emit("OrderClosed", "id", u(o.id), "maker", o.maker, "reason", reason, "refund", u(refund))
297}
298
299// CancelOrder: the maker gets the remaining escrow back. Works while paused
300// and for banned makers; only the maker can cancel.
301func CancelOrder(cur realm, id uint64) {
302 caller := exchangeCaller(cur)
303 // Lookup is by the caller's own orders only: nobody can name someone
304 // else's order here.
305 o := loadOrderOf(caller, id)
306 if o == nil {
307 panic("no such open order (or not your order)")
308 }
309 closeOrder(o, "cancel")
310}
311
312// SweepExpiredOrders closes up to maxScanPerTx expired orders of one book
313// side, refunding each maker. Anyone may call it (also while paused).
314func SweepExpiredOrders(cur realm, pay string, get string) int {
315 exchangeCaller(cur)
316 now := time.Now().Unix()
317 var expired []*order
318 scanned := 0
319 iterSide(pay, get, func(maker string, id uint64) bool {
320 scanned++
321 if scanned > maxScanPerTx {
322 return true
323 }
324 o := loadOrderOf(maker, id)
325 if o != nil && o.expiry < now {
326 expired = append(expired, o)
327 }
328 return false
329 })
330 for _, o := range expired {
331 closeOrder(o, "expired")
332 }
333 return len(expired)
334}
335
336type fillStep struct {
337 o *order
338 x, g uint64 // taker pays x (+fee) of `pay`, receives g of `get`
339}
340
341// planFills walks the book for a taker (read-only). budget is the most the
342// taker will spend INCLUDING the taker fee. Own orders are skipped (no
343// self-match); expired orders are returned for closing.
344func planFills(caller, pay, get string, budget uint64, maxFills int, now int64) ([]fillStep, []*order, uint64, uint64) {
345 if maxFills <= 0 || maxFills > maxFillsPerTx {
346 maxFills = maxFillsPerTx
347 }
348 var steps []fillStep
349 var expired []*order
350 remaining := budget
351 spent, got := uint64(0), uint64(0)
352 scanned := 0
353 iterSide(pay, get, func(maker string, id uint64) bool {
354 scanned++
355 if scanned > maxScanPerTx || len(steps) >= maxFills || remaining == 0 {
356 return true
357 }
358 o := loadOrderOf(maker, id)
359 if o == nil {
360 return false
361 }
362 if o.expiry < now {
363 expired = append(expired, o)
364 return false
365 }
366 if o.maker == caller {
367 return false // no self-match: skip, never touch the taker's own order
368 }
369 // largest x with x + ceil(x × takerFee) ≤ remaining
370 x := mulDiv(remaining, 10000, 10000+takerFeeBps)
371 for i := 0; i < 4 && x > 0 && addChk(x, mulDivUp(x, takerFeeBps, 10000)) > remaining; i++ {
372 x--
373 }
374 if x > o.remWant {
375 x = o.remWant
376 }
377 if x == 0 {
378 return true
379 }
380 g := o.remGive
381 if x < o.remWant {
382 g = mulDiv(x, o.remGive, o.remWant) // floor: the maker never sells below their price
383 }
384 if g == 0 {
385 return true
386 }
387 cost := addChk(x, mulDivUp(x, takerFeeBps, 10000))
388 steps = append(steps, fillStep{o: o, x: x, g: g})
389 remaining = subChk(remaining, cost)
390 spent = addChk(spent, cost)
391 got = addChk(got, g)
392 return false
393 })
394 return steps, expired, spent, got
395}
396
397// executeFills applies a plan: the taker pays each maker x and the protocol
398// fee, receives g from escrow. Returns the total received.
399func executeFills(caller, pay string, steps []fillStep) uint64 {
400 got := uint64(0)
401 for _, st := range steps {
402 o := st.o
403 fee := mulDivUp(st.x, takerFeeBps, 10000)
404 debitBal(caller, pay, addChk(st.x, fee))
405 accrueProtocolFee(pay, fee)
406 creditBal(o.maker, pay, st.x)
407 o.remWant = subChk(o.remWant, st.x)
408 o.remGive = subChk(o.remGive, st.g)
409 got = addChk(got, st.g)
410 chain.Emit("OrderFilled", "id", u(o.id), "maker", o.maker, "taker", caller,
411 "paid", u(st.x), "fee", u(fee), "got", u(st.g))
412 if o.remWant == 0 || o.remGive == 0 {
413 closeOrder(o, "filled")
414 } else if grinValueMilli(o.give, o.remGive) < minOrderGrinX1k {
415 closeOrder(o, "dust")
416 } else {
417 saveOrder(o)
418 }
419 }
420 return got
421}
422
423// FillOrders: spend at most payAmt of `pay` (taker fee included) on the
424// best-priced orders that give `get`; receive at least minGet or revert.
425// ≤ 10 fills and ≤ 20 scanned entries per call.
426func FillOrders(cur realm, pay string, get string, payAmt uint64, minGet uint64, maxFills int, deadline int64) uint64 {
427 caller := exchangeCaller(cur)
428 requireMarketOpen(caller)
429 requireDeadline(deadline)
430 requireCoin(pay)
431 requireCoin(get)
432 requireAmount("payAmt", payAmt)
433 steps, expired, spent, planned := planFills(caller, pay, get, payAmt, maxFills, time.Now().Unix())
434 if planned == 0 || planned < minGet {
435 panic("slippage: received below minimum")
436 }
437 requireBalance(caller, pay, spent)
438 // ── all checks passed; writes start here ──
439 for _, o := range expired {
440 closeOrder(o, "expired")
441 }
442 got := executeFills(caller, pay, steps)
443 if got != planned {
444 panic("invariant: fill plan mismatch")
445 }
446 creditBal(caller, get, got)
447 return got
448}
449
450// ── views ────────────────────────────────────────────────────────────────────
451
452func orderJSON(o *order) string {
453 return `{"id":"` + u(o.id) + `","maker":"` + o.maker + `","give":` + jsonStr(o.give) + `,"want":` + jsonStr(o.want) +
454 `,"remGive":"` + u(o.remGive) + `","remWant":"` + u(o.remWant) + `","expiry":` + strconv.FormatInt(o.expiry, 10) + `}`
455}
456
457// Order shows one open order of `maker` (lookups are per maker by design).
458func Order(maker string, id uint64) string {
459 o := loadOrderOf(maker, id)
460 if o == nil {
461 return `{"id":"` + u(id) + `","open":false}`
462 }
463 return orderJSON(o)
464}
465
466// OrdersOf lists an address's open orders (≤ 20 by construction).
467func OrdersOf(addr string) string {
468 out := "["
469 for i, r := range makerRecs(addr) {
470 if i > 0 {
471 out += ","
472 }
473 out += orderJSON(decodeOrder(addr, r))
474 }
475 return out + "]"
476}
477
478// BookDepth lists asks for a taker who pays `pay` and gets `get`, best price
479// first (≤ 50 rows; offset < maxSideOrders).
480func BookDepth(pay string, get string, limit int, offset int) string {
481 if limit <= 0 || limit > maxViewLimit {
482 limit = maxViewLimit
483 }
484 if offset < 0 || offset >= maxSideOrders {
485 offset = 0
486 }
487 out := "["
488 i, n := 0, 0
489 iterSide(pay, get, func(maker string, id uint64) bool {
490 if i < offset {
491 i++
492 return false
493 }
494 if o := loadOrderOf(maker, id); o != nil {
495 if n > 0 {
496 out += ","
497 }
498 out += orderJSON(o)
499 n++
500 }
501 return n >= limit
502 })
503 return out + "]"
504}
505
506// QuoteFill previews FillOrders for a budget (fee included): {"spent","got"}.
507func QuoteFill(caller string, pay string, get string, payAmt uint64, maxFills int) string {
508 if payAmt == 0 || payAmt > maxAmount {
509 return `{"spent":"0","got":"0","fills":0}`
510 }
511 steps, _, spent, got := planFills(caller, pay, get, payAmt, maxFills, time.Now().Unix())
512 return `{"spent":"` + u(spent) + `","got":"` + u(got) + `","fills":` + strconv.Itoa(len(steps)) + `}`
513}
