-
Notifications
You must be signed in to change notification settings - Fork 0
/
pools.go
246 lines (217 loc) · 8.07 KB
/
pools.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
package orderbook
import (
"math"
"github.com/holiman/uint256"
"github.com/shantanu-hashcash/go/support/errors"
"github.com/shantanu-hashcash/go/xdr"
)
// There are two different exchanges that can be simulated:
//
// 1. You know how much you can *give* to the pool, and are curious about the
// resulting payout. We call this a "deposit", and you should pass
// tradeTypeDeposit.
//
// 2. You know how much you'd like to *receive* from the pool, and want to know
// how much to deposit to achieve this. We call this an "expectation", and you
// should pass tradeTypeExpectation.
const (
tradeTypeDeposit = iota // deposit into pool, what's the payout?
tradeTypeExpectation = iota // expect payout, what to deposit?
)
var (
errPoolOverflows = errors.New("Liquidity pool overflows from this exchange")
errBadPoolType = errors.New("Unsupported liquidity pool: must be ConstantProduct")
errBadTradeType = errors.New("Unknown pool exchange type requested")
errBadAmount = errors.New("Exchange amount must be positive")
)
// makeTrade simulates execution of an exchange with a liquidity pool.
//
// In (1), this returns the amount that would be paid out by the pool (in terms
// of the *other* asset) for depositing `amount` of `asset`.
//
// In (2), this returns the amount of `asset` you'd need to deposit to get
// `amount` of the *other* asset in return.
//
// Refer to https://github.com/shantanu-hashcash/hcnet-protocol/blob/master/core/cap-0038.md#pathpaymentstrictsendop-and-pathpaymentstrictreceiveop
// and the calculation functions (below) for details on the exchange algorithm.
//
// Warning: If you pass an asset that is NOT one of the pool reserves, the
// behavior of this function is undefined (for performance).
func makeTrade(
pool liquidityPool,
asset int32,
tradeType int,
amount xdr.Int64,
) (xdr.Int64, error) {
details, ok := pool.Body.GetConstantProduct()
if !ok {
return 0, errBadPoolType
}
if amount <= 0 {
return 0, errBadAmount
}
// determine which asset `amount` corresponds to
X, Y := details.ReserveA, details.ReserveB
if pool.assetA != asset {
X, Y = Y, X
}
ok = false
var result xdr.Int64
switch tradeType {
case tradeTypeDeposit:
result, _, ok = CalculatePoolPayout(X, Y, amount, details.Params.Fee, false)
case tradeTypeExpectation:
result, _, ok = CalculatePoolExpectation(X, Y, amount, details.Params.Fee, false)
default:
return 0, errBadTradeType
}
if !ok {
// the error isn't strictly accurate (e.g. it could be div-by-0), but
// from the caller's perspective it's true enough
return 0, errPoolOverflows
}
return result, nil
}
// CalculatePoolPayout calculates the amount of `reserveB` disbursed from the
// pool for a `received` amount of `reserveA` . From CAP-38:
//
// y = floor[(1 - F) Yx / (X + x - Fx)]
//
// It returns false if the calculation overflows.
func CalculatePoolPayout(reserveA, reserveB, received xdr.Int64, feeBips xdr.Int32, calculateRoundingSlippage bool) (xdr.Int64, xdr.Int64, bool) {
X, Y := uint256.NewInt(uint64(reserveA)), uint256.NewInt(uint64(reserveB))
F, x := uint256.NewInt(uint64(feeBips)), uint256.NewInt(uint64(received))
// would this deposit overflow the reserve?
if received > math.MaxInt64-reserveA {
return 0, 0, false
}
// We do all of the math with 4 extra decimal places of precision, so it's
// all upscaled by this value.
maxBips := uint256.NewInt(10000)
f := new(uint256.Int).Sub(maxBips, F) // upscaled 1 - F
// right half: X + (1 - F)x
denom := X.Mul(X, maxBips).Add(X, new(uint256.Int).Mul(x, f))
if denom.IsZero() { // avoid div-by-zero panic
return 0, 0, false
}
// left half, a: (1 - F) Yx
numer := Y.Mul(Y, x).Mul(Y, f)
// divide & check overflow
result := new(uint256.Int)
result.Div(numer, denom)
var roundingSlippageBips xdr.Int64
ok := true
if calculateRoundingSlippage && !new(uint256.Int).Mod(numer, denom).IsZero() {
// Calculates the rounding slippage (S) in bips (Basis points)
//
// S is the % which the rounded result deviates from the unrounded.
// i.e. How much "error" did the rounding introduce?
//
// unrounded = Xy / ((Y - y)(1 - F))
// expectation = ceil[unrounded]
// S = abs(expectation - unrounded) / unrounded
//
// For example, for:
//
// X = 200 // 200 stroops of deposited asset in reserves
// Y = 300 // 300 stroops of disbursed asset in reserves
// y = 3 // disbursing 3 stroops
// F = 0.003 // fee is 0.3%
// unrounded = (200 * 3) / ((300 - 3)(1 - 0.003)) = 2.03
// S = abs(ceil(2.03) - 2.03) / 2.03 = 47.78%
// toBips(S) = 4778
//
S := new(uint256.Int)
unrounded, rounded := new(uint256.Int), new(uint256.Int)
// Upscale to centibips for extra precision
unrounded.Mul(numer, maxBips).Div(unrounded, denom)
rounded.Mul(result, maxBips)
S.Sub(unrounded, rounded)
S.Abs(S).Mul(S, maxBips)
S.Div(S, unrounded)
S.Div(S, uint256.NewInt(100)) // Downscale from centibips to bips
roundingSlippageBips = xdr.Int64(S.Uint64())
ok = ok && S.IsUint64() && roundingSlippageBips >= 0
}
val := xdr.Int64(result.Uint64())
ok = ok && result.IsUint64() && val >= 0
return val, roundingSlippageBips, ok
}
// CalculatePoolExpectation determines how much of `reserveA` you would need to
// put into a pool to get the `disbursed` amount of `reserveB`.
//
// x = ceil[Xy / ((Y - y)(1 - F))]
//
// It returns false if the calculation overflows.
func CalculatePoolExpectation(
reserveA, reserveB, disbursed xdr.Int64, feeBips xdr.Int32, calculateRoundingSlippage bool,
) (xdr.Int64, xdr.Int64, bool) {
X, Y := uint256.NewInt(uint64(reserveA)), uint256.NewInt(uint64(reserveB))
F, y := uint256.NewInt(uint64(feeBips)), uint256.NewInt(uint64(disbursed))
// sanity check: disbursing shouldn't underflow the reserve
if disbursed >= reserveB {
return 0, 0, false
}
// We do all of the math with 4 extra decimal places of precision, so it's
// all upscaled by this value.
maxBips := uint256.NewInt(10_000)
f := new(uint256.Int).Sub(maxBips, F) // upscaled 1 - F
denom := Y.Sub(Y, y).Mul(Y, f) // right half: (Y - y)(1 - F)
if denom.IsZero() { // avoid div-by-zero panic
return 0, 0, false
}
numer := X.Mul(X, y).Mul(X, maxBips) // left half: Xy
result, rem := new(uint256.Int), new(uint256.Int)
result.Div(numer, denom)
rem.Mod(numer, denom)
// hacky way to ceil(): if there's a remainder, add 1
var roundingSlippageBips xdr.Int64
ok := true
if !rem.IsZero() {
result.AddUint64(result, 1)
if calculateRoundingSlippage {
// Calculates the rounding slippage (S) in bips (Basis points)
//
// S is the % which the rounded result deviates from the unrounded.
// i.e. How much "error" did the rounding introduce?
//
// unrounded = Xy / ((Y - y)(1 - F))
// expectation = ceil[unrounded]
// S = abs(expectation - unrounded) / unrounded
//
// For example, for:
//
// X = 200 // 200 stroops of deposited asset in reserves
// Y = 300 // 300 stroops of disbursed asset in reserves
// y = 3 // disbursing 3 stroops
// F = 0.003 // fee is 0.3%
// unrounded = (200 * 3) / ((300 - 3)(1 - 0.003)) = 2.03
// S = abs(ceil(2.03) - 2.03) / 2.03 = 47.78%
// toBips(S) = 4778
//
S := new(uint256.Int)
unrounded, rounded := new(uint256.Int), new(uint256.Int)
// Upscale to centibips for extra precision
unrounded.Mul(numer, maxBips).Div(unrounded, denom)
rounded.Mul(result, maxBips)
S.Sub(unrounded, rounded)
S.Abs(S).Mul(S, maxBips)
S.Div(S, unrounded)
S.Div(S, uint256.NewInt(100)) // Downscale from centibips to bips
roundingSlippageBips = xdr.Int64(S.Uint64())
ok = ok && S.IsUint64() && roundingSlippageBips >= 0
}
}
val := xdr.Int64(result.Uint64())
ok = ok && result.IsUint64() && val >= 0
return val, roundingSlippageBips, ok
}
// getOtherAsset returns the other asset in the liquidity pool. Note that
// doesn't check to make sure the passed in `asset` is actually part of the
// pool; behavior in that case is undefined.
func getOtherAsset(asset int32, pool liquidityPool) int32 {
if pool.assetA == asset {
return pool.assetB
}
return pool.assetA
}