Source code for fleetmesh_core.storage.negentropy

"""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 Malformed(FleetmeshError, ValueError): """A message that is not a negentropy message, or is truncated."""
[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}