Lace-061 · ILTP Listing Reconciliation

Tags: transport, iltp, reconciliation

Purpose

Listing reconciliation lets two connected endpoints exchange their first-round listings at a cost that scales with the symmetric difference rather than with listing size. Two peers that reconnect after syncing 1000 records exchange one 73-byte symbol item and one empty 19-byte listing each instead of two complete listings.

It optimizes the full exchange of 060. Without it, a logical session’s first round sends the complete listing as a delta against the empty previous listing. Reconciliation replaces only that first-round exchange; every later round uses 060 ::offers-changed items. It produces exactly the complete peer listing the full exchange would have materialized, and its fallback is the complete listing itself, so a side whose listing is small or unlike its peer’s sends it whole. 050 sees only complete listings.

The scheme is rateless IBLT reconciliation (Yang, Gilad, Alizadeh, SIGCOMM 2024). It is part of the fixed ILTP 0.13 profile, not a negotiated option, and runs under the endpoint’s single Advertising deadline. Each side streams batches of symbols that summarize its listing; once both batches of a step decode, each side sends only the entries its peer lacks.

Keys

Each listed record contributes the 33-byte key type || digest: the type byte 0x42, 0x50, or 0x53 for B, P, or S, followed by the 32 decoded digest bytes of its hash text.

Session key

Both endpoints derive

K = BLAKE3("lace-iltp/listing-symbols/v1" || nonce-side0 || nonce-side1)

the unkeyed 32-byte BLAKE3 hash of the 28 ASCII bytes of the domain string immediately followed by the two decoded 32-byte preface nonces in role order, with no separator. Keying per logical session prevents a party that injects records beforehand from aiming key collisions or degenerate peeling structures. The domain string is an opaque exact value independent of the wire version.

Per-key stream

X = BLAKE3_KEYED(K, key) read as an extendable output. X[0..8] is the key’s 8-byte checksum. Each following 8-byte group, read as u64be, is one mapping draw u, consumed in order.

Mapping

A key maps to index 0 and then to successive indexes, one per draw, computed exactly as:

let factor = 4294967296.0_f64 / ((u as f64) + 1.0).sqrt() - 1.0;
let step = ((i as f64 + 1.5) * factor).ceil().max(1.0) as u64; // saturating cast
i = i.saturating_add(step);

i is the current u64 index. Only +, -, *, /, sqrt, ceil, and integer/binary64 conversions appear; each is a correctly rounded IEEE 754 binary64 operation. Implementations MUST NOT substitute powf, a fused multiply-add, or extended precision. The max(1.0) keeps the step at least one when u is near u64::MAX and the factor rounds to zero, so a key never maps twice to one index. Mapping stops once i reaches the prefix length in use and resumes from the next draw when a later batch extends the prefix.

Symbols

Symbol i is the triple of all keys mapped to i:

• sum: the XOR of those 33-byte keys, as 44 canonical 006 B64A characters;
• check: the XOR of their 8-byte checksums, as 11 canonical B64A characters;
• count: their number in canonical unsigned decimal.

An index with no keys has all-zero sum and check and count 0. The row

<sum> <check> <count>

separates the three fields with single spaces, has no indentation or index, and is 58 bytes plus the digits of count, including its LF.

Batches

Batch k (k >= 0) is one 060 ::symbols item: its label line, the rows of exactly the symbols with indexes [(4^k - 1)/3, (4^(k+1) - 1)/3) in index order, then an empty line:

::symbols
<sum> <check> <count>

The label names no batch: the receiver expects the batch of its current step. Batch k has 4^k rows, so 1, 4, 16, 64, 256, …, and the prefix through batch k has (4^(k+1) - 1)/3 symbols.

A difference of d keys decodes from a prefix of about 1.7 * d symbols for small d, falling toward 1.4 * d as d grows, and the session key varies that prefix from one logical session to the next. Decoding happens only at batch boundaries, so a session sends between that prefix and four times it: the same difference can cost one batch more under another session key. Each step costs one round trip, so smaller batches would trade round trips for those bytes. The decoder rejects an item without rows and any row with a malformed sum, check, or count; a batch whose row count is not 4^k for the current step k is a peer protocol failure.

Decoding

Once both endpoints hold each other’s batch k, each subtracts over the whole prefix:

cell_i = (sum_own XOR sum_peer, check_own XOR check_peer, count_own - count_peer)

count +1 marks an own-exclusive key and -1 a peer-exclusive key. Both endpoints compute the same cells with opposite signs, so they decode or fail at the same step and obtain the same difference with opposite sidedness.

1. A cell is pure when count is +1 or -1, check equals BLAKE3_KEYED(K, sum)[0..8], and sum[0] is a valid type byte.
2. Peeling a pure cell recovers its key and removes it from every index it maps to inside the prefix: XOR into sum and check, and subtract its sign from count. Peeling is incremental across batches: keys recovered from an earlier prefix are removed from the indexes they map to in a new batch before new pure cells are sought; the decoder never restarts.
3. Success: every cell in the prefix is (0, 0, 0); all three fields MUST be zero.
4. Peer protocol failure: a key recovered twice; an own-exclusive key absent from the own listing; or a peer-exclusive key present in it.
5. Continue: a nonzero remainder with no pure cell continues with step k + 1.

The guard against a false decode is probabilistic, as in the paper: a wrong key must pass the 64-bit keyed checksum, and a cancelled pair must also cancel 264 bits of sum.

Listing rule

Let S(k) = 59 * (4^(k+1) - 1)/3, the nominal cumulative symbol bytes through batch k: every row counted with a one-digit count, and batch label lines and empty lines left out. S(0) = 59, S(1) = 295, and S(2) = 1239. Let B be the byte size of a side’s complete listing rendered as a 060 ::offers item: 10 bytes for the empty listing, plus each offer’s 49-byte hash line and its field lines. A side sends its complete listing as ::offers at the first step k with B <= 2 * S(k); before that it sends batch k. A listing of up to 118 bytes, such as the empty listing or a single offer of up to 108 bytes, therefore lists at step 0. A side’s symbol bytes never exceed about half of its own listing, so strangers or a side with an empty listing cost at most about 1.5 times the listing bytes. A complete listing received in place of batch k MUST satisfy 2 * S(k-1) < B <= 2 * S(k) with S(-1) = 0; a listing outside that window is a peer protocol failure. A sender that should have listed but whose symbols decoded first is not detectable and needs no check: ingress stays bounded because the receiver’s own listing step ends the exchange.

Steps

Reconciliation proceeds in numbered steps. In step k each side sends exactly one item, batch k or its complete listing. The step-k item depends only on state at the end of step k - 1 and is sent even if the peer’s step-k item has already arrived. A peer step-k item is legal only after the local step-(k-1) item has been accepted by the retained writer; step 0 may arrive at any time during the first round’s Advertising phase. Once both step-k items are exchanged:

Any other item is a peer protocol failure: an extra or early step item, a listing of another form, a second answer, a symbol batch after a listing, or an inconsistent or repeated decode. Reconciliation items precede the endpoint’s ::want item in its stream.

Every item other than a symbol batch is a 060 listing item against one of these bases:

An unshared listing whose offered set differs from the decoded peer-exclusive set, including a nonempty one when that set is empty, is a peer protocol failure.

Completion

The complete peer listing is one of: the received complete listing, sent in a step or as an answer; or the intersection with the peer’s unshared listing applied. It is published atomically as the round’s complete peer listing and becomes the session’s previous peer listing; the frozen local listing becomes the previous local listing. The endpoint then enters Requesting.

Ingress and accounting

Reconciliation state and its one peer item slot are carrier-owned session state below the endpoint’s complete peer-listing slot. 060’s state-local ingress governs that slot, and its re-prefacing rule discards the state.

Under 060’s listing accounting, the materialized peer listing is charged once at size B. The bytes that are not part of it are every whole ::symbols item, including a crossed batch discarded in a mixed step. The configured received-control budget, together with the receiver’s own listing step, bounds symbol ingress; no further limit exists.

Example

With 1000 synced records and one new record K on side1, under the canonical 040 plan schema:

side0 -> side1: ::symbols\n<s> <c> 1000\n\n                  73 B  batch 0
side1 -> side0: ::symbols\n<t> <d> 1001\n\n                  73 B  batch 0
                cell 0 is pure (-1 at side0, +1 at side1); the prefix is then all zero
side0 -> side1: ::offers-unshared\n\n                       19 B  nothing unshared
side1 -> side0: ::offers-unshared\nK\n\tApp: chat\n\n        79 B  offers K

<s>, <c>, <t>, and <d> abbreviate the 44- and 11-character B64A fields and K one 48-byte hash text. Both complete listings of 1000 or more 60-byte offers exceed 2 * S(0) = 118 bytes, so both sides send batch 0. With nothing new, each side sends one 73-byte symbol item and an empty 19-byte ::offers-unshared, both decode an empty difference, and both complete peer listings equal their own listings.

Vectors

Byte-exact vectors for fixed nonces, covering the session key, checksums, mapping draws including u = 0 and u = u64::MAX, symbol rows, and batch items, are published with the implementation in the core/crates/lace-sans-io tests.