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