CECR.md

Convergent Extremal Coordinate Routing (CECR) v1.0

• Status: Normative specification
• Protocol identifier: cecr/1
• Supersedes: the original CECR design note (CECR draft 0)

CECR is a decentralized routing protocol for authenticated, partially connected peer-to-peer networks. It combines lease-based membership convergence, a one-dimensional ordering derived from membership extrema, and an XOR routing backbone.

CECR coordinates order identifiers. They do not measure latency, bandwidth, geographic distance, graph-hop distance, or physical network topology. Routing guarantees come from the overlay invariant in Section 6, not from the coordinate formula alone.

1. Requirements language and scope

The key words MUST, MUST NOT, REQUIRED, SHOULD, SHOULD NOT, and MAY are to be interpreted as described by BCP 14 when, and only when, they appear in bold capitals.

CECR v1 specifies:

• authenticated peer identifiers;
• live membership under joins, renewals, graceful leaves, crashes, replays, and rejoins;
• derivation and safe use of membership extrema;
• minimum overlay requirements;
• deterministic next-hop selection and failure behavior;
• bounded gossip fan-out; and
• conditions under which convergence, reachability, or complexity claims are valid.

Application payload formats, peer discovery, NAT traversal, transport negotiation, storage, broadcast delivery receipts, and Byzantine consensus are outside the CECR core.

2. Deployment configuration

All peers in a CECR deployment MUST agree on the following configuration:

Name	Meaning
W	fixed peer-ID width in bits
HASH	cryptographic hash function
SIGNATURE	signature algorithm and public-key encoding
ENCODING	deterministic message encoding
L_max	maximum membership lease duration
Delta	maximum permitted wall-clock error
G	maximum anti-entropy interval
T_record	retention time for expired records and leave tombstones
k_xor	desired contacts per non-empty XOR bucket; at least 1
alpha = A/Q	coordinate weight as an exact rational, 0 <= A <= Q
C	consecutive matching state announcements required for coordinate readiness
state_max_age	maximum age of a neighbor state announcement

T_record MUST be at least L_max + 2 * Delta + G. This ensures that every older alive lease has become invalid before a superseding leave tombstone or expired-version record may be forgotten.

The canonical encoding of these values is hashed as config_id. Peers with different config_id values MUST NOT use coordinate-assisted routing with one another. They MAY remain connected for negotiation or an explicitly defined compatibility mode.

The CECR/1 reference profile is given in Appendix A.

3. Identity and arithmetic

3.1 Peer identifiers

A peer_id is exactly W bits and is interpreted as an unsigned big-endian integer I(peer_id) in [0, 2^W - 1].

A deployment MUST cryptographically bind each peer_id to the credential that authenticates CECR messages. The reference binding is:

peer_id = HASH(canonical_public_key)

If HASH produces more than W bits, the deployment profile MUST define which bits are retained. Duplicate peer IDs or one credential presenting multiple encodings of the same public key MUST be rejected.

3.2 Precision

Implementations MUST NOT convert a peer ID to an arithmetic type that cannot exactly represent every W-bit value. In particular, a JavaScript implementation with W > 53 MUST NOT use Number for identifier, XOR, extrema, coordinate, or score arithmetic.

Normalized values are mathematical rationals. Implementations MUST compare them using arbitrary-precision integers, fixed-width integers proven wide enough for every intermediate product, or exact cross multiplication. Floating-point values MAY be exposed for diagnostics but MUST NOT determine a routing decision.

4. Authenticated membership under churn

4.1 Membership record

Each membership record contains at least:

protocol       = "cecr/1"
kind           = "membership"
peer_id        = W-bit identifier
public_key     = credential bound to peer_id
incarnation    = unsigned 64-bit integer
sequence       = unsigned 64-bit integer
state          = "alive" | "left"
issued_at      = Unix time in milliseconds
valid_until    = Unix time in milliseconds; required only for "alive"
endpoints      = canonical list of transport descriptors
signature      = signature by public_key over every preceding field

The signed input MUST include a protocol-domain separator and config_id. Forwarders preserve the origin signature and MUST NOT rewrite a record.

4.2 Versions and merge rule

Records for one peer_id are ordered lexicographically by (incarnation, sequence). A receiver retains the greatest valid version it has observed.

Two non-identical records with the same peer_id, incarnation, and sequence constitute equivocation. A receiver MUST exclude that peer from its live view, retain evidence for at least T_record, and surface the condition to the operator. State value is not a tie-breaker; a graceful-leave record therefore uses a higher sequence number than the peer's last alive record.

Before comparing versions, a receiver MUST verify the schema, ID width, credential binding, signature, configured lease limit, and time bounds. Invalid records do not participate in the merge.

4.3 Lease validity

An alive record is acceptable only if:

issued_at <= local_now + Delta
issued_at < valid_until
valid_until - issued_at <= L_max

It is live at a receiver only while:

local_now <= valid_until + Delta

The signer SHOULD renew its lease no later than one third of the remaining lease duration. A forwarded or replayed record never receives a new expiration time.

When an alive record expires, the peer is removed from the receiver's live view. The record and its version MUST remain cached for at least T_record so that older records cannot temporarily resurrect the peer.

An operating node MUST maintain a valid local alive record and include itself in its live view. If it cannot renew its own record before expiration, it MUST stop originating CECR gossip and routed messages until it rejoins with a higher incarnation.

4.4 Leave, crash, and rejoin

• Graceful leave: the peer signs state = "left" with the same incarnation and a sequence greater than every alive record it issued in that incarnation. The tombstone is retained for at least T_record.
• Crash or partition: no third party forges a leave. The last authenticated alive lease expires independently at every receiver.
• Rejoin: a peer reusing the same identity MUST durably increment incarnation before issuing a new alive record. Sequence restarts at zero. A peer unable to recover and increment its prior incarnation MUST create a new identity.
• Counter exhaustion: a peer MUST create a new identity before either counter wraps.

Implementations MUST NOT treat an additive set of every peer ID ever observed as live membership.

5. Canonical views, extrema, and convergence

5.1 Live view

At local time t, node u derives its live view:

V_u(t) = sorted list of (peer_id, incarnation)
         for every greatest valid record that is alive at t

sequence is deliberately excluded from the view identity so routine lease renewal does not change the coordinate system. The canonical view identifier is:

view_id = HASH("cecr/1 view" || config_id || canonical_encode(V_u(t)))

For N = |V_u(t)| >= 2, each node derives, rather than accepts, the extrema:

m = min(I(peer_id))
M = max(I(peer_id))
N = |V_u(t)|

For N < 2 or M = m, coordinates are undefined and coordinate-assisted routing is disabled.

5.2 State announcement

A node periodically signs a CECR state announcement containing at least peer_id, config_id, view_id, N, m, M, and announcement time. m and M are null when N < 2. A receiver MUST recompute N, m, and M from its own view. A remote announcement never authoritatively changes membership or extrema.

5.3 Convergence definitions

A connected component is view-converged during an interval when every correct live node in that component has the same config_id and canonical live view throughout the interval. Equal extrema without equal view_id are not convergence.

A node is locally coordinate-ready only when all of the following hold:

1. N >= 2 and M > m;
2. its overlay is not degraded;
3. its view_id has not changed for at least C * G;
4. every authenticated direct CECR routing neighbor has announced the same config_id and view_id in each of the last C state rounds;
5. every such announcement is younger than state_max_age; and
6. no membership record is in equivocation quarantine.

Any view change, neighbor mismatch, stale state, or partition evidence immediately makes the node not coordinate-ready. While not ready, the effective coordinate weight is zero and routing is XOR-only.

Local coordinate readiness is operational evidence, not Byzantine consensus. A deployment requiring agreement in the presence of malicious majorities needs a separate consensus protocol.

5.4 Stability and drift

For a fixed view, coordinates are stable. Adding or removing a non-extremal peer does not change the coordinates of existing peers, although it does change view_id and temporarily disables coordinate-assisted routing. Changing either extremum changes coordinates for some or all peers.

There is no unconditional small-drift bound between two different extrema pairs. For peer integer i, the exact drift is:

abs((i - m_old)/(M_old - m_old) - (i - m_new)/(M_new - m_new))

It can approach 1. An implementation MUST NOT claim drift <= epsilon without stating and enforcing assumptions that imply that bound.

6. Overlay construction

CECR routes only across authenticated, currently connected neighbors. Coordinates do not create connections.

For node u, define the XOR bucket of another node v:

B_b(u) = { v in V, v != u : floor(log2(I(u) XOR I(v))) = b }

where 0 <= b < W.

A CECR-conformant overlay MUST maintain:

1. XOR coverage: at least one live authenticated direct neighbor in every non-empty B_b(u); implementations SHOULD maintain up to k_xor for fault tolerance.
2. Coordinate adjacency: a direct neighbor to the immediate predecessor and immediate successor of u in numeric peer-ID order, when each exists. A connection satisfying XOR coverage can also satisfy this rule.
3. Repair: prompt replacement attempts when a required connection closes or its membership lease expires.

If a transport connection limit cannot satisfy these requirements, XOR coverage takes priority. The node MUST expose an overlay_degraded state and the deployment MUST NOT claim CECR's bounded-hop reachability guarantee while degraded.

This construction has at most W + 2 required distinct neighbors when k_xor = 1, and usually fewer because buckets may be empty and connections may satisfy multiple rules. Under uniformly distributed IDs, the expected number of non-empty buckets is logarithmic in live membership; neither uniform IDs nor an O(log N) worst-case degree is guaranteed by CECR.

The overlay MAY add connections selected for measured latency, capacity, administrative policy, or resilience. Such measurements are separate from CECR coordinates.

7. Coordinate and XOR metrics

For a coordinate-ready view V and peers x and t in that view:

C_V(x, t) = abs(I(x) - I(t)) / (M - m)
X(x, t)   = (I(x) XOR I(t)) / (2^W - 1)
S_V(x, t) = alpha * C_V(x, t) + (1 - alpha) * X(x, t)

alpha is the configured exact rational A/Q. When the node is not coordinate-ready, alpha_effective = 0.

The hybrid score ranks eligible next hops; it does not define physical closeness and it never overrides the mandatory XOR progress rule in Section 8.

8. Routed-message algorithm

8.1 Route envelope

A routed CECR frame contains an immutable origin section and a mutable hop section:

origin section: protocol, kind = "route", route_id, origin_id, target_id,
                origin_view_id, hop_limit, payload_digest, payload
hop section:    hop_count

route_id MUST be unpredictable or collision-resistant within the duplicate-cache lifetime. The origin signature covers the complete immutable section. A forwarder MUST NOT alter it. The mutable hop section is authenticated by the current hop's transport security or by a hop signature, and a forwarder may change only hop_count.

Each node MUST keep a bounded duplicate cache keyed by (origin_id, route_id). A duplicate is not delivered or forwarded again. hop_limit is mandatory; frames exceeding it are discarded.

8.2 Progress rank

For x != t, define:

bucket_rank(x, t) = floor(log2(I(x) XOR I(t)))
bucket_rank(t, t) = -1

A smaller rank shares a longer high-order prefix with the target.

8.3 Next-hop selection

At node u for target t, the implementation performs these steps in order:

1. If u = t, authenticate the envelope, deliver the payload at most once, and stop.

2. If t is not in the local live view, stop with local reason TARGET_NOT_LIVE.

3. If t is a live direct neighbor, send directly to t.

4. Form E, the set of authenticated, connected, live neighbors not already rejected for this forwarding attempt.

5. Form the prefix-progress set:

   P = { v in E : bucket_rank(v,t) < bucket_rank(u,t) }
   

6. If P is non-empty, choose the peer minimizing the exact tuple:

   (S_V(v,t), X(v,t), I(v))
   

   using alpha_effective = 0 unless both endpoints have fresh matching config_id and view_id announcements.

7. Otherwise form the XOR fallback set:

   F = { v in E : I(v) XOR I(t) < I(u) XOR I(t) }
   

   If F is non-empty, choose the peer minimizing:

   (I(v) XOR I(t), I(v))
   

8. If neither set is non-empty, stop with local reason NO_PROGRESS. A core implementation MUST NOT forward to a non-improving peer.

9. Before sending, increment hop_count. If it would exceed hop_limit, stop with local reason HOP_LIMIT_EXCEEDED.

All tie-breaks are exact and deterministic. Every forwarded hop strictly decreases raw XOR distance, so a route cannot loop even without a visited-peer list. The duplicate cache and hop limit additionally bound replays, retransmission races, and non-conformant peers.

If a selected link fails before accepting the frame, the current node re-evaluates the remaining eligible candidates in the same order. If none remains, it reports LINK_FAILURE locally. End-to-end failure reports and delivery receipts are optional extensions.

8.4 Reachability theorem

Assume a stable view, a live target, reliable links long enough to forward the route, and XOR coverage at every hop. Let b = bucket_rank(u,t). Because t is in B_b(u), XOR coverage gives u a neighbor v in that bucket. v agrees with t in bit b and in every more-significant bit, hence:

bucket_rank(v,t) < b

The prefix-progress set is therefore non-empty at every non-target hop. Rank decreases at least once per hop, so delivery requires at most W forwarding hops. Coordinate weighting only chooses among already-progressing candidates and cannot invalidate this bound.

Without XOR coverage, CECR's fallback is best-effort and the W-hop guarantee does not apply.

9. Gossip and fan-out

CECR uses gossip for membership records and state announcements. For each gossip round, a node computes:

liveN             = size of its current live view
connectedDegree   = number of eligible authenticated direct neighbors
fanout             = min(connectedDegree, ceil(log2(liveN)))

The node MUST NOT select more than connectedDegree neighbors and MUST NOT select the same neighbor twice in one round. Routed unicast uses one next hop and is not governed by this fan-out formula.

Immediately after establishing an authenticated connection, both endpoints MUST exchange their latest own membership record, configuration identifier, view identifier, and anti-entropy summary directly. This bootstrap exchange is not a gossip round and is required even when the current fan-out is zero.

Neighbor selection MAY be randomized or deterministic, but it MUST be fair: while a link remains eligible, it is selected infinitely often across an unbounded sequence of rounds. A rotating permutation seeded by (peer_id, round, view_id) is one conforming strategy. Implementations MUST deduplicate gossip items and periodically perform anti-entropy at an interval no greater than G.

Fan-out alone does not prove total-message complexity, convergence time, or complete dissemination. Those properties also depend on overlay connectivity, loss, retry policy, scheduling fairness, and churn.

10. Churn, partitions, and failures

• During active churn, nodes MAY hold different views. XOR routing remains available; coordinate assistance is gated by coordinate readiness.
• A partition produces independently converged component views after unreachable leases expire. Healing a partition invalidates coordinate readiness until records and state announcements reconverge.
• An expired target MUST NOT remain routable merely because its ID is cached.
• A peer whose required overlay links are being rebuilt MUST expose degraded status.
• CECR does not guarantee delivery across a disconnected component, to a crashed target, or through a transport that fails longer than the route's lifetime.

11. Security requirements and boundaries

A conforming implementation MUST:

• authenticate transport peers and verify that transport identity matches peer_id;
• verify membership, state, and route signatures before using them;
• bind signatures to protocol version, config_id, message kind, and every security-relevant field;
• reject IDs, integers, timestamps, counters, or encodings outside their canonical ranges;
• derive extrema from authenticated live membership rather than trusting advertised extrema;
• enforce L_max, Delta, message-size limits, endpoint limits, duplicate-cache bounds, and rate limits; and
• reject stale versions and surface equivocation.

Authentication prevents an attacker from impersonating an existing peer or forging that peer's lease. It does not prevent a participant from lying about its own endpoints, dropping traffic, selectively forwarding gossip, grinding keys to obtain chosen identifier regions, or creating many identities. Sybil resistance, admission control, proof of work/stake, reputation, and Byzantine membership agreement are deployment concerns outside CECR v1.

12. Properties and claim boundaries

A deployment may claim the following only with the stated conditions:

Claim	Required conditions
Deterministic next hop	identical live view, configuration, readiness state, and eligible-neighbor set
Loop-free conforming forwarding	every forwarded hop follows Section 8's strict XOR progress rule
Delivery in at most W hops	stable converged view, live target, reliable-enough links, and XOR coverage at every hop
Eventual membership convergence	churn eventually pauses, clocks satisfy Delta, the authenticated overlay remains connected, and fair anti-entropy continues
Coordinate stability	extrema remain unchanged; coordinate readiness may still reset for non-extremal membership changes
Expected logarithmic degree	IDs are approximately uniform and k_xor is bounded

CECR v1 makes no unconditional claim of O(log N) routing, low latency, bounded coordinate drift, Byzantine agreement, or reliable delivery.

13. Conformance

An implementation claiming CECR/1 Core conformance MUST implement every applicable MUST in this document and publish its deployment configuration and identity profile. A deployment claiming CECR/1 Overlay conformance MUST additionally satisfy Section 6 at the time of the claim.

A conformance suite MUST cover at least:

1. Arithmetic: IDs at 0, 2^53, and 2^W - 1; exact score comparison; deterministic ties; N < 2.
2. Membership: join, lease renewal, graceful leave, crash expiry, replay, future timestamp, overlong lease, stale version, equivocation, and higher-incarnation rejoin.
3. Convergence: identical views, equal extrema with unequal views, stale neighbor announcements, non-extremal changes, partitions, and partition healing.
4. Overlay: every occupied XOR bucket, predecessor/successor selection, repair after loss, connection-cap degradation, and an adversarially chosen ID distribution.
5. Routing: direct delivery, prefix progress, coordinate-weighted choice, XOR-only mode, fallback, exact tie-breaking, link retry, no-progress failure, duplicate suppression, target expiry, and hop-limit failure.
6. Fan-out: degree below, equal to, and above ceil(log2(liveN)); no duplicate selections; long-run fairness.
7. Security: invalid signatures, credential/ID mismatch, forged extrema, non-canonical encoding, oversized input, and replayed route IDs.

Test results MUST distinguish protocol conformance from performance measurements.

14. Extensions

Extensions use separate protocol identifiers and capability negotiation. They MUST NOT silently change CECR/1 membership, progress, tie-breaking, or fan-out semantics.

Delivery acknowledgements, aggregated receipts, retry reports, and broadcast coverage tracking belong in a separate extension, provisionally CECR-DR/1. A CECR/1 implementation does not need CECR-DR/1 to be conformant.

Appendix A: CECR/1 reference profile

The interoperable reference profile uses:

W                 = 256
HASH              = SHA-256
SIGNATURE         = Ed25519
ENCODING          = deterministic CBOR (RFC 8949)
L_max             = 30,000 ms
Delta             = 5,000 ms
G                 = 5,000 ms
T_record          = 120,000 ms
k_xor             = 1
alpha             = 7/20
C                 = 2
state_max_age     = 15,000 ms
default hop_limit = 256

Public keys and signatures use the canonical byte encodings defined by the selected Ed25519 profile. CBOR maps use deterministic encoding as defined by RFC 8949, and signatures cover the deterministic encoding with the signature field omitted.

Implementations MAY define other profiles, but two peers using different profiles have different config_id values and cannot claim interoperable CECR/1 routing without explicit negotiation.