"""Negentropy V1: the set reconciliation NIP-77 standardises, over a MeshStore.
The specification makes NIP-77 a hard prerequisite for peering and defines no
reconciliation of its own, so this is an implementation of somebody else's
protocol rather than a definition of ours. It follows
negentropy/docs/negentropy-protocol-v1.md.
Two halves, and only one of them is normative:
the wire format protocol byte 0x61, ranges of (upper bound, mode, payload),
delta-encoded timestamps, minimal id prefixes. Two
implementations MUST agree here byte for byte.
the split how a differing range is divided, and when to stop
splitting and just list the ids. The document does not
specify it, deliberately: any split interoperates as long
as the ranges stay adjacent and cover the whole space.
The constants below are therefore *this implementation's* choices, not the
protocol's, and are marked as such. Getting them wrong costs round trips and
bytes; it cannot cost correctness.
Standard library only.
Verified against hoytech's reference implementation.
scripts/check-negentropy.py drives fleetmesh_core/conformance/harness.py and the reference's own
test/js/harness.js through the negentropy project's conformance protocol, in
both directions, over the record distributions its fuzzer uses. Also verified
here: the encoder and decoder round trip, the frames match hand-computed bytes
in vectors/negentropy.json, and two stores holding different sets converge.
"""
from __future__ import annotations
import bisect
from typing import Any, Iterable, Optional, Sequence, TypedDict
from . import replication
from ..conformance.errors import FleetmeshError
[docs]class ReconcileReport(TypedDict):
have: list[str]
need: list[str]
rounds: int
bytes_sent: int
bytes_received: int
bytes: int
VERSION: int = 0x61
VERSION_MIN: int = 0x60
VERSION_MAX: int = 0x6F # the byte range reserved for versions
INFINITY: int = 2 ** 64 - 1
FINGERPRINT_BYTES: int = 16
ID_BYTES: int = 32
SKIP: int = 0
FINGERPRINT: int = 1
ID_LIST: int = 2
[docs]class UnsupportedVersion(FleetmeshError, ValueError):
"""A negentropy message in a version this code does not speak.
Not an error on the wire. A server answers it with the highest version it
does speak, which is the only way a client can find out to downgrade.
"""
[docs] def __init__(self, version: int) -> None:
super().__init__('negentropy protocol version %d' % (version - 0x60))
self.version = version
# Not normative: how far to split before giving up and listing ids. Sixteen is
# what the reference implementation uses; below twice that, a list is cheaper
# than another round trip.
BUCKETS: int = 16
LIST_THRESHOLD: int = BUCKETS * 2
# ------------------------------------------------------------------ varint --
[docs]def encode_varint(n: int) -> bytes:
return replication.varint(n)
[docs]def decode_varint(buf: bytes, i: int) -> tuple[int, int]:
n = 0
for _ in range(10):
if i >= len(buf):
raise Malformed('message ends inside a varint')
b = buf[i]
i += 1
n = (n << 7) | (b & 0x7F)
if not b & 0x80:
if n > INFINITY:
raise Malformed('varint exceeds 64 bits')
return n, i
raise Malformed('varint exceeds 64 bits')
# ------------------------------------------------------------------- bound --
[docs]class Bound:
"""An exclusive upper bound: a timestamp and a disambiguating id prefix.
Omitted trailing prefix bytes are implicitly zero, so a bound compares as
(timestamp, prefix padded to 32 bytes) against an item's (timestamp, id).
"""
__slots__ = ('timestamp', 'prefix')
[docs] def __init__(self, timestamp: int, prefix: bytes = b'') -> None:
self.timestamp = timestamp
self.prefix = prefix
[docs] def key(self) -> tuple[int, bytes]:
return (self.timestamp, self.prefix + b'\x00' * (32 - len(self.prefix)))
def __eq__(self, other: Any) -> bool:
if not isinstance(other, Bound):
return False
return (self.timestamp, self.prefix) == (other.timestamp, other.prefix)
def __repr__(self) -> str:
ts = 'infinity' if self.timestamp == INFINITY else self.timestamp
return 'Bound(%s, %s)' % (ts, self.prefix.hex() or '-')
[docs]def minimal_bound(prev_item: Optional[tuple[int, str]], item: tuple[int, str]) -> Bound:
"""The shortest bound separating two adjacent items.
Per the protocol: if the timestamps differ the prefix is empty, otherwise it
is their common id prefix plus one byte. Sending more than that is legal and
wasteful; sending less is wrong, because the bound would not separate them.
"""
if prev_item is None or prev_item[0] != item[0]:
return Bound(item[0])
a, b = bytes.fromhex(prev_item[1]), bytes.fromhex(item[1])
n = 0
while n < 32 and a[n] == b[n]:
n += 1
return Bound(item[0], b[:n + 1])
# ----------------------------------------------------------------- message --
[docs]def encode_message(ranges: Sequence[tuple[Bound, int, Any]]) -> bytes:
"""ranges: [(upper Bound, mode, payload)] in ascending order."""
out = bytearray([VERSION])
prev_ts = 0
for upper, mode, payload in ranges:
if upper.timestamp == INFINITY:
out += encode_varint(0)
else:
out += encode_varint(1 + upper.timestamp - prev_ts)
prev_ts = upper.timestamp
out += encode_varint(len(upper.prefix)) + upper.prefix
out += encode_varint(mode)
if mode == FINGERPRINT:
out += payload
elif mode == ID_LIST:
out += encode_varint(len(payload))
for i in payload:
out += bytes.fromhex(i)
return bytes(out)
def _take(buf: bytes, i: int, n: int, what: str) -> tuple[bytes, int]:
"""n bytes, or the message was truncated.
Slicing past the end of a bytes object returns what is there rather than
failing, which is how a truncated id list became an empty id string that a
caller then went looking for. Every fixed-width field goes through here.
"""
if i + n > len(buf):
raise Malformed('message ends inside %s: wanted %d bytes, %d left'
% (what, n, len(buf) - i))
return buf[i:i + n], i + n
[docs]def decode_message(buf: bytes) -> list[tuple[Bound, int, Any]]:
"""Bytes to ranges, or an exception. Never a partial parse.
A message arrives from a peer that has proved nothing yet, so this rejects
rather than repairs. The reference implementation makes the same choices,
and where it normalises instead of rejecting - a bound after infinity - so
does this, because two implementations that read the same bytes differently
is the failure this whole module exists to avoid.
"""
if not buf:
raise Malformed('empty message')
if not VERSION_MIN <= buf[0] <= VERSION_MAX:
raise Malformed('not a negentropy message (first byte %#04x)' % buf[0])
if buf[0] != VERSION:
raise UnsupportedVersion(buf[0])
i, prev_ts, ranges = 1, 0, []
while i < len(buf):
enc, i = decode_varint(buf, i)
if enc == 0 or prev_ts == INFINITY:
# Once a bound is infinity every later bound is too. The offsets
# that follow have nothing left to be an offset from.
ts = prev_ts = INFINITY
else:
ts = prev_ts = prev_ts + enc - 1
n, i = decode_varint(buf, i)
if n > ID_BYTES:
raise Malformed('bound prefix of %d bytes is longer than an id' % n)
prefix, i = _take(buf, i, n, 'a bound prefix')
mode, i = decode_varint(buf, i)
# The payload's shape is the mode's: nothing, 16 bytes, or a list of
# hex ids. One name for three shapes is why it is typed as Any.
payload: Any
if mode == SKIP:
payload = None
elif mode == FINGERPRINT:
payload, i = _take(buf, i, FINGERPRINT_BYTES, 'a fingerprint')
elif mode == ID_LIST:
count, i = decode_varint(buf, i)
ids: list[str] = []
for _ in range(count):
eid, i = _take(buf, i, ID_BYTES, 'an id list')
ids.append(eid.hex())
payload = ids
else:
raise Malformed('unknown range mode %d' % mode)
ranges.append((Bound(ts, prefix), mode, payload))
return ranges
[docs]def fingerprint(items: Sequence[tuple[int, str]]) -> bytes:
"""NIP-77's, over the ids in order-independent fashion. fleetmesh_core/storage/replication.py
owns the algorithm; this exists so the caller reads in terms of items."""
return bytes.fromhex(replication.fingerprint([i[1] for i in items]))
def _coalesce_skips(ranges: Sequence[tuple[Bound, int, Any]]) -> list[tuple[Bound, int, Any]]:
"""Adjacent Skips are one Skip. Purely a saving: a run of them says exactly
what the last one says, and a reconciliation that has almost converged is
mostly Skips."""
out: list[tuple[Bound, int, Any]] = []
for upper, mode, payload in ranges:
if mode == SKIP and out and out[-1][1] == SKIP:
out[-1] = (upper, SKIP, None)
else:
out.append((upper, mode, payload))
return out
[docs]class Negentropy:
"""One side of a reconciliation.
items are (timestamp, id-hex), sorted ascending by (timestamp, id) - which
is the order MeshStore.enumerate_range already returns, deliberately.
Only the client learns anything: reconcile() returns the ids it holds that
the server does not, and the ids the server holds that it does not. The
server answers and learns nothing, which is why a leaf can reconcile against
an anchor without telling it what a phone contains.
"""
[docs] def __init__(self, items: Iterable[tuple[int, str]], is_client: bool = True) -> None:
self.items: list[tuple[int, str]] = sorted(items)
self.is_client: bool = is_client
seen: set[str] = set()
for _, i in self.items:
if i in seen:
raise ValueError('duplicate id %s' % i[:16])
seen.add(i)
# The same (timestamp, id bytes) key a Bound compares against, computed
# once. Every range of every round used to walk the whole list decoding
# each id from hex again; with the keys held sorted a range is two
# bisections. 20k items: 2.22s -> 0.10s per reconciliation.
self._keys: list[tuple[int, bytes]] = [(ts, bytes.fromhex(i)) for ts, i in self.items]
# ---- helpers ---------------------------------------------------------
def _slice(self, lower: Bound, upper: Bound) -> list[tuple[int, str]]:
lo = bisect.bisect_left(self._keys, lower.key())
hi = bisect.bisect_left(self._keys, upper.key())
return self.items[lo:hi]
def _split(self, lower: Bound, upper: Bound, out: list[tuple[Bound, int, Any]]) -> None:
"""Emit ranges covering [lower, upper). Not normative; see the module
docstring. An empty range still has to be answered, or the other side
cannot tell 'I have nothing here' from 'I ignored you'."""
items = self._slice(lower, upper)
if len(items) < LIST_THRESHOLD:
out.append((upper, ID_LIST, [i[1] for i in items]))
return
# Sixteen buckets, the remainder spread one each over the first of
# them. Dividing and letting a short tail bucket fall out instead costs
# a seventeenth range whenever the count is not a multiple of sixteen.
per, extra = divmod(len(items), BUCKETS)
start = 0
for b in range(BUCKETS):
end = start + per + (1 if b < extra else 0)
chunk = items[start:end]
bound = upper if end >= len(items) else minimal_bound(items[end - 1],
items[end])
out.append((bound, FINGERPRINT, fingerprint(chunk)))
start = end
# ---- protocol --------------------------------------------------------
[docs] def initiate(self) -> bytes:
"""The client's opening message: the whole space, split."""
if not self.is_client:
raise ValueError('only the client initiates')
out: list[tuple[Bound, int, Any]] = []
self._split(Bound(0), Bound(INFINITY), out)
return encode_message(out)
[docs] def reconcile(self, message: bytes) -> tuple[Optional[bytes], list[str], list[str]]:
"""Process one message. Returns (reply or None, have, need).
`have` and `need` are only ever populated for the client. A reply of
None means this side has nothing further to say, which is how the
protocol terminates.
"""
try:
ranges = decode_message(message)
except UnsupportedVersion:
if self.is_client:
raise # we chose the version; the server disagreeing is a bug
# The protocol's only downgrade path: one byte, the highest version
# this side speaks, so the client can retry in a version we share.
return bytes([VERSION]), [], []
out: list[tuple[Bound, int, Any]] = []
have: list[str] = []
need: list[str] = []
lower = Bound(0)
for upper, mode, payload in ranges:
mine = self._slice(lower, upper)
if mode == FINGERPRINT and fingerprint(mine) != payload:
self._split(lower, upper, out)
elif mode == ID_LIST:
if self.is_client:
theirs, ours = set(payload), {i[1] for i in mine}
need.extend(sorted(theirs - ours))
have.extend(sorted(ours - theirs))
out.append((upper, SKIP, None))
else:
# The server answers with its own list so the client can
# diff. It does not compute a diff itself: this protocol
# tells one side what it is missing, not both. The ids go
# out in store order, which is the order _split uses and
# the order a node reading from a real store would emit.
out.append((upper, ID_LIST, [i[1] for i in mine]))
else:
# Nothing to say about this range - but something must still be
# said. Ranges are adjacent by definition and a receiver derives
# each lower bound from the previous upper, so omitting a
# matching range silently shifts every range after it.
out.append((upper, SKIP, None))
lower = upper
out = _coalesce_skips(out)
while out and out[-1][1] == SKIP:
# A message that stops short of infinity has an implicit Skip to
# infinity appended by the reader, so saying it costs bytes and
# says nothing. Intermediate Skips are not optional in the same
# way: drop one of those and every later range shifts.
out.pop()
if not out:
return None, have, need # nothing left to ask: the protocol ends
return encode_message(out), have, need
[docs]def reconcile(client_items: Iterable[tuple[int, str]], server_items: Iterable[tuple[int, str]], max_rounds: int = 32) -> ReconcileReport:
"""Run a whole reconciliation and report what it cost.
Returns a dict with the client's have/need, the number of round trips and
the bytes on the wire - which is the measurement the specification's claim
about catching up 'in kilobytes of fingerprints' has never been held to.
"""
client = Negentropy(client_items, is_client=True)
server = Negentropy(server_items, is_client=False)
msg: Optional[bytes] = client.initiate()
have: list[str] = []
need: list[str] = []
rounds = 0
assert msg is not None
sent = len(msg)
received = 0
while msg is not None and rounds < max_rounds:
rounds += 1
reply, _, _ = server.reconcile(msg)
if reply is None:
break
received += len(reply)
msg, h, n = client.reconcile(reply)
have.extend(h)
need.extend(n)
if msg is not None:
sent += len(msg)
return {'have': sorted(set(have)), 'need': sorted(set(need)), 'rounds': rounds,
'bytes_sent': sent, 'bytes_received': received, 'bytes': sent + received}