oracle.gno
13.92 Kb · 476 lines
1package pool
2
3import (
4 "errors"
5 "time"
6
7 "gno.land/p/gnoswap/consts/v1"
8 u256 "gno.land/p/gnoswap/uint256/v1"
9 pl "gno.land/r/gnoswap/pool"
10)
11
12// maxObservationCardinality defines the maximum number of observations to store
13const maxObservationCardinality uint16 = 65535
14
15// oracleConsult calculates the time-weighted average price between two points in time.
16// It returns the arithmetic mean tick and harmonic mean liquidity over the time period.
17func oracleConsult(p *pl.Pool, observations *pl.ObservationTree, secondsAgo uint32) (int32, *u256.Uint, error) {
18 if secondsAgo == 0 {
19 return 0, nil, errors.New("secondsAgo must be greater than 0")
20 }
21
22 if observations == nil {
23 return 0, nil, errors.New("observations not initialized")
24 }
25 slot0 := p.Slot0()
26
27 // Get observations for current time and secondsAgo
28 secondsAgos := []uint32{secondsAgo, 0}
29 blockTimestamp := time.Now().Unix()
30
31 tickCumulatives, secondsPerLiquidityCumulativeX128s, err := observe(
32 observations,
33 blockTimestamp,
34 secondsAgos,
35 slot0.Tick(),
36 slot0.ObservationIndex(),
37 p.Liquidity(),
38 slot0.ObservationCardinality(),
39 )
40 if err != nil {
41 return 0, nil, err
42 }
43
44 tickCumulativesDelta := tickCumulatives[1] - tickCumulatives[0]
45 secondsPerLiquidityDelta := u256.Zero().Sub(
46 u256.MustFromDecimal(secondsPerLiquidityCumulativeX128s[1]),
47 u256.MustFromDecimal(secondsPerLiquidityCumulativeX128s[0]),
48 )
49
50 arithmeticMeanTick := int32(tickCumulativesDelta / int64(secondsAgo))
51 if tickCumulativesDelta < 0 && (tickCumulativesDelta%int64(secondsAgo) != 0) {
52 arithmeticMeanTick--
53 }
54
55 if secondsPerLiquidityDelta.IsZero() {
56 return arithmeticMeanTick, u256.Zero(), nil
57 }
58
59 // Calculate harmonic mean liquidity
60 secondsAgoX160 := u256.Zero().Mul(u256.NewUint(uint64(secondsAgo)), consts.Max160())
61 denominator := u256.Zero().Lsh(secondsPerLiquidityDelta, 32)
62 harmonicMeanLiquidity := u256.Zero().Div(secondsAgoX160, denominator)
63
64 return arithmeticMeanTick, harmonicMeanLiquidity, nil
65}
66
67// snapshotCumulativesInside returns the accumulators that accrued while the
68// current price was inside [tickLower, tickUpper), following Uniswap V3's
69// snapshotCumulativesInside flow.
70func snapshotCumulativesInside(
71 p *pl.Pool,
72 observations *pl.ObservationTree,
73 tickLower int32,
74 tickUpper int32,
75) (int64, *u256.Uint, uint32, error) {
76 if err := validateTicks(tickLower, tickUpper); err != nil {
77 return 0, nil, 0, err
78 }
79
80 lower := getTick(p, tickLower)
81 if !lower.Initialized() {
82 return 0, nil, 0, makeErrorWithDetails(errDataNotFound, "lower tick is not initialized")
83 }
84
85 upper := getTick(p, tickUpper)
86 if !upper.Initialized() {
87 return 0, nil, 0, makeErrorWithDetails(errDataNotFound, "upper tick is not initialized")
88 }
89
90 lowerSecondsPerLiquidityOutsideX128 := u256.MustFromDecimal(lower.SecondsPerLiquidityOutsideX128())
91 upperSecondsPerLiquidityOutsideX128 := u256.MustFromDecimal(upper.SecondsPerLiquidityOutsideX128())
92 slot0 := p.Slot0()
93
94 if slot0.Tick() < tickLower {
95 return lower.TickCumulativeOutside() - upper.TickCumulativeOutside(),
96 u256.Zero().Sub(lowerSecondsPerLiquidityOutsideX128, upperSecondsPerLiquidityOutsideX128),
97 lower.SecondsOutside() - upper.SecondsOutside(), nil
98 }
99
100 if slot0.Tick() < tickUpper {
101 if observations == nil {
102 return 0, nil, 0, errors.New("observations not initialized")
103 }
104
105 currentTime := time.Now().Unix()
106 tickCumulative, secondsPerLiquidityCumulativeX128, err := observeSingle(
107 observations,
108 currentTime,
109 0,
110 slot0.Tick(),
111 slot0.ObservationIndex(),
112 p.Liquidity(),
113 slot0.ObservationCardinality(),
114 )
115 if err != nil {
116 return 0, nil, 0, err
117 }
118
119 secondsPerLiquidityInsideX128 := u256.Zero().Sub(
120 u256.Zero().Sub(
121 u256.MustFromDecimal(secondsPerLiquidityCumulativeX128),
122 lowerSecondsPerLiquidityOutsideX128,
123 ),
124 upperSecondsPerLiquidityOutsideX128,
125 )
126
127 return tickCumulative - lower.TickCumulativeOutside() - upper.TickCumulativeOutside(),
128 secondsPerLiquidityInsideX128,
129 uint32(currentTime) - lower.SecondsOutside() - upper.SecondsOutside(), nil
130 }
131
132 return upper.TickCumulativeOutside() - lower.TickCumulativeOutside(),
133 u256.Zero().Sub(upperSecondsPerLiquidityOutsideX128, lowerSecondsPerLiquidityOutsideX128),
134 upper.SecondsOutside() - lower.SecondsOutside(), nil
135}
136
137func transform(last pl.Observation, blockTimestamp int64, tick int32, liquidity *u256.Uint) (pl.Observation, error) {
138 timeDelta := blockTimestamp - last.BlockTimestamp()
139 if timeDelta < 0 {
140 return pl.DefaultObservation(), errors.New("time delta must be greater than 0")
141 }
142
143 // calculate cumulative values
144 tickCumulative := last.TickCumulative() + int64(tick)*timeDelta
145
146 // calculate seconds per liquidity
147 liquidityForCalc := liquidity
148 if liquidity.IsZero() {
149 liquidityForCalc = u256.One()
150 }
151
152 // secondsPerLiquidity += timeDelta * 2^128 / max(1, liquidity)
153 secondsPerLiquidityDelta := u256.MulDiv(
154 u256.NewUintFromInt64(timeDelta),
155 consts.Q128(),
156 liquidityForCalc,
157 )
158
159 prevSecPerLiq := u256.MustFromDecimal(last.SecondsPerLiquidityCumulativeX128())
160 secondsPerLiquidityCumulativeX128 := u256.Zero().Add(
161 prevSecPerLiq,
162 secondsPerLiquidityDelta,
163 )
164
165 observation := pl.MakeObservation(
166 blockTimestamp,
167 tickCumulative,
168 secondsPerLiquidityCumulativeX128.ToString(),
169 true,
170 )
171 return observation, nil
172}
173
174func grow(observations *pl.ObservationTree, current, next uint16) (uint16, error) {
175 if observations == nil {
176 return current, errors.New("observations not initialized")
177 }
178
179 if current <= 0 {
180 return current, errors.New("current must be greater than 0")
181 }
182
183 if next <= current {
184 return current, nil
185 }
186
187 if next > maxObservationCardinality {
188 return current, errors.New("next exceeds maximum")
189 }
190
191 // Reserve every new slot now so the caller that increases capacity pays for
192 // its storage. This matches Uniswap's Oracle.grow behavior and prevents an
193 // unrestricted reservation from shifting allocation cost to later swappers.
194 for i := current; i < next; i++ {
195 observations.Set(i, pl.MakeObservation(1, 0, "0", false))
196 }
197
198 return next, nil
199}
200
201func writeObservation(
202 observations *pl.ObservationTree,
203 index uint16,
204 blockTimestamp int64,
205 tick int32,
206 liquidity *u256.Uint,
207 cardinality uint16,
208 cardinalityNext uint16,
209) (indexUpdated uint16, cardinalityUpdated uint16, err error) {
210 if observations == nil {
211 return 0, 0, errors.New("observations not initialized")
212 }
213 if cardinality == 0 {
214 return 0, 0, errors.New("observation cardinality must be greater than 0")
215 }
216
217 last, err := observationAt(observations, index)
218 if err != nil {
219 return 0, 0, err
220 }
221
222 if last.BlockTimestamp() == blockTimestamp {
223 return index, cardinality, nil
224 }
225
226 // Check if we need to grow the cardinality
227 if cardinalityNext > cardinality && index == cardinality-1 {
228 cardinalityUpdated = cardinalityNext
229 } else {
230 cardinalityUpdated = cardinality
231 }
232
233 indexUpdated = (index + 1) % cardinalityUpdated
234 observation, err := transform(last, blockTimestamp, tick, liquidity)
235 if err != nil {
236 return 0, 0, err
237 }
238
239 observations.Set(indexUpdated, observation)
240 return indexUpdated, cardinalityUpdated, nil
241}
242
243// observationAt returns the observation at a specific index
244// Returns error if the observation doesn't exist
245func observationAt(observations *pl.ObservationTree, index uint16) (pl.Observation, error) {
246 if observations == nil {
247 return pl.DefaultObservation(), errors.New("observations not initialized")
248 }
249 obs, ok := observations.Get(index)
250 if !ok {
251 return pl.DefaultObservation(), errors.New(errNotInitializedObservation)
252 }
253
254 return obs, nil
255}
256
257// observeSingle returns the data for a single observation at a specific time ago
258func observeSingle(
259 observations *pl.ObservationTree,
260 time int64,
261 secondsAgo uint32,
262 tick int32,
263 index uint16,
264 liquidity *u256.Uint,
265 cardinality uint16,
266) (int64, string, error) {
267 if secondsAgo == 0 {
268 // if secondsAgo is 0, return current values
269 last, err := observationAt(observations, index)
270 if err != nil {
271 return 0, "", err
272 }
273
274 if last.BlockTimestamp() != time {
275 // need to create virtual observation for current time
276 transformed, err := transform(last, time, tick, liquidity)
277 if err != nil {
278 return 0, "", err
279 }
280
281 return transformed.TickCumulative(), transformed.SecondsPerLiquidityCumulativeX128(), nil
282 }
283
284 return last.TickCumulative(), last.SecondsPerLiquidityCumulativeX128(), nil
285 }
286
287 // A lookback longer than the chain's own age would place the target before unix epoch.
288 if int64(secondsAgo) > time {
289 return 0, "", errors.New(errObservationBeforeEpoch)
290 }
291
292 target := time - int64(secondsAgo)
293
294 // find the observations before and after the target
295 beforeOrAt, atOrAfter, err := getSurroundingObservations(
296 observations,
297 target,
298 tick,
299 index,
300 liquidity,
301 cardinality,
302 )
303 if err != nil {
304 return 0, "", err
305 }
306
307 if target == beforeOrAt.BlockTimestamp() {
308 return beforeOrAt.TickCumulative(), beforeOrAt.SecondsPerLiquidityCumulativeX128(), nil
309 }
310
311 if target == atOrAfter.BlockTimestamp() {
312 return atOrAfter.TickCumulative(), atOrAfter.SecondsPerLiquidityCumulativeX128(), nil
313 }
314
315 // interpolate between the two observations
316 observationTimeDelta := atOrAfter.BlockTimestamp() - beforeOrAt.BlockTimestamp()
317 targetDelta := target - beforeOrAt.BlockTimestamp()
318
319 // tickCumulative += (tickCumulativeAfter - tickCumulativeBefore) / observationTimeDelta * targetDelta
320 tickCumulative := beforeOrAt.TickCumulative() +
321 ((atOrAfter.TickCumulative()-beforeOrAt.TickCumulative())/observationTimeDelta)*targetDelta
322
323 beforeSecPerLiq := u256.MustFromDecimal(beforeOrAt.SecondsPerLiquidityCumulativeX128())
324 afterSecPerLiq := u256.MustFromDecimal(atOrAfter.SecondsPerLiquidityCumulativeX128())
325
326 // for secondsPerLiquidity, need to interpolate carefully
327 secondsPerLiquidityDelta := u256.Zero().Sub(afterSecPerLiq, beforeSecPerLiq)
328
329 secondsPerLiquidity := u256.Zero().Add(
330 beforeSecPerLiq,
331 u256.MulDiv(
332 secondsPerLiquidityDelta,
333 u256.NewUintFromInt64(targetDelta),
334 u256.NewUintFromInt64(observationTimeDelta),
335 ),
336 )
337
338 return tickCumulative, secondsPerLiquidity.ToString(), nil
339}
340
341// getSurroundingObservations finds the observations immediately before and after the target timestamp.
342// It uses binary search over the logical time-ordered view of the circular buffer.
343// Logical order starts at (index+1) % cardinality (oldest) and ends at index (latest).
344func getSurroundingObservations(
345 observations *pl.ObservationTree,
346 target int64,
347 tick int32,
348 index uint16,
349 liquidity *u256.Uint,
350 cardinality uint16,
351) (pl.Observation, pl.Observation, error) {
352 // Optimistically set before to the newest observation
353 beforeOrAt, err := observationAt(observations, index)
354 if err != nil {
355 return pl.DefaultObservation(), pl.DefaultObservation(), err
356 }
357
358 // Timestamps are int64, so natural ordering applies. Uniswap V3 needs a
359 // wraparound-aware comparison here only because it stores them as uint32.
360 // If the target is chronologically at or after the newest observation, we can early return
361 if beforeOrAt.BlockTimestamp() <= target {
362 if beforeOrAt.BlockTimestamp() == target {
363 // If newest observation equals target, we're in the same block, so we can ignore atOrAfter
364 return beforeOrAt, pl.DefaultObservation(), nil
365 }
366 // Otherwise, we need to transform
367 atOrAfter, err := transform(beforeOrAt, target, tick, liquidity)
368 if err != nil {
369 return pl.DefaultObservation(), pl.DefaultObservation(), err
370 }
371 return beforeOrAt, atOrAfter, nil
372 }
373
374 // Now, set before to the oldest observation
375 start := (index + 1) % cardinality
376 beforeOrAt, err = observationAt(observations, start)
377 if err != nil || !beforeOrAt.Initialized() {
378 beforeOrAt, err = observationAt(observations, 0)
379 if err != nil {
380 return pl.DefaultObservation(), pl.DefaultObservation(), err
381 }
382 }
383
384 // Ensure that the target is chronologically at or after the oldest observation
385 if beforeOrAt.BlockTimestamp() > target {
386 return pl.DefaultObservation(), pl.DefaultObservation(), errors.New(errObservationTooOld)
387 }
388
389 // If we've reached this point, we have to binary search
390 return binarySearch(observations, target, index, cardinality)
391}
392
393func binarySearch(
394 observations *pl.ObservationTree,
395 target int64,
396 index uint16,
397 cardinality uint16,
398) (pl.Observation, pl.Observation, error) {
399 l := uint64((index + 1) % cardinality) // oldest observation
400 r := l + uint64(cardinality) - 1 // newest observation
401 var i uint64
402 var beforeOrAt, atOrAfter pl.Observation
403 var err error
404
405 for {
406 i = (l + r) / 2
407
408 beforeIndex := uint16(i % uint64(cardinality))
409 beforeOrAt, err = observationAt(observations, beforeIndex)
410 if err != nil || !beforeOrAt.Initialized() {
411 // we've landed on an uninitialized tick, keep searching higher (more recently)
412 l = i + 1
413 continue
414 }
415
416 afterIndex := uint16((i + 1) % uint64(cardinality))
417 atOrAfter, err = observationAt(observations, afterIndex)
418 if err != nil {
419 return pl.DefaultObservation(), pl.DefaultObservation(), err
420 }
421
422 targetAtOrAfter := beforeOrAt.BlockTimestamp() <= target
423
424 // check if we've found the answer!
425 if targetAtOrAfter && target <= atOrAfter.BlockTimestamp() {
426 break
427 }
428
429 if !targetAtOrAfter {
430 r = i - 1
431 } else {
432 l = i + 1
433 }
434 }
435
436 return beforeOrAt, atOrAfter, nil
437}
438
439// observe returns the cumulative tick and liquidity as of each timestamp secondsAgo from the current time.
440func observe(
441 observations *pl.ObservationTree,
442 time int64,
443 secondsAgos []uint32,
444 tick int32,
445 index uint16,
446 liquidity *u256.Uint,
447 cardinality uint16,
448) ([]int64, []string, error) {
449 if cardinality <= 0 {
450 return nil, nil, errors.New("observation cardinality must be greater than 0")
451 }
452
453 historyCount := len(secondsAgos)
454 tickCumulatives := make([]int64, historyCount)
455 secondsPerLiquidityCumulativeX128s := make([]string, historyCount)
456
457 for i, secondsAgo := range secondsAgos {
458 tickCumulative, secondsPerLiquidity, err := observeSingle(
459 observations,
460 time,
461 secondsAgo,
462 tick,
463 index,
464 liquidity,
465 cardinality,
466 )
467 if err != nil {
468 return nil, nil, err
469 }
470
471 tickCumulatives[i] = tickCumulative
472 secondsPerLiquidityCumulativeX128s[i] = secondsPerLiquidity
473 }
474
475 return tickCumulatives, secondsPerLiquidityCumulativeX128s, nil
476}
