# Bloom: Implementation Roadmap Bloom (formerly kismet) is the consensus substrate for dendrite. The data structures are substantially complete. The protocol logic that stitches them together is absent. This document maps the gaps and orders them into executable phases. ## Architecture: Hierarchical Consensus Bloom is not a single flat consensus layer. It is a self-similar hierarchy where the same data structures (Branch, Epoch, Stem) operate at different time scales, connected by geography. ### Tips (local quorums, ~100ms epochs) The fast layer. Five geographically proximate nodes — same city, same metro, same datacenter cluster — form a quorum. RTT between members is 1-5ms. The 3.7ms micro-epoch works because the network is local. This is where user payloads enter the system and get immediate finality. Each tip cluster runs the full Branch/Epoch/Stem cycle independently. A tip epoch is 100ms: 27 micro-epochs at ~3.7ms each. The tip stem records local consensus history. Tip branches are pruned aggressively after their roots are committed upward. Geographic locality is enforced through GnarlShard prefix matching in quorum selection. Nodes whose shard addresses share a locality prefix can form tip-level quorums. Nodes with different prefixes cannot. ### Trunk (global aggregation, ~10s epochs) The slow layer. Tip-level epoch roots become the "payloads" at the trunk level. Trunk quorums can span continents because they have seconds, not milliseconds, to reach consensus. Trunk quorum members are tip-cluster representatives — one node per geographic cluster, elected by local reputation. A trunk epoch is ~10 seconds: 27 trunk micro-epochs at ~370ms each. This is comfortable for global internet RTT (50-200ms). The trunk stem is the global permanent record. Trunk branches aggregate the work of all tip clusters into a single ordered history. ### Self-Similarity The same code runs at both layers. The difference is parameters: | Parameter | Tip | Trunk | |-----------|----:|------:| | Micro-epoch | 3.7ms | 370ms | | Epoch | 100ms | 10s | | Quorum locality | same metro | global | | Quorum candidates | local nodes | cluster reps | | Payloads | user messages | tip epoch roots | | Stem growth | 470 B/s (local) | 4.7 B/s (global) | The ternary structure (27 = 3^3) operates identically at both levels. Sparse verification works at both levels. Pruning works at both levels. ### GnarlShard as Geographic Address GnarlShard is 27 trits (54 bits, 7 bytes). The trit decomposition maps naturally to hierarchical addressing: [ locality prefix : 9 trits ] [ identity : 18 trits ] The 9-trit locality prefix encodes geographic proximity. 3^9 = 19,683 possible localities — enough for fine-grained metro-level addressing. Nodes self-assign their locality based on measured latency to reference points, or it's assigned by the cluster they join. Quorum selection at the tip level filters candidates by matching locality prefix. Quorum selection at the trunk level ignores locality — it picks from the set of cluster representatives globally. ### Data Flow ``` User payload │ ▼ Tip quorum (local, 3.7ms micro-epoch) │ propose → vote → finalize ▼ Tip branch (27 micro-blocks, 100ms) │ ternary merge → tip epoch root ▼ Trunk quorum (global, 370ms micro-epoch) │ tip epoch roots are the payloads ▼ Trunk branch (27 trunk micro-blocks, 10s) │ ternary merge → trunk epoch root ▼ Trunk stem (permanent global record, 47 bytes per 10s epoch) ``` A user payload achieves local finality in <100ms (one tip epoch). It achieves global finality in <10s (one trunk epoch). The local finality is sufficient for most applications. The global finality is the permanent record. ## Inventory: What Exists | File | Status | Content | |------|--------|---------| | micro.go | Complete | MicroBlock (106B header), Payload, marshal/unmarshal, payload root | | branch.go | Complete | 27-block ternary tree, insert/seal/verify/prune | | stem.go | Complete | Append-only epoch chain, StemEntry (47B), chain verification | | epoch.go | Complete | Epoch boundary seal, EpochCycle driver, branch root collection | | message.go | Complete | Wire format (38B header), 10 message types, marshal/unmarshal | | reputation.go | Complete | Cayley accumulator stepping, consistency ratio, transition verify | | quorum.go | Partial | Local state machine (propose/vote/finalize), SelectionScore, DivHash PoW | | dendrite.go | Thin | ColonyNode wrapper, SubmitPayload (encrypt + hashcash) | | store.go | Complete | StemStore (flat file persistence), BranchStore (epoch-scoped scratch) | | doc.go | Complete | Package documentation | | WHITEPAPER.md | Complete | Full design document (needs hierarchy update) | | transport.go | Complete | Transport interface, ChannelHub, ChannelTransport (in-process) | | layer_driver.go | Complete | BloomLayer lifecycle driver, propose/vote/finalize/seal loop | | bridge.go | Complete | Bridge: tip epoch roots → trunk payloads | | udp_transport.go | Complete | UDPTransport: UDP sockets, peer table, GnarlSeal encryption | | candidate_pool.go | Complete | CandidatePool: admission, liveness, eviction, tip/trunk modes | | view_change.go | Complete | ViewChange: leader timeout, seat succession, view change messages | | sync.go | Complete | Sync protocol: stem/branch/pool download, request/response wire format | | difficulty.go | Complete | DifficultyController: sliding window, adaptive DivHash per locality | | payload_router.go | Complete | PayloadRouter: trial-decrypt payloads, trunk epoch root extraction | | *_test.go | Complete | 226 tests across 18 files, all passing | The existing data structures are layer-agnostic. Branch, Epoch, Stem, Quorum all operate on abstract parameters. The hierarchy is a deployment/wiring concern, not a data structure change. The main additions are: layer parameterization, geographic quorum selection, and the inter-layer bridge that feeds tip epoch roots into trunk micro-blocks. ## Gaps, Sorted by Dependency ### Tier 0: Foundation — DONE **G1. Tests for existing data structures.** DONE. 75 tests across 7 files. **G2. Persistence layer.** DONE. StemStore (append-only flat file, fsync, load/verify on startup) and BranchStore (epoch-scoped scratch directory, save/load with root integrity check, purge). 14 tests. ### Tier 1: Layer Abstraction and Timing **G3. Layer parameterization.** The current code has hardcoded `EpochDuration = 100ms` and `MicroEpochDuration = EpochDuration / 27`. These become parameters of a `LayerConfig` struct. Each layer (tip, trunk) instantiates the same Branch/Epoch/Stem machinery with different timing and quorum selection rules. **G4. Geographic quorum selection.** `SelectQuorum` currently picks the 5 lowest GnarlShard scores globally. Tip-level selection must filter by locality prefix first, then pick the 5 lowest within that locality. Trunk-level selection picks from the set of cluster representatives without locality filtering. GnarlShard needs a locality prefix accessor. Node needs a locality field or it's derived from the shard address. **G5. Epoch clock.** Per-layer ticker driving micro-epoch transitions. Tip clock ticks at ~3.7ms. Trunk clock ticks at ~370ms. Timeout detection for leader deadlines. Channel-based interface for the lifecycle driver. ### Tier 2: Authentication **G6. Signed consensus messages.** `Quorum.Vote()` takes `position uint8` — a trusted local call. Real votes are Gnarl-signed messages. Each consensus message (propose, vote, finalize) needs: sender signature, quorum membership verification, replay rejection. Same at both tip and trunk layers. **G7. Key exchange.** Quorum members need pairwise shared secrets for GnarlSeal. When a quorum forms (5 members identified by SelectQuorum), they exchange ephemeral public keys (signed by long-term identity) and derive pairwise secrets. 10 pairwise secrets per quorum. At the tip level, key exchange is fast (local RTT). At the trunk level, it happens within the ~370ms micro-epoch budget. ### Tier 3: The Main Loops **G8. Tip lifecycle driver.** The local consensus loop. On each tip micro-epoch tick: 1. SelectQuorum from local candidate pool (locality-filtered) 2. Leader proposes, members vote (signed), finalize on threshold 3. Insert into tip branch 4. On branch complete: seal, submit root to tip epoch 5. On tip epoch boundary: seal epoch, extend tip stem 6. Package tip epoch root as a payload for the trunk layer Testable in-process with 5 nodes connected by Go channels. **G9. Trunk lifecycle driver.** Same logic as G8 but operating on tip epoch roots as payloads. Trunk quorum candidates are cluster representatives. Trunk micro-epoch is ~370ms. On trunk epoch boundary: seal trunk epoch, extend trunk stem (the global permanent record). **G10. Inter-layer bridge.** The wiring between tip and trunk. A tip cluster's sealed epoch root becomes a signed payload submitted to the trunk quorum. The bridge: monitor tip stem for new entries, package as trunk MsgPayload, submit to trunk quorum through the trunk node's representative. ### Tier 4: Network **G11. Network transport.** Two scales of networking: - **Tip transport**: UDP between nearby nodes. Low latency, high frequency. Can assume reliable local network (packet loss is rare within a metro). - **Trunk transport**: UDP between global nodes. Higher latency, lower frequency. Needs more tolerance for packet loss and jitter. Transport interface is the same: Send(peer, message), Receive() channel. Tip and trunk use different socket bindings but the same protocol. **G12. Candidate pool and peer management.** Two pools: - **Tip pool**: local nodes within the same locality prefix. Admission via DivHash proof. Liveness via heartbeat. Eviction on missed quorum duty. - **Trunk pool**: cluster representatives. One per locality. Admission by presenting a tip-level reputation (Cayley accumulator depth) above a threshold. Cluster-internal election determines who represents. ### Tier 5: Robustness **G13. View change.** Leader timeout at both layers. Tip: if no proposal within ~2ms, next seat takes over. Trunk: if no proposal within ~200ms, next seat takes over. **G14. Sync protocol.** Joining a tip cluster: download tip stem, request recent tip branches, verify, enter local candidate pool. Joining the trunk: download trunk stem, request recent trunk branches, present tip-level credentials. **G15. Difficulty adjustment.** Adaptive DivHash repetitions per locality, targeting a healthy candidate pool size. Broadcast current difficulty in epoch metadata. **G16. Payload routing (receive path).** On finalized micro-block (tip or trunk), iterate payloads, attempt GnarlOpen with session secrets, deliver decrypted payloads. At the tip level, payloads are user messages. At the trunk level, payloads are tip epoch roots (not encrypted, just signed). ## Execution Phases ### Phase 1: Test and Harden — DONE 75 tests covering every existing data structure. ### Phase 2: Persistence — DONE StemStore and BranchStore with 14 tests. Flat file stem, epoch-scoped branch scratch, integrity verification on load. ### Phase 3: Layer Abstraction and Clock — DONE Made data structures layer-aware without changing internals. G3: Layer parameterization G4: Geographic quorum selection G5: Epoch clock Deliverables: - `LayerConfig` struct: epoch duration, micro-epoch duration, quorum selection mode (local vs global), locality prefix length. - `TipConfig` and `TrunkConfig` as concrete instances. - Locality prefix on GnarlShard: `Locality() [9]uint8` (9 trits) or similar accessor. `MatchLocality(a, b GnarlShard) bool`. - `SelectLocalQuorum`: filter candidates by locality prefix, then pick 5 lowest scores. Used at tip level. - `SelectGlobalQuorum`: pick 5 lowest scores from cluster representatives. Used at trunk level. - `EpochClock`: parameterized ticker. Fires micro-epoch events on a channel. Tracks epoch/micro-epoch counters. Detects epoch boundaries. Tests with accelerated time (no real 100ms waits in tests). ### Phase 4: Signed Messages and Key Exchange — DONE Authenticated communication for both layers. G6: Signed consensus messages G7: Key exchange Deliverables: - `SignedMessage`: Message + Gnarl signature + signer public key. Marshal/Unmarshal/Verify. Verify checks signature and that signer is in the expected quorum for this micro-epoch. - Quorum key exchange: ephemeral key pairs, signed exchange, pairwise secret derivation. 5 nodes → 10 secrets. Stored in SessionStore. - Refactor `Quorum.Vote()` to accept `SignedMessage`. - Replay protection: seen nonces per quorum per micro-epoch. ### Phase 5: The Main Loops — DONE Connected everything into running consensus at both layers. G8: Tip lifecycle driver G9: Trunk lifecycle driver G10: Inter-layer bridge Deliverables: - `BloomLayer`: generic lifecycle driver parameterized by LayerConfig. Owns: EpochClock, EpochCycle (Stem + current Epoch), active Branches, candidate pool reference, transport interface. - `BloomLayer.Run(ctx)`: the main loop. On each micro-epoch tick: select quorum, propose/vote/finalize, manage branches, seal epochs. - `TipNode`: wraps BloomLayer with tip config. Produces tip epoch roots. - `TrunkNode`: wraps BloomLayer with trunk config. Consumes tip epoch roots as payloads. - `Bridge`: monitors a TipNode's stem, packages new epoch roots as signed payloads, submits to TrunkNode. - **Integration test**: 2 tip clusters of 5 nodes each + 1 trunk cluster of 5 nodes (2 of which are tip cluster representatives). All connected by Go channels. Full lifecycle: user payload → tip finality → trunk finality → trunk stem grows. This is the proof that the hierarchy works. ### Phase 6: Network Transport — DONE Moved from in-process channels to UDP. G11: Network transport Deliverables: - Transport interface: `Send(peer GnarlMid, msg []byte) error` and `Receive() <-chan IncomingMessage`. - `ChannelTransport`: in-process implementation (for tests). Already implicit in Phase 5. - `UDPTransport`: real network. Bind socket, GnarlSeal encrypt/decrypt, peer address table (GnarlMid → net.UDPAddr). - Tip transport binds a local-network socket. Trunk transport binds a public-facing socket. ### Phase 7: Peer Management — DONE Manage candidate pools at both layers. G12: Candidate pool and peer management Deliverables: - `CandidatePool`: concurrent-safe node set with reputation, admission proof, last-seen, locality. - Tip admission: DivHash proof + matching locality prefix. - Trunk admission: tip-level reputation depth above threshold. - Liveness tracking: miss counter per node. Exceed MaxMisses → inactive. Grace period → eviction via EvictStale(). - Touch reactivation: observed participation resets miss counter. - Bootstrap: static peer list via AdmitDirect (no proof required). - Pool wired into BloomLayer.selectQuorum: prefers pool.ActiveCandidates() over static candidate list. - DefaultTipPoolConfig / DefaultTrunkPoolConfig with sensible defaults. - 22 tests covering admission, liveness, eviction, pool+layer integration. ### Phase 8: Robustness — DONE Handle failures, late joiners, and adversarial conditions. G13: View change G14: Sync protocol G15: Difficulty adjustment G16: Payload routing Deliverables: - `ViewChange`: per-micro-epoch tracker with deadline-based timeout detection. Seat succession (0→1→2→3→4) when leader fails to propose. `MarkProposed()` prevents unnecessary view changes. `IsExpired()` detects all-seats-exhausted. `ViewChangeMsg` marshal/unmarshal for broadcasting timeout notifications. Integrated into `BloomLayer.handleMicroEpoch` — current view determines which seat proposes. 9 tests. - `SyncHandler`: answers peer sync requests against local state. Three modes: `SyncStem` (epoch range from stem), `SyncBranch` (micro-block headers), `SyncPool` (candidate identities). Request/response wire format with marshal/unmarshal. `ApplyStemSync`, `ApplyBranchSync`, `ApplyPoolSync` for processing received sync data. 15 tests. - `DifficultyController`: sliding window average over pool sizes. One-step increase/decrease within floor/ceiling bounds. `DefaultTipDifficultyConfig` (min=1, max=8, start=4, target pool 10-50) and `DefaultTrunkDifficultyConfig` (min=0, max=6, start=2, target pool 5-20). `ApplyToPool()` applies current difficulty to CandidatePool config. 10 tests. - `PayloadRouter`: session secret management, GnarlPacket decryption using known secrets, trial decryption with all secrets (privacy-preserving path when sender identity doesn't match). Hashcash verification. Non-blocking delivery to consumer channel. `ProcessTrunkBlock` extracts tip epoch roots from trunk-level finalized blocks. 11 tests. ## Dependency Graph ``` Phase 1: Tests ────────────────────────────── DONE │ Phase 2: Persistence ──────────────────────── DONE │ Phase 3: Layer Abstraction + Clock ──────────── DONE │ Phase 4: Signed Messages + Key Exchange ─────── DONE │ Phase 5: Main Loops + Inter-layer Bridge ────── DONE │ │ Phase 6: Network Transport (UDP) ────────────── DONE │ │ Phase 7: Peer Management ──────────────────────── DONE │ Phase 8: Robustness ──────────────────────────── DONE ``` Phase 5 is the critical integration point. It's the first time tip clusters and trunk consensus run together end-to-end, proving the hierarchical architecture works. Everything before Phase 5 is groundwork. Everything after Phase 5 is production hardening. The in-process test in Phase 5 (2 tip clusters + 1 trunk, Go channels) is the architectural proof of concept. If that works, the remaining phases are incremental: swap channels for UDP, add peer management, add robustness. ## Stem Growth (Revised) | Layer | Epoch | Entry size | Rate | Daily | Yearly | |-------|------:|-----------:|-----:|------:|-------:| | Tip | 100ms | 47 B | 470 B/s | 40 MB | 15 GB | | Trunk | 10s | 47 B | 4.7 B/s | 400 KB | 150 MB | Tip stems are local and can be pruned once their roots are committed to the trunk. Only the trunk stem is the permanent global record. A node that participates in one tip cluster and tracks the trunk stem stores: Trunk: 150 MB/year (permanent) Tip: 15 GB/year (prunable after trunk commitment, keep last N epochs) A node that only tracks the trunk (light client) stores 150 MB/year.