curated.gno
19.26 Kb · 604 lines
1// Package curated is the engine behind a curated list where being on the list
2// costs something: anyone may list an entry by locking a deposit, anyone may
3// challenge an entry by matching that deposit with a bond, and the loser of the
4// challenge pays the winner.
5//
6// # Why a deposit
7//
8// A list anybody can write to for free is a list nobody can read, because the
9// cheapest way to be on it is to be on it a thousand times. A deposit does not
10// make an entry good; it makes a bad entry expensive to leave standing, because
11// somebody who disagrees can put the same amount at risk and take yours. The
12// list is worth reading in proportion to what it would cost to pollute it.
13//
14// # The model
15//
16// Registry every entry, plus the credit ledger the payouts land in
17// Entry a key, a URL, a description, an owner, the deposit, the height
18// it was listed at, and one of three states
19// Challenge a challenger, a matching bond, a deadline, and the votes
20//
21// A key is unique while it is on the list ([ValidKey] bounds it to a
22// slug), and a removed key is free again: a challenge that wins removes an
23// entry, it does not burn the name forever.
24//
25// # The money, and why nothing is ever sent from here
26//
27// This package moves no coins. Every payout is a credit in an internal ledger
28// that the payee collects with [Registry.Withdraw], which is the pull-payment
29// shape: a realm that loops over winners and sends to each one fails entirely
30// when one of them cannot be paid, and hands a griefer a cheap denial of
31// service. [Registry.Locked] plus [Registry.Owed] is what the holding realm
32// must have at its address, and a realm can assert exactly that.
33//
34// # Voting is sybil-prone, deliberately and visibly
35//
36// [Registry.Vote] is one address, one vote, unweighted. An address is free, so
37// a challenge outcome is a poll of whoever bothered to make keys, not of
38// anybody in particular. That is not a gap this package can close: deciding who
39// counts as a person is a different problem with a different realm behind it,
40// r/moul/x/social/vouch, a sibling in this family. Until a vote is
41// gated on a vouched identity, read a resolution as "nobody with a stake
42// objected enough", not as a verdict.
43//
44// # What v0 does not do, in the order it should be fixed
45//
46// 1. Voters are paid nothing. Voting costs gas and returns nothing, so the
47// only addresses with a reason to vote are the two with money on the
48// outcome. A share of the loser's stake for the winning side is the
49// standard answer and it is the first thing to add.
50// 2. There is no application period: [Registry.Apply] lists immediately, so a
51// bad entry is visible until somebody challenges it.
52// 3. A challenge cannot be withdrawn, and a vote cannot be changed.
53package curated
54
55import (
56 "chain/markdown"
57 "errors"
58 "strings"
59)
60
61const (
62 // MaxKeyLen is the longest key accepted. A key is a name people type and
63 // link to, not a payload.
64 MaxKeyLen = 64
65
66 // MaxURLLen and MaxDescLen bound what one entry can lock up of somebody
67 // else's storage deposit.
68 MaxURLLen = 240
69 MaxDescLen = 240
70
71 // MaxEntries bounds the registry so a listing stays predictable in gas.
72 MaxEntries = 4096
73
74 // MaxPayees bounds the credit ledger for the same reason.
75 MaxPayees = 4096
76)
77
78const maxInt64 = int64(9223372036854775807)
79
80// The errors a caller can get back. A p/ returns them; the realm decides to
81// abort.
82var (
83 ErrBadKey = errors.New("curated: not a key: 1 to 64 bytes of a-z 0-9 - _ . starting alphanumeric")
84 ErrBadURL = errors.New("curated: url is empty, too long, or has a space or a control character")
85 ErrBadDescription = errors.New("curated: description is empty, too long, or not a single line")
86 ErrTaken = errors.New("curated: that key is already on the list")
87 ErrNoEntry = errors.New("curated: no such entry")
88 ErrWrongDeposit = errors.New("curated: the deposit must be paid exactly")
89 ErrWrongBond = errors.New("curated: the bond must match the entry's deposit")
90 ErrChallenged = errors.New("curated: that entry is under challenge")
91 ErrSelfChallenge = errors.New("curated: an owner cannot challenge their own entry")
92 ErrNoChallenge = errors.New("curated: that entry is not under challenge")
93 ErrVotingClosed = errors.New("curated: the challenge deadline has passed")
94 ErrAlreadyVoted = errors.New("curated: one address, one vote")
95 ErrTooEarly = errors.New("curated: the challenge is still open")
96 ErrNotOwner = errors.New("curated: only the entry's owner can do that")
97 ErrNothingOwed = errors.New("curated: nothing to withdraw")
98 ErrFull = errors.New("curated: the registry is full")
99 ErrOverflow = errors.New("curated: the credit would overflow")
100 ErrBadAmount = errors.New("curated: amount must be positive")
101)
102
103// State is where an entry stands.
104type State uint8
105
106const (
107 // StateListed is on the list and unchallenged.
108 StateListed State = iota
109
110 // StateChallenged is on the list with a challenge open against it. It
111 // still renders: a challenge is an objection, not a verdict.
112 StateChallenged
113
114 // StateRemoved is off the list, either lost to a challenge or taken down
115 // by its own owner. The key is free for anyone to apply for again.
116 StateRemoved
117)
118
119// String names the state for a reader and for an event.
120func (s State) String() string {
121 switch s {
122 case StateListed:
123 return "listed"
124 case StateChallenged:
125 return "challenged"
126 case StateRemoved:
127 return "removed"
128 default:
129 return "unknown"
130 }
131}
132
133// Challenge is an open objection to one entry.
134type Challenge struct {
135 Challenger address
136 Bond int64
137 Deadline int64 // block height the voting stops at, exclusive
138
139 // Keep and Remove are the unweighted vote counts. See the package doc on
140 // what they are and are not worth.
141 Keep int64
142 Remove int64
143
144 // voters is the set of addresses that have voted, so one address votes
145 // once. It is unexported: a caller reads [Challenge.Voters].
146 voters map[string]bool
147}
148
149// Voters is how many distinct addresses have voted.
150func (c *Challenge) Voters() int {
151 if c == nil {
152 return 0
153 }
154 return len(c.voters)
155}
156
157// HasVoted reports whether who has already voted in this challenge.
158func (c *Challenge) HasVoted(who address) bool {
159 if c == nil {
160 return false
161 }
162 return c.voters[who.String()]
163}
164
165// Open reports whether votes are still being taken at height now.
166func (c *Challenge) Open(now int64) bool { return c != nil && now < c.Deadline }
167
168// Entry is one row of the list.
169type Entry struct {
170 Key string
171 URL string
172 Description string
173 Owner address
174 Deposit int64 // what the owner locked to list it
175 At int64 // the block height it was listed at
176 State State
177
178 // challenge is the open objection, or nil. It is cleared on resolution:
179 // the outcome is in the entry's state and in the ledger, and keeping a
180 // resolved challenge would be a second place to read it from.
181 challenge *Challenge
182}
183
184// Live reports whether the entry is on the list, challenged or not.
185func (e *Entry) Live() bool { return e != nil && e.State != StateRemoved }
186
187// Registry is the whole list: the entries, and the credits waiting to be
188// withdrawn.
189type Registry struct {
190 deposit int64
191 challengeBlocks int64
192
193 entries map[string]*Entry
194 order []string // keys in the order they were first listed
195
196 credits map[string]int64
197 owed int64
198 locked int64
199}
200
201// New returns an empty registry where listing costs deposit and a challenge
202// runs for challengeBlocks blocks.
203//
204// Both are fixed for the life of the registry. An entry remembers the deposit
205// it actually paid, so a future registry that can reprice itself still charges
206// a challenger what the owner of that entry risked, and not today's number.
207func New(deposit, challengeBlocks int64) *Registry {
208 return &Registry{
209 deposit: deposit,
210 challengeBlocks: challengeBlocks,
211 entries: map[string]*Entry{},
212 credits: map[string]int64{},
213 }
214}
215
216// Deposit is what listing costs.
217func (r *Registry) Deposit() int64 { return r.deposit }
218
219// ChallengeBlocks is how long a challenge takes to resolve.
220func (r *Registry) ChallengeBlocks() int64 { return r.challengeBlocks }
221
222// Apply lists an entry immediately, in exchange for exactly the deposit.
223//
224// There is no application period in v0: the entry is on the list the moment the
225// deposit is paid, and the check on it is that anybody can challenge it.
226//
227// A key whose entry was removed is free again, and applying for it writes a
228// fresh entry in the same position in the listing order.
229func (r *Registry) Apply(key, url, description string, owner address, paid, now int64) error {
230 if !ValidKey(key) {
231 return ErrBadKey
232 }
233 if !ValidURL(url) {
234 return ErrBadURL
235 }
236 if !ValidDescription(description) {
237 return ErrBadDescription
238 }
239 if paid != r.deposit {
240 return ErrWrongDeposit
241 }
242 old, seen := r.entries[key]
243 if seen && old.Live() {
244 return ErrTaken
245 }
246 if !seen {
247 if len(r.order) >= MaxEntries {
248 return ErrFull
249 }
250 r.order = append(r.order, key)
251 }
252 r.entries[key] = &Entry{
253 Key: key,
254 URL: url,
255 Description: description,
256 Owner: owner,
257 Deposit: paid,
258 At: now,
259 State: StateListed,
260 }
261 r.locked += paid
262 return nil
263}
264
265// BondFor is what challenging key would cost, and whether it can be challenged
266// at all.
267//
268// The realm reads this BEFORE it reads the envelope, so a caller who attaches
269// coins to a challenge of something unchallengeable is refused on the entry and
270// not on the amount.
271func (r *Registry) BondFor(key string) (int64, bool) {
272 e, ok := r.entries[key]
273 if !ok || e.State != StateListed {
274 return 0, false
275 }
276 return e.Deposit, true
277}
278
279// Challenge opens an objection to an entry, against a bond equal to that
280// entry's deposit, and sets the deadline at now + ChallengeBlocks.
281//
282// An owner may not challenge their own entry. It would cost nothing (a kept
283// entry credits its owner the bond, which here is their own) and it would make
284// the entry immune to a real challenge for the whole window.
285func (r *Registry) Challenge(key string, challenger address, bond, now int64) error {
286 e, ok := r.entries[key]
287 if !ok || !e.Live() {
288 return ErrNoEntry
289 }
290 if e.State == StateChallenged {
291 return ErrChallenged
292 }
293 if challenger == e.Owner {
294 return ErrSelfChallenge
295 }
296 if bond != e.Deposit {
297 return ErrWrongBond
298 }
299 e.State = StateChallenged
300 e.challenge = &Challenge{
301 Challenger: challenger,
302 Bond: bond,
303 Deadline: now + r.challengeBlocks,
304 voters: map[string]bool{},
305 }
306 r.locked += bond
307 return nil
308}
309
310// Vote records one address's opinion on an open challenge: keep the entry, or
311// remove it.
312//
313// One address, one vote, unweighted, and it cannot be changed. Anyone may vote,
314// including the owner and the challenger, because excluding them would only
315// move their vote to another address they control. See the package doc: this is
316// sybil-prone on purpose rather than by oversight, and gating it is the job of
317// the vouch realm.
318func (r *Registry) Vote(key string, voter address, keep bool, now int64) error {
319 e, ok := r.entries[key]
320 if !ok {
321 return ErrNoEntry
322 }
323 c := e.challenge
324 if e.State != StateChallenged || c == nil {
325 return ErrNoChallenge
326 }
327 if !c.Open(now) {
328 return ErrVotingClosed
329 }
330 k := voter.String()
331 if c.voters[k] {
332 return ErrAlreadyVoted
333 }
334 c.voters[k] = true
335 if keep {
336 c.Keep++
337 } else {
338 c.Remove++
339 }
340 return nil
341}
342
343// Outcome is what a resolution decided and who it paid.
344type Outcome struct {
345 Key string
346 Kept bool
347 Winner address
348 Amount int64 // credited to the winner
349 Keep int64
350 Remove int64
351}
352
353// Resolve closes a challenge whose deadline has passed. Anyone may call it: the
354// two parties both have a reason to and neither can stall the other.
355//
356// A majority of keep votes keeps the entry and credits its owner the
357// challenger's bond. Otherwise the entry is removed and the challenger is
358// credited the bond plus the deposit.
359//
360// A TIE KEEPS THE ENTRY, including the tie of nobody voting at all. The
361// incumbent paid first and is already at risk, so the burden is on the
362// challenger to produce a reason; if ties went the other way, a challenge that
363// convinced nobody would still win, and listing anything would be pointless.
364// The cost of that choice is the one a challenger signs up for: being wrong
365// costs the bond.
366func (r *Registry) Resolve(key string, now int64) (Outcome, error) {
367 e, ok := r.entries[key]
368 if !ok {
369 return Outcome{}, ErrNoEntry
370 }
371 c := e.challenge
372 if e.State != StateChallenged || c == nil {
373 return Outcome{}, ErrNoChallenge
374 }
375 if c.Open(now) {
376 return Outcome{}, ErrTooEarly
377 }
378
379 out := Outcome{Key: key, Kept: c.Keep >= c.Remove, Keep: c.Keep, Remove: c.Remove}
380 if out.Kept {
381 out.Winner, out.Amount = e.Owner, c.Bond
382 } else {
383 out.Winner, out.Amount = c.Challenger, c.Bond+e.Deposit
384 }
385
386 // Credit first: it is the only step that can fail, and a half-applied
387 // resolution would leave an entry with no challenge and nobody paid.
388 if err := r.credit(out.Winner, out.Amount); err != nil {
389 return Outcome{}, err
390 }
391 if out.Kept {
392 e.State = StateListed
393 r.locked -= c.Bond
394 } else {
395 e.State = StateRemoved
396 r.locked -= c.Bond + e.Deposit
397 }
398 e.challenge = nil
399 return out, nil
400}
401
402// Unlist takes an owner's own entry down and credits them the deposit back.
403//
404// It is refused while a challenge is open, which is the whole point of the
405// bond: an owner who could walk away mid-challenge would be risking nothing.
406func (r *Registry) Unlist(key string, owner address) error {
407 e, ok := r.entries[key]
408 if !ok || !e.Live() {
409 return ErrNoEntry
410 }
411 if e.Owner != owner {
412 return ErrNotOwner
413 }
414 if e.State == StateChallenged {
415 return ErrChallenged
416 }
417 if err := r.credit(owner, e.Deposit); err != nil {
418 return err
419 }
420 e.State = StateRemoved
421 r.locked -= e.Deposit
422 return nil
423}
424
425// Withdraw zeroes who's credit and returns what they were owed.
426//
427// The holding realm sends the coins AFTER this returns. That ordering is the
428// pattern: the credit is already gone from the ledger when control passes to
429// the recipient, so a reentrant withdrawal finds ErrNothingOwed.
430func (r *Registry) Withdraw(who address) (int64, error) {
431 k := who.String()
432 amount := r.credits[k]
433 if amount <= 0 {
434 return 0, ErrNothingOwed
435 }
436 delete(r.credits, k) // effects before interactions
437 r.owed -= amount
438 return amount, nil
439}
440
441// credit records that who is owed amount more.
442func (r *Registry) credit(who address, amount int64) error {
443 if amount <= 0 {
444 return ErrBadAmount
445 }
446 k := who.String()
447 have, seen := r.credits[k]
448 if !seen && len(r.credits) >= MaxPayees {
449 return ErrFull
450 }
451 if have > maxInt64-amount || r.owed > maxInt64-amount {
452 return ErrOverflow
453 }
454 r.credits[k] = have + amount
455 r.owed += amount
456 return nil
457}
458
459// Get returns an entry by key, whatever its state, and whether it ever existed.
460func (r *Registry) Get(key string) (*Entry, bool) {
461 e, ok := r.entries[key]
462 return e, ok
463}
464
465// IsListed reports whether key is on the list right now. A challenged entry is
466// still listed.
467func (r *Registry) IsListed(key string) bool {
468 e, ok := r.entries[key]
469 return ok && e.Live()
470}
471
472// Count is how many entries are on the list right now.
473func (r *Registry) Count() int {
474 n := 0
475 for _, key := range r.order {
476 if r.entries[key].Live() {
477 n++
478 }
479 }
480 return n
481}
482
483// Records is how many keys the registry has ever held, removed ones included.
484func (r *Registry) Records() int { return len(r.order) }
485
486// Listed returns every entry on the list, oldest first.
487//
488// The order comes from a slice and not from iterating the map, so it is a
489// stable sequence a Render can be pinned against rather than an insertion order
490// that a delete-and-re-add would reshuffle.
491func (r *Registry) Listed() []*Entry {
492 out := []*Entry{}
493 for _, key := range r.order {
494 if e := r.entries[key]; e.Live() {
495 out = append(out, e)
496 }
497 }
498 return out
499}
500
501// Challenged returns every entry with a challenge open against it, oldest
502// listing first.
503func (r *Registry) Challenged() []*Entry {
504 out := []*Entry{}
505 for _, key := range r.order {
506 if e := r.entries[key]; e.State == StateChallenged {
507 out = append(out, e)
508 }
509 }
510 return out
511}
512
513// ChallengeOf returns the open challenge against key, if there is one.
514func (r *Registry) ChallengeOf(key string) (*Challenge, bool) {
515 e, ok := r.entries[key]
516 if !ok || e.challenge == nil {
517 return nil, false
518 }
519 return e.challenge, true
520}
521
522// CreditOf is what who can withdraw right now.
523func (r *Registry) CreditOf(who address) int64 { return r.credits[who.String()] }
524
525// Owed is every credit not yet withdrawn.
526func (r *Registry) Owed() int64 { return r.owed }
527
528// Locked is the deposits behind live entries plus the bonds behind open
529// challenges.
530//
531// Locked plus [Registry.Owed] is what the holding realm must have at its
532// address: every ugnot it ever took is either still backing something or
533// already assigned to somebody. A realm can assert that equality against its
534// own balance, and this package's tests do.
535func (r *Registry) Locked() int64 { return r.locked }
536
537// ValidKey reports whether key is usable: 1 to [MaxKeyLen] bytes of lowercase
538// ASCII letters, digits, '-', '_' and '.', starting with a letter or a digit.
539//
540// The leading-alphanumeric rule is what stops "." and "..", and what stops a
541// key that reads as punctuation in the list it is shown in. The charset is
542// narrow so a key can be typed, linked and compared without surprises; it is
543// still escaped at render time, because a validator and an escaper protect
544// against different mistakes.
545func ValidKey(key string) bool {
546 if key == "" || len(key) > MaxKeyLen {
547 return false
548 }
549 if c := key[0]; !(c >= 'a' && c <= 'z' || c >= '0' && c <= '9') {
550 return false
551 }
552 for i := 0; i < len(key); i++ {
553 c := key[i]
554 switch {
555 case c >= 'a' && c <= 'z', c >= '0' && c <= '9':
556 case c == '-' || c == '_' || c == '.':
557 default:
558 return false
559 }
560 }
561 return true
562}
563
564// ValidURL reports whether url can be stored: non-empty after the render's own
565// stripping and trimming, within [MaxURLLen],
566// and free of spaces and control characters.
567//
568// No scheme is required, because a list of on-chain things is the obvious use
569// and those have no host. A renderer treats a schemeless URL as a path
570// relative to the chain's web root, so an on-chain target is written
571// "/r/moul/home" and an off-chain one carries its own "https://".
572//
573// Nothing here checks that the target exists: a deposit backs the claim that
574// the entry is worth listing, not the claim that it resolves.
575func ValidURL(url string) bool {
576 if strings.TrimSpace(markdown.StripBidiAndZeroWidth(url)) == "" || len(url) > MaxURLLen {
577 return false
578 }
579 for i := 0; i < len(url); i++ {
580 if c := url[i]; c <= 0x20 || c == 0x7f {
581 return false
582 }
583 }
584 return true
585}
586
587// ValidDescription reports whether description can be stored: non-empty after
588// the render's own stripping and trimming, within [MaxDescLen], and a single line.
589//
590// Newlines and tabs are refused rather than stripped, because a description is
591// shown back to the person who wrote it and silently rewriting it is worse than
592// telling them it was refused. It lives in a table cell, which a newline would
593// break out of and an escaper would then have to repair.
594func ValidDescription(description string) bool {
595 if len(description) > MaxDescLen || strings.TrimSpace(markdown.StripBidiAndZeroWidth(description)) == "" {
596 return false
597 }
598 for i := 0; i < len(description); i++ {
599 if c := description[i]; c < 0x20 || c == 0x7f {
600 return false
601 }
602 }
603 return true
604}
