1 // Package negentropy implements NIP-77 negentropy-based set reconciliation.
2 // It provides efficient synchronization between two sets of Nostr events
3 // by exchanging fingerprints and identifying missing items.
4 package negentropy
5 6 import (
7 "encoding/hex"
8 "fmt"
9 )
10 11 // Mode represents the type of range in the negentropy protocol.
12 type Mode uint8
13 14 const (
15 // ModeSkip indicates the range should be skipped (already in sync).
16 ModeSkip Mode = 0
17 // ModeFingerprint indicates the range is represented by a fingerprint.
18 ModeFingerprint Mode = 1
19 // ModeIdList indicates the range contains an explicit list of IDs.
20 ModeIdList Mode = 2
21 )
22 23 // ProtocolVersion is the negentropy protocol version byte.
24 const ProtocolVersion byte = 0x61 // Version 1
25 26 // DefaultFrameSizeLimit is the default maximum message size.
27 // Set to 4MB to reduce round-trip count for large syncs (206k+ events).
28 // WebSocket max message size is typically 10MB, so 4MB is well within bounds.
29 const DefaultFrameSizeLimit = 4 * 1024 * 1024 // 4MB
30 31 // DefaultIDSize is the fingerprint size (16 bytes).
32 const DefaultIDSize = 16
33 34 // FullIDSize is the size of a full event ID (32 bytes).
35 // Used for ID lists in the negentropy protocol.
36 const FullIDSize = 32
37 38 // Item represents a single item in the negentropy set.
39 // Items are sorted by timestamp first, then by ID.
40 type Item struct {
41 Timestamp int64 // Unix timestamp in seconds
42 ID string // 32-byte event ID as hex string (64 chars)
43 }
44 45 // Compare compares two items for sorting.
46 // Returns -1 if a < b, 0 if a == b, 1 if a > b.
47 func (a Item) Compare(b Item) int {
48 if a.Timestamp < b.Timestamp {
49 return -1
50 }
51 if a.Timestamp > b.Timestamp {
52 return 1
53 }
54 // Timestamps equal, compare IDs lexicographically
55 if a.ID < b.ID {
56 return -1
57 }
58 if a.ID > b.ID {
59 return 1
60 }
61 return 0
62 }
63 64 // String returns a string representation of the item.
65 func (i Item) String() string {
66 return fmt.Sprintf("Item{ts=%d, id=%s}", i.Timestamp, truncateID(i.ID))
67 }
68 69 // Bound represents a boundary in the negentropy range.
70 type Bound struct {
71 Item
72 }
73 74 // MinBound returns the minimum possible bound.
75 func MinBound() Bound {
76 return Bound{Item{Timestamp: 0, ID: ""}}
77 }
78 79 // MaxBound returns the maximum possible bound.
80 func MaxBound() Bound {
81 return Bound{Item{Timestamp: MaxTimestamp, ID: ""}}
82 }
83 84 // MaxTimestamp is the maximum timestamp value.
85 const MaxTimestamp int64 = 1<<62 - 1
86 87 // IsMin returns true if this is the minimum bound.
88 func (b Bound) IsMin() bool {
89 return b.Timestamp == 0 && b.ID == ""
90 }
91 92 // IsMax returns true if this is the maximum bound.
93 func (b Bound) IsMax() bool {
94 return b.Timestamp == MaxTimestamp
95 }
96 97 // String returns a string representation of the bound.
98 func (b Bound) String() string {
99 if b.IsMin() {
100 return "Bound{MIN}"
101 }
102 if b.IsMax() {
103 return "Bound{MAX}"
104 }
105 return fmt.Sprintf("Bound{ts=%d, id=%s}", b.Timestamp, truncateID(b.ID))
106 }
107 108 // truncateID truncates an ID for display purposes.
109 func truncateID(id string) string {
110 if len(id) > 16 {
111 return id[:8] + "..." + id[len(id)-4:]
112 }
113 return id
114 }
115 116 // Fingerprint represents a 16-byte fingerprint of a range.
117 type Fingerprint [DefaultIDSize]byte
118 119 // String returns the hex representation of the fingerprint.
120 func (f Fingerprint) String() string {
121 return hex.EncodeToString(f[:])
122 }
123 124 // EmptyFingerprint is a zero fingerprint.
125 var EmptyFingerprint = Fingerprint{}
126 127 // XOR combines two fingerprints using XOR.
128 func (f Fingerprint) XOR(other Fingerprint) Fingerprint {
129 var result Fingerprint
130 for i := 0; i < DefaultIDSize; i++ {
131 result[i] = f[i] ^ other[i]
132 }
133 return result
134 }
135