engine_test.go raw
1 package grapevine
2
3 import (
4 "encoding/json"
5 "fmt"
6 "math"
7 "testing"
8
9 "lukechampine.com/frand"
10 )
11
12 // mockGraphSource provides a controllable follow graph for testing.
13 type mockGraphSource struct {
14 follows map[string][]string // source -> targets
15 followers map[string][]string // target -> sources (reverse)
16 }
17
18 func newMockGraph() *mockGraphSource {
19 return &mockGraphSource{
20 follows: make(map[string][]string),
21 followers: make(map[string][]string),
22 }
23 }
24
25 func (m *mockGraphSource) addFollow(from, to string) {
26 m.follows[from] = append(m.follows[from], to)
27 m.followers[to] = append(m.followers[to], from)
28 }
29
30 func (m *mockGraphSource) TraverseFollowsOutbound(seedPubkey []byte, maxDepth int) (
31 map[int][]string, map[string]int, error,
32 ) {
33 seedHex := bytesToHex(seedPubkey)
34 visited := map[string]int{seedHex: 0}
35 byDepth := map[int][]string{0: {seedHex}}
36
37 for depth := 1; depth <= maxDepth; depth++ {
38 prevDepth := byDepth[depth-1]
39 for _, pk := range prevDepth {
40 for _, followed := range m.follows[pk] {
41 if _, seen := visited[followed]; !seen {
42 visited[followed] = depth
43 byDepth[depth] = append(byDepth[depth], followed)
44 }
45 }
46 }
47 if len(byDepth[depth]) == 0 {
48 break
49 }
50 }
51 return byDepth, visited, nil
52 }
53
54 func (m *mockGraphSource) GetFollowerPubkeys(targetHex string) ([]string, error) {
55 return m.followers[targetHex], nil
56 }
57
58 func (m *mockGraphSource) GetFollowsPubkeys(sourceHex string) ([]string, error) {
59 return m.follows[sourceHex], nil
60 }
61
62 func bytesToHex(b []byte) string {
63 const hexChars = "0123456789abcdef"
64 out := make([]byte, len(b)*2)
65 for i, v := range b {
66 out[i*2] = hexChars[v>>4]
67 out[i*2+1] = hexChars[v&0x0f]
68 }
69 return string(out)
70 }
71
72 // mockStore stores score data in memory.
73 type mockStore struct {
74 sets map[string][]byte
75 entries map[string][]byte
76 }
77
78 func newMockStore() *mockStore {
79 return &mockStore{
80 sets: make(map[string][]byte),
81 entries: make(map[string][]byte),
82 }
83 }
84
85 func (s *mockStore) SaveScoreSet(observerHex string, setData []byte, entries map[string][]byte) error {
86 s.sets[observerHex] = setData
87 for target, data := range entries {
88 s.entries[observerHex+":"+target] = data
89 }
90 return nil
91 }
92
93 func (s *mockStore) GetScoreSet(observerHex string) ([]byte, error) {
94 return s.sets[observerHex], nil
95 }
96
97 func (s *mockStore) GetScore(observerHex, targetHex string) ([]byte, error) {
98 return s.entries[observerHex+":"+targetHex], nil
99 }
100
101 // generateDeterministicGraph builds a realistic follow graph using frand with a fixed seed.
102 // Parameters:
103 // - numUsers: total number of pubkeys
104 // - avgFollows: average number of follows per user
105 // - observerFollows: number of follows for the observer specifically
106 //
107 // Returns the graph, all pubkey hexes (index 0 is observer), and the observer hex.
108 func generateDeterministicGraph(numUsers, avgFollows, observerFollows int) (*mockGraphSource, []string, string) {
109 rng := frand.NewCustom(make([]byte, 32), 1024, 12) // fixed zero seed
110
111 graph := newMockGraph()
112 pubkeys := make([]string, numUsers)
113 for i := 0; i < numUsers; i++ {
114 var buf [32]byte
115 rng.Read(buf[:])
116 pubkeys[i] = bytesToHex(buf[:])
117 }
118 observerHex := pubkeys[0]
119
120 // Observer follows first N users (deterministic, always the same set)
121 for i := 1; i <= observerFollows && i < numUsers; i++ {
122 graph.addFollow(observerHex, pubkeys[i])
123 }
124
125 // Each other user follows a random subset
126 for i := 1; i < numUsers; i++ {
127 nFollows := avgFollows/2 + int(rng.Uint64n(uint64(avgFollows)))
128 if nFollows > numUsers-1 {
129 nFollows = numUsers - 1
130 }
131 for j := 0; j < nFollows; j++ {
132 target := int(rng.Uint64n(uint64(numUsers)))
133 if target != i {
134 graph.addFollow(pubkeys[i], pubkeys[target])
135 }
136 }
137 }
138
139 return graph, pubkeys, observerHex
140 }
141
142 func TestComputeEmptyGraph(t *testing.T) {
143 graph := newMockGraph()
144 store := newMockStore()
145 engine := NewEngine(graph, store, DefaultConfig())
146
147 rng := frand.NewCustom(make([]byte, 32), 1024, 12)
148 var buf [32]byte
149 rng.Read(buf[:])
150 obs := bytesToHex(buf[:])
151
152 set, err := engine.Compute(obs)
153 if err != nil {
154 t.Fatalf("unexpected error: %v", err)
155 }
156 // Observer alone with no follows — hop set has just the observer (depth 0)
157 if set.TotalPubkeys > 1 {
158 t.Errorf("expected at most 1 pubkey (observer), got %d", set.TotalPubkeys)
159 }
160 }
161
162 func TestComputeDeterministicSmall(t *testing.T) {
163 // 20 users, observer follows 5, avg 4 follows each
164 graph, pubkeys, obs := generateDeterministicGraph(20, 4, 5)
165 store := newMockStore()
166 cfg := DefaultConfig()
167 cfg.MaxDepth = 3
168 cfg.Cycles = 5
169 engine := NewEngine(graph, store, cfg)
170
171 set, err := engine.Compute(obs)
172 if err != nil {
173 t.Fatalf("unexpected error: %v", err)
174 }
175
176 // Should discover users beyond direct follows
177 if set.TotalPubkeys < 6 {
178 t.Errorf("expected > 5 pubkeys in hop set (observer + 5 follows + their follows), got %d", set.TotalPubkeys)
179 }
180
181 // Observer's score should be 1.0
182 scores := scoreMap(set)
183 if s, ok := scores[obs]; !ok || s.Influence != 1.0 {
184 t.Errorf("observer influence should be 1.0")
185 }
186
187 // Direct follows should have positive influence
188 for i := 1; i <= 5; i++ {
189 if s, ok := scores[pubkeys[i]]; !ok || s.Influence <= 0 {
190 t.Errorf("direct follow %d should have positive influence", i)
191 }
192 }
193
194 // Verify determinism: run again, same results
195 store2 := newMockStore()
196 engine2 := NewEngine(graph, store2, cfg)
197 set2, _ := engine2.Compute(obs)
198 if len(set.Scores) != len(set2.Scores) {
199 t.Errorf("determinism: score count mismatch %d vs %d", len(set.Scores), len(set2.Scores))
200 }
201 }
202
203 func TestComputeDeterministicMedium(t *testing.T) {
204 // 200 users, observer follows 20, avg 10 follows each
205 // This creates a denser graph that exercises the convergence loop more thoroughly
206 graph, pubkeys, obs := generateDeterministicGraph(200, 10, 20)
207 store := newMockStore()
208 cfg := DefaultConfig()
209 cfg.MaxDepth = 4
210 cfg.Cycles = 8
211 engine := NewEngine(graph, store, cfg)
212
213 set, err := engine.Compute(obs)
214 if err != nil {
215 t.Fatalf("unexpected error: %v", err)
216 }
217
218 scores := scoreMap(set)
219 t.Logf("total pubkeys in hop set: %d, scored: %d, compute time: %dms",
220 set.TotalPubkeys, len(set.Scores), set.ComputeMs)
221
222 // Observer should always be 1.0
223 if s := scores[obs]; s == nil || s.Influence != 1.0 {
224 t.Error("observer influence should be 1.0")
225 }
226
227 // All direct follows should have positive influence
228 for i := 1; i <= 20 && i < len(pubkeys); i++ {
229 if s := scores[pubkeys[i]]; s == nil || s.Influence <= 0 {
230 t.Errorf("direct follow pubkeys[%d] should have positive influence", i)
231 }
232 }
233
234 // Depth distribution: should have pubkeys at multiple depths
235 depthCounts := make(map[int]int)
236 for _, s := range set.Scores {
237 depthCounts[s.Depth]++
238 }
239 if len(depthCounts) < 2 {
240 t.Error("expected pubkeys at multiple depths")
241 }
242 t.Logf("depth distribution: %v", depthCounts)
243
244 // WoT scores should vary (not all zero)
245 nonZeroWoT := 0
246 for _, s := range set.Scores {
247 if s.WoTScore > 0 {
248 nonZeroWoT++
249 }
250 }
251 if nonZeroWoT == 0 {
252 t.Error("expected some non-zero WoT intersection scores")
253 }
254 t.Logf("non-zero WoT scores: %d/%d", nonZeroWoT, len(set.Scores))
255
256 // Influence scores should generally decrease with depth
257 var depth1Avg, depth2Avg float64
258 var d1Count, d2Count int
259 for _, s := range set.Scores {
260 if s.Depth == 1 {
261 depth1Avg += s.Influence
262 d1Count++
263 } else if s.Depth == 2 {
264 depth2Avg += s.Influence
265 d2Count++
266 }
267 }
268 if d1Count > 0 && d2Count > 0 {
269 depth1Avg /= float64(d1Count)
270 depth2Avg /= float64(d2Count)
271 if depth1Avg <= depth2Avg {
272 t.Errorf("expected depth-1 avg influence (%f) > depth-2 avg (%f)", depth1Avg, depth2Avg)
273 }
274 t.Logf("avg influence: depth1=%.4f, depth2=%.4f", depth1Avg, depth2Avg)
275 }
276 }
277
278 func TestComputeConvergenceStabilizes(t *testing.T) {
279 // Run with increasing cycle counts and verify scores stabilize
280 graph, _, obs := generateDeterministicGraph(50, 8, 10)
281
282 var prevScores map[string]float64
283 for cycles := 1; cycles <= 10; cycles++ {
284 store := newMockStore()
285 cfg := DefaultConfig()
286 cfg.MaxDepth = 3
287 cfg.Cycles = cycles
288 engine := NewEngine(graph, store, cfg)
289
290 set, err := engine.Compute(obs)
291 if err != nil {
292 t.Fatalf("cycle %d: unexpected error: %v", cycles, err)
293 }
294
295 currentScores := make(map[string]float64)
296 for _, s := range set.Scores {
297 currentScores[s.PubkeyHex] = s.Influence
298 }
299
300 if prevScores != nil && cycles >= 5 {
301 maxDelta := 0.0
302 for pk, score := range currentScores {
303 if prev, ok := prevScores[pk]; ok {
304 delta := math.Abs(score - prev)
305 if delta > maxDelta {
306 maxDelta = delta
307 }
308 }
309 }
310 if maxDelta > 0.01 {
311 t.Errorf("scores not stabilized by cycle %d, max delta: %f", cycles, maxDelta)
312 }
313 }
314 prevScores = currentScores
315 }
316 }
317
318 func TestObserverScoreImmutable(t *testing.T) {
319 // Even with many followers pointing back at observer, score stays 1.0
320 graph, pubkeys, obs := generateDeterministicGraph(30, 6, 10)
321 // Add reverse follows: everyone follows observer
322 for i := 1; i < len(pubkeys); i++ {
323 graph.addFollow(pubkeys[i], obs)
324 }
325
326 store := newMockStore()
327 engine := NewEngine(graph, store, DefaultConfig())
328
329 set, err := engine.Compute(obs)
330 if err != nil {
331 t.Fatalf("unexpected error: %v", err)
332 }
333
334 scores := scoreMap(set)
335 if s := scores[obs]; s == nil || s.Influence != 1.0 {
336 inf := 0.0
337 if s != nil {
338 inf = s.Influence
339 }
340 t.Errorf("observer influence should be exactly 1.0, got %f", inf)
341 }
342 }
343
344 func TestStorageRoundtrip(t *testing.T) {
345 graph, _, obs := generateDeterministicGraph(30, 5, 8)
346 store := newMockStore()
347 engine := NewEngine(graph, store, DefaultConfig())
348
349 computed, err := engine.Compute(obs)
350 if err != nil {
351 t.Fatalf("compute error: %v", err)
352 }
353
354 // Retrieve full set
355 retrieved, err := engine.GetScores(obs)
356 if err != nil {
357 t.Fatalf("GetScores error: %v", err)
358 }
359 if retrieved == nil {
360 t.Fatal("expected non-nil score set")
361 }
362 if retrieved.ObserverHex != obs {
363 t.Errorf("observer mismatch")
364 }
365 if len(retrieved.Scores) != len(computed.Scores) {
366 t.Errorf("score count mismatch: %d vs %d", len(retrieved.Scores), len(computed.Scores))
367 }
368
369 // Retrieve individual entries
370 for _, s := range computed.Scores {
371 entry, err := engine.GetScore(obs, s.PubkeyHex)
372 if err != nil {
373 t.Errorf("GetScore error for %s: %v", s.PubkeyHex[:12], err)
374 continue
375 }
376 if entry == nil {
377 t.Errorf("missing entry for %s", s.PubkeyHex[:12])
378 continue
379 }
380 if entry.Influence != s.Influence {
381 t.Errorf("influence mismatch for %s: %.6f vs %.6f", s.PubkeyHex[:12], entry.Influence, s.Influence)
382 }
383 }
384 }
385
386 func TestGetScoresUnknownObserver(t *testing.T) {
387 store := newMockStore()
388 graph := newMockGraph()
389 engine := NewEngine(graph, store, DefaultConfig())
390
391 rng := frand.NewCustom([]byte("unknown-observer-seed-padding!!X"), 1024, 12)
392 var buf [32]byte
393 rng.Read(buf[:])
394 unknown := bytesToHex(buf[:])
395
396 set, err := engine.GetScores(unknown)
397 if err != nil {
398 t.Fatalf("unexpected error: %v", err)
399 }
400 if set != nil {
401 t.Error("expected nil for unknown observer")
402 }
403 }
404
405 func TestCertaintyFormula(t *testing.T) {
406 rigor := 0.25
407 rigority := -math.Log(rigor)
408
409 // input=0 → certainty=0
410 c0 := 1 - math.Exp(-0.0*rigority)
411 if math.Abs(c0) > 1e-10 {
412 t.Errorf("certainty(0) should be 0, got %f", c0)
413 }
414
415 // input=high → certainty≈1
416 cHigh := 1 - math.Exp(-10.0*rigority)
417 if cHigh < 0.99 {
418 t.Errorf("certainty(10) should be near 1.0, got %f", cHigh)
419 }
420
421 // input=moderate → 0 < certainty < 1
422 cMid := 1 - math.Exp(-1.0*rigority)
423 if cMid <= 0 || cMid >= 1 {
424 t.Errorf("certainty(1) should be in (0,1), got %f", cMid)
425 }
426 }
427
428 func TestScoreSetJSON(t *testing.T) {
429 rng := frand.NewCustom([]byte("json-test-seed-padding-bytes!!!!"), 1024, 12)
430 var buf [32]byte
431 rng.Read(buf[:])
432 obs := bytesToHex(buf[:])
433 rng.Read(buf[:])
434 target := bytesToHex(buf[:])
435
436 set := ScoreSet{
437 ObserverHex: obs,
438 TotalPubkeys: 1,
439 Scores: []ScoreEntry{
440 {PubkeyHex: target, Influence: 0.5, Average: 0.8, Certainty: 0.625, Input: 0.1, WoTScore: 3, Depth: 1},
441 },
442 }
443
444 data, err := json.Marshal(set)
445 if err != nil {
446 t.Fatalf("marshal error: %v", err)
447 }
448
449 var decoded ScoreSet
450 if err := json.Unmarshal(data, &decoded); err != nil {
451 t.Fatalf("unmarshal error: %v", err)
452 }
453 if decoded.ObserverHex != obs {
454 t.Error("observer mismatch after roundtrip")
455 }
456 if len(decoded.Scores) != 1 {
457 t.Fatalf("expected 1 score, got %d", len(decoded.Scores))
458 }
459 if decoded.Scores[0].Influence != 0.5 {
460 t.Errorf("influence mismatch: %f", decoded.Scores[0].Influence)
461 }
462 if decoded.Scores[0].WoTScore != 3 {
463 t.Errorf("wot_score mismatch: %d", decoded.Scores[0].WoTScore)
464 }
465 }
466
467 func TestDefaultConfig(t *testing.T) {
468 cfg := DefaultConfig()
469 if cfg.MaxDepth != 6 {
470 t.Errorf("expected MaxDepth=6, got %d", cfg.MaxDepth)
471 }
472 if cfg.Cycles != 5 {
473 t.Errorf("expected Cycles=5, got %d", cfg.Cycles)
474 }
475 if cfg.AttenuationFactor != 0.8 {
476 t.Errorf("expected AttenuationFactor=0.8, got %f", cfg.AttenuationFactor)
477 }
478 if cfg.Rigor != 0.25 {
479 t.Errorf("expected Rigor=0.25, got %f", cfg.Rigor)
480 }
481 if cfg.FollowConfidence != 0.05 {
482 t.Errorf("expected FollowConfidence=0.05, got %f", cfg.FollowConfidence)
483 }
484 }
485
486 func TestComputeLargeGraph(t *testing.T) {
487 if testing.Short() {
488 t.Skip("skipping large graph test in short mode")
489 }
490
491 // 1000 users, observer follows 50, avg 15 follows each
492 graph, _, obs := generateDeterministicGraph(1000, 15, 50)
493 store := newMockStore()
494 cfg := DefaultConfig()
495 cfg.MaxDepth = 3
496 cfg.Cycles = 5
497 engine := NewEngine(graph, store, cfg)
498
499 set, err := engine.Compute(obs)
500 if err != nil {
501 t.Fatalf("unexpected error: %v", err)
502 }
503
504 t.Logf("large graph: %d pubkeys in hop set, %d scored, %dms",
505 set.TotalPubkeys, len(set.Scores), set.ComputeMs)
506
507 // Should discover most of the network via 3 hops in a connected graph
508 if set.TotalPubkeys < 100 {
509 t.Errorf("expected > 100 pubkeys in hop set with 1000 users, got %d", set.TotalPubkeys)
510 }
511
512 // Scores should be stored and retrievable
513 retrieved, err := engine.GetScores(obs)
514 if err != nil || retrieved == nil {
515 t.Fatal("failed to retrieve scores after large computation")
516 }
517
518 // Spot check: pick 5 random scores and verify individual lookup
519 rng := frand.NewCustom([]byte("spot-check-seed-padding-bytes!!!"), 1024, 12)
520 for i := 0; i < 5 && i < len(set.Scores); i++ {
521 idx := int(rng.Uint64n(uint64(len(set.Scores))))
522 entry, err := engine.GetScore(obs, set.Scores[idx].PubkeyHex)
523 if err != nil || entry == nil {
524 t.Errorf("spot check %d: failed to retrieve individual score", i)
525 continue
526 }
527 if entry.PubkeyHex != set.Scores[idx].PubkeyHex {
528 t.Errorf("spot check %d: pubkey mismatch", i)
529 }
530 }
531 }
532
533 // scoreMap converts a ScoreSet to a map for easy lookup.
534 func scoreMap(set *ScoreSet) map[string]*ScoreEntry {
535 m := make(map[string]*ScoreEntry, len(set.Scores))
536 for i := range set.Scores {
537 m[set.Scores[i].PubkeyHex] = &set.Scores[i]
538 }
539 return m
540 }
541
542 func BenchmarkCompute(b *testing.B) {
543 for _, size := range []int{50, 200, 500} {
544 b.Run(fmt.Sprintf("users=%d", size), func(b *testing.B) {
545 graph, _, obs := generateDeterministicGraph(size, 10, 15)
546 cfg := DefaultConfig()
547 cfg.MaxDepth = 3
548
549 b.ResetTimer()
550 for i := 0; i < b.N; i++ {
551 store := newMockStore()
552 engine := NewEngine(graph, store, cfg)
553 engine.Compute(obs)
554 }
555 })
556 }
557 }
558