curve.gno

  1// Package curve is a linear, one-way bonding curve for issuing a token against a
  2// reserve: price rises linearly with the position on the curve, and the cost of
  3// minting is the exact integral, computed in 128-bit so it never overflows and
  4// never issues a coin for less than its backing.
  5//
  6// # Why a reciprocal slope
  7//
  8// The marginal price is p(s) = s/D — a RECIPROCAL denominator D, not a numerator
  9// slope. That is not cosmetic. The cost of moving from s0 to s1 is the integral
 10// (s1²−s0²)/(2D). With a numerator slope k the product k·(s1²−s0²) can exceed
 11// 2^128 for a realistic k at a large supply, and the single 128-bit multiply
 12// overflows. As 1/D the numerator is only s1²−s0², at most cap² which for a cap
 13// near 9.2e14 is about 2^100 — always inside 128 bits — and D sits safely in the
 14// divisor. D is chosen from economics: larger D is a gentler curve.
 15//
 16// # No coin is ever minted below its backing
 17//
 18// Two rounding rules, and one belt-and-suspenders check, guarantee it:
 19//
 20//   - Cost rounds UP. The buyer pays at least the integral, so backing (the sum
 21//     of integrals) never exceeds treasury (the sum charged).
 22//   - Minted rounds DOWN. It floors the number of coins a payment buys — but it
 23//     does not trust the square root. It uses isqrt only for a CANDIDATE, then
 24//     corrects ±1 against the canonical Cost, so an off-by-one in the root can
 25//     never over-issue. This re-check is mandatory, not optional.
 26//
 27// # A value, not an object
 28//
 29// A Curve is immutable configuration (the slope denominator and the position
 30// cap); it holds no mutable state and is never a heap object. The CURVE POSITION
 31// — how far up the curve issuance has walked — lives in the consuming realm as a
 32// monotonic counter it passes in as `from`. Burning or redeeming the token must
 33// NOT move that counter back: the curve prices the next mint off total-ever-
 34// minted, and walking it backward would let the same region be bought twice.
 35package curve
 36
 37import (
 38	"math/bits"
 39	"math/overflow"
 40)
 41
 42const maxInt64 = int64(9223372036854775807)
 43
 44// maxCap bounds the position cap so cap² ≤ 2^100 and every 128-bit operand here
 45// stays well inside 2^126 (where isqrt128's search bound is exact). 2^50 ≈ 1.1e15
 46// comfortably covers a token's ~9.2e14 supply ceiling.
 47const maxCap = int64(1) << 50
 48
 49// Curve is a linear one-way bonding curve. Build it with New.
 50type Curve struct {
 51	d   int64 // reciprocal slope: marginal price p(s) = s/d
 52	cap int64 // the highest position issuance may reach
 53}
 54
 55// New builds a curve with reciprocal slope d and position cap. A larger d is a
 56// gentler price rise. cap bounds the position so cap² stays inside 128 bits and
 57// the token's own supply ceiling is respected.
 58func New(d, cap int64) Curve {
 59	if d < 1 || d > maxInt64/2 {
 60		panic("curve: d must be in [1, MaxInt64/2] so 2d does not overflow")
 61	}
 62	if cap < 1 || cap > maxCap {
 63		panic("curve: cap must be in [1, 2^50]")
 64	}
 65	return Curve{d: d, cap: cap}
 66}
 67
 68// D and Cap expose the construction parameters.
 69func (c Curve) D() int64   { return c.d }
 70func (c Curve) Cap() int64 { return c.cap }
 71
 72// Cost is the coin a buyer must pay to move the position from `from` to
 73// `from+delta`, the integral of the price over that span, ROUNDED UP. ok is false
 74// when the move would pass the cap or the cost would not fit in an int64 (only at
 75// absurd positions). Minting zero costs zero.
 76func (c Curve) Cost(from, delta int64) (coin int64, ok bool) {
 77	if from < 0 || delta < 0 || from > c.cap {
 78		return 0, false
 79	}
 80	s1, add := overflow.Add64(from, delta)
 81	if !add || s1 > c.cap {
 82		return 0, false
 83	}
 84	// diff = s1² − s0², an exact 128-bit value (s1 ≥ s0 so it never borrows past 0).
 85	sh1, sl1 := bits.Mul64(uint64(s1), uint64(s1))
 86	sh0, sl0 := bits.Mul64(uint64(from), uint64(from))
 87	lo, borrow := bits.Sub64(sl1, sl0, 0)
 88	hi, _ := bits.Sub64(sh1, sh0, borrow)
 89
 90	m := uint64(2 * c.d)
 91	// Ceil-divide the 128-bit diff by m: (diff + m − 1) / m.
 92	lo2, carry := bits.Add64(lo, m-1, 0)
 93	hi2 := hi + carry
 94	if hi2 >= m {
 95		// The quotient would not fit int64 (and bits.Div64 REQUIRES hi < m). This IS
 96		// reachable well below the position cap — for the court's d=1e9 it fires around
 97		// s1≈1.9e14, far under cap≈9.2e14 — but only at positions whose fill cost exceeds
 98		// MaxInt64 µGNOT, i.e. more GNOT than can exist, so no funded Buy reaches it.
 99		// Do NOT delete this as "dead": Minted relies on ok=false meaning "unaffordable",
100		// and without the guard bits.Div64 would violate its hi<m precondition (over-issue).
101		return 0, false
102	}
103	q, _ := bits.Div64(hi2, lo2, m)
104	if q > uint64(maxInt64) {
105		// Same story one step later: the cost is a valid 128-bit value but exceeds int64,
106		// so it is unaffordable (MaxInt64 µGNOT is more than the whole supply's worth).
107		return 0, false
108	}
109	return int64(q), true
110}
111
112// Minted is the largest whole number of coins `coin` can buy starting at position
113// `from`, and the coin actually spent on them (≤ coin; the caller keeps or refunds
114// the remainder). It floors: it finds a candidate with a 128-bit integer square
115// root, then corrects ±1 against the canonical Cost, so issued coin is never worth
116// more than what was paid, and it is zero when even one coin costs more than
117// `coin`.
118func (c Curve) Minted(from, coin int64) (delta, spent int64) {
119	if from < 0 || from >= c.cap || coin <= 0 {
120		return 0, 0
121	}
122	// Short-circuit a payment large enough to buy the whole remaining curve. This
123	// bounds the isqrt operand below to at most cap² (so isqrt128's search bound is
124	// exact) and handles the huge-coin case explicitly instead of relying on the
125	// later cap clamp. When filling to the cap costs more than an int64 can hold
126	// (a very steep curve), full is !ok and coin (≤ MaxInt64) is necessarily below
127	// it, so we fall through — and then s1 < cap keeps the operand under cap² too.
128	if full, ok := c.Cost(from, c.cap-from); ok && coin >= full {
129		return c.cap - from, full
130	}
131	// operand = from² + 2·d·coin, a 128-bit value; s1 = floor(sqrt(operand)).
132	fh, fl := bits.Mul64(uint64(from), uint64(from))
133	ph, pl := bits.Mul64(uint64(2*c.d), uint64(coin))
134	lo, carry := bits.Add64(fl, pl, 0)
135	hi := fh + ph + carry
136	r := isqrt128(hi, lo)
137
138	// UNREACHABLE AND LOAD-BEARING, which is not a contradiction — the same standing
139	// as the hi2 >= m guard above, and it is worth being explicit because no test can
140	// pin it. Nothing reaches it while the domain check at the top of this function
141	// stands: on fall-through coin < full, so the operand is at most cap²−1 and r is
142	// at most cap−1. There is NO margin in that bound (r does reach exactly cap−1), and
143	// the clamp is the second line, not a redundant one. Delete BOTH and, on a curve
144	// New will happily build, Minted(1, -1) returns 9223372036854775807 units for a
145	// spend of 0 — measured, not argued: uint64(-1) makes the operand exceed isqrt128's
146	// exact range, r comes back as its search bound 2^63, int64(r) is MinInt64, and
147	// s1 - from WRAPS to MaxInt64, which the delta <= 0 exit below then waves through
148	// as a positive mint.
149	var s1 int64
150	if r > uint64(c.cap) {
151		s1 = c.cap // clamp before the correction so Cost never sees an over-cap span
152	} else {
153		s1 = int64(r)
154	}
155
156	// Step DOWN while the rounded-up cost of reaching s1 exceeds the payment.
157	for s1 > from {
158		cst, ok := c.Cost(from, s1-from)
159		if ok && cst <= coin {
160			break
161		}
162		s1--
163	}
164	// Step UP while one more coin still fits (and stays under the cap).
165	for s1 < c.cap {
166		cst, ok := c.Cost(from, s1+1-from)
167		if !ok || cst > coin {
168			break
169		}
170		s1++
171	}
172	delta = s1 - from
173	if delta <= 0 {
174		return 0, 0
175	}
176	spent, _ = c.Cost(from, delta) // round-up cost of exactly what was minted
177	return delta, spent
178}
179
180// Price is the marginal price at position s (coin per unit), floor(s/d). Backing
181// is the reserve behind one unit at position s, exactly half the marginal price —
182// the reason every buyer pays about twice the backing of the coin they buy.
183func (c Curve) Price(s int64) int64   { return s / c.d }
184func (c Curve) Backing(s int64) int64 { return s / (2 * c.d) }
185
186// isqrt128 returns floor(sqrt(x)) for the 128-bit unsigned value x = hi:lo, by
187// binary search on the ≤64-bit result — each step squares a candidate with a
188// 128-bit multiply and compares. Division-free and deterministic.
189func isqrt128(hi, lo uint64) uint64 {
190	var ans, lo_ uint64
191	hi_ := uint64(1) << 63 // search bound: covers every result up to sqrt(2^126)=2^63 (our operands stay < 2^100)
192	for lo_ <= hi_ {
193		mid := lo_ + (hi_-lo_)/2
194		mh, ml := bits.Mul64(mid, mid)
195		if mh < hi || (mh == hi && ml <= lo) { // mid² ≤ x
196			ans = mid
197			if mid == ^uint64(0) {
198				break
199			}
200			lo_ = mid + 1
201		} else {
202			if mid == 0 {
203				break
204			}
205			hi_ = mid - 1
206		}
207	}
208	return ans
209}