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