Building a decentralized bulletin board (and accidentally reinventing Nostr)

Let's do a software engineering exercise. Our goal is to build a bulletin board. A place where anyone can post an ad, a note, a message, with no account and no sign-up. Some old hands already know I mean a BBS without registration, others will picture something like X or Mastodon. It sits somewhere in between. Let's carry on.

We add a new requirement: I don't want it to depend on a single server. Each person can run their own instance to publish, or publish on someone else's instance. It makes no difference to the end result. Every reader, no matter which server they check, will end up seeing the same notes in the same order. We just opened the box of decentralization.

Now the servers have to coordinate. If every board is a copy of the whole list, and anyone can write on any board, theirs or someone else's, how on earth do they all agree on which ads exist? That is the heart of this article.

Let me give you a spoiler: by the time we finish, we will have accidentally reinvented two technologies that already existed: FidoNet (1984) and Nostr, with its negentropy sync (2023). But let's not get ahead of ourselves.

Let's set some limits to narrow the problem down and learn what interests us.

The rules of the game

The features that define our board:

• There will be a single board shared across all servers: no topics, no sections.
• Each node keeps a full copy of the board.
• Everything is public: no login, no sign-up, no passwords, no authentication. You show up, you write, you pin your ad, done.
• A reply is just another ad: if Bob wants to answer Ana's ad, he posts a new ad that points to hers. Some hang off others, but deep down they are the same thing.

So a board is a list of ads. And syncing two nodes means getting both to hold the same list.

In maths that is called a set, and agreeing on a set is called reconciliation. Remember the terms, because I'll keep using them.

First attempt: send me everything

Ana brings up her node. Bob brings up his. Each has their own ads. Let's sync them.

The obvious approach would be this: Ana sends Bob her entire list of ads, Bob compares it with his own and keeps the ones he was missing. Then the other way around. And that's it. Solved. Believe it or not, this works. It is the simplest way to reconcile sets: exchange everything and drop the duplicates. However, it is extremely inefficient.

Imagine the two of them have 1,000,000 ads and differ in only 3. With this method, Ana sends a million lines to find out that Bob already had 999,997 of them right. You moved an entire house to discover only three bricks were missing.

Now picture doing this every few minutes to stay up to date. A million lines every time! It is unsustainable, slow and expensive.

Let's change strategy: the cost of syncing should be proportional to how much the two boards differ, not to how big they are. In other words, if both nodes have 1,000,000 ads and differ in only 3, then only 3 ads should move.

But first we need to solve a previous problem.

How do we know we already have the same ad?

When Ana and Bob compare their ads, how do they know if two of them are the same? The first thing that comes to mind is to compare letter by letter. But that is fragile. A single extra space, a different line break, and the ad looks like another one.

The solution is to give each ad an identifier that comes from its own content. You run the text through a hash function (a fixed-length summary, like SHA-256) and that summary is its identifier.

For example, the ad:

ad:  "Selling bike, reach me at Ana's node"
id:  3f9a...c17

You can compute it with a simple terminal command:

echo -n "Selling bike, reach me at Ana's node" | sha256sum

And here is the good part. Two ads with the same content have the same identifier, always, on any node, without coordinating. And two different ads have different identifiers. The identifier is assigned by the content, not by some central authoritative node or anything like that.

This is called content addressing.

And that's not all. It has other useful properties:

• Duplicate detection: if the same ad reaches Bob twice, along two different paths, both carry the same id. He keeps one and drops the other. Without thinking.
• An order: a hash is really just a huge number. That 3f9a...c17 is in hexadecimal, but underneath it is a figure, so the ids can be sorted from smallest to largest.

And a sorted set will come in very handy for reconciliation.

Telling the neighbors

Let's go back to syncing, but thinking in terms of a network, not two lone nodes.

When someone pins an ad on Ana's node, the natural thing is for Ana to pass it to the nodes she knows. Those pass it to theirs. And so the ad spreads across the whole network, hopping from neighbor to neighbor, like a rumor. This technique is called flood-fill, flooding. Many peer-to-peer networks use it to spread information with no central node, but it has a design flaw: if the network grows a lot, the information can get stuck in a loop.

For example, Ana tells Bob, Bob tells Carla, Carla tells Ana again... and the ad goes around forever.

Here content addressing already saves us halfway: since the id is the same, when the ad comes back to Ana she recognizes it and does not resend it. But we can do better and not send things we know the other one already has.

The classic trick is to write down, next to each ad, which nodes it has already passed through. A "seen by" list. Before sending an ad to Carla, I check whether Carla is already in its "seen by" list. If she is, I save myself the trouble. It is exactly what FidoNet did in the eighties with its SEEN-BY field, and Usenet with the Path and Message-ID headers.

FidoNet is a network of BBSes from the 80s that synced in the middle of the night, when phone calls were cheap.

Another technique, complementary or alternative, is to have a hop limit. If an ad has passed through N nodes, I stop resending it. For example, the Meshtastic network uses a hop limit, recommended at 3, together with the "seen by" list.

Even so, flooding takes for granted something that is not realistic: that all nodes are connected and listening at the exact moment the ad goes by.

If you weren't there, you miss it

Flooding has a big flaw: it only works if you are listening at the right moment. What if your node was off when the rumor went by? Then you never find out. The ad passed by and nobody is going to offer it to you again.

We need something more robust. Instead of living in the stream, we need a reconciliation mechanism: when two nodes meet, they compare what they have and catch up. Whenever that happens, no matter how old their ads are, even if you have been offline for a month.

We are back to the first problem: how do we compare without sending each other the whole board?

Comparing summaries: the Merkle tree

Let's bring back the hash function that told us whether two ads are equal.

Instead of sending the ads, Ana and Bob send a summary of their ads. A single hash that represents all of their board. If both summaries match, they have exactly the same list. Done. That way only a single message is sent, one that says: "we have the same thing, nothing to do".

And if they don't match... the rock and roll begins.

The classic way to look without checking everything is a Merkle tree. You take your ads, group them, hash each group, then hash the hashes, and so on until you reach a single hash at the very top: the root. You compare roots. If they differ, you go down the branches whose hashes don't match, and ignore the ones that do. You corner the difference.

For example, suppose Ana and Bob have these ads:

Ana: {3, 8, 15, 16, 23, 42, 55, 60}
Bob: {3, 8, 15, 16, 23, 42, 55, 99}

We group them in pairs, hash each group, then hash those hashes, and so on up to the root:

flowchart TD
    Root["ROOT = hash(Left, Right)"] --> L["Left = hash(A, B)"]
    Root --> R["Right = hash(C, D)"]
    L --> A["A = hash(3, 8)"]
    L --> B["B = hash(15, 16)"]
    R --> C["C = hash(23, 42)"]
    R --> D["D = hash(55, 60)"]

Ana and Bob have the same tree except at leaf D: Ana holds 60 and Bob holds 99. They agree like this:

1. They compare roots. Different, there is a difference somewhere.
2. They go down a level. The Left branch matches on both, so they prune it whole: half the list discarded in one shot.
3. The Right branch does not match. They keep going down. Inside, C matches and D does not.

In four comparisons they have cornered the difference down to group D, without looking at the rest of the board. Exactly what we wanted: compare summaries and go down only where things don't add up.

Fun fact for the nerds: this is what Cassandra or Amazon's Dynamo use to keep their replicas in check.

It is almost perfect. It just has 2 limitations:

• The tree has a fixed shape. To compare level with level, both nodes must have chopped up their ads exactly the same way, into the same groups. You don't decide on the fly where to look, the structure is decided in advance.
• The tree's leaves are fixed-size buckets. If a bucket doesn't match, they send you the whole bucket, even if only one ad inside it changed. The tree takes you to the box, not to the ad.

These are subtle limitations, but they can turn huge under heavy traffic.

Luckily, 2023 brought us a solution.

The evolution: range-based reconciliation

The idea is called range-based set reconciliation. You'll be surprised how simple and elegant it is.

To start with, there is no tree. It is 2 ideas working together: fingerprints and binary search.

First, a fingerprint is a hash that summarizes all the ads in a range. A range is a stretch of the sorted list, for example "all ads whose id runs from 3 to 60". If the fingerprint of a range matches on both nodes, that stretch is synced and there is no need to look inside.

The simplest way to compute the fingerprint is to take the ids of all the ads in the range and combine them with an operation that does not depend on order, like adding them up or XOR-ing them.

That has two advantages:

• Two nodes with the same ads get the same fingerprint even if they store them in a different order.
• It can be recomposed in chunks: the fingerprint of a big range comes from joining those of its halves, without recomputing anything.

In a real system you use something more robust than a sum, so that nobody can craft two different sets with the same fingerprint, but the idea is exactly that.

And second: if the fingerprints of a range don't match, I split the range in half and repeat on each half.

That's it. It is a binary search over the difference.

The whole algorithm fits in a handful of lines:

def reconcile(range):
    if my_fingerprint(range) == other_fingerprint(range):
        return                        # equal: nothing to do
    if few_items(range):
        exchange_ads(range)           # cheap now: just send them
        return
    left, right = split(range)        # split the range in half
    reconcile(left)                   # and repeat on each part
    reconcile(right)

Three cases and no more. If the fingerprints match, you stay quiet. If the range is already small, you send the ads directly. And if not, you split in half and go down each side. The recursion switches itself off on the branches that match and only digs where there are real differences.

Let's go with an example.

Remember that an ad's id is a hash, that is, a huge number, so sorting the ads by their id makes total sense. Here I draw them as small numbers so it reads easily. Ana's board and Bob's are almost identical, they only differ in the last one:

Ana: {3, 8, 15, 16, 23, 42, 55, 60}
Bob: {3, 8, 15, 16, 23, 42, 55, 99}

Watch how they agree:

flowchart TD
    R["Whole board
Ana's fingerprint ≠ Bob's fingerprint"] --> L["Left half: {3,8,15,16}
fingerprints MATCH, we stop here"]
    R --> D["Right half: {23,42,55,...}
fingerprints differ, we keep going"]
    D --> DL["{23,42}
fingerprints MATCH, we stop"]
    D --> DR["{55, last}
fingerprints differ, we keep going"]
    DR --> DRL["{55}
MATCH"]
    DR --> DRR["{60} on Ana vs {99} on Bob
tiny range: the ads are exchanged"]

1. Ana sends a single fingerprint of her whole board. Bob compares it with his. They don't match, there is a difference.
2. They split in half. The left half, {3,8,15,16}, gives the same fingerprint on both. With a single comparison, half the list is discarded. Nothing more is looked at there.
3. The right half doesn't match. It is split again. {23,42} matches, out. The other chunk doesn't.
4. It keeps splitting until the range is so small that summarizing no longer pays off. Ana sends 60, Bob sends 99, and the two converge.

Count the messages, it's a handful of fingerprints and two ads! Instead of the eight lines of the dumb method.

With eight elements it is not impressive. But give it a million ads that differ in a single one. Range-based reconciliation finds it in about twenty comparisons, the logarithm of the size, instead of sending a million lines.

This holds as long as the differences are few. The more there are, the more branches you have to open. But you never pay for what you already have in common. It is very efficient.

Traffic stops depending on how big the board is and starts depending only on how much the two of them differ. We have already solved the syncing problem.

And look at everything we have gained over the Merkle tree:

It is true that there are modern Merkle trees that dodge part of this: Merkle Search Trees and Prolly Trees. Their shape is derived from the content, so two replicas with the same ads reach the same tree no matter what order they received them in. They are great, and Bluesky actually uses them for its repositories. Still, they remain a tree you have to build and load. It is a design problem you can only ease, not remove.

For the record, reconciling sets over a network was not invented yesterday, there is work going back to the 2000s (Minsky and company). What the range-based approach that Aljoscha Meyer formalized (2022-2023) brings is a generic version, practical and easy to implement. And it is not chalkboard theory: the Willow protocol uses it to sync decentralized data, and Iroh brings it to Rust in its documents layer, iroh-docs, to sync devices directly. It is some of the most interesting work being built in syncing today.

Wait a second: I just reinvented FidoNet

Look back at what we have built. Many equal nodes. Each with its copy of the board. Ads identified by their content so they don't duplicate. A "seen by" field to avoid sending the same thing twice. Syncing every now and then to catch up.

That is FidoNet, literally. The BBS network that Tom Jennings started in 1984 did exactly this. They solved the decentralized board problem forty years ago, with modems and in the dark.

We have not invented anything new. We have polished something that was already good.

Prototyping the endpoints

Without writing the code, this is what the API would look like.

For people, to publish and read:

Publishing is sending the text and getting back the id the node computed:

POST /ads
Content-Type: text/plain

Selling bike, reach me at Ana's node

{ "id": "3f9a...c17" }

And reading an ad returns its text along with the id:

GET /ads/3f9a...c17

{ "id": "3f9a...c17", "text": "Selling bike, reach me at Ana's node" }

Between nodes, to sync:

To /reconcile you pass a range and its fingerprint:

{ "range": { "from": "0000", "to": "ffff" }, "fingerprint": "a3f1b2..." }

And it answers with one of the three cases from the pseudocode:

// 1. Match: nothing to do in this stretch
{ "status": "equal" }

// 2. Small range: here are my ids, compare them yourself
{ "status": "ids", "ids": ["3f9a...c17", "8b21...0d4"] }

// 3. They differ: I split it and give you each half's fingerprint
{ "status": "partition", "subranges": [
    { "from": "0000", "to": "8000", "fingerprint": "11aa..." },
    { "from": "8000", "to": "ffff", "fingerprint": "cc44..." }
]}

When reconciliation reveals which ids you are missing, you ask for their texts with /ads/fetch:

POST /ads/fetch
Content-Type: application/json

{ "ids": ["8b21...0d4"] }

[ { "id": "8b21...0d4", "text": "Looking for a flat downtown" } ]

The node that syncs calls /reconcile in a loop, going down the subranges that differ (the three cases from the pseudocode above), and at the end asks with /ads/fetch only for the ads it didn't have. The hashes travel many times; the full text, only once and at the end.

A reply needs no route of its own: it is another POST /ads whose text carries inside it the id of the ad it answers.

This is Nostr, piece by piece

Without meaning to, we have almost built Nostr:

• Every Nostr event is identified by the SHA-256 hash of its content. That is our content id, exactly.
• It is published on relays: open servers where you write without signing up, just with a key pair. That is our HTTP endpoint with no accounts.
• And to sync, the relays speak negentropy, which is nothing other than range-based reconciliation. The very same one we just derived by hand. Doug Hoyte wrote it for the strfry relay, and it lives in the spec as NIP-77.

So our BBS is practically Nostr. The one deep difference is that Nostr events are signed with the author's key, so there is an identity behind them. We dropped it to keep things simple.

Now we understand what is under the hood of Nostr and why it works.

The problems we haven't solved

Our BBS works, but it has holes:

• There is no identity, so there are no culprits. We dropped login and sign-up to keep it simple, and a network where publishing is free and anonymous is a network that fills up with spam within hours.
• We can't moderate without authority. On a single server, the admin deletes and that's that. Here there is no admin. If Ana flags an ad as garbage, why would Bob's node listen to her? And what if the one flagging garbage is the spammer, to bury everyone else? A mess.
• Without identity, voting is useless. The temptation is to let people flag spam and have an algorithm sink it. But with no accounts, I fabricate a thousand fake identities and vote whatever I like. It is the famous Sybil attack.
• It grows forever. If nobody can really delete, and everything is replicated on every node, the board only gets fatter.

None of these problems is about syncing, they are about trust.

Every decentralized system fights with this, and each one solves it in its own way.

• Mastodon and the Fediverse trust the admin of each instance. Each server moderates its own: it deletes, suspends users and can defederate, that is, block another whole instance. Shared block lists circulate among admins. You pick an instance and inherit its judgment. It works, but moderation ends up fragmented, and moving instances is costly.
• Bluesky flips it around with composable labels. Anyone can run a service that labels accounts and posts ("spam", "nsfw"), and each user subscribes to the labelers they trust. Your client hides or warns based on those labels. Moderation stops being a single truth and becomes a service you sign up for.
• The reputation route, the closest to our account-less BBS, weights each vote by how much those who are already trusted trust you (EigenTrust-style algorithms). A freshly fabricated fake identity has nobody vouching for it, so its vote carries no weight. That is the trick to dodge the Sybil attack fairly well.

It is funny, because Bluesky does the same thing Usenet already did in the nineties with NoCeM: signed notices saying "this is spam" that each reader chose whether to apply or not.

Final notes

Syncing, which looked like the hard part, turned out to be a closed and even elegant problem. What has beaten us is trust: who you are, whether I believe you, how I kick out a spammer with no boss to press the button. Syncing is a maths problem. Trust is a political one.

So next time you hear about Nostr, about Willow, about Iroh or about "local-first", you won't see magic anymore. You'll see a bulletin board with an id that is a hash and two nodes comparing fingerprints. And that is the beautiful part of deriving something from scratch.

Sources

• Range-Based Set Reconciliation, by Aljoscha Meyer. The work that generalizes and analyzes the technique. Dense, but it is the source.
• 3d Range-Based Set Reconciliation in the Willow protocol specification. The applied version, with fingerprints and recursive partitioning.
• Range-Based Set Reconciliation at Log Periodic, a more digestible explanation of the same idea.
• Iroh and Iroh-Docs, the Rust implementation that brings range-based reconciliation to real devices.
• NIP-77: Negentropy Syncing, range-based reconciliation as Nostr uses it, with Doug Hoyte's strfry relay as the reference implementation.
• Earthstar, a decentralized database with no traditional accounts that syncs by ranges, today on top of Willow.
• FTS-0004 EchoMail Specification from the FTSC, where FidoNet's MSGID and SEEN-BY live.
• FidoNet on Wikipedia, for the history of Tom Jennings' BBS network and its nightly sync model.
• ActivityPub, the W3C recommendation. The inbox-delivery model that dispatches instead of reconciling.
• Merkle tree and Apache Cassandra's anti-entropy, for the step before range-based reconciliation.
• Composable Moderation on the Bluesky blog, the model of labelers you subscribe to.
• The EigenTrust Algorithm for Reputation Management in P2P Networks, the transitive reputation that isolates the Sybil attack.
• NoCeM, the signed spam notices on Usenet in the nineties, ancestor of composable labels.
• Prolly Trees and Merkle Search Trees, variants of the Merkle tree whose shape is derived from the content and not from the insertion order.
• Mastodon 4.5 for Developers, which enables fetching a thread's missing replies by default.