1// NIP-77 Negentropy v1: range-based set reconciliation. A port of the Go2// implementation in the root package; both sides hold a sorted (timestamp,3// id) list and exchange ranges carrying fingerprints or id lists until the4// initiator knows exactly which ids each side is missing.56export interface SyncItem {7 timestamp: number; // unix seconds8 id: Uint8Array; // 32 bytes9}1011const VERSION = 0x61;12const MODE_SKIP = 0n;13const MODE_FP = 1n;14const MODE_IDLIST = 2n;15const INFINITY = (1n << 64n) - 1n;16const BUCKETS = 16;17export const FRAME_SIZE = 60_000;1819interface Bound {20 ts: bigint;21 id: Uint8Array; // 32 bytes, zero padded22 len: number; // significant prefix bytes23}2425const ZERO32 = new Uint8Array(32);2627function cmpBytes(a: Uint8Array, b: Uint8Array): number {28 for (let i = 0; i < 32; i++) {29 if (a[i] !== b[i]) return a[i] < b[i] ? -1 : 1;30 }31 return 0;32}3334export function itemLess(a: SyncItem, b: SyncItem): boolean {35 if (a.timestamp !== b.timestamp) return a.timestamp < b.timestamp;36 return cmpBytes(a.id, b.id) < 0;37}3839export function hexToBytes(h: string): Uint8Array {40 const out = new Uint8Array(h.length / 2);41 for (let i = 0; i < out.length; i++) out[i] = parseInt(h.substr(i * 2, 2), 16);42 return out;43}4445export function bytesToHex(b: Uint8Array): string {46 let s = "";47 for (const x of b) s += x.toString(16).padStart(2, "0");48 return s;49}5051class Writer {52 parts: number[] = [];53 varint(v: bigint) {54 const digits: number[] = [];55 do {56 digits.unshift(Number(v & 0x7fn));57 v >>= 7n;58 } while (v > 0n);59 for (let i = 0; i < digits.length - 1; i++) digits[i] |= 0x80;60 this.parts.push(...digits);61 }62 bytes(b: Uint8Array) {63 for (const x of b) this.parts.push(x);64 }65 get length() {66 return this.parts.length;67 }68 toBytes() {69 return new Uint8Array(this.parts);70 }71}7273class Reader {74 pos = 0;75 constructor(private buf: Uint8Array) {}76 get remaining() {77 return this.buf.length - this.pos;78 }79 varint(): bigint {80 let v = 0n;81 for (let i = 0; ; i++) {82 if (this.pos >= this.buf.length || i === 10) throw new Error("bad varint");83 const b = this.buf[this.pos++];84 v = (v << 7n) | BigInt(b & 0x7f);85 if ((b & 0x80) === 0) return v;86 }87 }88 bytes(n: number): Uint8Array {89 if (this.remaining < n) throw new Error("truncated message");90 const out = this.buf.subarray(this.pos, this.pos + n);91 this.pos += n;92 return out;93 }94}9596export class Negentropy {97 items: SyncItem[];98 initiator = false;99 frame = FRAME_SIZE;100 private lastIn = 0n;101 private lastOut = 0n;102103 constructor(items: SyncItem[], private sha256: (b: Uint8Array) => Uint8Array) {104 this.items = [...items].sort((a, b) => (itemLess(a, b) ? -1 : itemLess(b, a) ? 1 : 0));105 }106107 initiate(): Uint8Array {108 this.initiator = true;109 this.lastOut = 0n;110 const w = new Writer();111 w.parts.push(VERSION);112 this.splitRange(0, this.items.length, { ts: INFINITY, id: ZERO32, len: 0 }, w);113 return w.toBytes();114 }115116 // Returns the reply (null when an initiator is done) and, for the117 // initiator, the ids only we have and the ids only the peer has.118 reconcile(msg: Uint8Array): { reply: Uint8Array | null; have: string[]; need: string[] } {119 const have: string[] = [];120 const need: string[] = [];121 if (msg.length === 0) throw new Error("empty message");122 if (msg[0] !== VERSION) {123 if (this.initiator) throw new Error("peer does not support protocol v1");124 return { reply: new Uint8Array([VERSION]), have, need };125 }126 const r = new Reader(msg.subarray(1));127 this.lastIn = 0n;128 this.lastOut = 0n;129 const out = new Writer();130 out.parts.push(VERSION);131 let prevBound: Bound = { ts: 0n, id: ZERO32, len: 0 };132 let prevIndex = 0;133 let pendingSkip = false;134 const flushSkip = () => {135 if (pendingSkip) {136 pendingSkip = false;137 this.writeBound(out, prevBound);138 out.varint(MODE_SKIP);139 }140 };141142 while (r.remaining > 0) {143 let bound = this.readBound(r);144 const mode = r.varint();145 const lower = prevIndex;146 let upper = this.findUpper(lower, bound);147148 if (mode === MODE_SKIP) {149 pendingSkip = true;150 } else if (mode === MODE_FP) {151 const theirs = r.bytes(16);152 const ours = this.fingerprint(lower, upper);153 let same = true;154 for (let i = 0; i < 16; i++) if (theirs[i] !== ours[i]) same = false;155 if (same) pendingSkip = true;156 else {157 flushSkip();158 this.splitRange(lower, upper, bound, out);159 }160 } else if (mode === MODE_IDLIST) {161 const count = Number(r.varint());162 const theirs = new Map<string, true>();163 for (let i = 0; i < count; i++) theirs.set(bytesToHex(r.bytes(32)), true);164 if (this.initiator) {165 pendingSkip = true;166 for (let i = lower; i < upper; i++) {167 const h = bytesToHex(this.items[i].id);168 if (theirs.has(h)) theirs.delete(h);169 else have.push(h);170 }171 for (const h of theirs.keys()) need.push(h);172 } else {173 flushSkip();174 let end = bound;175 const ids: number[] = [];176 let cnt = 0;177 for (let i = lower; i < upper; i++) {178 if (out.length + ids.length > this.frame) {179 end = { ts: BigInt(this.items[i].timestamp), id: this.items[i].id, len: 32 };180 upper = i;181 break;182 }183 ids.push(...this.items[i].id);184 cnt++;185 }186 this.writeBound(out, end);187 out.varint(MODE_IDLIST);188 out.varint(BigInt(cnt));189 out.parts.push(...ids);190 bound = end;191 }192 } else {193 throw new Error("unknown range mode");194 }195 prevIndex = upper;196 prevBound = bound;197198 if (out.length > this.frame) {199 flushSkip();200 this.writeBound(out, { ts: INFINITY, id: ZERO32, len: 0 });201 out.varint(MODE_FP);202 out.bytes(this.fingerprint(upper, this.items.length));203 break;204 }205 }206 if (this.initiator && out.length === 1) return { reply: null, have, need };207 return { reply: out.toBytes(), have, need };208 }209210 private splitRange(lower: number, upper: number, bound: Bound, out: Writer) {211 const count = upper - lower;212 if (count < BUCKETS * 2) {213 this.writeBound(out, bound);214 out.varint(MODE_IDLIST);215 out.varint(BigInt(count));216 for (let i = lower; i < upper; i++) out.bytes(this.items[i].id);217 return;218 }219 const per = Math.floor(count / BUCKETS);220 const extra = count % BUCKETS;221 let cur = lower;222 for (let i = 0; i < BUCKETS; i++) {223 const size = per + (i < extra ? 1 : 0);224 const fp = this.fingerprint(cur, cur + size);225 cur += size;226 const next = cur < upper ? minimalBound(this.items[cur - 1], this.items[cur]) : bound;227 this.writeBound(out, next);228 out.varint(MODE_FP);229 out.bytes(fp);230 }231 }232233 fingerprint(lower: number, upper: number): Uint8Array {234 const sum = new Uint8Array(32);235 for (let i = lower; i < upper; i++) {236 let carry = 0;237 const id = this.items[i].id;238 for (let j = 0; j < 32; j++) {239 const v = sum[j] + id[j] + carry;240 sum[j] = v & 0xff;241 carry = v >> 8;242 }243 }244 const w = new Writer();245 w.bytes(sum);246 w.varint(BigInt(upper - lower));247 return this.sha256(w.toBytes()).subarray(0, 16);248 }249250 private findUpper(lower: number, b: Bound): number {251 let lo = lower;252 let hi = this.items.length;253 while (lo < hi) {254 const mid = (lo + hi) >> 1;255 const it = this.items[mid];256 const ts = BigInt(it.timestamp);257 const below = ts !== b.ts ? ts < b.ts : cmpBytes(it.id, b.id) < 0;258 if (below) lo = mid + 1;259 else hi = mid;260 }261 return lo;262 }263264 private writeBound(w: Writer, b: Bound) {265 if (b.ts === INFINITY) {266 this.lastOut = INFINITY;267 w.varint(0n);268 } else {269 w.varint(b.ts - this.lastOut + 1n);270 this.lastOut = b.ts;271 }272 w.varint(BigInt(b.len));273 w.bytes(b.id.subarray(0, b.len));274 }275276 private readBound(r: Reader): Bound {277 const v = r.varint();278 let ts: bigint;279 if (v === 0n) ts = INFINITY;280 else {281 ts = this.lastIn + v - 1n;282 if (ts < this.lastIn || ts > INFINITY) ts = INFINITY;283 }284 this.lastIn = ts;285 const len = Number(r.varint());286 if (len > 32) throw new Error("bound id prefix too long");287 const id = new Uint8Array(32);288 id.set(r.bytes(len));289 return { ts, id, len };290 }291}292293export function minimalBound(prev: SyncItem, cur: SyncItem): Bound {294 if (cur.timestamp !== prev.timestamp) return { ts: BigInt(cur.timestamp), id: ZERO32, len: 0 };295 let shared = 0;296 while (shared < 32 && prev.id[shared] === cur.id[shared]) shared++;297 const id = new Uint8Array(32);298 id.set(cur.id.subarray(0, shared + 1));299 return { ts: BigInt(cur.timestamp), id, len: shared + 1 };300}301302export function encodeVarint(v: bigint): Uint8Array {303 const w = new Writer();304 w.varint(v);305 return w.toBytes();306}