*/
.highlight .vc { color: #369 } /* Name.Variable.Class */
.highlight .vg { color: #D70 } /* Name.Variable.Global */
.highlight .vi { color: #33B } /* Name.Variable.Instance */
.highlight .vm { color: #369 } /* Name.Variable.Magic */
.highlight .il { color: #00D; font-weight: bold } /* Literal.Number.Integer.Long */// 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) };
}
