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