twap.gno
12.02 Kb · 310 lines
1// Package twap is a fixed-window trailing average of an integer series: cheap to
2// 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 token
6// vote wants from a supply-or-turnout figure: a value that a flash spike cannot
7// shift, because moving the average requires HOLDING the pushed value for a real
8// fraction of the window.
9//
10// # Not checkpoint
11//
12// The sibling p/kourt/checkpoint answers a different question — "what was
13// this value at sealed epoch N?" — from unbounded, paged history. This is a
14// 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 object
18//
19// A Ring is a plain value the caller stores inline on a record it was going to
20// write anyway — a market's own row. It is never a heap object of its own, and
21// never held by pointer in realm state: every method takes a Ring by value and
22// returns an updated one. The reason to keep it a value is purely GAS, not
23// safety: gno charges per object touched, so a Ring that rides its host's write
24// costs nothing extra to keep, whereas a *Ring would be a second object (a second
25// key) — and it would buy nothing, since every method is a value receiver that
26// hands back a copy anyway. There is no mutator to borrow and so no security
27// question here at all; the value shape is a cost decision.
28//
29// r = r.Observe(height, price) // store r back onto your own record
30// avg, ok := r.Average(height, window)
31//
32// # Buckets, and why a spike does not move the average
33//
34// Time is quantised into fixed-width buckets. Each bucket remembers the last
35// value seen in it; a bucket with no observation carries the previous value
36// forward, so a quiet series reads as "unchanged", not as a gap. The average
37// 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 the
40// average — and only if it is still the last value in that bucket when the bucket
41// closes. To move the average by a fraction f of the series' range you must keep
42// it moved across about f·(W/width) buckets, i.e. hold the pushed value for f of
43// the whole window against everyone trading back. One block is ~1/(W/width) of
44// that, which for a week of hourly buckets is under a thousandth of a spike.
45//
46// # The freshness contract
47//
48// That guarantee holds only while observations keep arriving. An empty bucket
49// carries the last value forward, so if the caller STOPS observing, the last
50// value — a spike included — persists across the whole window and the average
51// becomes that single value, still reported mature. So the caller must Observe on
52// 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 a
54// caller that cannot guarantee the former. `mature` means "the window is
55// covered", never "the data is recent".
56package twap
57
58import "math/overflow"
59
60// Ring is a fixed-window trailing average. The zero value is not usable; build
61// one with New.
62//
63// bpp is bytes per sample: 1 for a 0..255 value such as a percentage price, up
64// to 8 for a full int64. Samples are packed big-endian into buf so the whole
65// history is one []byte-shaped field rather than N times the 40 bytes gno spends
66// on a slice element of any wider type.
67type Ring struct {
68 width int64 // bucket width, in the caller's height units
69 n int // number of buckets
70 bpp int // bytes per sample
71 head int // ring index of the newest bucket
72 base int64 // bucket number (height/width) at head
73 last int64 // most recent value, carried across empty buckets
74 filled int // buckets ever written, for maturity
75 buf string // n*bpp packed big-endian samples
76}
77
78// New builds an empty ring of n buckets, each width height-units wide, storing
79// bpp bytes per sample.
80//
81// The window a caller later asks Average for must be at most n*width, or the ring
82// cannot cover it and the read is reported immature. Size n to the longest window
83// you will read.
84//
85// width is the resolution-versus-cost trade: a finer width puts more buckets in a
86// window (more storage, a longer Average scan) but resists a spike that is held
87// for less real time; a coarser width is cheaper and blunter. n*width fixes the
88// span, so the two are chosen together — e.g. a week resisted at hourly grain is
89// 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}
98
99// 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 a
102// caller that keeps width/n/bpp as package constants stores just the head fields
103// and the bytes.
104//
105// Load validates SHAPE — buf length, and head/filled in range — and panics on a
106// mismatch. It TRUSTS base and last: a wrong value there only skews a later
107// average (never reads out of bounds), so pass back exactly what the accessors
108// 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}
119
120// 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 chain
123// height only ever increases, and a caller that resets it (a test harness) is the
124// one case this refuses, loudly, because a backwards write would corrupt every
125// 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.width
131 b := []byte(r.buf)
132 if r.filled == 0 {
133 // Seed on the FIRST real observation, wherever it lands. A market is
134 // created at some height H and its first Observe is at H, not at 0 — so
135 // base must start at H's bucket, not at zero. Seeding at zero and then
136 // advancing to H would carry the zero-value `last` into every bucket in
137 // between and count them in `filled`, and the ring would then report a
138 // week of history averaging zero as mature and true when the only value
139 // ever seen was, say, 50. That is a wrong average handed to a quorum, and
140 // it is exactly the case no test with a height-0 start ever reaches.
141 r.base = bn
142 put(b, r.head*r.bpp, r.bpp, value)
143 r.filled, r.last, r.buf = 1, value, string(b)
144 return r
145 }
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 = value
153 r.buf = string(b)
154 return r
155 }
156 // Advance across the gap, carrying `last` into every skipped bucket and
157 // `value` into the newest. More than n steps just laps the ring, so cap the
158 // work at n — the older laps are overwritten anyway.
159 steps := bn - r.base
160 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 = 0
167 }
168 fill := r.last
169 if i == steps-1 {
170 fill = value
171 }
172 put(b, r.head*r.bpp, r.bpp, fill)
173 if r.filled < r.n {
174 r.filled++
175 }
176 }
177 r.base = bn
178 r.last = value
179 r.buf = string(b)
180 return r
181}
182
183// Average returns the trailing average over [height-window, height] and whether
184// 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 are
187// RECENT. An empty tail carries the last value forward (see StaleBy and the
188// freshness contract), so a lone spike that is the last observation before a quiet
189// spell fills the window and still reads mature. A caller acting on the average
190// against manipulation — gating a vote, pricing a payout — must BOTH refuse to act
191// while mature is false AND keep the read fresh: Observe at (or near) the height
192// it reads, or gate on StaleBy. Reading is pure — a transient decode, no object
193// 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.width
200 }
201 // want is how many buckets the window asks for, UNCAPPED. Maturity is measured
202 // against it, so a window wider than the ring can ever hold (want > n) reads
203 // immature — rather than silently returning the ring's shorter average stamped
204 // as the requested one. k is want capped to what the ring can scan.
205 want := int(window / r.width)
206 k := want
207 if k > r.n {
208 k = r.n
209 }
210 bn := height / r.width
211 var sum int64
212 count := 0
213 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 data
217 }
218 var v int64
219 if bkt > r.base {
220 v = r.last // beyond the last observation: value has persisted
221 } else {
222 idx := r.head - int(r.base-bkt)
223 for idx < 0 {
224 idx += r.n
225 }
226 v = get(r.buf, idx*r.bpp, r.bpp) // read the string directly; no []byte copy
227 }
228 // Checked, not assumed. Values are non-negative, so a wrapped sum goes
229 // negative and would hand a quorum a negative "average"; refuse loudly
230 // instead. Trips only when the ring holds more large buckets than fit in
231 // int64 (e.g. per-minute buckets at the supply cap) — size the ring or
232 // narrow the value range.
233 next, ok := overflow.Add64(sum, v)
234 if !ok {
235 panic("twap: window sum overflowed int64")
236 }
237 sum = next
238 count++
239 }
240 if count == 0 {
241 return 0, false
242 }
243 return sum / int64(count), count == want && r.filled >= want
244}
245
246// Head, Base, Last, Filled, Bytes expose the fields a caller stores alongside buf
247// 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 }
253
254// StaleBy reports how many buckets the read height lies beyond the newest
255// observation. Zero means the newest real value sits in height's own bucket; a
256// larger number means the window a caller is about to Average is that many buckets
257// of carried-forward value rather than fresh data. Because `mature` only says the
258// window is covered, a caller acting against manipulation should require StaleBy
259// to be small — ideally 0, i.e. Observe at the height it reads (see the freshness
260// 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.width
266 if bn <= r.base {
267 return 0
268 }
269 return bn - r.base
270}
271
272func 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}
283
284// put writes v big-endian into b[off:off+bpp]. The caller guarantees v fits in
285// bpp bytes; a value wider than the sample width is a caller bug, and truncating
286// it silently is the one behaviour this must not have — so the top bytes are
287// 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 >>= 8
298 }
299}
300
301// get reads a big-endian sample straight from the buf STRING, so a read never
302// allocates a []byte copy. Only Observe needs the mutable []byte (for put); a
303// read (Average) is the hot path and stays allocation-free.
304func get(s string, off, bpp int) int64 {
305 var v int64
306 for i := 0; i < bpp; i++ {
307 v = (v << 8) | int64(s[off+i])
308 }
309 return v
310}
