Nymstr Federated Discovery Protocol v1.0

🪻 Nym Squad League Proposals
1

This is a high level overview of the system, please see full design spec here:
nymstr-federation-spec-v1.md · GitHub

Nymstr Federated Discovery Quick Pitch

What problem are we solving?

You want to send a message to @alice, but:

  • You don’t want a central server owning the global “phone book”
  • You don’t want anyone to know where Alice really is on the network
  • You still need cryptographic proof that @alice actually belongs to Alice — not an impostor

How It Works

A. Alice joins the network

  • She picks a human-readable username (@alice)
  • She picks a home node to act like a PO box (but can’t read her mail)
  • She signs a registration request and sends it to the network
  • The discovery nodes (independent servers) each vote on it
  • Once 2/3 of them agree, they add her to a shared Merkle tree and sign the new root

B. Bob wants to message @alice

  • He asks any discovery node for @alice
  • That node returns:
    • Alice’s public key
    • Alice’s home node
    • A Merkle proof showing this info was signed by the federation

C. Bob sends the message

  • He encrypts the message using Alice’s public key
  • He sends it anonymously through the mixnet to Alice’s home node
  • The home node uses a Single-Use Reply Block (SURB) to forward the message to Alice

How Nodes Stays Honest

  • Merkle trees — Every user registration is hashed into a global log anyone can verify
  • 2f + 1 quorum — No change is official unless most discovery nodes agree
  • Gossip — Updates and votes are randomly shared so bad nodes can’t hide their lies
  • Conflict proofs — If a node cheats, others can prove it and mark it as untrustworthy
  • SURBs — Keep user locations hidden; even home nodes can’t see where messages go
2 Likes
2

Thank you @code-zm! We discussed your proposal on the first Nym Council meeting. This is a really impressive implementation and we appreciate the detailed documentation.

We’d love to keep working with you on this and see how we can support your new project moving it forward. There are devs on the team who are also working on something similar and we can put you in touch.

Generally speaking, from our side this proposal is a go - but first, can you detail your milestones and the grant amount you have in mind for the project?

1 Like
3

Awesome, glad it was well received! You can find the proposal here nymCHAT to Nymstr: Continuation Grant Proposal

I’ll talk to Max about setting up an element group for the devs working on discovery.

1 Like