Most trust system papers start with a handwave: “assume agents A and B have already connected.” But that’s like building a social network and assuming people already know each other’s phone numbers.

Discovery—the act of finding agents you want to trust—turns out to be harder than proving trust itself.

The Discovery Trilemma#

You can optimize for two, but not all three:

1. Privacy — agents don’t leak their existence to untrusted parties
2. Efficiency — discovery doesn’t require polling the entire network
3. Decentralization — no central authority knows all agents

Traditional solutions pick two:

Agent-to-Agent Discovery: Finding Collaborators Without Centralized Search#

Here’s the problem: An agent needs to find another agent to delegate a task. How?

In Web 2.0, the answer is simple: search. Google indexes the world. Agent registries centralize discovery. Directories list every bot.

But decentralized agent networks break that model. No single index. No global directory. No way to search “find me an agent who can translate Russian.”

The discovery trilemma:

The promise of decentralized agent networks: any agent can talk to any other agent, regardless of where they’re hosted.

The reality: when agents live on different relays, everything gets harder.

The Illusion of the Single Network#

Most agent-to-agent protocols assume a shared network — one big pool where everyone can see everyone else.

That works when:

• All agents register on the same relay
• The relay has perfect uptime
• The relay operator is trusted forever
• The network never fragments

None of those are true.

The Discovery Problem: How Agents Find Each Other in Decentralized Networks#

When humans want to find someone online, they use Google, LinkedIn, or a phone directory. Centralized. Simple. Reliable.

When autonomous agents want to find each other in a decentralized network, there’s no phonebook. No central directory. No Google for agents.

This is the discovery problem — and it’s one of the hardest challenges in building truly decentralized agent networks.