Seeking Community Feedback on Logos Discovery Capability RFC

Vac IFT research call
1

RFC: Logos Capability Discovery

Hey VAC community :wave:

We’re excited to share a draft RFC and proof-of-concept for Logos Capability Discovery — a service-oriented discovery layer built on top of Kad-DHT. This work targets a core problem in decentralized networks: efficient, fair, and resilient peer discovery across many services.

:page_facing_up: RFC

:test_tube: PoC

:warning: The RFC is marked raw and evolving quickly. Early feedback is highly encouraged.

What is Logos Capability Discovery?

Logos Discovery is a service (capability) discovery protocol inspired by DISC-NG, designed as an extension of Kad-DHT.

It enables nodes to:

  • Advertise participation in specific services (libp2p protocol IDs)
  • Discover peers offering a given service efficiently
  • Maintain resilience against Sybil, DoS, and cache-domination attacks
  • Scale logarithmically across many services

In the RFC:

  • Service ≡ Capability
  • Node ≡ Peer

Logos preserves Kad-DHT behavior wherever not explicitly overridden.

Motivation

Service discovery in multi-service P2P networks faces persistent challenges:

  • Unpopular services are hard to discover

    Random walks or gossip-style propagation converge slowly.

  • Popular services overload the network

    Advertising at peers closest to the service ID creates hotspots.

  • Weak admission control

    Simple provider records are easy to spam and eclipse.

  • Poor fairness guarantees

    Popular services dominate storage and lookup bandwidth.

Logos addresses these problems by moving discovery from content-based routing to service-centric routing, while keeping Kad-DHT semantics intact.

Protocol Overview

Logos defines three roles (a node may play multiple):

1. Advertisers

Nodes that provide a service and want to be discovered.

  • Maintain a service-specific advertise table
  • Register advertisements across multiple registrars
  • Retry registration using ticket-based waiting

2. Discoverers

Nodes looking for peers that provide a service.

  • Maintain a service-specific search table
  • Query registrars progressively from far to close buckets
  • Verify advertisement signatures locally

3. Registrars

Nodes that store and serve advertisements.

  • Maintain a bounded ️advertisement cache
  • Enforce waiting-time–based admission control
  • Return both advertisements and topology hints

Key Design Ideas

:small_blue_diamond: Service-Centric Routing Tables

Instead of routing around a node’s peerID, Logos introduces routing tables centered on the service ID (SHA-256(protocolID)):

  • AdvT(service_id_hash) for advertisers
  • DiscT(service_id_hash) for discoverers
  • RegT(service_id_hash) for registrars

This allows logarithmic navigation toward service-specific peers, not just nodes.

:small_blue_diamond: Distributed Advertisement Placement

Advertisements are placed:

  • Across multiple buckets
  • At multiple registrars
  • With bounded fan-out per bucket (K_register)

This avoids hotspots and single points of failure.

:small_blue_diamond: Waiting-Time–Based Admission Control (Core Innovation)

Registrars do not immediately accept advertisements.

Instead, they compute a waiting time based on:

  • Cache occupancy
  • Service popularity within the cache
  • IP similarity (Sybil resistance)

Advertisers receive signed tickets that:

  • Accumulate waiting time across retries
  • Require no per-request state on registrars
  • Are robust to clock skew

This achieves:

  • Natural prioritization of rare services
  • Penalization of Sybil identities
  • Strong DoS resistance

:small_blue_diamond: Progressive Bucket-Based Lookup

Discoverers query registrars:

  1. Starting from far buckets
  2. Progressively moving toward the service ID
  3. Stopping early once enough peers are found

This ensures:

  • Fast discovery for popular services
  • Guaranteed logarithmic discovery for unpopular ones
  • Reduced eclipse risk near the target

Why This Matters

Logos Discovery achieves a rare balance:

  • Efficiency: O(log N) discovery across services
  • Fairness: Rare services are not starved
  • Security: Strong resistance to Sybil, cache flooding, and eclipse attacks
  • Compatibility: Built entirely on Kad-DHT primitives

The admission protocol is especially important: no PoW, no global coordination, no per-request memory, yet strong economic-style throttling emerges naturally.

Logos vs Kad-DHT vs Discv5 (Corrected)

Feature Kad-DHT Discv5 Logos Discovery
Discovery unit Content / providers Topics Services / capabilities
Routing center peerID nodeID service ID
Admission control None Rate limits + queues Waiting-time tickets
Sybil resistance Weak IP-based limits IP similarity + waiting
Load balancing Hotspots Topic queues Distributed across buckets
Unpopular services Inefficient Slow convergence Logarithmic lookup

Proof of Concept

The PoC demonstrates:

  • Service-specific routing tables
  • REGISTER / GET_ADS flows
  • Waiting-time ticket issuance and verification
  • Progressive discovery
  • IP similarity scoring

:test_tube: Please try it locally by following PLAYGROUND.md.

We’d love feedback on behavior under churn, scale, or adversarial setups.

Open Questions (We Want Your Input)

  • Multiple services per node

    How should nodes efficiently manage participation in multiple services without incurring excessive overhead?

  • Service table management

    Should service-specific routing tables be fully independent, lazily instantiated, or partially shared across related services?

  • Multi-role nodes

    How should behavior be defined and constrained when a single node simultaneously acts as advertiser, discoverer, and registrar for one or more services?

  • Registrar incentives

    What mechanisms can encourage nodes to operate as registrars rather than free-riding as clients only?

Call for Feedback

We’re especially interested in:

  • Security reviews and missed attack vectors
  • Suitability for your protocols
  • Deployment concernsy

This is early-stage work, and community input will shape the direction significantly.

Looking forward to your thoughts :speech_balloon:

3 Likes
2

Thanks for the post!

Went through the rfc and have some feedback and questions.

I had noticed that when an registrar issues a ticket to an advertiser the complete Ad is included in the ticket which is again expected to be included by an advertiser in subsequent register request to registrar. This leads to a redundant copy of Ad data. Why not just use some sort of a hash or an ID of the ad to be included in the Ticket?

In the Get_Ads message, would it make sense to include a repeated serviceHash field? This would help the case where a discoverer wants to discover nodes with multiple capabilities and would avoid multiple Get_Ads message. Or this would complicate the search algo for registrars?

Is it safe to assume that all nodes participating the the DHT would have registrar role? If not, then while adding nodes to tables(Advertise, Search or Registrar) there is no way to determine if a node is registrar or not.

Could not yet finish reading the complete spec, will add more questions as i go through it.

1 Like
3

It is not clear how the Registrar table will be maintained from the rfc, it is indicated that we populate it during bootstrap, but there is no indication of when entries have to be added to this table and what is the criteria for the same? If an entry gets added to adCache, does it mean it gets added to registrar table as well?
If so, what if a bucket is full in registrar table where the entry is supposed to get added? Maybe it will replace an oldest entry or not get added at all. If so will it be removed from adCache as well?
Will adCache and RegistrarTable be always in sync?

While going through the admission control requirements section, i have realized one thing. This sounds like a flow control mechanism to ensure too many requests don’t come from peers and also seems like a lightweight prevention of an eclipse attack.

If so, why not define a threshold only after which flow control gets triggered(tickets start getting issued)? How about something like based on number of entries in a bucket for a specific serviceID, registrar can decide whether to add an entry directly or issue a ticket.
I maybe missing something here though.

1 Like
4

I had one more question wrt speed of discovery. Any approximation as to how fast(e.g how many round-trips or queries) can a discoverer discover say x nodes for a specific capability/service?

This is in relation to scenario like Mix where a publisher node that comes up and wants to publish via mixnet would want to discover quickly a good number of nodes so that the mix pool is broader to select from. Ref rfc

1 Like
5

Great question! The discovery speed depends on the algorithm and network size, but here’s the breakdown:

Discovery Complexity

For discovering x nodes providing a specific service:

Best case: O(log N) queries

  • If you get lucky with bucket distribution and registrars return different peers
  • Each query to a registrar returns up to F_return (10) advertisements
  • With good distribution: ceil(x / F_return) queries minimum

Typical case: O(K_lookup × m) queries

  • K_lookup = 5 queries per bucket
  • m = 16 buckets in the search table
  • Maximum ~80 queries to traverse all buckets
  • Early termination when F_lookup (30) peers found

Round-trips: 1 RTT per query (can be parallelized within buckets)

Mix-Specific Considerations

For your Mix use case (needing ~100 nodes quickly):

Option 1: Increase F_return

  • Current: Registrars return max 10 ads per query
  • For Mix: Could increase to 20-30 for faster pool building
  • Trade-off: More bandwidth per query, but fewer total queries

Option 2: Parallel bucket queries

  • Query multiple registrars per bucket simultaneously
  • With K_lookup=5 parallel queries returning 10 ads each → 50 peers per bucket
  • 2-3 buckets needed to reach 100 peers
  • Completes in 2-3 RTTs if network is dense

Option 3: Bootstrap from Kad-DHT

  • Initialize DiscT(service_id_hash) from existing KadDHT(peerID)
  • Then query only to filter for Mix support
  • Faster initial pool, but may not be diverse enough

Hope this clears the doubt. Happy to discuss further or dive deeper if needed.

2 Likes
6

You’re right - including the full Ad in tickets is redundant. Using a hash would be cleaner. I’ll update the RFC to use ad_hash instead. Good catch!

Multiple Services in GET_ADS

Short answer: Yes, this makes sense but complicates things.

Option A - Simple batching:

message Message {
    repeated bytes keys = 2;     // multiple service_id_hashes
    repeated Advertisement ads = 13;
}

Challenges:

  • Registrar needs to handle multiple cache lookups
  • Response size limits (F_return per service or total?)
  • closerPeers becomes ambiguous - closer to which service?

Option B - Keep it simple:

  • Use multiple GET_ADS requests on same stream (already supported)

Recommendation: Start with Option B. If required, we can add Option A in v2.

Registrar Role Discovery

Current problem: No way to identify registrar capability before adding to tables (AdvT, DiscT, RegT).

Solutions:

Option 1 - Protocol ID Advertisement (simplest):

  • Registrars advertise support via identify protocol
  • Use dedicated protocol ID: /logos-discovery/registrar/1.0.0
  • Filter peers when populating tables

Option 2 - ENR Field (for Waku/discovery-based systems):

Recommendation:

  • Use Option 1 (protocol ID) as baseline - it’s already part of libp2p identify
  • Add Option 2 (ENR) for networks using ENR-based discovery
  • Nodes in client mode don’t advertise the registrar protocol ID
7

Well, my point is is there a need for 3 different node roles itself. Mostly in a service network , i envision following node types:

  1. service providing nodes (would be advertisers, but would also be registrars)
  2. service consuming nodes (discoverers)
  3. discovery bootstrap nodes (would only be registrars)

All other nodes in the network can also be advertisers+registrars.

I am not able to think of a use-case where a node would only act as advertiser and not a registrar. Maybe i am missing something here.

Wondering if we can collapse roles, would it be simpler.

I don’t think we should make it more complex ,wherein node roles within discovery domain itself are again to be discovered(i hope you get what i am trying to get at here).

1 Like
8

Great questions! These expose some critical gaps in the RFC.

You’re right - the RFC is unclear about RegT maintenance. I will update that in the RFC.

Also RegT and ad_cache are independent structures. I will add clarity about that in the RFC.

Admission Protocol with Threshold-Based Flow Control

I think we should keep the always-calculate-waiting-time approach for these reasons:

Why NOT use thresholds

1. Security-first design

The waiting-time mechanism provides continuous Sybil resistance, not just when cache is full. An attacker shouldn’t get a “free window” to flood the cache before thresholds kick in.

2. Waiting time is already fast when cache is empty

w(ad) = E × (1/(1 - c/C)^P_occ) × (c(service)/C + score(IP) + G)

When cache is empty (c ≈ 0):

  • Occupancy factor ≈ 1 (no penalty)
  • Service similarity ≈ 0 (new service)
  • IP score ≈ 0 (new IP)
  • Result: w ≈ E × 1 × (0 + 0 + G) = E × G

With G = 10⁻⁷, waiting time is essentially zero for first advertisements!

The waiting time naturally acts like a threshold - it’s negligible when cache is empty and grows as pressure increases.

3. State management complexity

Thresholds require tracking:

  • Per-service counts
  • Per-IP counts in fast-path
  • Rush attack detection
  • Probabilistic admission near boundaries

Current approach: Stateless waiting time calculation. Registrar only needs current cache state.

TL;DR: The current design is simpler, secure, and already fast for empty caches through the safety parameter G.

9

Thanks for setting out the work that has been done so far and thinking deeply about the domain.

My rough idea was that we’ll define a new libp2p protocol ID for kad-DHT based capability discovery and assume that all participants mounting this protocol will act as both registrar and (optionally) advertiser. We can bootstrap both the kad-DHT routing table and registrar table with the same configured bootstrap list (as all kad-DHT discovery nodes will be registrars). It may even be possible to enforce a tit-for-tat here by disconnecting from advertisers that have not mounted the libp2p protocol (i.e., are not acting as registrars).

Wouldn’t the advertised service_id suffice here or do we need to keep track of specific REGISTER attempts?

In general I think we can remove some duplication/nesting of information in the wire protocol. Do you have any thoughts on if/how we can use the “Extensible Peer Record” that we’re defining here: Extensible Records RFC by SionoiS · Pull Request #220 · vacp2p/rfc-index · GitHub?
For me an advertiser’s REGISTER request should simply contain it’s signed (extensible) peer record and the advertised service_id in separate fields.

10

This sounds fine to me.

Makes sense.

Sounds good.

11

We will have to be careful about how we separate all the functionalities and how we characterize nodes in the network.

I see many options;

  • We could not add any new libp2p protocols and just add our cap. logic on top of Kad-DHT. The problem I foresee is that we won’t know which nodes support cap. disco. AND have no way to discover them either.
  • We could add a new libp2p protocol for cap. disco. then we CAN discover nodes that supports cap. disco. but only via random walk, which is what cap. disco. is suppose to replace…
  • We could replace the Kad-DHT libp2p protocol ID with our own and fully separate the DHTs. This way we don’t have to “discover” cap. disco. nodes BUT we loss interoperability which result in less resilience because the network size is smaller.

I’m not sure what would be best TBH… :thinking:

1 Like
12

Since we are defining a new wire protocol, I imagine the easiest would be to define a new libp2p protocol ID for our “discovery-only DHT”. This wouldn’t prohibit us from designing an interopable version in future that could piggyback off existing libp2p kad-DHT instances, but will make our lives a bit easier in the beginning while Logos node numbers are quite low.

1 Like