reaper.gno
9.36 Kb · 257 lines
1// Package reaper is a noticeboard whose garbage is a standing bounty.
2//
3// Anyone can post a note with an expiry. Posting locks a storage deposit, paid
4// by the poster. Once a note expires, anyone at all can delete it, and the
5// chain refunds that deposit to whoever signed the deleting transaction. So
6// the poster pays to occupy space and a stranger is paid to reclaim it.
7//
8// Nothing here is a token, a reward pool or an emission schedule. The incentive
9// is the chain's own storage accounting, which already works this way for every
10// realm on gno.land; this realm only makes it legible. Reap and Compact are
11// permissionless because the expiry predicate is checked on chain, so the
12// worst a malicious reaper can do is waste their own gas.
13//
14// Two collaborators own the parts this realm does not:
15//
16// - gno.land/p/moul/ulist/v1 stores the notes and owns compaction. Its
17// Delete is a soft delete that leaves a dead tree node behind, and its
18// Compact frees those nodes without moving any live index.
19// - gno.land/p/moul/x/storagecost/v0 owns the arithmetic: what a byte
20// refunds, and how many bytes a transaction must free to pay for itself.
21//
22// The realm deliberately cannot see its own byte count. No stdlib call exposes
23// a realm's locked storage, so every figure Render shows is an estimate from
24// payload length. The authoritative numbers are the chain's, in the
25// StorageDepositEvent and StorageUnlockEvent each transaction emits.
26package reaper
27
28import (
29 "strings"
30
31 "chain/runtime"
32
33 "gno.land/p/moul/md/v0"
34 "gno.land/p/moul/txlink/v0"
35 "gno.land/p/moul/ulist/v1"
36 "gno.land/p/moul/x/storagecost/v0"
37 "gno.land/p/nt/ufmt/v0"
38)
39
40// gasWantedReap is the gas ceiling a reaping transaction is assumed to ask
41// for, used only to price the advertised bounty. It is the measured cost of a
42// ten-note reap rounded up; a caller reaping more notes should re-price with
43// storagecost.EvaluateAtFloor directly rather than trust this.
44const gasWantedReap int64 = 5_000_000
45
46// maxBody caps a note so one poster cannot lock an unbounded deposit in a
47// single call, which would also make the gas cost of reaping it unpredictable.
48const maxBody = 4096
49
50// Note is one posting. Body is what costs storage; the rest is bookkeeping
51// that makes the incentive visible in Render.
52type Note struct {
53 Body string
54 Author address
55 Posted int64 // block height
56 Expires int64 // block height; reapable once ChainHeight passes it
57}
58
59// notes is append-addressed: an index is stable for the life of the realm,
60// which is what lets Compact reclaim dead nodes without renumbering.
61var notes = ulist.New()
62
63// Post adds a note that becomes reapable ttl blocks from now, and locks the
64// storage deposit for it against the caller.
65//
66// A ttl of zero is allowed and makes the note reapable immediately, which is
67// the cheapest way to demonstrate the mechanism.
68func Post(cur realm, body string, ttl int64) int {
69 if body == "" {
70 panic("reaper: empty note")
71 }
72 if len(body) > maxBody {
73 panic(ufmt.Sprintf("reaper: note too long, %d bytes against a %d cap", len(body), maxBody))
74 }
75 if ttl < 0 {
76 panic("reaper: negative ttl")
77 }
78 height := runtime.ChainHeight()
79 notes.Append(&Note{
80 Body: body,
81 Author: cur.Previous().Address(),
82 Posted: height,
83 Expires: height + ttl,
84 })
85 return notes.TotalSize() - 1
86}
87
88// Reap deletes up to limit expired notes and returns how many it deleted.
89//
90// Permissionless by design. The storage deposit freed goes to whoever signed
91// this transaction, so a stranger keeping the board tidy is paid for it out of
92// the deposits the posters locked. A note that has not expired is skipped, not
93// refused, so a reaper never has to guess which indices are ripe.
94//
95// It walks from the highest index down, which is not cosmetic. In the backing
96// list the oldest indices are the ancestors of the newest, so a node can only
97// be freed once everything below it is dead. Reaping oldest-first with a
98// binding limit therefore never creates a dead tail and leaves Compactable at
99// zero, stranding the tree structure, which measures at roughly two thirds of
100// what an entry costs. Reaping newest-first makes each batch immediately
101// compactable. Every candidate is expired either way, so the order changes
102// only who gets paid how much, and it is measured: see the ulist package doc.
103func Reap(cur realm, limit int) int {
104 if limit <= 0 {
105 panic("reaper: limit must be positive")
106 }
107 height := runtime.ChainHeight()
108 reaped := 0
109 for i := notes.TotalSize() - 1; i >= 0 && reaped < limit; i-- {
110 n, ok := noteAt(i)
111 if !ok || n.Expires > height {
112 continue
113 }
114 notes.MustDelete(i)
115 reaped++
116 }
117 return reaped
118}
119
120// Compact frees the tree nodes that reaping left behind and returns how many.
121//
122// Also permissionless, and also paid the same way. It is a separate call
123// because it is a separate economic decision, and a surprisingly large one: on
124// chain, compacting a drained board returned about three times what deleting
125// the notes themselves did, because a list node costs more than the note it
126// carries. But it returns nothing at all while any live note sits below the
127// dead ones, so the two calls are worth batching in that order: reap, then
128// compact. Compactable says how much is actually there, for free.
129func Compact(cur realm) int {
130 return notes.Compact()
131}
132
133// Reapable counts the notes that have expired and not yet been reaped.
134func Reapable() int {
135 height := runtime.ChainHeight()
136 count := 0
137 total := notes.TotalSize()
138 for i := 0; i < total; i++ {
139 n, ok := noteAt(i)
140 if ok && n.Expires <= height {
141 count++
142 }
143 }
144 return count
145}
146
147// Compactable reports how many dead tree nodes a Compact would free.
148func Compactable() int { return notes.Compactable() }
149
150// Live counts the notes still holding storage.
151func Live() int { return notes.Size() }
152
153// Bounty prices what is currently on the table for a reaper, at the default
154// storage price and the floor gas price.
155//
156// The byte figure is an estimate from payload length, never the chain's own
157// accounting. Treat it as an advertisement, not a settlement.
158func Bounty() storagecost.Quote {
159 height := runtime.ChainHeight()
160 var payload int64
161 total := notes.TotalSize()
162 for i := 0; i < total; i++ {
163 n, ok := noteAt(i)
164 if ok && n.Expires <= height {
165 payload += int64(len(n.Body))
166 }
167 }
168 return storagecost.EvaluateAtFloor(storagecost.EstimateBytes(payload), gasWantedReap)
169}
170
171// noteAt reads index i, reporting whether a live note is there. A reaped or
172// compacted index reads as absent.
173func noteAt(i int) (*Note, bool) {
174 v := notes.Get(i)
175 if v == nil {
176 return nil, false
177 }
178 n, ok := v.(*Note)
179 return n, ok
180}
181
182func Render(path string) string {
183 var b strings.Builder
184
185 b.WriteString(md.H1("Reaper"))
186 b.WriteString("\nA noticeboard whose garbage is a standing bounty. Posting a note locks a storage deposit. Once the note expires, anyone can delete it and the chain refunds that deposit **to whoever signs the deleting transaction**.\n\n")
187
188 quote := Bounty()
189 b.WriteString(md.H2("On the table right now"))
190 b.WriteString("\n")
191
192 reapable := Reapable()
193 if reapable == 0 {
194 b.WriteString("Nothing has expired. Every note here is still paid for.\n\n")
195 } else {
196 b.WriteString(md.BulletList([]string{
197 ufmt.Sprintf("**%d expired notes**, about %d bytes of state", reapable, quote.Bytes),
198 ufmt.Sprintf("refunds roughly **%s** to the reaper", storagecost.FormatGNOT(quote.Refund)),
199 ufmt.Sprintf("against **%s** of gas at the floor price, break-even at %d bytes", storagecost.FormatGNOT(quote.Fee), quote.BreakEven),
200 ufmt.Sprintf("verdict: **%s**", verdictWord(quote)),
201 }))
202 b.WriteString("\n")
203 b.WriteString(ufmt.Sprintf("[Reap them](%s)\n\n", txlink.Call("Reap", "limit", "100")))
204 }
205
206 if dead := Compactable(); dead > 0 {
207 b.WriteString(md.H2("Compaction available"))
208 b.WriteString(ufmt.Sprintf("\n%d dead tree nodes are reclaimable. Compacting frees fewer bytes per unit of gas than reaping does, so it is worth doing in batches.\n\n[Compact](%s)\n\n",
209 dead, txlink.Call("Compact")))
210 }
211
212 b.WriteString(md.H2("Board"))
213 b.WriteString("\n")
214 if notes.Size() == 0 {
215 b.WriteString("Empty. [Post the first note](" + txlink.Call("Post", "body", "hello", "ttl", "0") + ")\n\n")
216 } else {
217 height := runtime.ChainHeight()
218 rows := []string{}
219 total := notes.TotalSize()
220 for i := 0; i < total; i++ {
221 n, ok := noteAt(i)
222 if !ok {
223 continue
224 }
225 state := ufmt.Sprintf("expires at %d", n.Expires)
226 if n.Expires <= height {
227 state = "**reapable**"
228 }
229 rows = append(rows, ufmt.Sprintf("`#%d` %s | %d bytes by %s, %s",
230 i, summarize(n.Body), len(n.Body), n.Author.String(), state))
231 }
232 b.WriteString(md.BulletList(rows))
233 b.WriteString("\n")
234 }
235
236 b.WriteString(md.HorizontalRule())
237 b.WriteString("\nThe arithmetic is [p/moul/x/storagecost](/p/moul/x/storagecost/v0); the storage is [p/moul/ulist](/p/moul/ulist/v1), whose `Compact` reclaims dead nodes without moving a live index. Byte figures on this page are estimates from payload length: no stdlib call exposes a realm's real locked storage.\n")
238
239 return b.String()
240}
241
242func verdictWord(q storagecost.Quote) string {
243 if q.Worth() {
244 return "worth " + storagecost.FormatGNOT(q.Net)
245 }
246 return "not worth the gas yet"
247}
248
249// summarize keeps the board readable when a note is long.
250func summarize(body string) string {
251 const width = 48
252 oneLine := strings.ReplaceAll(strings.ReplaceAll(body, "\n", " "), "|", " ")
253 if len(oneLine) <= width {
254 return oneLine
255 }
256 return oneLine[:width] + "..."
257}
