1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
// The negentropy client (NIP-77, src/negentropy.js) on the wire as strfry
// and the reference implementation speak it: the opening message for a
// fixed set is byte-identical to the reference's (checked against
// hoytech/negentropy's JS on 2026-10-16: seven pairings of ours and theirs
// as client and relay agreed on every have/need), and a reconciliation
// against our own relay side finds exactly what each side lacks — in one
// round for a small difference, in several when the relay's frame is
// small — and ends with nothing to say once the sets match.
// Run: bun tools/negentropy-test.js
import assert from 'node:assert/strict';
import { createHash } from 'node:crypto';
import { NegSet, Negentropy } from '../src/negentropy.js';
const id = (n) => createHash('sha256').update('item-' + n).digest('hex');
const sha = (s) => createHash('sha256').update(s).digest('hex');
// the fixed sets the reference was run on
const A = Array.from({ length: 120 }, (_, i) => [1000 + Math.floor(i / 3), id(i)]);
const B = [...A.filter((_, i) => i % 17 !== 0), ...Array.from({ length: 9 }, (_, i) => [1000 + i * 4, id(1000 + i)])];
const first = await new Negentropy(new NegSet(A)).initiate();
assert.equal(first.length, 634, 'the opening message for the fixed set is 317 bytes');
assert.equal(first.slice(0, 2), '61', 'protocol version 1');
assert.equal(sha(first), 'c926c013652f6e2f727abff15c0838aebd7f613fb4749ee691952dfc8be8ff81', 'the opening message is the reference implementation\'s, byte for byte');
async function talk(client, relay) {
let msg = await client.initiate(), rounds = 0;
const have = [], need = [];
while (msg) {
rounds++;
const r = await relay.reconcile(msg);
assert(r.next, 'the relay side always answers');
const c = await client.reconcile(r.next);
have.push(...c.have); need.push(...c.need); msg = c.next;
}
return { rounds, have: have.sort(), need: need.sort() };
}
{
const r = await talk(new Negentropy(new NegSet(A)), new Negentropy(new NegSet(B)));
assert.equal(r.rounds, 1, 'a small difference reconciles in one round');
assert.deepEqual(r.have, A.filter((_, i) => i % 17 === 0).map((x) => x[1]).sort(), 'have: the ids the relay lacks');
assert.deepEqual(r.need, Array.from({ length: 9 }, (_, i) => id(1000 + i)).sort(), 'need: the ids we lack');
}
{
const r = await talk(new Negentropy(new NegSet(A)), new Negentropy(new NegSet(A)));
assert.equal(r.rounds, 1); assert.deepEqual(r.have, []); assert.deepEqual(r.need, []);
const r2 = await talk(new Negentropy(new NegSet([])), new Negentropy(new NegSet(B)));
assert.equal(r2.need.length, B.length, 'holding nothing, we need everything');
const r3 = await talk(new Negentropy(new NegSet(B)), new Negentropy(new NegSet([])));
assert.equal(r3.have.length, B.length, 'the relay holding nothing lacks everything');
}
{
// a big set and a relay with a small frame: many rounds, the same answer
const big = Array.from({ length: 3000 }, (_, i) => [1000 + i, id(i)]);
const theirs = [...big.filter((_, i) => i % 101 !== 0), ...Array.from({ length: 25 }, (_, i) => [1000 + i * 7, id(5000 + i)])];
const r = await talk(new Negentropy(new NegSet(big)), new Negentropy(new NegSet(theirs), { frameSizeLimit: 4096 }));
assert(r.rounds > 1, 'a small frame takes several rounds: ' + r.rounds);
assert.equal(r.have.length, 30); assert.equal(r.need.length, 25);
}
{
// the set drops duplicates and bad ids, and sorts by time then id
const s = new NegSet([[5, id(1)], [5, id(1)], [3, 'nope'], [4, id(2)], [5, id(0)]]);
assert.equal(s.size, 3);
assert.deepEqual(s.items.map((x) => x.ts), [4, 5, 5]);
}
console.log('✓ negentropy: the reference\'s bytes, one round for a small difference, several for a small frame, nothing to say when equal');
|
