1// Package curated is the engine behind a curated list where being on the list2// costs something: anyone may list an entry by locking a deposit, anyone may3// challenge an entry by matching that deposit with a bond, and the loser of the4// challenge pays the winner.5//6// # Why a deposit7//8// A list anybody can write to for free is a list nobody can read, because the9// cheapest way to be on it is to be on it a thousand times. A deposit does not10// make an entry good; it makes a bad entry expensive to leave standing, because11// somebody who disagrees can put the same amount at risk and take yours. The12// list is worth reading in proportion to what it would cost to pollute it.13//14// # The model15//16// Registry every entry, plus the credit ledger the payouts land in17// Entry a key, a URL, a description, an owner, the deposit, the height18// it was listed at, and one of three states19// Challenge a challenger, a matching bond, a deadline, and the votes20//21// A key is unique while it is on the list ([ValidKey] bounds it to a22// slug), and a removed key is free again: a challenge that wins removes an23// entry, it does not burn the name forever.24//25// # The money, and why nothing is ever sent from here26//27// This package moves no coins. Every payout is a credit in an internal ledger28// that the payee collects with [Registry.Withdraw], which is the pull-payment29// shape: a realm that loops over winners and sends to each one fails entirely30// when one of them cannot be paid, and hands a griefer a cheap denial of31// service. [Registry.Locked] plus [Registry.Owed] is what the holding realm32// must have at its address, and a realm can assert exactly that.33//34// # Voting is sybil-prone, deliberately and visibly35//36// [Registry.Vote] is one address, one vote, unweighted. An address is free, so37// a challenge outcome is a poll of whoever bothered to make keys, not of38// anybody in particular. That is not a gap this package can close: deciding who39// 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 is41// gated on a vouched identity, read a resolution as "nobody with a stake42// objected enough", not as a verdict.43//44// # What v0 does not do, in the order it should be fixed45//46// 1. Voters are paid nothing. Voting costs gas and returns nothing, so the47// only addresses with a reason to vote are the two with money on the48// outcome. A share of the loser's stake for the winning side is the49// standard answer and it is the first thing to add.50// 2. There is no application period: [Registry.Apply] lists immediately, so a51// bad entry is visible until somebody challenges it.52// 3. A challenge cannot be withdrawn, and a vote cannot be changed.53package curated5455import (56 "errors"57 "strings"58)5960const (61 // MaxKeyLen is the longest key accepted. A key is a name people type and62 // link to, not a payload.63 MaxKeyLen = 646465 // MaxURLLen and MaxDescLen bound what one entry can lock up of somebody66 // else's storage deposit.67 MaxURLLen = 24068 MaxDescLen = 2406970 // MaxEntries bounds the registry so a listing stays predictable in gas.71 MaxEntries = 40967273 // MaxPayees bounds the credit ledger for the same reason.74 MaxPayees = 409675)7677const maxInt64 = int64(9223372036854775807)7879// The errors a caller can get back. A p/ returns them; the realm decides to80// 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)101102// State is where an entry stands.103type State uint8104105const (106 // StateListed is on the list and unchallenged.107 StateListed State = iota108109 // StateChallenged is on the list with a challenge open against it. It110 // still renders: a challenge is an objection, not a verdict.111 StateChallenged112113 // StateRemoved is off the list, either lost to a challenge or taken down114 // by its own owner. The key is free for anyone to apply for again.115 StateRemoved116)117118// 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}131132// Challenge is an open objection to one entry.133type Challenge struct {134 Challenger address135 Bond int64136 Deadline int64 // block height the voting stops at, exclusive137138 // Keep and Remove are the unweighted vote counts. See the package doc on139 // what they are and are not worth.140 Keep int64141 Remove int64142143 // voters is the set of addresses that have voted, so one address votes144 // once. It is unexported: a caller reads [Challenge.Voters].145 voters map[string]bool146}147148// Voters is how many distinct addresses have voted.149func (c *Challenge) Voters() int {150 if c == nil {151 return 0152 }153 return len(c.voters)154}155156// HasVoted reports whether who has already voted in this challenge.157func (c *Challenge) HasVoted(who address) bool {158 if c == nil {159 return false160 }161 return c.voters[who.String()]162}163164// Open reports whether votes are still being taken at height now.165func (c *Challenge) Open(now int64) bool { return c != nil && now < c.Deadline }166167// Entry is one row of the list.168type Entry struct {169 Key string170 URL string171 Description string172 Owner address173 Deposit int64 // what the owner locked to list it174 At int64 // the block height it was listed at175 State State176177 // 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 a179 // resolved challenge would be a second place to read it from.180 challenge *Challenge181}182183// Live reports whether the entry is on the list, challenged or not.184func (e *Entry) Live() bool { return e != nil && e.State != StateRemoved }185186// Registry is the whole list: the entries, and the credits waiting to be187// withdrawn.188type Registry struct {189 deposit int64190 challengeBlocks int64191192 entries map[string]*Entry193 order []string // keys in the order they were first listed194195 credits map[string]int64196 owed int64197 locked int64198}199200// New returns an empty registry where listing costs deposit and a challenge201// runs for challengeBlocks blocks.202//203// Both are fixed for the life of the registry. An entry remembers the deposit204// it actually paid, so a future registry that can reprice itself still charges205// 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}214215// Deposit is what listing costs.216func (r *Registry) Deposit() int64 { return r.deposit }217218// ChallengeBlocks is how long a challenge takes to resolve.219func (r *Registry) ChallengeBlocks() int64 { return r.challengeBlocks }220221// 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 the224// 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 a227// 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 ErrBadKey231 }232 if !ValidURL(url) {233 return ErrBadURL234 }235 if !ValidDescription(description) {236 return ErrBadDescription237 }238 if paid != r.deposit {239 return ErrWrongDeposit240 }241 old, seen := r.entries[key]242 if seen && old.Live() {243 return ErrTaken244 }245 if !seen {246 if len(r.order) >= MaxEntries {247 return ErrFull248 }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 += paid261 return nil262}263264// BondFor is what challenging key would cost, and whether it can be challenged265// at all.266//267// The realm reads this BEFORE it reads the envelope, so a caller who attaches268// coins to a challenge of something unchallengeable is refused on the entry and269// 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, false274 }275 return e.Deposit, true276}277278// Challenge opens an objection to an entry, against a bond equal to that279// 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 kept282// entry credits its owner the bond, which here is their own) and it would make283// 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 ErrNoEntry288 }289 if e.State == StateChallenged {290 return ErrChallenged291 }292 if challenger == e.Owner {293 return ErrSelfChallenge294 }295 if bond != e.Deposit {296 return ErrWrongBond297 }298 e.State = StateChallenged299 e.challenge = &Challenge{300 Challenger: challenger,301 Bond: bond,302 Deadline: now + r.challengeBlocks,303 voters: map[string]bool{},304 }305 r.locked += bond306 return nil307}308309// Vote records one address's opinion on an open challenge: keep the entry, or310// 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 only314// move their vote to another address they control. See the package doc: this is315// sybil-prone on purpose rather than by oversight, and gating it is the job of316// 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 ErrNoEntry321 }322 c := e.challenge323 if e.State != StateChallenged || c == nil {324 return ErrNoChallenge325 }326 if !c.Open(now) {327 return ErrVotingClosed328 }329 k := voter.String()330 if c.voters[k] {331 return ErrAlreadyVoted332 }333 c.voters[k] = true334 if keep {335 c.Keep++336 } else {337 c.Remove++338 }339 return nil340}341342// Outcome is what a resolution decided and who it paid.343type Outcome struct {344 Key string345 Kept bool346 Winner address347 Amount int64 // credited to the winner348 Keep int64349 Remove int64350}351352// Resolve closes a challenge whose deadline has passed. Anyone may call it: the353// 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 the356// challenger's bond. Otherwise the entry is removed and the challenger is357// credited the bond plus the deposit.358//359// A TIE KEEPS THE ENTRY, including the tie of nobody voting at all. The360// incumbent paid first and is already at risk, so the burden is on the361// challenger to produce a reason; if ties went the other way, a challenge that362// 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 wrong364// 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{}, ErrNoEntry369 }370 c := e.challenge371 if e.State != StateChallenged || c == nil {372 return Outcome{}, ErrNoChallenge373 }374 if c.Open(now) {375 return Outcome{}, ErrTooEarly376 }377378 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.Bond381 } else {382 out.Winner, out.Amount = c.Challenger, c.Bond+e.Deposit383 }384385 // Credit first: it is the only step that can fail, and a half-applied386 // 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{}, err389 }390 if out.Kept {391 e.State = StateListed392 r.locked -= c.Bond393 } else {394 e.State = StateRemoved395 r.locked -= c.Bond + e.Deposit396 }397 e.challenge = nil398 return out, nil399}400401// 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 the404// 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 ErrNoEntry409 }410 if e.Owner != owner {411 return ErrNotOwner412 }413 if e.State == StateChallenged {414 return ErrChallenged415 }416 if err := r.credit(owner, e.Deposit); err != nil {417 return err418 }419 e.State = StateRemoved420 r.locked -= e.Deposit421 return nil422}423424// 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 the427// pattern: the credit is already gone from the ledger when control passes to428// 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, ErrNothingOwed434 }435 delete(r.credits, k) // effects before interactions436 r.owed -= amount437 return amount, nil438}439440// credit records that who is owed amount more.441func (r *Registry) credit(who address, amount int64) error {442 if amount <= 0 {443 return ErrBadAmount444 }445 k := who.String()446 have, seen := r.credits[k]447 if !seen && len(r.credits) >= MaxPayees {448 return ErrFull449 }450 if have > maxInt64-amount || r.owed > maxInt64-amount {451 return ErrOverflow452 }453 r.credits[k] = have + amount454 r.owed += amount455 return nil456}457458// 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, ok462}463464// IsListed reports whether key is on the list right now. A challenged entry is465// still listed.466func (r *Registry) IsListed(key string) bool {467 e, ok := r.entries[key]468 return ok && e.Live()469}470471// Count is how many entries are on the list right now.472func (r *Registry) Count() int {473 n := 0474 for _, key := range r.order {475 if r.entries[key].Live() {476 n++477 }478 }479 return n480}481482// Records is how many keys the registry has ever held, removed ones included.483func (r *Registry) Records() int { return len(r.order) }484485// 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 a488// stable sequence a Render can be pinned against rather than an insertion order489// 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 out498}499500// Challenged returns every entry with a challenge open against it, oldest501// 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 out510}511512// 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, false517 }518 return e.challenge, true519}520521// CreditOf is what who can withdraw right now.522func (r *Registry) CreditOf(who address) int64 { return r.credits[who.String()] }523524// Owed is every credit not yet withdrawn.525func (r *Registry) Owed() int64 { return r.owed }526527// Locked is the deposits behind live entries plus the bonds behind open528// challenges.529//530// Locked plus [Registry.Owed] is what the holding realm must have at its531// address: every ugnot it ever took is either still backing something or532// already assigned to somebody. A realm can assert that equality against its533// own balance, and this package's tests do.534func (r *Registry) Locked() int64 { return r.locked }535536// ValidKey reports whether key is usable: 1 to [MaxKeyLen] bytes of lowercase537// ASCII letters, digits, '-', '_' and '.', starting with a letter or a digit.538//539// The leading-alphanumeric rule is what stops "." and "..", and what stops a540// key that reads as punctuation in the list it is shown in. The charset is541// narrow so a key can be typed, linked and compared without surprises; it is542// still escaped at render time, because a validator and an escaper protect543// against different mistakes.544func ValidKey(key string) bool {545 if key == "" || len(key) > MaxKeyLen {546 return false547 }548 if c := key[0]; !(c >= 'a' && c <= 'z' || c >= '0' && c <= '9') {549 return false550 }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 false558 }559 }560 return true561}562563// 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 use567// and those have no host. A renderer treats a schemeless URL as a path568// relative to the chain's web root, so an on-chain target is written569// "/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 that572// the entry is worth listing, not the claim that it resolves.573func ValidURL(url string) bool {574 if url == "" || len(url) > MaxURLLen {575 return false576 }577 for i := 0; i < len(url); i++ {578 if c := url[i]; c <= 0x20 || c == 0x7f {579 return false580 }581 }582 return true583}584585// ValidDescription reports whether description can be stored: non-empty after586// trimming, within [MaxDescLen], and a single line.587//588// Newlines and tabs are refused rather than stripped, because a description is589// shown back to the person who wrote it and silently rewriting it is worse than590// telling them it was refused. It lives in a table cell, which a newline would591// 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 false595 }596 for i := 0; i < len(description); i++ {597 if c := description[i]; c < 0x20 || c == 0x7f {598 return false599 }600 }601 return true602}603Signatures reconstructed verbatim from vm/qfuncs — interface params keep their inline definitions.