From ed3c047bf3969f81488a2cf9cb52af009407f07f Mon Sep 17 00:00:00 2001 From: Adam Soltys Date: Fri, 16 Oct 2026 21:31:06 -0700 Subject: Negentropy (NIP-77): DM and notification catch-up fetch only what this device lacks. MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit A relay that speaks it compares the ids it holds for a filter with the ids we hold and answers with the difference — a few hundred bytes, one round — instead of re-serving its newest events every time we ask. Measured on relay.coinos.io: the DM subscription re-served 200 gift wraps (468 KB) on every boot and every resubscribe, the Notifications refresh 120 events (105 KB) a visit; a reconcile holding the newest 100 of 120 found the 20 missing in 1.8 KB and 41 ms. src/negentropy.js: the protocol (version 1, as strfry speaks it), a port of Doug Hoyte's reference client (MIT): NegSet of [created_at, id] items, Negentropy.initiate / reconcile → { next, have, need }, WebCrypto SHA-256. Byte-identical opening message to the reference's; seven pairings of ours and theirs as client and relay agreed on every have/need. src/nostr.js: reconcileOn(url, filter, items) on its own socket (the pool's parser has no ear for NEG-* frames) → { need, have } or null; a relay that doesn't speak it (NOTICE "negentropy disabled", CLOSED, a socket shut on the opening message, silence) is remembered for a day in coinos-neg-off, so the plain query goes straight out there next time; NEG-ERR blocked/closed is not remembered. syncOn(relays, filter, items): reconciliation where it works, the plain query where it doesn't, the ids we lack fetched by id in slices, each event once, verified. messages.js — DMs: relay by relay, one that speaks it gets the live subscription with limit 0 (opened first, so nothing slips between) and a reconcile of its newest 400 against wrapItems (the wraps held, full id and time, 600 kept beside the 16-char prefix log; a wrap the prefix log knows but the list doesn't is added as the relay re-serves it, once); nos.lol, with negentropy disabled, keeps the plain subscription with its backlog, and so does every relay while the one-time heal pass runs. Notifications: the refresh reconciles the relay's newest 120 against notifHeld (every notification event seen, 300 kept — not just the rows, or a folded zap twin would come back every visit), persisted beside the rows; the watch is unchanged. Not applied to feeds: the outbox relays mostly lack it (nos.lol, damus, primal, nostr.wine, nostr.mom, nostrplebs say no; relay.coinos.io, purplepag.es, ditto, oxtr, nostr21, offchain yes) and a first older page has nothing to reconcile against. Tests: tools/negentropy-test.js (the reference's bytes, one round for a small difference, eight for a 4 KB frame, nothing to say when equal); tools/negentropy-sync-test.js (an in-page relay speaking NEG with the library on its side: the wrap subscription opens limit 0 and the three wraps lacked are fetched by id, nos.lol's "disabled" gets the plain subscription and is remembered, the boot refresh fetches the three notifications by id and the page's refresh and a refresh after reload fetch nothing). notif-report-fold, notif-faces, dm-filter, dm-row-resort, dm-nip42 pass. Co-Authored-By: Claude Fable 5.1 Claude-Session: https://claude.ai/code/session_01J1Kon8bxJoHRpJdSzshCkp --- src/negentropy.js | 197 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 197 insertions(+) create mode 100644 src/negentropy.js (limited to 'src/negentropy.js') diff --git a/src/negentropy.js b/src/negentropy.js new file mode 100644 index 0000000..83f65ae --- /dev/null +++ b/src/negentropy.js @@ -0,0 +1,197 @@ +// Negentropy (NIP-77): set reconciliation with a relay. The client holds a +// set of (created_at, id) pairs — the events it already has for a filter — +// and the relay holds its own. Instead of the relay re-sending every event +// the filter matches (a DM catch-up re-served 200 gift wraps, half a +// megabyte, on every subscribe; a notification refresh a hundred kilobytes), +// the two sides exchange fingerprints of ranges of their sets, split the +// ranges that differ, and end with the ids each side lacks — a few hundred +// bytes, usually in one round. The events themselves are then fetched by id. +// +// Protocol version 1 (0x61), as strfry speaks it. A port of Doug Hoyte's +// reference client (github.com/hoytech/negentropy, MIT, © 2023), trimmed to +// the initiator's side plus what a test needs to play the relay. +// Hashing is WebCrypto SHA-256, so everything here is async. + +const PROTOCOL_VERSION = 0x61; +const ID_SIZE = 32; +const FINGERPRINT_SIZE = 16; +const MODE = { skip: 0, fingerprint: 1, idList: 2 }; +const MAX_TS = Number.MAX_SAFE_INTEGER; // "infinity": the bound past every item + +// ---- bytes ---------------------------------------------------------------- +const hexOf = (a) => { let s = ''; for (let i = 0; i < a.length; i++) s += (a[i] < 16 ? '0' : '') + a[i].toString(16); return s; }; +const bytesOf = (h) => { if (h instanceof Uint8Array) return h; if (h.length % 2) throw new Error('odd hex'); const a = new Uint8Array(h.length / 2); for (let i = 0; i < a.length; i++) a[i] = parseInt(h.substr(i * 2, 2), 16); return a; }; +const cmpBytes = (a, b) => { const n = Math.min(a.length, b.length); for (let i = 0; i < n; i++) { if (a[i] !== b[i]) return a[i] < b[i] ? -1 : 1; } return a.length === b.length ? 0 : a.length < b.length ? -1 : 1; }; +const cmpItem = (a, b) => (a.ts === b.ts ? cmpBytes(a.id, b.id) : a.ts < b.ts ? -1 : 1); + +class Out { + constructor() { this.parts = []; this.length = 0; } + push(a) { if (Array.isArray(a)) a = Uint8Array.from(a); this.parts.push(a); this.length += a.length; } + bytes() { const o = new Uint8Array(this.length); let p = 0; for (const a of this.parts) { o.set(a, p); p += a.length; } return o; } +} +class In { + constructor(a) { this.a = a; this.p = 0; } + get left() { return this.a.length - this.p; } + byte() { if (this.p >= this.a.length) throw new Error('negentropy: message ends early'); return this.a[this.p++]; } + take(n) { if (this.p + n > this.a.length) throw new Error('negentropy: message ends early'); const s = this.a.subarray(this.p, this.p + n); this.p += n; return s; } +} +// varints, big-endian 7-bit groups with a continuation bit (the protocol's) +const putVar = (o, n) => { if (n === 0) return o.push([0]); const g = []; while (n > 0) { g.push(n % 128); n = Math.floor(n / 128); } g.reverse(); for (let i = 0; i < g.length - 1; i++) g[i] |= 128; o.push(g); }; +const getVar = (i) => { let n = 0; for (;;) { const b = i.byte(); n = n * 128 + (b & 127); if (!(b & 128)) return n; } }; + +// ---- the fingerprint of a range: the ids summed mod 2^256, hashed with the count +const sha256 = async (bytes) => new Uint8Array(await crypto.subtle.digest('SHA-256', bytes)); +function addInto(acc, id) { + let carry = 0; + for (let i = 0; i < ID_SIZE; i++) { const s = acc[i] + id[i] + carry; acc[i] = s & 255; carry = s >> 8; } +} +async function fingerprint(items, begin, end) { + const acc = new Uint8Array(ID_SIZE); + for (let i = begin; i < end; i++) addInto(acc, items[i].id); + const o = new Out(); o.push(acc); putVar(o, end - begin); + return (await sha256(o.bytes())).subarray(0, FINGERPRINT_SIZE); +} + +// ---- the set ---------------------------------------------------------------- +// `items`: [[created_at, id hex], ...] in any order; duplicates are dropped. +export class NegSet { + constructor(items = []) { + const seen = new Set(); + this.items = []; + for (const [ts, id] of items) { + if (typeof id !== 'string' || id.length !== 64 || seen.has(id)) continue; + seen.add(id); + this.items.push({ ts: Math.max(0, Math.floor(ts || 0)), id: bytesOf(id) }); + } + this.items.sort(cmpItem); + } + get size() { return this.items.length; } + // the first index in [begin, end) at or past the bound + lowerBound(begin, end, bound) { + let lo = begin, hi = end; + while (lo < hi) { const m = (lo + hi) >> 1; if (cmpItem(this.items[m], bound) < 0) lo = m + 1; else hi = m; } + return lo; + } +} + +// ---- one side of a reconciliation ------------------------------------------ +export class Negentropy { + constructor(set, { frameSizeLimit = 0 } = {}) { + if (frameSizeLimit && frameSizeLimit < 4096) throw new Error('negentropy: frame size limit too small'); + this.set = set; + this.frameSizeLimit = frameSizeLimit; + this.initiator = false; + this.lastTsIn = 0; this.lastTsOut = 0; + } + // the client's opening message (hex) + async initiate() { + this.initiator = true; + const o = new Out(); o.push([PROTOCOL_VERSION]); + await this.splitRange(0, this.set.size, { ts: MAX_TS, id: new Uint8Array(0) }, o); + return hexOf(o.bytes()); + } + // One message in, one out. For the initiator the answer is null once the + // sets are reconciled; `have` are ids we hold that the other side lacks, + // `need` the ones it holds that we lack. The non-initiator (a relay, or + // a test playing one) always answers and collects nothing. + async reconcile(hex) { + const q = new In(bytesOf(hex)); + const have = [], need = []; + this.lastTsIn = this.lastTsOut = 0; + const full = new Out(); full.push([PROTOCOL_VERSION]); + const version = q.byte(); + if (version < 0x60 || version > 0x6f) throw new Error('negentropy: not a negentropy message'); + if (version !== PROTOCOL_VERSION) { + if (this.initiator) throw new Error('negentropy: unsupported protocol version ' + (version - 0x60)); + return { next: hexOf(full.bytes()), have, need }; + } + const items = this.set.items, size = this.set.size; + let prevBound = { ts: 0, id: new Uint8Array(0) }, prevIndex = 0, skip = false; + while (q.left) { + const o = new Out(); + const doSkip = () => { if (skip) { skip = false; this.putBound(o, prevBound); putVar(o, MODE.skip); } }; + const bound = this.getBound(q); + const mode = getVar(q); + const lower = prevIndex; + let upper = this.set.lowerBound(prevIndex, size, bound); + if (mode === MODE.skip) skip = true; + else if (mode === MODE.fingerprint) { + const theirs = q.take(FINGERPRINT_SIZE); + const ours = await fingerprint(items, lower, upper); + if (cmpBytes(theirs, ours) !== 0) { doSkip(); await this.splitRange(lower, upper, bound, o); } + else skip = true; + } else if (mode === MODE.idList) { + const n = getVar(q); + const theirs = new Map(); + for (let i = 0; i < n; i++) { const id = q.take(ID_SIZE); if (this.initiator) theirs.set(hexOf(id), id); } + if (this.initiator) { + skip = true; + for (let i = lower; i < upper; i++) { + const k = hexOf(items[i].id); + if (theirs.has(k)) theirs.delete(k); else have.push(k); + } + for (const k of theirs.keys()) need.push(k); + } else { + doSkip(); + const ids = new Out(); let count = 0, endBound = bound; + for (let i = lower; i < upper; i++) { + if (this.overFrame(full.length + ids.length)) { endBound = items[i]; upper = i; break; } + ids.push(items[i].id); count++; + } + this.putBound(o, endBound); putVar(o, MODE.idList); putVar(o, count); o.push(ids.bytes()); + full.push(o.bytes()); o.parts = []; o.length = 0; + } + } else throw new Error('negentropy: unexpected mode ' + mode); + if (this.overFrame(full.length + o.length)) { + // the frame is full: one fingerprint for everything left + const rest = await fingerprint(items, upper, size); + this.putBound(full, { ts: MAX_TS, id: new Uint8Array(0) }); putVar(full, MODE.fingerprint); full.push(rest); + break; + } + full.push(o.bytes()); + prevIndex = upper; prevBound = bound; + } + return { next: full.length === 1 && this.initiator ? null : hexOf(full.bytes()), have, need }; + } + // a range that differs: sixteen fingerprinted buckets, or the ids outright when small + async splitRange(lower, upper, upperBound, o) { + const items = this.set.items, n = upper - lower, buckets = 16; + if (n < buckets * 2) { + this.putBound(o, upperBound); putVar(o, MODE.idList); putVar(o, n); + for (let i = lower; i < upper; i++) o.push(items[i].id); + return; + } + const per = Math.floor(n / buckets), extra = n % buckets; + let cur = lower; + for (let b = 0; b < buckets; b++) { + const size = per + (b < extra ? 1 : 0); + const fp = await fingerprint(items, cur, cur + size); + cur += size; + const next = cur === upper ? upperBound : minimalBound(items[cur - 1], items[cur]); + this.putBound(o, next); putVar(o, MODE.fingerprint); o.push(fp); + } + } + overFrame(n) { return !!this.frameSizeLimit && n > this.frameSizeLimit - 200; } + // bounds: a timestamp as a delta from the last one (+1; 0 = infinity), then a prefix of an id + getBound(q) { + let ts = getVar(q); + ts = ts === 0 ? MAX_TS : ts - 1; + if (this.lastTsIn === MAX_TS || ts === MAX_TS) { this.lastTsIn = MAX_TS; ts = MAX_TS; } + else { ts += this.lastTsIn; this.lastTsIn = ts; } + const len = getVar(q); + if (len > ID_SIZE) throw new Error('negentropy: bound key too long'); + return { ts, id: q.take(len) }; + } + putBound(o, b) { + if (b.ts === MAX_TS) { this.lastTsOut = MAX_TS; putVar(o, 0); } + else { putVar(o, b.ts - this.lastTsOut + 1); this.lastTsOut = b.ts; } + putVar(o, b.id.length); o.push(b.id); + } +} +// the shortest bound that separates two neighbouring items +function minimalBound(prev, cur) { + if (cur.ts !== prev.ts) return { ts: cur.ts, id: new Uint8Array(0) }; + let shared = 0; + while (shared < ID_SIZE && cur.id[shared] === prev.id[shared]) shared++; + return { ts: cur.ts, id: cur.id.subarray(0, shared + 1) }; +} -- cgit v1.2.3