hecate_plumtree (macula v11.4.0)
View SourcePlumtree push-lazy gossip (Leitão, Pereira, Rodrigues 2007, Part 3 §7.2).
Disseminates realm-scoped publications over HyParView's active view with a tree-emergent topology and lazy-push recovery.
A message is a publication signed by its publisher (macula_frame:publish/2), and its message id is the SHA-384 of the publication's tbs. GOSSIP carries the publication bytes unchanged. Every node verifies a publication once, keyed by that id, before it delivers or forwards it (macula_frame:verify_publication/3), under the node's configured crypto profile: a publication that does not verify, or names another realm, stops at the first node that sees it, and a copy that arrives again is recognised by its id without a second verification. Frames leave this module without a signature of their own: the connection that sends a frame adds its neighbour signature (D17).
State
- eager_push: peers receiving full GOSSIP publications. The eager-push set is the Plumtree spanning tree.
- lazy_push: peers receiving only IHAVE announcements. They graft into eager_push when they GRAFT in response to an IHAVE.
- received:
MsgId => {Publication, ExpiresAt}for the verified publications delivered locally, each kept until its publication expires (sweep/2). Used to recognise repeat GOSSIPs and to answer GRAFTs. - missing:
MsgId => {#{Peer => GraftedAt}, NotedAt}for the peers who sent IHAVE for a publication not yet received in full, when this node sent each its GRAFT (monotonic milliseconds), and when the first IHAVE for it came (wall-clock milliseconds); forgotten after 70 minutes (sweep/2). - open:
Peer => Count, how many missing entries each neighbour is on. A neighbour is on at most 1,024 (DESIGN_PQ_DHT_SLOTS_AND_BUDGET.md, 3.1).
Message handling
- Local publish: verify the PUBLISH, record its publication, deliver it locally, GOSSIP it to every eager peer and IHAVE it to every lazy peer.
- Receive GOSSIP: the first time, verify the publication; when it verifies, deliver it, remove it from missing, eager-forward it to every other eager peer, IHAVE-forward it to every lazy peer and ensure the sender is eager, and when it does not, drop it and return the refusal. Either way its missing entry ends, at no charge to its announcers. A duplicate is not verified again: PRUNE the sender and move it from eager to lazy.
- Receive IHAVE: if already received, or the sender is already on its missing entry, ignore. A neighbour on 1,024 open entries gets no new one: its IHAVE is not recorded, gets no GRAFT and returns a refusal. Else record the sender with the time of its GRAFT and emit a GRAFT to the sender right away (Phase 5.3 MVP: a real deployment delays the GRAFT briefly to give the eager push a chance to win the race; eager grafting is correct but slightly heavier).
- Receive GRAFT: for a publication this node holds, the sender becomes eager and gets the GOSSIP publication; for any other id nothing changes, the push sets included.
- Receive PRUNE: move the sender from eager to lazy.
- A sender outside both push sets: a frame moves a peer between the sets and never adds one. Through a station's relay the sender is the frame's origin, which need not be a neighbour, so from such a sender a GRAFT, a PRUNE and an IHAVE move no one, send nothing and are refused as
not_a_peer, a first GOSSIP delivers and forwards its verified publication but moves no one, and a duplicate GOSSIP gets no PRUNE and is refused asnot_a_peertoo.
This module is pure apart from reading the configured profile when a node starts. The caller passes the clocks: wall-clock milliseconds for publication freshness and retention, and monotonic milliseconds for GRAFT timing. The wrapping process transmits the send actions, reports each {refused, Peer, Kind} action through macula_peering:object_refused/2, feeds deliveries to the local consumer, calls expired_grafts/2 about once a second, and calls sweep/2 on a timer, so a node remembers a publication hash until the publication expires, and no longer.
Reference: plans/PLAN_MACULA_V2_PART3_DISCOVERY.md §7.2; plans/PLAN_PHASE_5_BREAKDOWN.md Session 5.3; DESIGN_PQ_SIGNED_FRAMES_AND_RECORDS.md, Publications.
Summary
Types
A delivery is the message id and the verified publication: publisher, realm, topic, seq, published_at, payload.
Functions
When HyParView promotes a peer to active, the Plumtree layer adds it to the eager-push set. Any GOSSIP we publish reaches the new peer immediately.
Take each neighbour off the missing entries whose GRAFT it has not answered within 10 seconds, at MonoMs in monotonic milliseconds: one refused action per neighbour and entry, and an entry left with no neighbour ends. The wrapping process calls this about once a second.
A Plumtree node for a realm, in the node's configured crypto profile, under which it verifies every publication. A node with no configured profile does not start.
Handle a Plumtree frame from the neighbour From, at the caller's clocks.
Publish a PUBLISH this node made: verify its publication, record it, push it fully to every eager peer and announce it to every lazy peer, and return it as the local delivery the caller's consumer handles. A publication that does not verify, or names another realm, is refused; one already received is not delivered again.
When HyParView removes a peer from active, the Plumtree layer removes it from both push sets.
Forget, at NowMs in milliseconds of wall-clock time, every received publication that has expired (its published_at plus its ttl_ms, or 10 minutes without one, plus 5 minutes) and every missing publication first announced more than 70 minutes ago. A node keeps a publication hash until the publication expires, and no longer; a later copy is refused by verification, and a GRAFT for it gets no answer. Each neighbour still on a forgotten missing entry has one open entry less, at no charge.
Types
-type action() :: {send, peer(), macula_frame:frame()} | {refused, peer(), ihave_allowance | graft_unanswered | wrong_realm | not_a_peer | macula_frame_refusal()}.
-type macula_frame_refusal() :: malformed_frame | signature_invalid | key_id_mismatch | {not_yet_valid, pos_integer()} | {expired, pos_integer()}.
A delivery is the message id and the verified publication: publisher, realm, topic, seq, published_at, payload.
-type msg_id() :: <<_:384>>.
-type peer() :: <<_:256>>.
-type state() :: #{self_id := peer(), realm := <<_:256>>, profile := macula_crypto_profile:profile(), eager_push := sets:set(peer()), lazy_push := sets:set(peer()), received := #{msg_id() => {macula_signed_object:object(), non_neg_integer()}}, missing := #{msg_id() => {#{peer() => integer()}, integer()}}, open := #{peer() => pos_integer()}}.
Functions
When HyParView promotes a peer to active, the Plumtree layer adds it to the eager-push set. Any GOSSIP we publish reaches the new peer immediately.
Take each neighbour off the missing entries whose GRAFT it has not answered within 10 seconds, at MonoMs in monotonic milliseconds: one refused action per neighbour and entry, and an entry left with no neighbour ends. The wrapping process calls this about once a second.
-spec new(peer(), <<_:256>>) -> {ok, state()} | {error, macula_crypto_profile:refusal()}.
A Plumtree node for a realm, in the node's configured crypto profile, under which it verifies every publication. A node with no configured profile does not start.
-spec process(state(), peer(), macula_frame:frame(), clocks()) -> {state(), [action()], [delivery()]}.
Handle a Plumtree frame from the neighbour From, at the caller's clocks.
-spec publish(state(), macula_frame:frame(), integer()) -> {state(), [action()], [delivery()]} | {error, term()}.
Publish a PUBLISH this node made: verify its publication, record it, push it fully to every eager peer and announce it to every lazy peer, and return it as the local delivery the caller's consumer handles. A publication that does not verify, or names another realm, is refused; one already received is not delivered again.
When HyParView removes a peer from active, the Plumtree layer removes it from both push sets.
Forget, at NowMs in milliseconds of wall-clock time, every received publication that has expired (its published_at plus its ttl_ms, or 10 minutes without one, plus 5 minutes) and every missing publication first announced more than 70 minutes ago. A node keeps a publication hash until the publication expires, and no longer; a later copy is refused by verification, and a GRAFT for it gets no answer. Each neighbour still on a forgotten missing entry has one open entry less, at no charge.