feeledger.gno
8.52 Kb · 273 lines
1// Package feeledger is a pure accounting primitive for realms that hold
2// coins on behalf of users and charge an explicit protocol fee on
3// deposits. It tracks per-account balances, the sum of user liabilities,
4// and a separately-accrued fee pot. It never touches coins itself: the
5// importing realm moves coins and drives this ledger, keeping the two in
6// lock-step so that
7//
8// coins held by realm == UsersTotal() + FeesAccrued() + surplus
9//
10// where surplus is coins pushed to the realm outside the ledger's flow
11// (always >= 0, and 0 if every coin movement goes through the ledger).
12//
13// Fee model:
14// - Fees are expressed in basis points (1 bps = 0.01%); BpsDenominator
15// is 10000, so bps == 10000 means the whole deposit is fee.
16// - fee = floor(amount * bps / 10000). Rounding always favors the
17// DEPOSITOR: any fractional fee is dropped, the account is credited
18// amount - fee. A small deposit may therefore pay zero fee.
19// - There is no minimum fee. The maximum fee is bounded by the
20// per-ledger cap set at construction (maxFeeBps <= 10000), so a fee
21// can never exceed its deposit.
22// - bps == 0 is a valid configuration: fee is exactly 0 and the full
23// amount is credited.
24//
25// All failures are returned as errors and leave the ledger COMPLETELY
26// UNCHANGED; callers in realms typically wrap calls so an error panics
27// and aborts the transaction. Must* wrappers are provided and are the
28// only functions in this package that panic.
29//
30// The ledger is address-agnostic: accounts are non-empty strings. Realms
31// normally use address.String().
32package feeledger
33
34import (
35 "errors"
36
37 "gno.land/p/nt/avl/v0"
38)
39
40// BpsDenominator is the fee basis: fees are bps/BpsDenominator of the
41// deposited amount.
42const BpsDenominator = int64(10000)
43
44// Errors returned by Ledger operations.
45var (
46 ErrEmptyAccount = errors.New("feeledger: empty account key")
47 ErrInvalidAmount = errors.New("feeledger: amount must be positive")
48 ErrInvalidBps = errors.New("feeledger: fee bps out of range")
49 ErrInsufficient = errors.New("feeledger: insufficient balance")
50 ErrOverflow = errors.New("feeledger: int64 overflow")
51)
52
53// Ledger tracks per-account balances, their sum (user liabilities), and
54// separately-accrued protocol fees. The zero value is not usable;
55// construct with New.
56type Ledger struct {
57 maxFeeBps int64
58 balances *avl.Tree // account string -> int64 (always > 0)
59 usersTotal int64 // == sum of all balances
60 feesAccrued int64 // fees charged but not yet withdrawn
61}
62
63// New returns an empty ledger that rejects deposit fees above maxFeeBps.
64// maxFeeBps must be in [0, BpsDenominator].
65func New(maxFeeBps int64) (*Ledger, error) {
66 if maxFeeBps < 0 || maxFeeBps > BpsDenominator {
67 return nil, ErrInvalidBps
68 }
69 return &Ledger{
70 maxFeeBps: maxFeeBps,
71 balances: avl.NewTree(),
72 }, nil
73}
74
75// MustNew is New but panics on error.
76func MustNew(maxFeeBps int64) *Ledger {
77 l, err := New(maxFeeBps)
78 if err != nil {
79 panic(err)
80 }
81 return l
82}
83
84// MaxFeeBps returns the ledger's hard fee cap.
85func (l *Ledger) MaxFeeBps() int64 {
86 return l.maxFeeBps
87}
88
89// FeeFor returns the fee charged on amount at bps, using the ledger's
90// rounding rule: floor(amount * bps / BpsDenominator). It is a pure
91// preview — no state is read or written beyond validation against
92// BpsDenominator (NOT the ledger cap; use it to inspect any policy).
93// amount must be >= 0 and bps in [0, BpsDenominator].
94func FeeFor(amount, bps int64) (int64, error) {
95 if amount < 0 {
96 return 0, ErrInvalidAmount
97 }
98 if bps < 0 || bps > BpsDenominator {
99 return 0, ErrInvalidBps
100 }
101 return feeFor(amount, bps), nil
102}
103
104// feeFor computes floor(amount*bps/BpsDenominator) without intermediate
105// overflow: amount = q*BpsDenominator + r, so the fee is
106// q*bps + floor(r*bps/BpsDenominator). q*bps <= amount because
107// bps <= BpsDenominator, and r*bps < BpsDenominator^2 (10^8), so every
108// intermediate fits comfortably in int64. Inputs must be pre-validated.
109func feeFor(amount, bps int64) int64 {
110 q := amount / BpsDenominator
111 r := amount % BpsDenominator
112 return q*bps + r*bps/BpsDenominator
113}
114
115// Deposit credits account with amount minus the fee at feeBps, accruing
116// the fee to the fee pot. Returns the credited amount and the fee
117// (credited + fee == amount always). Fails with ErrEmptyAccount,
118// ErrInvalidAmount (amount <= 0), ErrInvalidBps (feeBps outside
119// [0, MaxFeeBps]), or ErrOverflow if the account balance or total
120// liabilities would leave int64 range. On error nothing is modified.
121func (l *Ledger) Deposit(account string, amount, feeBps int64) (credited, fee int64, err error) {
122 if account == "" {
123 return 0, 0, ErrEmptyAccount
124 }
125 if amount <= 0 {
126 return 0, 0, ErrInvalidAmount
127 }
128 if feeBps < 0 || feeBps > l.maxFeeBps {
129 return 0, 0, ErrInvalidBps
130 }
131
132 fee = feeFor(amount, feeBps)
133 credited = amount - fee // >= 0; > 0 whenever feeBps < BpsDenominator
134
135 newBalance, ok := checkedAdd(l.BalanceOf(account), credited)
136 if !ok {
137 return 0, 0, ErrOverflow
138 }
139 newUsersTotal, ok := checkedAdd(l.usersTotal, credited)
140 if !ok {
141 return 0, 0, ErrOverflow
142 }
143 newFeesAccrued, ok := checkedAdd(l.feesAccrued, fee)
144 if !ok {
145 return 0, 0, ErrOverflow
146 }
147 // Total liabilities must stay representable as one int64, since they
148 // mirror a single coin balance held by the importing realm.
149 if _, ok := checkedAdd(newUsersTotal, newFeesAccrued); !ok {
150 return 0, 0, ErrOverflow
151 }
152
153 if newBalance > 0 {
154 l.balances.Set(account, newBalance)
155 }
156 l.usersTotal = newUsersTotal
157 l.feesAccrued = newFeesAccrued
158 return credited, fee, nil
159}
160
161// MustDeposit is Deposit but panics on error.
162func (l *Ledger) MustDeposit(account string, amount, feeBps int64) (credited, fee int64) {
163 credited, fee, err := l.Deposit(account, amount, feeBps)
164 if err != nil {
165 panic(err)
166 }
167 return credited, fee
168}
169
170// Withdraw debits amount from account. Fails with ErrEmptyAccount,
171// ErrInvalidAmount (amount <= 0), or ErrInsufficient if the balance is
172// smaller than amount. A balance drained to zero is removed from
173// storage. On error nothing is modified.
174func (l *Ledger) Withdraw(account string, amount int64) error {
175 if account == "" {
176 return ErrEmptyAccount
177 }
178 if amount <= 0 {
179 return ErrInvalidAmount
180 }
181 balance := l.BalanceOf(account)
182 if balance < amount {
183 return ErrInsufficient
184 }
185 if balance == amount {
186 l.balances.Remove(account)
187 } else {
188 l.balances.Set(account, balance-amount)
189 }
190 // usersTotal >= balance >= amount by the sum invariant, so this
191 // cannot underflow.
192 l.usersTotal -= amount
193 return nil
194}
195
196// MustWithdraw is Withdraw but panics on error.
197func (l *Ledger) MustWithdraw(account string, amount int64) {
198 if err := l.Withdraw(account, amount); err != nil {
199 panic(err)
200 }
201}
202
203// WithdrawAll drains account's entire balance and returns it. Returns
204// (0, nil) if the account holds nothing. Fails only with
205// ErrEmptyAccount.
206func (l *Ledger) WithdrawAll(account string) (int64, error) {
207 if account == "" {
208 return 0, ErrEmptyAccount
209 }
210 balance := l.BalanceOf(account)
211 if balance == 0 {
212 return 0, nil
213 }
214 l.balances.Remove(account)
215 l.usersTotal -= balance
216 return balance, nil
217}
218
219// WithdrawFees drains the accrued fee pot and returns the amount
220// (0 if nothing has accrued). Never fails.
221func (l *Ledger) WithdrawFees() int64 {
222 fees := l.feesAccrued
223 l.feesAccrued = 0
224 return fees
225}
226
227// BalanceOf returns account's balance, or 0 if absent.
228func (l *Ledger) BalanceOf(account string) int64 {
229 v := l.balances.Get(account)
230 if v == nil {
231 return 0
232 }
233 return v.(int64)
234}
235
236// UsersTotal returns the sum of all account balances (user liabilities).
237func (l *Ledger) UsersTotal() int64 {
238 return l.usersTotal
239}
240
241// FeesAccrued returns the fee pot: charged but not yet withdrawn.
242func (l *Ledger) FeesAccrued() int64 {
243 return l.feesAccrued
244}
245
246// Liabilities returns UsersTotal() + FeesAccrued() — everything the
247// importing realm owes. Deposit guarantees this sum fits in int64.
248func (l *Ledger) Liabilities() int64 {
249 return l.usersTotal + l.feesAccrued
250}
251
252// Accounts returns the number of accounts with a non-zero balance.
253func (l *Ledger) Accounts() int {
254 return l.balances.Size()
255}
256
257// Iterate calls fn for each account in sorted order with its balance.
258// Iteration stops early when fn returns true.
259func (l *Ledger) Iterate(fn func(account string, balance int64) bool) {
260 l.balances.Iterate("", "", func(key string, value any) bool {
261 return fn(key, value.(int64))
262 })
263}
264
265// checkedAdd returns a+b and reports whether the addition did not
266// overflow int64.
267func checkedAdd(a, b int64) (int64, bool) {
268 sum := a + b
269 if (b > 0 && sum < a) || (b < 0 && sum > a) {
270 return 0, false
271 }
272 return sum, true
273}
