grapevine.mx raw
1 // Package grapevine computes Web-of-Trust scores by BFS traversal
2 // of the follow graph (kind 3 events).
3 package grapevine
4
5 import (
6 "git.smesh.lol/moxie/pkg/mxutil"
7 "bytes"
8
9 "git.smesh.lol/nostr/pkg/event"
10 "git.smesh.lol/nostr/pkg/filter"
11 "git.smesh.lol/nostr/pkg/kind"
12 "git.smesh.lol/nostr/pkg/tag"
13 "git.smesh.lol/morly/pkg/store"
14 )
15
16 // Score is a WoT score for a pubkey.
17 type Score struct {
18 Pubkey []byte
19 Value float64
20 Depth int32
21 }
22
23 // WoT computes Web-of-Trust scores from the follow graph.
24 type WoT struct {
25 store *store.Engine
26 }
27
28 // New creates a WoT scorer.
29 func New(s *store.Engine) (w *WoT) { return &WoT{store: s} }
30
31 // Compute runs BFS from seed to maxDepth, returning scored pubkeys
32 // sorted by score descending.
33 func (w *WoT) Compute(seed []byte, maxDepth int32) (ss []Score) {
34 scores := map[string]*Score{}
35 visited := map[string]bool{string(seed): true}
36 queue := [][]byte{seed}
37
38 for depth := 1; depth <= maxDepth && len(queue) > 0; depth++ {
39 decay := 1.0 / float64(int32(1)<<uint32(depth-1))
40 var next [][]byte
41 for _, pk := range queue {
42 for _, fpk := range w.GetFollows(pk) {
43 key := string(fpk)
44 if sc, ok := scores[key]; ok {
45 sc.Value += decay
46 continue
47 }
48 if visited[key] {
49 continue
50 }
51 visited[key] = true
52 scores[key] = &Score{Pubkey: fpk, Value: decay, Depth: depth}
53 next = mxutil.Ensure(next, 1)
54 next = push(next, fpk)
55 }
56 }
57 queue = next
58 }
59
60 out := []Score{:0:len(scores)}
61 for _, sc := range scores {
62 out = mxutil.Ensure(out, 1)
63 out = push(out, *sc)
64 }
65 for i := 1; i < len(out); i++ {
66 for j := i; j > 0 && out[j].Value > out[j-1].Value; j-- {
67 out[j], out[j-1] = out[j-1], out[j]
68 }
69 }
70 return out
71 }
72
73 // IsTrusted returns true if pubkey has score >= threshold.
74 func IsTrusted(scores []Score, pubkey []byte, threshold float64) (ok bool) {
75 for i := range scores {
76 if bytes.Equal(scores[i].Pubkey, pubkey) {
77 return scores[i].Value >= threshold
78 }
79 }
80 return false
81 }
82
83 // GetFollows returns the set of pubkeys followed by pubkey (kind-3 p-tags).
84 func GetFollows(s *store.Engine, pubkey []byte) (ss [][]byte) {
85 return (&WoT{store: s}).GetFollows(pubkey)
86 }
87
88 func (w *WoT) GetFollows(pubkey []byte) (ss [][]byte) {
89 kind.Ensure()
90 f := &filter.F{
91 Kinds: kind.NewS(kind.FollowList),
92 Authors: tag.NewFromBytesSlice(pubkey),
93 }
94 limit := uint32(1)
95 f.Limit = &limit
96
97 // The result type is spelled out, and event imported, because stage4
98 // cannot resolve `[]*event.E` through another package's export data when
99 // the caller does not import event itself: the short var came out with no
100 // type, every later use of it did too, and grapevine failed to build from
101 // source (`cannot resolve type of short var ev ... rhs=ssatype=nil`, then
102 // `%t35 defined with type '{ i64, ptr }' but expected '{ ptr, i64, i64 }'`).
103 // It only ever built from a stale cache entry, which is why the relay and
104 // the pipeline tests passed until the store was edited.
105 var events []*event.E
106 var err error
107 events, err = w.store.QueryEvents(f)
108 if err != nil || len(events) == 0 {
109 return nil
110 }
111 ev := events[0]
112 if ev.Tags == nil {
113 return nil
114 }
115 pTags := ev.Tags.GetAll([]byte("p"))
116 out := [][]byte{:0:len(pTags)}
117 for _, pt := range pTags {
118 val := pt.ValueBinary()
119 if val != nil && len(val) == 32 {
120 pk := []byte{:32}
121 copy(pk, val)
122 out = mxutil.Ensure(out, 1)
123 out = push(out, pk)
124 }
125 }
126 return out
127 }
128