1// Package twap is a fixed-window trailing average of an integer series: cheap to2// keep, cheap to read, and hard to move with a one-block spike.3//4// It answers one question — "what has this number averaged over the last W?" —5// which is what an on-chain market wants from a price oracle and what a token6// vote wants from a supply-or-turnout figure: a value that a flash spike cannot7// shift, because moving the average requires HOLDING the pushed value for a real8// fraction of the window.9//10// # Not checkpoint11//12// The sibling p/kourt/checkpoint answers a different question — "what was13// this value at sealed epoch N?" — from unbounded, paged history. This is a14// bounded rolling window with no archive: the last N buckets and nothing older.15// Different query, different structure, no overlap.16//17// # A value, not an object18//19// A Ring is a plain value the caller stores inline on a record it was going to20// write anyway — a market's own row. It is never a heap object of its own, and21// never held by pointer in realm state: every method takes a Ring by value and22// returns an updated one. The reason to keep it a value is purely GAS, not23// safety: gno charges per object touched, so a Ring that rides its host's write24// costs nothing extra to keep, whereas a *Ring would be a second object (a second25// key) — and it would buy nothing, since every method is a value receiver that26// hands back a copy anyway. There is no mutator to borrow and so no security27// question here at all; the value shape is a cost decision.28//29// r = r.Observe(height, price) // store r back onto your own record30// avg, ok := r.Average(height, window)31//32// # Buckets, and why a spike does not move the average33//34// Time is quantised into fixed-width buckets. Each bucket remembers the last35// value seen in it; a bucket with no observation carries the previous value36// forward, so a quiet series reads as "unchanged", not as a gap. The average37// over a window of W is the mean of the W/width most recent buckets.38//39// A spike therefore lands in at most one bucket — one part in W/width of the40// average — and only if it is still the last value in that bucket when the bucket41// closes. To move the average by a fraction f of the series' range you must keep42// it moved across about f·(W/width) buckets, i.e. hold the pushed value for f of43// the whole window against everyone trading back. One block is ~1/(W/width) of44// that, which for a week of hourly buckets is under a thousandth of a spike.45//46// # The freshness contract47//48// That guarantee holds only while observations keep arriving. An empty bucket49// carries the last value forward, so if the caller STOPS observing, the last50// value — a spike included — persists across the whole window and the average51// becomes that single value, still reported mature. So the caller must Observe on52// every change to the tracked quantity, OR Observe at the height it later reads.53// StaleBy reports how far a read has drifted from the newest observation, for a54// caller that cannot guarantee the former. `mature` means "the window is55// covered", never "the data is recent".56package twap5758import "math/overflow"5960// Ring is a fixed-window trailing average. The zero value is not usable; build61// one with New.62//63// bpp is bytes per sample: 1 for a 0..255 value such as a percentage price, up64// to 8 for a full int64. Samples are packed big-endian into buf so the whole65// history is one []byte-shaped field rather than N times the 40 bytes gno spends66// on a slice element of any wider type.67type Ring struct {68 width int64 // bucket width, in the caller's height units69 n int // number of buckets70 bpp int // bytes per sample71 head int // ring index of the newest bucket72 base int64 // bucket number (height/width) at head73 last int64 // most recent value, carried across empty buckets74 filled int // buckets ever written, for maturity75 buf string // n*bpp packed big-endian samples76}7778// New builds an empty ring of n buckets, each width height-units wide, storing79// bpp bytes per sample.80//81// The window a caller later asks Average for must be at most n*width, or the ring82// cannot cover it and the read is reported immature. Size n to the longest window83// you will read.84//85// width is the resolution-versus-cost trade: a finer width puts more buckets in a86// window (more storage, a longer Average scan) but resists a spike that is held87// for less real time; a coarser width is cheaper and blunter. n*width fixes the88// span, so the two are chosen together — e.g. a week resisted at hourly grain is89// width=1h, n=168.90func New(width int64, n, bpp int) Ring {91 mustSane(width, n, bpp)92 return Ring{93 width: width, n: n, bpp: bpp,94 head: 0, base: 0, last: 0, filled: 0,95 buf: string(make([]byte, n*bpp)),96 }97}9899// Load reconstructs a ring from a previously stored header and its buf.100//101// The three shape numbers are the caller's own constants; only buf is data, so a102// caller that keeps width/n/bpp as package constants stores just the head fields103// and the bytes.104//105// Load validates SHAPE — buf length, and head/filled in range — and panics on a106// mismatch. It TRUSTS base and last: a wrong value there only skews a later107// average (never reads out of bounds), so pass back exactly what the accessors108// returned rather than hand-built numbers.109func Load(width int64, n, bpp int, head int, base, last int64, filled int, buf string) Ring {110 mustSane(width, n, bpp)111 if len(buf) != n*bpp {112 panic("twap: buf length does not match n*bpp")113 }114 if head < 0 || head >= n || filled < 0 || filled > n {115 panic("twap: head or filled out of range")116 }117 return Ring{width: width, n: n, bpp: bpp, head: head, base: base, last: last, filled: filled, buf: buf}118}119120// Observe records value as of height and returns the updated ring.121//122// Height must not go backwards below the newest bucket already written; a chain123// height only ever increases, and a caller that resets it (a test harness) is the124// one case this refuses, loudly, because a backwards write would corrupt every125// later average.126func (r Ring) Observe(height, value int64) Ring {127 if r.n == 0 {128 panic("twap: zero-value ring; use New")129 }130 bn := height / r.width131 b := []byte(r.buf)132 if r.filled == 0 {133 // Seed on the FIRST real observation, wherever it lands. A market is134 // created at some height H and its first Observe is at H, not at 0 — so135 // base must start at H's bucket, not at zero. Seeding at zero and then136 // advancing to H would carry the zero-value `last` into every bucket in137 // between and count them in `filled`, and the ring would then report a138 // week of history averaging zero as mature and true when the only value139 // ever seen was, say, 50. That is a wrong average handed to a quorum, and140 // it is exactly the case no test with a height-0 start ever reaches.141 r.base = bn142 put(b, r.head*r.bpp, r.bpp, value)143 r.filled, r.last, r.buf = 1, value, string(b)144 return r145 }146 if bn < r.base {147 panic("twap: height went backwards")148 }149 if bn == r.base {150 // Same bucket: overwrite its representative value.151 put(b, r.head*r.bpp, r.bpp, value)152 r.last = value153 r.buf = string(b)154 return r155 }156 // Advance across the gap, carrying `last` into every skipped bucket and157 // `value` into the newest. More than n steps just laps the ring, so cap the158 // work at n — the older laps are overwritten anyway.159 steps := bn - r.base160 if steps > int64(r.n) {161 steps = int64(r.n)162 }163 for i := int64(0); i < steps; i++ {164 r.head++165 if r.head == r.n {166 r.head = 0167 }168 fill := r.last169 if i == steps-1 {170 fill = value171 }172 put(b, r.head*r.bpp, r.bpp, fill)173 if r.filled < r.n {174 r.filled++175 }176 }177 r.base = bn178 r.last = value179 r.buf = string(b)180 return r181}182183// Average returns the trailing average over [height-window, height] and whether184// the ring held enough history to cover the whole window.185//186// mature means the window is COVERED by real buckets — not that those buckets are187// RECENT. An empty tail carries the last value forward (see StaleBy and the188// freshness contract), so a lone spike that is the last observation before a quiet189// spell fills the window and still reads mature. A caller acting on the average190// against manipulation — gating a vote, pricing a payout — must BOTH refuse to act191// while mature is false AND keep the read fresh: Observe at (or near) the height192// it reads, or gate on StaleBy. Reading is pure — a transient decode, no object193// touched — so it is safe inside a Render.194func (r Ring) Average(height, window int64) (avg int64, mature bool) {195 if r.n == 0 {196 panic("twap: zero-value ring; use New")197 }198 if window < r.width {199 window = r.width200 }201 // want is how many buckets the window asks for, UNCAPPED. Maturity is measured202 // against it, so a window wider than the ring can ever hold (want > n) reads203 // immature — rather than silently returning the ring's shorter average stamped204 // as the requested one. k is want capped to what the ring can scan.205 want := int(window / r.width)206 k := want207 if k > r.n {208 k = r.n209 }210 bn := height / r.width211 var sum int64212 count := 0213 for i := 0; i < k; i++ {214 bkt := bn - int64(i)215 if bkt < 0 || bkt <= r.base-int64(r.filled) {216 break // older than the ring has ever held real data217 }218 var v int64219 if bkt > r.base {220 v = r.last // beyond the last observation: value has persisted221 } else {222 idx := r.head - int(r.base-bkt)223 for idx < 0 {224 idx += r.n225 }226 v = get(r.buf, idx*r.bpp, r.bpp) // read the string directly; no []byte copy227 }228 // Checked, not assumed. Values are non-negative, so a wrapped sum goes229 // negative and would hand a quorum a negative "average"; refuse loudly230 // instead. Trips only when the ring holds more large buckets than fit in231 // int64 (e.g. per-minute buckets at the supply cap) — size the ring or232 // narrow the value range.233 next, ok := overflow.Add64(sum, v)234 if !ok {235 panic("twap: window sum overflowed int64")236 }237 sum = next238 count++239 }240 if count == 0 {241 return 0, false242 }243 return sum / int64(count), count == want && r.filled >= want244}245246// Head, Base, Last, Filled, Bytes expose the fields a caller stores alongside buf247// to reconstruct the ring with Load.248func (r Ring) Head() int { return r.head }249func (r Ring) Base() int64 { return r.base }250func (r Ring) Last() int64 { return r.last }251func (r Ring) Filled() int { return r.filled }252func (r Ring) Bytes() string { return r.buf }253254// StaleBy reports how many buckets the read height lies beyond the newest255// observation. Zero means the newest real value sits in height's own bucket; a256// larger number means the window a caller is about to Average is that many buckets257// of carried-forward value rather than fresh data. Because `mature` only says the258// window is covered, a caller acting against manipulation should require StaleBy259// to be small — ideally 0, i.e. Observe at the height it reads (see the freshness260// contract on the package).261func (r Ring) StaleBy(height int64) int64 {262 if r.n == 0 {263 panic("twap: zero-value ring; use New")264 }265 bn := height / r.width266 if bn <= r.base {267 return 0268 }269 return bn - r.base270}271272func mustSane(width int64, n, bpp int) {273 if width <= 0 {274 panic("twap: width must be positive")275 }276 if n <= 0 {277 panic("twap: n must be positive")278 }279 if bpp < 1 || bpp > 8 {280 panic("twap: bpp must be 1..8")281 }282}283284// put writes v big-endian into b[off:off+bpp]. The caller guarantees v fits in285// bpp bytes; a value wider than the sample width is a caller bug, and truncating286// it silently is the one behaviour this must not have — so the top bytes are287// asserted zero.288func put(b []byte, off, bpp int, v int64) {289 if v < 0 {290 panic("twap: negative value")291 }292 if bpp < 8 && v>>(uint(bpp)*8) != 0 {293 panic("twap: value does not fit in bpp bytes")294 }295 for i := bpp - 1; i >= 0; i-- {296 b[off+i] = byte(v & 0xff)297 v >>= 8298 }299}300301// get reads a big-endian sample straight from the buf STRING, so a read never302// allocates a []byte copy. Only Observe needs the mutable []byte (for put); a303// read (Average) is the hot path and stays allocation-free.304func get(s string, off, bpp int) int64 {305 var v int64306 for i := 0; i < bpp; i++ {307 v = (v << 8) | int64(s[off+i])308 }309 return v310}311Signatures reconstructed verbatim from vm/qfuncs — interface params keep their inline definitions.