vouch.gno

  1// Package vouch is the engine behind a web of trust: one address says it
  2// stands behind another, in writing, optionally with its own money locked
  3// against the claim.
  4//
  5// # What it is for
  6//
  7// It is a sybil gate, and it exists because the apps around it do not have
  8// one. A realm that mints a point per distinct replier is farmed by two
  9// addresses replying to each other; a realm that counts one vote per address
 10// 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 under
 14// their own name, that an address is a person they stand behind. A realm asks
 15// [Graph.IsTrusted] and gates on the answer. That is the whole product, and
 16// every other read here exists to make that one legible.
 17//
 18// # The model
 19//
 20//	Graph   every vouch, in both directions, plus the refund ledger
 21//	Vouch   a directed statement: from, for, reason, bond, heights
 22//
 23// A vouch is directed and at most one exists per ordered pair. A second
 24// [Graph.Record] from the same address to the same target UPDATES the reason
 25// and ADDS to the bond rather than counting twice, which is what makes the
 26// score a count of people instead of a count of transactions. An address
 27// cannot vouch for itself.
 28//
 29// # The bond
 30//
 31// A vouch may lock coins. The engine only counts them: it takes the amount as
 32// an argument, tracks who posted how much on whom, and on [Graph.Revoke] moves
 33// that amount into a withdrawal ledger the voucher pulls from. It moves
 34// nothing itself. The realm holding the coins performs the transfer AFTER
 35// [Graph.Withdraw] has zeroed the credit, which is the ordering the
 36// pull-payment pattern demands.
 37//
 38// # No slashing, and why that is the hard part
 39//
 40// A bond here is value at risk only in the sense that it is illiquid: it can
 41// be withdrawn by revoking, and nothing can take it away. That is deliberate
 42// 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 popularity
 46// contest against whoever is unpopular this month. A challenge market pays
 47// whoever is loudest and turns the graph into a griefing surface. An oracle is
 48// one key that can confiscate anyone's money. Shipping any of them by default
 49// would be shipping the wrong one, so this version ships the part that is
 50// uncontroversial: who said what, who put money behind it, and the gate that
 51// reads it.
 52//
 53// # Reasons are attacker-controlled markdown
 54//
 55// A reason is free text. [ValidReason] bounds it to [MaxReasonLen] bytes on
 56// one line and refuses control characters, but everything inside that is
 57// allowed and must be escaped where it is shown: ui.Inline in prose, ui.Cell
 58// in a table cell.
 59package vouch
 60
 61import (
 62	"chain/markdown"
 63	"errors"
 64	"strconv"
 65	"strings"
 66
 67	"gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/addrset/v1"
 68	"gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/kit/num/v0"
 69	"gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/kit/tally/v0"
 70	"gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/md/v0"
 71	"gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/x/daily/pullpayment/v0"
 72)
 73
 74// MaxReasonLen is the longest reason accepted, in bytes. Long enough to say
 75// how you know somebody, short enough that one call cannot lock an unbounded
 76// storage deposit the realm's deployer is paying for.
 77const MaxReasonLen = 200
 78
 79const maxInt64 = int64(9223372036854775807)
 80
 81// The errors a caller can get back. A p/ returns them; the realm decides to
 82// abort.
 83var (
 84	ErrSelfVouch   = errors.New("vouch: an address cannot vouch for itself")
 85	ErrBadReason   = errors.New("vouch: reason is empty, too long, multi-line, or has control characters")
 86	ErrBadBond     = errors.New("vouch: a bond cannot be negative")
 87	ErrNoVouch     = errors.New("vouch: no such vouch")
 88	ErrNothingOwed = errors.New("vouch: nothing to withdraw")
 89	ErrOverflow    = errors.New("vouch: bond would overflow")
 90)
 91
 92// Vouch is one directed statement of trust.
 93type Vouch struct {
 94	From   address
 95	For    address
 96	Reason string
 97
 98	// Bond is the amount locked on this vouch, in the realm's denom. It is
 99	// the sum of every bond sent with this pair, since a repeated vouch
100	// adds to it rather than replacing it.
101	Bond int64
102
103	// At is the height the vouch was first made, UpdatedAt the height it
104	// last changed. They are equal until the voucher restates it.
105	At        int64
106	UpdatedAt int64
107}
108
109// Graph is the whole web of trust: every vouch, both directions of every
110// edge, what is bonded on whom, and what revoking owes back to whom.
111type Graph struct {
112	edges    map[string]*Vouch       // "from|for" -> the vouch
113	inbound  map[string]*addrset.Set // target -> who vouches for them
114	outbound map[string]*addrset.Set // voucher -> who they vouch for
115	bonded   map[string]int64        // target -> total bonded on them
116
117	// people is every address with at least one inbound vouch, sorted, so
118	// a listing never has to iterate a map to build rendered output.
119	people addrset.Set
120
121	refunds     *pullpayment.Ledger
122	count       int
123	totalBonded int64
124}
125
126// NewGraph returns an empty graph.
127func NewGraph() *Graph {
128	return &Graph{
129		edges:    map[string]*Vouch{},
130		inbound:  map[string]*addrset.Set{},
131		outbound: map[string]*addrset.Set{},
132		bonded:   map[string]int64{},
133		refunds:  pullpayment.New(),
134	}
135}
136
137// Record writes from's vouch for target and reports whether it replaced one
138// that already existed.
139//
140// A repeated vouch is an update and not a second voice: the reason is
141// replaced, the bond is added to the one already posted, and the score does
142// not move. bond may be zero, which is the ordinary case.
143func (g *Graph) Record(from, target address, reason string, bond, at int64) (updated bool, err error) {
144	if from == target {
145		return false, ErrSelfVouch
146	}
147	if !ValidReason(reason) {
148		return false, ErrBadReason
149	}
150	if bond < 0 {
151		return false, ErrBadBond
152	}
153	tk := target.String()
154	if g.bonded[tk] > maxInt64-bond || g.totalBonded > maxInt64-bond {
155		return false, ErrOverflow
156	}
157
158	if v, ok := g.edges[key(from, target)]; ok {
159		if v.Bond > maxInt64-bond {
160			return false, ErrOverflow
161		}
162		v.Reason = reason
163		v.Bond += bond
164		v.UpdatedAt = at
165		g.bonded[tk] += bond
166		g.totalBonded += bond
167		return true, nil
168	}
169
170	g.edges[key(from, target)] = &Vouch{
171		From:      from,
172		For:       target,
173		Reason:    reason,
174		Bond:      bond,
175		At:        at,
176		UpdatedAt: at,
177	}
178	g.set(g.inbound, tk).Add(from)
179	g.set(g.outbound, from.String()).Add(target)
180	g.people.Add(target)
181	g.bonded[tk] += bond
182	g.totalBonded += bond
183	g.count++
184	return false, nil
185}
186
187// Revoke removes from's vouch for target and credits the bond back to from,
188// returning the amount credited.
189//
190// The coins are not sent here and this package never holds any: the credit
191// waits in the refund ledger until from calls [Graph.Withdraw].
192func (g *Graph) Revoke(from, target address) (refund int64, err error) {
193	v, ok := g.edges[key(from, target)]
194	if !ok {
195		return 0, ErrNoVouch
196	}
197	// Credit first, because it is the only step that can fail. Nothing is
198	// mutated until the refund is certain, so a full ledger leaves the
199	// graph exactly as it was rather than half revoked.
200	if v.Bond > 0 {
201		if err := g.refunds.Credit(from.String(), v.Bond); err != nil {
202			return 0, err
203		}
204	}
205
206	delete(g.edges, key(from, target))
207	tk, fk := target.String(), from.String()
208
209	if in, ok := g.inbound[tk]; ok {
210		in.Remove(from)
211		if in.Size() == 0 {
212			delete(g.inbound, tk)
213			g.people.Remove(target)
214		}
215	}
216	if out, ok := g.outbound[fk]; ok {
217		out.Remove(target)
218		if out.Size() == 0 {
219			delete(g.outbound, fk)
220		}
221	}
222
223	g.bonded[tk] -= v.Bond
224	if g.bonded[tk] == 0 {
225		delete(g.bonded, tk)
226	}
227	g.totalBonded -= v.Bond
228	g.count--
229	return v.Bond, nil
230}
231
232// Withdraw zeroes what the graph owes who and returns it, so the realm can
233// send exactly that much.
234//
235// The credit is gone from the ledger before this returns, which is what makes
236// a reentrant call find nothing: the realm transfers after, never before.
237func (g *Graph) Withdraw(who address) (int64, error) {
238	amount, err := g.refunds.Withdraw(who.String())
239	if err != nil {
240		return 0, ErrNothingOwed
241	}
242	return amount, nil
243}
244
245// Get returns one vouch.
246func (g *Graph) Get(from, target address) (*Vouch, bool) {
247	v, ok := g.edges[key(from, target)]
248	return v, ok
249}
250
251// ScoreOf is how many distinct addresses vouch for addr.
252//
253// It counts people and not statements: restating a vouch does not raise it,
254// and revoking lowers it.
255func (g *Graph) ScoreOf(addr address) int {
256	if in, ok := g.inbound[addr.String()]; ok {
257		return in.Size()
258	}
259	return 0
260}
261
262// BondedFor is the total locked on addr by everyone vouching for them.
263func (g *Graph) BondedFor(addr address) int64 { return g.bonded[addr.String()] }
264
265// IsTrusted reports whether addr is vouched for by at least min distinct
266// addresses. It is the gate another realm calls, and the reason this package
267// exists.
268//
269// A min below one is raised to one. A gate that lets everybody through is a
270// bug at the call site rather than an answer worth returning, and silently
271// agreeing with it is how a sybil check ships disabled.
272//
273// What it cannot tell you is whether those vouchers are distinct PEOPLE. Two
274// addresses vouching for each other both reach a score of one for the price of
275// two transactions, which is why [Graph.Mutual] is exported and why a gate
276// that matters should ask for more than one.
277func (g *Graph) IsTrusted(addr address, min int) bool {
278	if min < 1 {
279		min = 1
280	}
281	return g.ScoreOf(addr) >= min
282}
283
284// VouchedBy is every address that vouches for addr, sorted.
285//
286// Sorted and not chronological: the set is the storage, the order is a total
287// order on the address, and two identical calls therefore render identically.
288func (g *Graph) VouchedBy(addr address) []address {
289	return collect(g.inbound[addr.String()])
290}
291
292// VouchesOf is every address addr vouches for, sorted. It is the other
293// direction of [Graph.VouchedBy].
294func (g *Graph) VouchesOf(addr address) []address {
295	return collect(g.outbound[addr.String()])
296}
297
298// Mutual reports whether a and b vouch for each other.
299//
300// A mutual pair is the cheapest sybil shape there is, so this is here to be
301// discounted by a caller that cares, not as a badge.
302func (g *Graph) Mutual(a, b address) bool {
303	if a == b {
304		return false
305	}
306	_, there := g.edges[key(a, b)]
307	_, back := g.edges[key(b, a)]
308	return there && back
309}
310
311// ReasonFrom is what from wrote about target, or the empty string when there
312// is no such vouch. It is raw caller text: escape it where it is shown.
313func (g *Graph) ReasonFrom(from, target address) string {
314	if v, ok := g.edges[key(from, target)]; ok {
315		return v.Reason
316	}
317	return ""
318}
319
320// BondFrom is what from locked on target, or zero.
321func (g *Graph) BondFrom(from, target address) int64 {
322	if v, ok := g.edges[key(from, target)]; ok {
323		return v.Bond
324	}
325	return 0
326}
327
328// Count is how many vouches exist, across everybody.
329func (g *Graph) Count() int { return g.count }
330
331// People is how many addresses have at least one vouch for them.
332func (g *Graph) People() int { return g.people.Size() }
333
334// Owed is what revoking has credited to addr and nobody has withdrawn yet.
335func (g *Graph) Owed(addr address) int64 { return g.refunds.Balance(addr.String()) }
336
337// TotalOwed is every unwithdrawn refund. The realm must hold at least
338// TotalOwed plus [Graph.TotalBonded] to be solvent.
339func (g *Graph) TotalOwed() int64 { return g.refunds.TotalOwed() }
340
341// TotalBonded is everything locked on every vouch that still stands.
342func (g *Graph) TotalBonded() int64 { return g.totalBonded }
343
344// Ranked is one row of [Graph.Leaderboard].
345type Ranked struct {
346	Addr   address
347	Score  int
348	Bonded int64
349}
350
351// Leaderboard is the most vouched for addresses, highest score first, ties
352// broken by address so the order is total and a Render never reshuffles.
353//
354// limit at or below zero returns nothing.
355func (g *Graph) Leaderboard(limit int) []Ranked {
356	if limit <= 0 || g.people.Size() == 0 {
357		return nil
358	}
359	entries := make([]tally.Entry, 0, g.people.Size())
360	g.people.IterateByOffset(0, g.people.Size(), func(a address) bool {
361		entries = append(entries, tally.Entry{Key: a.String(), Score: int64(g.ScoreOf(a))})
362		return false
363	})
364	top := tally.Top(entries, limit)
365
366	out := make([]Ranked, 0, len(top))
367	for _, e := range top {
368		a := address(e.Key)
369		out = append(out, Ranked{Addr: a, Score: int(e.Score), Bonded: g.bonded[e.Key]})
370	}
371	return out
372}
373
374// ValidReason reports whether reason can be stored: non-empty after the
375// render's own stripping and trimming,
376// within [MaxReasonLen], on one line, and free of control characters.
377//
378// One line is a deliberate bound rather than a rendering workaround. A reason
379// is shown in a table cell beside the address it is about, and a writer who
380// needs a second paragraph is writing something other than a reason.
381//
382// Control characters are refused rather than stripped because the text is
383// shown back to whoever wrote it, and silently rewriting what somebody said is
384// worse than telling them it was refused. Everything else is allowed and
385// escaped at render time, since a validator and an escaper protect against
386// different mistakes.
387func ValidReason(reason string) bool {
388	if len(reason) > MaxReasonLen || strings.TrimSpace(markdown.StripBidiAndZeroWidth(reason)) == "" {
389		return false
390	}
391	for i := 0; i < len(reason); i++ {
392		if c := reason[i]; c < 0x20 || c == 0x7f {
393			return false
394		}
395	}
396	return true
397}
398
399// Badge is the one-line trust mark, for a realm that wants to show what the
400// gate it just called was reading.
401//
402// It takes the numbers rather than the graph because the realm holding the
403// graph is the only one that can read it: everybody else has the two integers
404// from a cross-realm call and needs nothing more to render them.
405func Badge(realmPath string, addr address, score int, bonded int64) string {
406	if score == 0 {
407		return md.Link("not vouched for", AddrURL(realmPath, addr))
408	}
409	word := " vouchers"
410	if score == 1 {
411		word = " voucher"
412	}
413	out := "\U0001F91D " + md.Link(strconv.Itoa(score)+word, AddrURL(realmPath, addr))
414	if bonded > 0 {
415		out += " · " + num.GNOTf(bonded) + " bonded"
416	}
417	return out
418}
419
420// AddrURL is the gnoweb path of one address's page on the hosting realm.
421func AddrURL(realmPath string, addr address) string {
422	return RealmURL(realmPath) + ":addr/" + addr.String()
423}
424
425// RealmURL is the gnoweb path of a realm given as a package path.
426//
427// The chain domain is the first element of a package path and a gnoweb path is
428// the rest of it, so this is a prefix strip and not a hostname this package
429// has to know.
430func RealmURL(realmPath string) string {
431	if i := strings.Index(realmPath, "/"); i >= 0 {
432		return realmPath[i:]
433	}
434	return "/" + realmPath
435}
436
437// key is the storage key of one directed edge. Addresses are fixed-length
438// bech32, so the separator is belt and braces rather than load-bearing.
439func key(from, target address) string { return from.String() + "|" + target.String() }
440
441// set returns the address set stored under k, creating it on first use.
442func (g *Graph) set(m map[string]*addrset.Set, k string) *addrset.Set {
443	if s, ok := m[k]; ok {
444		return s
445	}
446	s := &addrset.Set{}
447	m[k] = s
448	return s
449}
450
451// collect reads a set out in sorted order.
452func collect(s *addrset.Set) []address {
453	if s == nil || s.Size() == 0 {
454		return nil
455	}
456	out := make([]address, 0, s.Size())
457	s.IterateByOffset(0, s.Size(), func(a address) bool {
458		out = append(out, a)
459		return false
460	})
461	return out
462}