| 1 | // NIP-77 Negentropy v1: range-based set reconciliation used by the |
| 2 | // conformance client. Both sides hold a sorted (timestamp, |
| 3 | // id) list and exchange ranges carrying fingerprints or id lists until the |
| 4 | // initiator knows exactly which ids each side is missing. |
| 5 | |
| 6 | export interface SyncItem { |
| 7 | timestamp: number; // unix seconds |
| 8 | id: Uint8Array; // 32 bytes |
| 9 | } |
| 10 | |
| 11 | const VERSION = 0x61; |
| 12 | const MODE_SKIP = 0n; |
| 13 | const MODE_FP = 1n; |
| 14 | const MODE_IDLIST = 2n; |
| 15 | const INFINITY = (1n << 64n) - 1n; |
| 16 | const BUCKETS = 16; |
| 17 | export const FRAME_SIZE = 60_000; |
| 18 | |
| 19 | interface Bound { |
| 20 | ts: bigint; |
| 21 | id: Uint8Array; // 32 bytes, zero padded |
| 22 | len: number; // significant prefix bytes |
| 23 | } |
| 24 | |
| 25 | const ZERO32 = new Uint8Array(32); |
| 26 | |
| 27 | function 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 | } |
| 33 | |
| 34 | export 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 | } |
| 38 | |
| 39 | export 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 | } |
| 44 | |
| 45 | export 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 | } |
| 50 | |
| 51 | class 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 | } |
| 72 | |
| 73 | class 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 | } |
| 95 | |
| 96 | export class Negentropy { |
| 97 | items: SyncItem[]; |
| 98 | initiator = false; |
| 99 | frame = FRAME_SIZE; |
| 100 | private lastIn = 0n; |
| 101 | private lastOut = 0n; |
| 102 | |
| 103 | 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 | } |
| 106 | |
| 107 | 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 | } |
| 115 | |
| 116 | // Returns the reply (null when an initiator is done) and, for the |
| 117 | // 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 | }; |
| 141 | |
| 142 | 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); |
| 147 | |
| 148 | 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; |
| 197 | |
| 198 | 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 | } |
| 209 | |
| 210 | 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 | } |
| 232 | |
| 233 | 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 | } |
| 249 | |
| 250 | 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 | } |
| 263 | |
| 264 | 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 | } |
| 275 | |
| 276 | 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 | } |
| 292 | |
| 293 | export 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 | } |
| 301 | |
| 302 | export function encodeVarint(v: bigint): Uint8Array { |
| 303 | const w = new Writer(); |
| 304 | w.varint(v); |
| 305 | return w.toBytes(); |
| 306 | } |