vouch.gno
15.09 Kb · 460 lines
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 "errors"
63 "strconv"
64 "strings"
65
66 "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)
72
73// MaxReasonLen is the longest reason accepted, in bytes. Long enough to say
74// how you know somebody, short enough that one call cannot lock an unbounded
75// storage deposit the realm's deployer is paying for.
76const MaxReasonLen = 200
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 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)
90
91// Vouch is one directed statement of trust.
92type Vouch struct {
93 From address
94 For address
95 Reason string
96
97 // Bond is the amount locked on this vouch, in the realm's denom. It is
98 // the sum of every bond sent with this pair, since a repeated vouch
99 // adds to it rather than replacing it.
100 Bond int64
101
102 // At is the height the vouch was first made, UpdatedAt the height it
103 // last changed. They are equal until the voucher restates it.
104 At int64
105 UpdatedAt int64
106}
107
108// Graph is the whole web of trust: every vouch, both directions of every
109// edge, what is bonded on whom, and what revoking owes back to whom.
110type Graph struct {
111 edges map[string]*Vouch // "from|for" -> the vouch
112 inbound map[string]*addrset.Set // target -> who vouches for them
113 outbound map[string]*addrset.Set // voucher -> who they vouch for
114 bonded map[string]int64 // target -> total bonded on them
115
116 // people is every address with at least one inbound vouch, sorted, so
117 // a listing never has to iterate a map to build rendered output.
118 people addrset.Set
119
120 refunds *pullpayment.Ledger
121 count int
122 totalBonded int64
123}
124
125// 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}
135
136// Record writes from's vouch for target and reports whether it replaced one
137// that already existed.
138//
139// A repeated vouch is an update and not a second voice: the reason is
140// replaced, the bond is added to the one already posted, and the score does
141// 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, ErrSelfVouch
145 }
146 if !ValidReason(reason) {
147 return false, ErrBadReason
148 }
149 if bond < 0 {
150 return false, ErrBadBond
151 }
152 tk := target.String()
153 if g.bonded[tk] > maxInt64-bond || g.totalBonded > maxInt64-bond {
154 return false, ErrOverflow
155 }
156
157 if v, ok := g.edges[key(from, target)]; ok {
158 if v.Bond > maxInt64-bond {
159 return false, ErrOverflow
160 }
161 v.Reason = reason
162 v.Bond += bond
163 v.UpdatedAt = at
164 g.bonded[tk] += bond
165 g.totalBonded += bond
166 return true, nil
167 }
168
169 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] += bond
181 g.totalBonded += bond
182 g.count++
183 return false, nil
184}
185
186// 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 credit
190// 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, ErrNoVouch
195 }
196 // Credit first, because it is the only step that can fail. Nothing is
197 // mutated until the refund is certain, so a full ledger leaves the
198 // 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, err
202 }
203 }
204
205 delete(g.edges, key(from, target))
206 tk, fk := target.String(), from.String()
207
208 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 }
221
222 g.bonded[tk] -= v.Bond
223 if g.bonded[tk] == 0 {
224 delete(g.bonded, tk)
225 }
226 g.totalBonded -= v.Bond
227 g.count--
228 return v.Bond, nil
229}
230
231// Withdraw zeroes what the graph owes who and returns it, so the realm can
232// send exactly that much.
233//
234// The credit is gone from the ledger before this returns, which is what makes
235// 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, ErrNothingOwed
240 }
241 return amount, nil
242}
243
244// Get returns one vouch.
245func (g *Graph) Get(from, target address) (*Vouch, bool) {
246 v, ok := g.edges[key(from, target)]
247 return v, ok
248}
249
250// 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 0
259}
260
261// BondedFor is the total locked on addr by everyone vouching for them.
262func (g *Graph) BondedFor(addr address) int64 { return g.bonded[addr.String()] }
263
264// IsTrusted reports whether addr is vouched for by at least min distinct
265// addresses. It is the gate another realm calls, and the reason this package
266// exists.
267//
268// A min below one is raised to one. A gate that lets everybody through is a
269// bug at the call site rather than an answer worth returning, and silently
270// agreeing with it is how a sybil check ships disabled.
271//
272// What it cannot tell you is whether those vouchers are distinct PEOPLE. Two
273// addresses vouching for each other both reach a score of one for the price of
274// two transactions, which is why [Graph.Mutual] is exported and why a gate
275// that matters should ask for more than one.
276func (g *Graph) IsTrusted(addr address, min int) bool {
277 if min < 1 {
278 min = 1
279 }
280 return g.ScoreOf(addr) >= min
281}
282
283// VouchedBy is every address that vouches for addr, sorted.
284//
285// Sorted and not chronological: the set is the storage, the order is a total
286// 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}
290
291// VouchesOf is every address addr vouches for, sorted. It is the other
292// direction of [Graph.VouchedBy].
293func (g *Graph) VouchesOf(addr address) []address {
294 return collect(g.outbound[addr.String()])
295}
296
297// 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 be
300// discounted by a caller that cares, not as a badge.
301func (g *Graph) Mutual(a, b address) bool {
302 if a == b {
303 return false
304 }
305 _, there := g.edges[key(a, b)]
306 _, back := g.edges[key(b, a)]
307 return there && back
308}
309
310// ReasonFrom is what from wrote about target, or the empty string when there
311// 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.Reason
315 }
316 return ""
317}
318
319// 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.Bond
323 }
324 return 0
325}
326
327// Count is how many vouches exist, across everybody.
328func (g *Graph) Count() int { return g.count }
329
330// People is how many addresses have at least one vouch for them.
331func (g *Graph) People() int { return g.people.Size() }
332
333// 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()) }
335
336// TotalOwed is every unwithdrawn refund. The realm must hold at least
337// TotalOwed plus [Graph.TotalBonded] to be solvent.
338func (g *Graph) TotalOwed() int64 { return g.refunds.TotalOwed() }
339
340// TotalBonded is everything locked on every vouch that still stands.
341func (g *Graph) TotalBonded() int64 { return g.totalBonded }
342
343// Ranked is one row of [Graph.Leaderboard].
344type Ranked struct {
345 Addr address
346 Score int
347 Bonded int64
348}
349
350// Leaderboard is the most vouched for addresses, highest score first, ties
351// 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 nil
357 }
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 false
362 })
363 top := tally.Top(entries, limit)
364
365 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 out
371}
372
373// 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 reason
377// is shown in a table cell beside the address it is about, and a writer who
378// needs a second paragraph is writing something other than a reason.
379//
380// Control characters are refused rather than stripped because the text is
381// shown back to whoever wrote it, and silently rewriting what somebody said is
382// worse than telling them it was refused. Everything else is allowed and
383// escaped at render time, since a validator and an escaper protect against
384// different mistakes.
385func ValidReason(reason string) bool {
386 if len(reason) > MaxReasonLen || strings.TrimSpace(reason) == "" {
387 return false
388 }
389 for i := 0; i < len(reason); i++ {
390 if c := reason[i]; c < 0x20 || c == 0x7f {
391 return false
392 }
393 }
394 return true
395}
396
397// Badge is the one-line trust mark, for a realm that wants to show what the
398// gate it just called was reading.
399//
400// It takes the numbers rather than the graph because the realm holding the
401// graph is the only one that can read it: everybody else has the two integers
402// 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 out
416}
417
418// 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}
422
423// 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 is
426// the rest of it, so this is a prefix strip and not a hostname this package
427// has to know.
428func RealmURL(realmPath string) string {
429 if i := strings.Index(realmPath, "/"); i >= 0 {
430 return realmPath[i:]
431 }
432 return "/" + realmPath
433}
434
435// key is the storage key of one directed edge. Addresses are fixed-length
436// bech32, so the separator is belt and braces rather than load-bearing.
437func key(from, target address) string { return from.String() + "|" + target.String() }
438
439// 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 s
443 }
444 s := &addrset.Set{}
445 m[k] = s
446 return s
447}
448
449// collect reads a set out in sorted order.
450func collect(s *addrset.Set) []address {
451 if s == nil || s.Size() == 0 {
452 return nil
453 }
454 out := make([]address, 0, s.Size())
455 s.IterateByOffset(0, s.Size(), func(a address) bool {
456 out = append(out, a)
457 return false
458 })
459 return out
460}
