1 files changed, 197 insertions, 0 deletions
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) };
+}