exchange_book.gno
14.97 Kb · 510 lines
1package game33
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). No upfront posting fee — the 0.90% maker fee is deducted
209// from the maker's proceeds at fill time. Returns the order id.
210// expirySecs 0 = 72 h; max 7 days.
211func PlaceOrder(cur realm, give string, giveAmt uint64, want string, wantAmt uint64, expirySecs int64) uint64 {
212 caller := exchangeCaller(cur)
213 requireMarketOpen(caller)
214 requireCoin(give)
215 requireCoin(want)
216 if give == want {
217 panic("give and want must differ")
218 }
219 requireAmount("giveAmt", giveAmt)
220 requireAmount("wantAmt", wantAmt)
221 if grinValueMilli(give, giveAmt) < minOrderGrinX1k {
222 panic("order too small: minimum is 50 grin of value")
223 }
224 if expirySecs == 0 {
225 expirySecs = defaultExpiry
226 }
227 if expirySecs < 60 || expirySecs > maxExpiry {
228 panic("expiry must be between 60 s and 7 days")
229 }
230 if openOrderCount(caller) >= maxOpenOrders {
231 panic("max 20 open orders")
232 }
233 if len(caller) != 40 {
234 panic("invalid maker address")
235 }
236 pk := priceKey(wantAmt, giveAmt)
237 nextId := addChk(nextOrderId, 1)
238 // A full side only takes an order that beats its worst one (which is then
239 // refunded to its maker): spam can't lock the book with absurd prices.
240 var evict *order
241 if sideCount(want, give) >= maxSideOrders {
242 s := sideStr(sideKey(want, give))
243 w := s[len(s)-sideEntryLen:]
244 if pk+padU(nextId, 12) >= w[:sideSortLen] {
245 panic("book side full: price must beat the worst open order")
246 }
247 wid, _ := strconv.ParseUint(w[24:36], 10, 64)
248 evict = loadOrderOf(w[36:], wid)
249 if evict == nil {
250 panic("invariant: book entry without order")
251 }
252 }
253 requireBalance(caller, give, giveAmt)
254 // ── all checks passed; writes start here ──
255 debitBal(caller, give, giveAmt) // escrow
256
257 if evict != nil {
258 closeOrder(evict, "evicted")
259 }
260 nextOrderId = nextId
261 o := &order{id: nextId, maker: caller, give: give, want: want, remGive: giveAmt, remWant: wantAmt,
262 expiry: time.Now().Unix() + expirySecs, pk: pk}
263 setMakerRecs(caller, append(makerRecs(caller), encodeOrder(o)))
264 sideInsert(o)
265 openOrderTotal = addChk(openOrderTotal, 1)
266 chain.Emit("OrderPlaced", "id", u(o.id), "maker", caller, "give", give, "giveAmt", u(giveAmt),
267 "want", want, "wantAmt", u(wantAmt), "expiry", strconv.FormatInt(o.expiry, 10))
268 return o.id
269}
270
271// closeOrder refunds the remaining escrow to the MAKER (never anyone else)
272// and deletes the order. Every close path goes through here.
273func closeOrder(o *order, reason string) {
274 refund := o.remGive
275 if refund > 0 {
276 creditBal(o.maker, o.give, refund)
277 o.remGive = 0
278 }
279 sideRemove(o)
280 recs := makerRecs(o.maker)
281 pre := padU(o.id, 12) + "|"
282 for i, r := range recs {
283 if strings.HasPrefix(r, pre) {
284 recs = append(recs[:i], recs[i+1:]...)
285 break
286 }
287 }
288 setMakerRecs(o.maker, recs)
289 openOrderTotal = subChk(openOrderTotal, 1)
290 chain.Emit("OrderClosed", "id", u(o.id), "maker", o.maker, "reason", reason, "refund", u(refund))
291}
292
293// CancelOrder: the maker gets the remaining escrow back. Works while paused
294// and for banned makers; only the maker can cancel.
295func CancelOrder(cur realm, id uint64) {
296 caller := exchangeCaller(cur)
297 // Lookup is by the caller's own orders only: nobody can name someone
298 // else's order here.
299 o := loadOrderOf(caller, id)
300 if o == nil {
301 panic("no such open order (or not your order)")
302 }
303 closeOrder(o, "cancel")
304}
305
306// SweepExpiredOrders closes up to maxScanPerTx expired orders of one book
307// side, refunding each maker. Anyone may call it (also while paused).
308func SweepExpiredOrders(cur realm, pay string, get string) int {
309 exchangeCaller(cur)
310 now := time.Now().Unix()
311 var expired []*order
312 scanned := 0
313 iterSide(pay, get, func(maker string, id uint64) bool {
314 scanned++
315 if scanned > maxScanPerTx {
316 return true
317 }
318 o := loadOrderOf(maker, id)
319 if o != nil && o.expiry < now {
320 expired = append(expired, o)
321 }
322 return false
323 })
324 for _, o := range expired {
325 closeOrder(o, "expired")
326 }
327 return len(expired)
328}
329
330type fillStep struct {
331 o *order
332 x, g uint64 // taker pays x (+fee) of `pay`, receives g of `get`
333}
334
335// planFills walks the book for a taker (read-only). budget is the most the
336// taker will spend INCLUDING the taker fee. Own orders are skipped (no
337// self-match); expired orders are returned for closing.
338func planFills(caller, pay, get string, budget uint64, maxFills int, now int64) ([]fillStep, []*order, uint64, uint64) {
339 if maxFills <= 0 || maxFills > maxFillsPerTx {
340 maxFills = maxFillsPerTx
341 }
342 var steps []fillStep
343 var expired []*order
344 remaining := budget
345 spent, got := uint64(0), uint64(0)
346 scanned := 0
347 iterSide(pay, get, func(maker string, id uint64) bool {
348 scanned++
349 if scanned > maxScanPerTx || len(steps) >= maxFills || remaining == 0 {
350 return true
351 }
352 o := loadOrderOf(maker, id)
353 if o == nil {
354 return false
355 }
356 if o.expiry < now {
357 expired = append(expired, o)
358 return false
359 }
360 if o.maker == caller {
361 return false // no self-match: skip, never touch the taker's own order
362 }
363 // largest x with x + ceil(x × takerFee) ≤ remaining
364 x := mulDiv(remaining, 10000, 10000+takerFeeBps)
365 for i := 0; i < 4 && x > 0 && addChk(x, mulDivUp(x, takerFeeBps, 10000)) > remaining; i++ {
366 x--
367 }
368 if x > o.remWant {
369 x = o.remWant
370 }
371 if x == 0 {
372 return true
373 }
374 g := o.remGive
375 if x < o.remWant {
376 g = mulDiv(x, o.remGive, o.remWant) // floor: the maker never sells below their price
377 }
378 if g == 0 {
379 return true
380 }
381 cost := addChk(x, mulDivUp(x, takerFeeBps, 10000))
382 steps = append(steps, fillStep{o: o, x: x, g: g})
383 remaining = subChk(remaining, cost)
384 spent = addChk(spent, cost)
385 got = addChk(got, g)
386 return false
387 })
388 return steps, expired, spent, got
389}
390
391// executeFills applies a plan: the taker pays each maker x (plus taker fee),
392// receives g from escrow. The maker receives x minus the 0.90% maker fee
393// (deducted from proceeds, not from escrow). Returns total received by taker.
394func executeFills(caller, pay string, steps []fillStep) uint64 {
395 got := uint64(0)
396 for _, st := range steps {
397 o := st.o
398 takerFee := mulDivUp(st.x, takerFeeBps, 10000)
399 makerFee := mulDivUp(st.x, makerFeeBps, 10000)
400 // Taker pays x + takerFee; maker receives x - makerFee
401 debitBal(caller, pay, addChk(st.x, takerFee))
402 accrueProtocolFee(pay, addChk(takerFee, makerFee))
403 creditBal(o.maker, pay, subChk(st.x, makerFee))
404 o.remWant = subChk(o.remWant, st.x)
405 o.remGive = subChk(o.remGive, st.g)
406 got = addChk(got, st.g)
407 chain.Emit("OrderFilled", "id", u(o.id), "maker", o.maker, "taker", caller,
408 "paid", u(st.x), "takerFee", u(takerFee), "makerFee", u(makerFee), "got", u(st.g))
409 if o.remWant == 0 || o.remGive == 0 {
410 closeOrder(o, "filled")
411 } else if grinValueMilli(o.give, o.remGive) < minOrderGrinX1k {
412 closeOrder(o, "dust")
413 } else {
414 saveOrder(o)
415 }
416 }
417 return got
418}
419
420// FillOrders: spend at most payAmt of `pay` (taker fee included) on the
421// best-priced orders that give `get`; receive at least minGet or revert.
422// ≤ 10 fills and ≤ 20 scanned entries per call.
423func FillOrders(cur realm, pay string, get string, payAmt uint64, minGet uint64, maxFills int, deadline int64) uint64 {
424 caller := exchangeCaller(cur)
425 requireMarketOpen(caller)
426 requireDeadline(deadline)
427 requireCoin(pay)
428 requireCoin(get)
429 requireAmount("payAmt", payAmt)
430 steps, expired, spent, planned := planFills(caller, pay, get, payAmt, maxFills, time.Now().Unix())
431 if planned == 0 || planned < minGet {
432 panic("slippage: received below minimum")
433 }
434 requireBalance(caller, pay, spent)
435 // ── all checks passed; writes start here ──
436 for _, o := range expired {
437 closeOrder(o, "expired")
438 }
439 got := executeFills(caller, pay, steps)
440 if got != planned {
441 panic("invariant: fill plan mismatch")
442 }
443 creditBal(caller, get, got)
444 return got
445}
446
447// ── views ────────────────────────────────────────────────────────────────────
448
449func orderJSON(o *order) string {
450 return `{"id":"` + u(o.id) + `","maker":"` + o.maker + `","give":` + jsonStr(o.give) + `,"want":` + jsonStr(o.want) +
451 `,"remGive":"` + u(o.remGive) + `","remWant":"` + u(o.remWant) + `","expiry":` + strconv.FormatInt(o.expiry, 10) + `}`
452}
453
454// Order shows one open order of `maker` (lookups are per maker by design).
455func Order(maker string, id uint64) string {
456 o := loadOrderOf(maker, id)
457 if o == nil {
458 return `{"id":"` + u(id) + `","open":false}`
459 }
460 return orderJSON(o)
461}
462
463// OrdersOf lists an address's open orders (≤ 20 by construction).
464func OrdersOf(addr string) string {
465 out := "["
466 for i, r := range makerRecs(addr) {
467 if i > 0 {
468 out += ","
469 }
470 out += orderJSON(decodeOrder(addr, r))
471 }
472 return out + "]"
473}
474
475// BookDepth lists asks for a taker who pays `pay` and gets `get`, best price
476// first (≤ 50 rows; offset < maxSideOrders).
477func BookDepth(pay string, get string, limit int, offset int) string {
478 if limit <= 0 || limit > maxViewLimit {
479 limit = maxViewLimit
480 }
481 if offset < 0 || offset >= maxSideOrders {
482 offset = 0
483 }
484 out := "["
485 i, n := 0, 0
486 iterSide(pay, get, func(maker string, id uint64) bool {
487 if i < offset {
488 i++
489 return false
490 }
491 if o := loadOrderOf(maker, id); o != nil {
492 if n > 0 {
493 out += ","
494 }
495 out += orderJSON(o)
496 n++
497 }
498 return n >= limit
499 })
500 return out + "]"
501}
502
503// QuoteFill previews FillOrders for a budget (fee included): {"spent","got"}.
504func QuoteFill(caller string, pay string, get string, payAmt uint64, maxFills int) string {
505 if payAmt == 0 || payAmt > maxAmount {
506 return `{"spent":"0","got":"0","fills":0}`
507 }
508 steps, _, spent, got := planFills(caller, pay, get, payAmt, maxFills, time.Now().Unix())
509 return `{"spent":"` + u(spent) + `","got":"` + u(got) + `","fills":` + strconv.Itoa(len(steps)) + `}`
510}
