1// Package vouch is the engine behind a web of trust: one address says it2// stands behind another, in writing, optionally with its own money locked3// against the claim.4//5// # What it is for6//7// It is a sybil gate, and it exists because the apps around it do not have8// one. A realm that mints a point per distinct replier is farmed by two9// addresses replying to each other; a realm that counts one vote per address10// is farmed by holding a hundred addresses. Neither can fix that alone,11// because neither knows anything about the people behind the addresses.12//13// This package knows one thing: who was willing to say, on chain and under14// their own name, that an address is a person they stand behind. A realm asks15// [Graph.IsTrusted] and gates on the answer. That is the whole product, and16// every other read here exists to make that one legible.17//18// # The model19//20// Graph every vouch, in both directions, plus the refund ledger21// Vouch a directed statement: from, for, reason, bond, heights22//23// A vouch is directed and at most one exists per ordered pair. A second24// [Graph.Record] from the same address to the same target UPDATES the reason25// and ADDS to the bond rather than counting twice, which is what makes the26// score a count of people instead of a count of transactions. An address27// cannot vouch for itself.28//29// # The bond30//31// A vouch may lock coins. The engine only counts them: it takes the amount as32// an argument, tracks who posted how much on whom, and on [Graph.Revoke] moves33// that amount into a withdrawal ledger the voucher pulls from. It moves34// nothing itself. The realm holding the coins performs the transfer AFTER35// [Graph.Withdraw] has zeroed the credit, which is the ordering the36// pull-payment pattern demands.37//38// # No slashing, and why that is the hard part39//40// A bond here is value at risk only in the sense that it is illiquid: it can41// be withdrawn by revoking, and nothing can take it away. That is deliberate42// for a v0, and the missing half is not the accounting.43//44// Slashing needs an arbiter: somebody has to decide that a vouch was a lie.45// Every candidate is a design question with teeth. A DAO vote is a popularity46// contest against whoever is unpopular this month. A challenge market pays47// whoever is loudest and turns the graph into a griefing surface. An oracle is48// one key that can confiscate anyone's money. Shipping any of them by default49// would be shipping the wrong one, so this version ships the part that is50// uncontroversial: who said what, who put money behind it, and the gate that51// reads it.52//53// # Reasons are attacker-controlled markdown54//55// A reason is free text. [ValidReason] bounds it to [MaxReasonLen] bytes on56// one line and refuses control characters, but everything inside that is57// allowed and must be escaped where it is shown: ui.Inline in prose, ui.Cell58// in a table cell.59package vouch6061import (62 "errors"63 "strconv"64 "strings"6566 "gno.land/p/moul/addrset/v1"67 "gno.land/p/moul/kit/num/v0"68 "gno.land/p/moul/kit/tally/v0"69 "gno.land/p/moul/md/v0"70 "gno.land/p/moul/x/daily/pullpayment/v0"71)7273// MaxReasonLen is the longest reason accepted, in bytes. Long enough to say74// how you know somebody, short enough that one call cannot lock an unbounded75// storage deposit the realm's deployer is paying for.76const MaxReasonLen = 2007778const maxInt64 = int64(9223372036854775807)7980// The errors a caller can get back. A p/ returns them; the realm decides to81// abort.82var (83 ErrSelfVouch = errors.New("vouch: an address cannot vouch for itself")84 ErrBadReason = errors.New("vouch: reason is empty, too long, multi-line, or has control characters")85 ErrBadBond = errors.New("vouch: a bond cannot be negative")86 ErrNoVouch = errors.New("vouch: no such vouch")87 ErrNothingOwed = errors.New("vouch: nothing to withdraw")88 ErrOverflow = errors.New("vouch: bond would overflow")89)9091// Vouch is one directed statement of trust.92type Vouch struct {93 From address94 For address95 Reason string9697 // Bond is the amount locked on this vouch, in the realm's denom. It is98 // the sum of every bond sent with this pair, since a repeated vouch99 // adds to it rather than replacing it.100 Bond int64101102 // At is the height the vouch was first made, UpdatedAt the height it103 // last changed. They are equal until the voucher restates it.104 At int64105 UpdatedAt int64106}107108// Graph is the whole web of trust: every vouch, both directions of every109// edge, what is bonded on whom, and what revoking owes back to whom.110type Graph struct {111 edges map[string]*Vouch // "from|for" -> the vouch112 inbound map[string]*addrset.Set // target -> who vouches for them113 outbound map[string]*addrset.Set // voucher -> who they vouch for114 bonded map[string]int64 // target -> total bonded on them115116 // people is every address with at least one inbound vouch, sorted, so117 // a listing never has to iterate a map to build rendered output.118 people addrset.Set119120 refunds *pullpayment.Ledger121 count int122 totalBonded int64123}124125// NewGraph returns an empty graph.126func NewGraph() *Graph {127 return &Graph{128 edges: map[string]*Vouch{},129 inbound: map[string]*addrset.Set{},130 outbound: map[string]*addrset.Set{},131 bonded: map[string]int64{},132 refunds: pullpayment.New(),133 }134}135136// Record writes from's vouch for target and reports whether it replaced one137// that already existed.138//139// A repeated vouch is an update and not a second voice: the reason is140// replaced, the bond is added to the one already posted, and the score does141// not move. bond may be zero, which is the ordinary case.142func (g *Graph) Record(from, target address, reason string, bond, at int64) (updated bool, err error) {143 if from == target {144 return false, ErrSelfVouch145 }146 if !ValidReason(reason) {147 return false, ErrBadReason148 }149 if bond < 0 {150 return false, ErrBadBond151 }152 tk := target.String()153 if g.bonded[tk] > maxInt64-bond || g.totalBonded > maxInt64-bond {154 return false, ErrOverflow155 }156157 if v, ok := g.edges[key(from, target)]; ok {158 if v.Bond > maxInt64-bond {159 return false, ErrOverflow160 }161 v.Reason = reason162 v.Bond += bond163 v.UpdatedAt = at164 g.bonded[tk] += bond165 g.totalBonded += bond166 return true, nil167 }168169 g.edges[key(from, target)] = &Vouch{170 From: from,171 For: target,172 Reason: reason,173 Bond: bond,174 At: at,175 UpdatedAt: at,176 }177 g.set(g.inbound, tk).Add(from)178 g.set(g.outbound, from.String()).Add(target)179 g.people.Add(target)180 g.bonded[tk] += bond181 g.totalBonded += bond182 g.count++183 return false, nil184}185186// Revoke removes from's vouch for target and credits the bond back to from,187// returning the amount credited.188//189// The coins are not sent here and this package never holds any: the credit190// waits in the refund ledger until from calls [Graph.Withdraw].191func (g *Graph) Revoke(from, target address) (refund int64, err error) {192 v, ok := g.edges[key(from, target)]193 if !ok {194 return 0, ErrNoVouch195 }196 // Credit first, because it is the only step that can fail. Nothing is197 // mutated until the refund is certain, so a full ledger leaves the198 // graph exactly as it was rather than half revoked.199 if v.Bond > 0 {200 if err := g.refunds.Credit(from.String(), v.Bond); err != nil {201 return 0, err202 }203 }204205 delete(g.edges, key(from, target))206 tk, fk := target.String(), from.String()207208 if in, ok := g.inbound[tk]; ok {209 in.Remove(from)210 if in.Size() == 0 {211 delete(g.inbound, tk)212 g.people.Remove(target)213 }214 }215 if out, ok := g.outbound[fk]; ok {216 out.Remove(target)217 if out.Size() == 0 {218 delete(g.outbound, fk)219 }220 }221222 g.bonded[tk] -= v.Bond223 if g.bonded[tk] == 0 {224 delete(g.bonded, tk)225 }226 g.totalBonded -= v.Bond227 g.count--228 return v.Bond, nil229}230231// Withdraw zeroes what the graph owes who and returns it, so the realm can232// send exactly that much.233//234// The credit is gone from the ledger before this returns, which is what makes235// a reentrant call find nothing: the realm transfers after, never before.236func (g *Graph) Withdraw(who address) (int64, error) {237 amount, err := g.refunds.Withdraw(who.String())238 if err != nil {239 return 0, ErrNothingOwed240 }241 return amount, nil242}243244// Get returns one vouch.245func (g *Graph) Get(from, target address) (*Vouch, bool) {246 v, ok := g.edges[key(from, target)]247 return v, ok248}249250// ScoreOf is how many distinct addresses vouch for addr.251//252// It counts people and not statements: restating a vouch does not raise it,253// and revoking lowers it.254func (g *Graph) ScoreOf(addr address) int {255 if in, ok := g.inbound[addr.String()]; ok {256 return in.Size()257 }258 return 0259}260261// BondedFor is the total locked on addr by everyone vouching for them.262func (g *Graph) BondedFor(addr address) int64 { return g.bonded[addr.String()] }263264// IsTrusted reports whether addr is vouched for by at least min distinct265// addresses. It is the gate another realm calls, and the reason this package266// exists.267//268// A min below one is raised to one. A gate that lets everybody through is a269// bug at the call site rather than an answer worth returning, and silently270// agreeing with it is how a sybil check ships disabled.271//272// What it cannot tell you is whether those vouchers are distinct PEOPLE. Two273// addresses vouching for each other both reach a score of one for the price of274// two transactions, which is why [Graph.Mutual] is exported and why a gate275// that matters should ask for more than one.276func (g *Graph) IsTrusted(addr address, min int) bool {277 if min < 1 {278 min = 1279 }280 return g.ScoreOf(addr) >= min281}282283// VouchedBy is every address that vouches for addr, sorted.284//285// Sorted and not chronological: the set is the storage, the order is a total286// order on the address, and two identical calls therefore render identically.287func (g *Graph) VouchedBy(addr address) []address {288 return collect(g.inbound[addr.String()])289}290291// VouchesOf is every address addr vouches for, sorted. It is the other292// direction of [Graph.VouchedBy].293func (g *Graph) VouchesOf(addr address) []address {294 return collect(g.outbound[addr.String()])295}296297// Mutual reports whether a and b vouch for each other.298//299// A mutual pair is the cheapest sybil shape there is, so this is here to be300// discounted by a caller that cares, not as a badge.301func (g *Graph) Mutual(a, b address) bool {302 if a == b {303 return false304 }305 _, there := g.edges[key(a, b)]306 _, back := g.edges[key(b, a)]307 return there && back308}309310// ReasonFrom is what from wrote about target, or the empty string when there311// is no such vouch. It is raw caller text: escape it where it is shown.312func (g *Graph) ReasonFrom(from, target address) string {313 if v, ok := g.edges[key(from, target)]; ok {314 return v.Reason315 }316 return ""317}318319// BondFrom is what from locked on target, or zero.320func (g *Graph) BondFrom(from, target address) int64 {321 if v, ok := g.edges[key(from, target)]; ok {322 return v.Bond323 }324 return 0325}326327// Count is how many vouches exist, across everybody.328func (g *Graph) Count() int { return g.count }329330// People is how many addresses have at least one vouch for them.331func (g *Graph) People() int { return g.people.Size() }332333// Owed is what revoking has credited to addr and nobody has withdrawn yet.334func (g *Graph) Owed(addr address) int64 { return g.refunds.Balance(addr.String()) }335336// TotalOwed is every unwithdrawn refund. The realm must hold at least337// TotalOwed plus [Graph.TotalBonded] to be solvent.338func (g *Graph) TotalOwed() int64 { return g.refunds.TotalOwed() }339340// TotalBonded is everything locked on every vouch that still stands.341func (g *Graph) TotalBonded() int64 { return g.totalBonded }342343// Ranked is one row of [Graph.Leaderboard].344type Ranked struct {345 Addr address346 Score int347 Bonded int64348}349350// Leaderboard is the most vouched for addresses, highest score first, ties351// broken by address so the order is total and a Render never reshuffles.352//353// limit at or below zero returns nothing.354func (g *Graph) Leaderboard(limit int) []Ranked {355 if limit <= 0 || g.people.Size() == 0 {356 return nil357 }358 entries := make([]tally.Entry, 0, g.people.Size())359 g.people.IterateByOffset(0, g.people.Size(), func(a address) bool {360 entries = append(entries, tally.Entry{Key: a.String(), Score: int64(g.ScoreOf(a))})361 return false362 })363 top := tally.Top(entries, limit)364365 out := make([]Ranked, 0, len(top))366 for _, e := range top {367 a := address(e.Key)368 out = append(out, Ranked{Addr: a, Score: int(e.Score), Bonded: g.bonded[e.Key]})369 }370 return out371}372373// ValidReason reports whether reason can be stored: non-empty after trimming,374// within [MaxReasonLen], on one line, and free of control characters.375//376// One line is a deliberate bound rather than a rendering workaround. A reason377// is shown in a table cell beside the address it is about, and a writer who378// needs a second paragraph is writing something other than a reason.379//380// Control characters are refused rather than stripped because the text is381// shown back to whoever wrote it, and silently rewriting what somebody said is382// worse than telling them it was refused. Everything else is allowed and383// escaped at render time, since a validator and an escaper protect against384// different mistakes.385func ValidReason(reason string) bool {386 if len(reason) > MaxReasonLen || strings.TrimSpace(reason) == "" {387 return false388 }389 for i := 0; i < len(reason); i++ {390 if c := reason[i]; c < 0x20 || c == 0x7f {391 return false392 }393 }394 return true395}396397// Badge is the one-line trust mark, for a realm that wants to show what the398// gate it just called was reading.399//400// It takes the numbers rather than the graph because the realm holding the401// graph is the only one that can read it: everybody else has the two integers402// from a cross-realm call and needs nothing more to render them.403func Badge(realmPath string, addr address, score int, bonded int64) string {404 if score == 0 {405 return md.Link("not vouched for", AddrURL(realmPath, addr))406 }407 word := " vouchers"408 if score == 1 {409 word = " voucher"410 }411 out := "\U0001F91D " + md.Link(strconv.Itoa(score)+word, AddrURL(realmPath, addr))412 if bonded > 0 {413 out += " · " + num.GNOTf(bonded) + " bonded"414 }415 return out416}417418// AddrURL is the gnoweb path of one address's page on the hosting realm.419func AddrURL(realmPath string, addr address) string {420 return RealmURL(realmPath) + ":addr/" + addr.String()421}422423// RealmURL is the gnoweb path of a realm given as a package path.424//425// The chain domain is the first element of a package path and a gnoweb path is426// the rest of it, so this is a prefix strip and not a hostname this package427// has to know.428func RealmURL(realmPath string) string {429 if i := strings.Index(realmPath, "/"); i >= 0 {430 return realmPath[i:]431 }432 return "/" + realmPath433}434435// key is the storage key of one directed edge. Addresses are fixed-length436// bech32, so the separator is belt and braces rather than load-bearing.437func key(from, target address) string { return from.String() + "|" + target.String() }438439// set returns the address set stored under k, creating it on first use.440func (g *Graph) set(m map[string]*addrset.Set, k string) *addrset.Set {441 if s, ok := m[k]; ok {442 return s443 }444 s := &addrset.Set{}445 m[k] = s446 return s447}448449// collect reads a set out in sorted order.450func collect(s *addrset.Set) []address {451 if s == nil || s.Size() == 0 {452 return nil453 }454 out := make([]address, 0, s.Size())455 s.IterateByOffset(0, s.Size(), func(a address) bool {456 out = append(out, a)457 return false458 })459 return out460}461Signatures reconstructed verbatim from vm/qfuncs — interface params keep their inline definitions.