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  	"bytes"
   7  	"sort"
   8  
   9  	"smesh.lol/pkg/nostr/filter"
  10  	"smesh.lol/pkg/nostr/kind"
  11  	"smesh.lol/pkg/nostr/tag"
  12  	"smesh.lol/pkg/store"
  13  )
  14  
  15  // Score is a WoT score for a pubkey.
  16  type Score struct {
  17  	Pubkey []byte
  18  	Value  float64
  19  	Depth  int
  20  }
  21  
  22  // WoT computes Web-of-Trust scores from the follow graph.
  23  type WoT struct {
  24  	store *store.Engine
  25  }
  26  
  27  // New creates a WoT scorer.
  28  func New(s *store.Engine) *WoT { return &WoT{store: s} }
  29  
  30  // Compute runs BFS from seed to maxDepth, returning scored pubkeys
  31  // sorted by score descending.
  32  func (w *WoT) Compute(seed []byte, maxDepth int) []Score {
  33  	scores := map[string]*Score{}
  34  	visited := map[string]bool{string(seed): true}
  35  	queue := [][]byte{seed}
  36  
  37  	for depth := 1; depth <= maxDepth && len(queue) > 0; depth++ {
  38  		decay := 1.0 / float64(int(1)<<uint(depth-1))
  39  		var next [][]byte
  40  		for _, pk := range queue {
  41  			for _, fpk := range w.getFollows(pk) {
  42  				key := string(fpk)
  43  				if sc, ok := scores[key]; ok {
  44  					sc.Value += decay
  45  					continue
  46  				}
  47  				if visited[key] {
  48  					continue
  49  				}
  50  				visited[key] = true
  51  				scores[key] = &Score{Pubkey: fpk, Value: decay, Depth: depth}
  52  				next = append(next, fpk)
  53  			}
  54  		}
  55  		queue = next
  56  	}
  57  
  58  	out := []Score{:0:len(scores)}
  59  	for _, sc := range scores {
  60  		out = append(out, *sc)
  61  	}
  62  	sort.Slice(out, func(i, j int) bool { return out[i].Value > out[j].Value })
  63  	return out
  64  }
  65  
  66  // IsTrusted returns true if pubkey has score >= threshold.
  67  func IsTrusted(scores []Score, pubkey []byte, threshold float64) bool {
  68  	for i := range scores {
  69  		if bytes.Equal(scores[i].Pubkey, pubkey) {
  70  			return scores[i].Value >= threshold
  71  		}
  72  	}
  73  	return false
  74  }
  75  
  76  func (w *WoT) getFollows(pubkey []byte) [][]byte {
  77  	f := &filter.F{
  78  		Kinds:   kind.NewS(kind.FollowList),
  79  		Authors: tag.NewFromBytesSlice(pubkey),
  80  	}
  81  	limit := uint(1)
  82  	f.Limit = &limit
  83  
  84  	events, err := w.store.QueryEvents(f)
  85  	if err != nil || len(events) == 0 {
  86  		return nil
  87  	}
  88  	ev := events[0]
  89  	if ev.Tags == nil {
  90  		return nil
  91  	}
  92  	pTags := ev.Tags.GetAll([]byte("p"))
  93  	out := [][]byte{:0:len(pTags)}
  94  	for _, pt := range pTags {
  95  		val := pt.ValueBinary()
  96  		if val != nil && len(val) == 32 {
  97  			pk := []byte{:32}
  98  			copy(pk, val)
  99  			out = append(out, pk)
 100  		}
 101  	}
 102  	return out
 103  }
 104