Construyendo un tablón de anuncios descentralizado (y reinventando Nostr sin querer)

Vamos a hacer un ejercicio ingenieril de software. Nuestro objetivo es construir un tablón de anuncios. Un espacio donde cualquiera pueda publicar un anuncio/nota/mensaje, sin una cuenta o registro. Algunos viejos lobos ya sabrán que me refiero a BBS sin registro, otros se imaginarán algo parecido a X/Mastodon. Es un punto medio. Sigamos.

Añadimos un nuevo requisito: no quiero que dependa de un solo servidor. Cada persona puede tener su propia instancia para publicar o publicar en la instancia de un tercero. No afecta al resultado final. Todos los lectores, independientemente de cuál sea su servidor de consulta, acabarán viendo las mismas notas en el mismo orden. Acabamos de abrir la caja de la descentralización.

Ahora los servidores deberán coordinarse. Si cada tablón es una copia de todo el listado, y cualquiera puede escribir en cualquier tablón, suyo o de otro, ¿cómo demonios se ponen todos de acuerdo sobre qué anuncios existen? Aquí está el meollo del artículo.

Te voy a hacer un spoiler: cuando terminemos habremos reinventado, sin querer, 2 tecnologías que ya existían: FidoNet (1984) y Nostr, con sincronización negentropy (2023). Pero no nos adelantemos.

Vamos a definir algunos límites para acotar el problema y aprender lo que nos interesa.

Las reglas del juego

Las características que definen nuestro tablón:

• Habrá un único tablón compartido para todos los servidores: nada de temas ni de secciones.
• Cada nodo guarda una copia completa del tablón.
• Todo es público: no hay login, ni registro, ni contraseñas, ni autenticación. Llegas, escribes, clavas tu anuncio y ya está.
• Una réplica/respuesta es otro anuncio: si Bob quiere contestar al anuncio de Ana, publica un anuncio nuevo que apunta al de ella. Unos cuelgan de otros, pero en el fondo son la misma cosa.

Por lo tanto un tablón es una lista de anuncios. Y sincronizar dos nodos es lograr que ambos tengan la misma lista.

En matemáticas a eso se le llama un conjunto, y a ponerse de acuerdo sobre un conjunto se le llama reconciliación. Recuerda los términos porque los voy a ir nombrando.

Primer intento: mándamelo todo

Ana levanta su nodo. Bob levanta el suyo. Cada uno tiene sus anuncios. Los sincronizamos.

Lo más lógico sería lo siguiente: Ana le manda a Bob la lista entera de sus anuncios, Bob compara con la suya y se queda con los que le faltan. Luego al revés. Y ya está. Solucionado. Aunque no lo parezca, esto funciona. Es la forma más simple de reconciliar conjuntos: intercambiar todo y descartar duplicados. Sin embargo, es extremadamente ineficiente.

Imagina que los dos tienen 1.000.000 de anuncios y solo se diferencian en 3. Con este método, Ana envía un millón de líneas para descubrir que Bob ya tenía 999.997 correctos. Has movido una casa para descubrir que solo faltaban tres ladrillos.

Ahora ponte que lo quieres hacer cada pocos minutos, para estar al día. ¡Un millón de líneas cada vez! Es insostenible, lento y caro.

Cambiamos de estrategia: que el coste de sincronizar sea proporcional a lo que se diferencian los dos tablones, no a lo grandes que son. En otras palabras, si los dos nodos tienen 1.000.000 de anuncios y solo se diferencian en 3, que solo se muevan 3 anuncios.

Antes vamos a resolver un problema previo.

¿Cómo sabemos que ya tenemos el mismo anuncio?

Cuando Ana y Bob comparan sus anuncios, ¿cómo saben si 2 son el mismo? Lo primero que nos viene a la cabeza es comparar letra a letra. Pero eso es frágil. Un solo espacio de más, un salto de línea distinto, y el anuncio parece otro.

La solución es darle a cada anuncio un identificador que salga de su propio contenido. Le pasas el texto por una función de hash (un resumen de longitud fija, tipo SHA-256) y ese resumen es su identificador.

Por ejemplo, el anuncio:

anuncio: "Vendo bici, contacto en el nodo de Ana"
id:      3f9a...c17

Lo puedes calcular con un simple comando de terminal:

echo -n "Vendo bici, contacto en el nodo de Ana" | sha256sum

Y aquí viene lo bueno. Dos anuncios con el mismo contenido tienen el mismo identificador, siempre, en cualquier nodo, sin coordinarse. Y dos anuncios distintos tienen identificadores distintos. El identificador lo asigna el contenido, no un nodo central con autoridad o similar.

A esto se le llama direccionamiento por contenido.

Y no solo eso. Tiene otras propiedades útiles:

• Detección de duplicados: Si a Bob le llega dos veces el mismo anuncio por dos caminos distintos, los dos traen el mismo id. Se queda con uno y tira el otro. Sin pensar.
• Un orden: Un hash no deja de ser un número enorme. Ese 3f9a...c17 está en hexadecimal, pero por debajo es una cifra, así que los id se pueden ordenar de menor a mayor.

Y un conjunto ordenado nos va a venir muy bien para la reconciliación.

Contárselo a los vecinos

Volvamos a la sincronización, pero pensando en red, no en dos nodos sueltos.

Cuando alguien clava un anuncio en el nodo de Ana, lo suyo es que Ana se lo pase a los nodos que conoce. Esos, a los suyos. Y así el anuncio se va extendiendo por toda la red, saltando de vecino en vecino, como un rumor. A esta técnica se le llama flood-fill, inundación. Muchas redes de pares la usan para propagar información sin un nodo central, pero tiene un problema de diseño: si la red crece mucho, la información puede quedarse atrapada en un bucle.

Por ejemplo, Ana se lo cuenta a Bob, Bob a Carla, Carla a Ana otra vez... y el anuncio da vueltas para siempre.

Aquí el direccionamiento por contenido ya nos salva a medias: como el id es el mismo, cuando el anuncio vuelve a Ana, ella lo reconoce y no lo reenvía. Pero podemos hacerlo mejor y no mandar cosas que sabemos que el otro ya tiene.

El truco clásico es apuntar, junto a cada anuncio, por qué nodos ha pasado ya. Una lista de "visto por". Antes de mandarle un anuncio a Carla, miro si Carla ya está en su lista de "visto por". Si está, me lo ahorro. Es exactamente lo que hacía FidoNet en los ochenta con su campo SEEN-BY, y Usenet con las cabeceras Path y Message-ID.

FidoNet es una red de BBS de los 80 que se sincronizaban de madrugada, cuando la llamada telefónica era barata.

Otra técnica, complementaria o sustitutiva, es tener un límite de saltos. Si un anuncio ha pasado por N nodos, no lo reenvío más. Por ejemplo, la red Meshtastic usa el límite de saltos, recomendado en 3, junto con la lista de "visto por".

Aun así, la inundación da por sentado algo que no es realista: que todos los nodos están conectados y escuchando justo cuando pasa el anuncio.

Si no estabas, te lo pierdes

La inundación tiene un fallo gordo, y es que solo funciona si estás escuchando en el momento justo. ¿Y si tu nodo estaba apagado cuando pasó el rumor? Pues no te enteras. El anuncio pasó de largo y nadie te lo va a volver a ofrecer.

Necesitamos algo más robusto. En lugar de vivir en el streaming, necesitamos un mecanismo de reconciliación: cuando dos nodos se ven, comparan lo que tienen y se ponen al día. Sea cuando sea, sin importar la antigüedad de sus anuncios, aunque hayas estado un mes desconectado.

Volvemos al primer problema: ¿cómo comparamos sin enviarnos todo el tablón?

Comparar resúmenes: el árbol de Merkle

Rescatemos la función de hash que nos decía si dos anuncios son iguales.

En vez de mandar los anuncios, Ana y Bob mandan un resumen de sus anuncios. Un único hash que representa todo su tablón. Si los dos resúmenes coinciden, tienen exactamente la misma lista. Fin. Así, solo se envía un único mensaje que dice: "tenemos lo mismo, no hay nada que hacer".

Y si no coinciden... empieza el rock and roll.

La forma clásica de mirar sin revisarlo todo es un árbol de Merkle. Coges tus anuncios, los agrupas, haces un hash de cada grupo, luego un hash de los hashes, y así hasta llegar a un único hash arriba del todo: la raíz. Comparas raíces. Si difieren, bajas por las ramas cuyos hashes no cuadran, e ignoras las que sí. Vas acorralando la diferencia.

Por ejemplo, supongamos que Ana y Bob tienen estos anuncios:

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

Los agrupamos de dos en dos, hacemos el hash de cada grupo, luego el hash de esos hashes, y así hasta la raíz:

flowchart TD
    Root["RAÍZ = hash(Izq, Der)"] --> Izq["Izq = hash(A, B)"]
    Root --> Der["Der = hash(C, D)"]
    Izq --> A["A = hash(3, 8)"]
    Izq --> B["B = hash(15, 16)"]
    Der --> C["C = hash(23, 42)"]
    Der --> D["D = hash(55, 60)"]

Ana y Bob tienen el mismo árbol salvo en la hoja D: Ana guarda el 60 y Bob el 99. Se ponen de acuerdo así:

1. Comparan las raíces. Distintas, hay diferencia en algún sitio.
2. Bajan un nivel. La rama Izq coincide en los dos, así que la podan entera: media lista descartada de un plumazo.
3. La rama Der no coincide. Siguen bajando. Dentro, C coincide y D no.

En cuatro comparaciones han acorralado la diferencia hasta el grupo D, sin mirar el resto del tablón. Justo lo que buscábamos: comparar resúmenes y bajar solo por donde no cuadra.

Como dato nerd, te comento que es lo que usan Cassandra o el Dynamo de Amazon para mantener sus réplicas a raya.

Es casi perfecto, solo tiene 2 limitaciones:

• El árbol tiene una forma fija. Para poder comparar nivel con nivel, los dos nodos tienen que haber troceado sus anuncios exactamente igual, en los mismos grupos. No decides sobre la marcha dónde mirar, la estructura está decidida de antemano.
• Las hojas del árbol son cajones de tamaño fijo. Si un cajón no cuadra, te mandan el cajón entero, aunque dentro solo hubiera cambiado un anuncio. El árbol te lleva hasta la caja, no hasta el anuncio.

Son limitaciones sutiles, pero pueden volverse enormes con mucho tráfico.

Por suerte, el 2023 nos trajo una solución.

La evolución: reconciliación por rangos

La idea se llama range-based set reconciliation, reconciliación de conjuntos basada en rangos. Te va a sorprender lo simple y elegante que es.

Para empezar, no hay árbol. Son 2 ideas trabajando juntas: huellas y búsqueda binaria.

Primero, una huella (fingerprint) es un hash que resume todos los anuncios de un rango. Un rango es un tramo de la lista ordenada, por ejemplo "todos los anuncios cuyo id va del 3 al 60". Si la huella de un rango coincide en los dos nodos, ese tramo está sincronizado y no hay que mirar dentro.

La forma más simple de calcular la huella es coger los id de todos los anuncios del rango y combinarlos con una operación que no dependa del orden, como sumarlos o aplicarles un XOR.

Eso tiene dos ventajas:

• Dos nodos con los mismos anuncios sacan la misma huella aunque los tengan guardados en distinto orden.
• Se puede recomponer por trozos: la huella de un rango grande sale de juntar las de sus mitades, sin recalcular nada.

En un sistema real se usa algo más robusto que una suma, para que nadie pueda fabricar dos conjuntos distintos con la misma huella, pero la idea es exactamente esa.

Y segundo: si las huellas de un rango no coinciden, parto el rango por la mitad y repito en cada mitad.

Ya está. Es una búsqueda binaria sobre la diferencia.

El algoritmo entero cabe en un puñado de líneas:

def reconciliar(rango):
    if mi_huella(rango) == huella_del_otro(rango):
        return                          # iguales: no hay nada que hacer
    if pocos_elementos(rango):
        intercambiar_anuncios(rango)    # ya es barato: mándalos y punto
        return
    izquierda, derecha = partir(rango)  # parte el rango por la mitad
    reconciliar(izquierda)              # y repite en cada trozo
    reconciliar(derecha)

Tres casos y ninguno más. Si las huellas cuadran, te callas. Si el rango ya es pequeño, mandas los anuncios directamente. Y si no, partes por la mitad y bajas por cada lado. La recursión se apaga sola en las ramas que coinciden y solo profundiza donde hay diferencias de verdad.

Vamos con un ejemplo.

Acuérdate de que el id de un anuncio es un hash, o sea un número enorme, así que ordenar los anuncios por su id tiene todo el sentido. Aquí los pinto como números pequeños para que se lea. El tablón de Ana y el de Bob son casi iguales, solo se diferencian en el último:

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

Mira cómo se ponen de acuerdo:

flowchart TD
    R["Todo el tablón
huella de Ana ≠ huella de Bob"] --> L["Mitad izquierda: {3,8,15,16}
huellas IGUALES, paramos aquí"]
    R --> D["Mitad derecha: {23,42,55,...}
huellas distintas, seguimos"]
    D --> DL["{23,42}
huellas IGUALES, paramos"]
    D --> DR["{55, último}
huellas distintas, seguimos"]
    DR --> DRL["{55}
IGUAL"]
    DR --> DRR["{60} en Ana vs {99} en Bob
rango minúsculo: se intercambian los anuncios"]

1. Ana manda una sola huella de todo su tablón. Bob compara con la suya. No coinciden, hay diferencia.
2. Parten por la mitad. La mitad izquierda, {3,8,15,16}, da la misma huella en los dos. Con una sola comparación se descarta media lista. Ahí no se mira nada más.
3. La mitad derecha no coincide. Se vuelve a partir. {23,42} coincide, fuera. El otro trozo no.
4. Se sigue partiendo hasta que el rango es tan pequeño que ya no compensa resumir. Ana manda el 60, Bob manda el 99, y los dos convergen.

Cuenta los mensajes, ¡son un puñado de huellas y dos anuncios! En vez de las ocho líneas del método tonto.

Con ocho elementos no impresiona. Pero ponle un millón de anuncios que se diferencian en uno solo. La reconciliación por rangos lo encuentra en unas veinte comparaciones, el logaritmo del tamaño, en lugar de mandar un millón de líneas.

Esto vale mientras las diferencias sean pocas. Cuantas más haya, más ramas hay que abrir. Pero nunca pagas por lo que ya tenéis en común. Es muy eficiente.

El tráfico deja de depender de lo grande que es el tablón y pasa a depender solo de cuánto se diferencian los dos. Ya hemos resuelto el problema de la sincronización.

Y fíjate en todo lo que hemos ganado frente al árbol de Merkle:

Es cierto que hay árboles de Merkle modernos que esquivan parte de esto: los Merkle Search Trees y los Prolly Trees. Tienen una forma que se deduce del contenido, así que dos réplicas con los mismos anuncios llegan al mismo árbol sin importar en qué orden los recibieron. Son estupendos, y Bluesky los usa de verdad para sus repositorios. Sin embargo, siguen siendo un árbol que hay que construir y cargar. Es un problema de diseño que solo puedes aliviar, no eliminar.

Como dato, reconciliar conjuntos por red no lo inventó nadie ayer, hay trabajo desde los 2000 (Minsky y compañía). Lo que aporta el enfoque por rangos que formalizó Aljoscha Meyer (2022-2023) es una versión genérica, práctica y fácil de implementar. Y no es teoría de pizarra: el protocolo Willow lo usa para sincronizar datos descentralizados, e Iroh lo lleva a Rust en su capa de documentos, iroh-docs, para sincronizar dispositivos directamente. Es de lo más interesante que se está construyendo a día de hoy en sincronización.

Un momento: acabo de reinventar FidoNet

Repasa lo que hemos construido. Muchos nodos iguales. Cada uno con su copia del tablón. Anuncios que se identifican por su contenido para no duplicarse. Un campo de "visto por" para no mandar dos veces lo mismo. Sincronización de tanto en tanto para ponerse al día.

Eso es FidoNet, literalmente. La red de BBS que Tom Jennings arrancó en 1984 hacía justo esto. Resolvieron el problema del tablón descentralizado hace cuarenta años, con módems y a oscuras.

No hemos inventado nada nuevo. Hemos pulido algo que ya era bueno.

Prototipando los endpoints

Sin escribir el código, así se vería la API.

Para las personas, publicar y leer:

Publicar es mandar el texto y recibir el id que el nodo ha calculado:

POST /anuncios
Content-Type: text/plain

Vendo bici, contacto en el nodo de Ana

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

Y leer un anuncio te devuelve su texto junto al id:

GET /anuncios/3f9a...c17

{ "id": "3f9a...c17", "texto": "Vendo bici, contacto en el nodo de Ana" }

Entre nodos, para sincronizar:

A /reconcile le pasas un rango y su huella:

{ "rango": { "desde": "0000", "hasta": "ffff" }, "huella": "a3f1b2..." }

Y responde con uno de los tres casos del pseudocódigo:

// 1. Coinciden: nada que hacer en este tramo
{ "estado": "igual" }

// 2. Rango pequeño: aquí van mis id, compáralos tú
{ "estado": "ids", "ids": ["3f9a...c17", "8b21...0d4"] }

// 3. Difieren: lo parto y te doy la huella de cada mitad
{ "estado": "particion", "subrangos": [
    { "desde": "0000", "hasta": "8000", "huella": "11aa..." },
    { "desde": "8000", "hasta": "ffff", "huella": "cc44..." }
]}

Cuando la reconciliación revela qué id te faltan, pides sus textos con /anuncios/fetch:

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

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

[ { "id": "8b21...0d4", "texto": "Busco piso en el centro" } ]

El nodo que sincroniza llama a /reconcile en bucle, bajando por los subrangos que difieren (los tres casos del pseudocódigo de antes), y al final pide con /anuncios/fetch solo los anuncios que no tenía. Los hashes viajan muchas veces; el texto completo, una sola vez y al final.

Una respuesta no necesita ruta propia: es otro POST /anuncios cuyo texto lleva dentro el id del anuncio al que contesta.

Esto es Nostr, pieza por pieza

Sin querer, casi hemos hecho Nostr:

• Cada evento de Nostr se identifica por el hash SHA-256 de su contenido. Es nuestro id por contenido, calcado.
• Se publica en relays: servidores abiertos donde escribes sin registrarte, solo con un par de claves. Es nuestro endpoint HTTP sin cuentas.
• Y para sincronizar, los relays hablan negentropy, que no es otra cosa que reconciliación por rangos. La misma que acabamos de derivar a mano. La escribió Doug Hoyte para el relay strfry, y está en la especificación como NIP-77.

O sea, nuestro BBS es prácticamente Nostr. La única diferencia de fondo es que los eventos de Nostr van firmados con la clave del autor, así que ahí sí hay una identidad detrás. Nosotros la quitamos para simplificar.

Ahora entendemos qué hay debajo de Nostr y por qué funciona.

Los problemas que no hemos resuelto

Nuestro BBS funciona, pero tiene agujeros:

• No hay identidad, así que no hay culpables. Quitamos el login y el registro para simplificar, y una red donde publicar es gratis y anónimo es una red que se llena de spam en cuestión de horas.
• No podemos moderar sin autoridad. En un servidor único, el administrador borra y arreglado. Aquí no hay administrador. Si Ana marca un anuncio como basura, ¿por qué iba a hacerle caso el nodo de Bob? ¿Y si quien marca basura es el propio spammer, para tapar a los demás? Un lío.
• Sin identidad, votar no sirve. La tentación es dejar que la gente marque el spam y que un algoritmo lo hunda. Pero sin cuentas, yo me fabrico mil identidades falsas y voto lo que me dé la gana. Es el famoso ataque Sybil.
• Crece para siempre. Si nadie puede borrar de verdad, y todo se replica en todos los nodos, el tablón solo engorda.

Ninguno de estos problemas es de sincronización, sino de confianza.

Cada sistema descentralizado pelea con esto, y cada uno lo resuelve a su manera.

• Mastodon y el Fediverso confían en el administrador de cada instancia. Cada servidor modera lo suyo: borra, suspende usuarios y puede defederar, o sea bloquear a otra instancia entera. Entre admins circulan listas de bloqueo compartidas. Eliges instancia y heredas su criterio. Funciona, pero la moderación queda troceada y mudarte de instancia cuesta.
• Bluesky le da la vuelta con las etiquetas componibles. Cualquiera puede montar un servicio que etiquete cuentas y anuncios ("spam", "nsfw"), y cada usuario se suscribe a los etiquetadores en los que confía. Tu cliente oculta o avisa según esas etiquetas. La moderación deja de ser una verdad única y pasa a ser un servicio al que te apuntas.
• La vía de la reputación, la más cercana a nuestro BBS sin cuentas, pondera cada voto según cuánto confían en ti quienes ya son de fiar (algoritmos tipo EigenTrust). Una identidad falsa recién fabricada no tiene a nadie que la avale, así que su voto no pesa. Ese es el truco para esquivar bastante bien el ataque Sybil.

Es curioso, porque Bluesky hace lo mismo que ya hacía Usenet en los noventa con NoCeM: unos avisos firmados de "esto es spam" que cada lector decidía aplicar o no.

Apuntes finales

Sincronizar, que parecía lo difícil, ha resultado ser un problema cerrado y hasta elegante. Lo que se nos ha quedado grande es la confianza: quién eres, si te creo, cómo echo a un spammer sin un jefe que apriete el botón. La sincronización es un problema de matemáticas. La confianza es un problema de política.

Así que la próxima vez que oigas hablar de Nostr, de Willow, de Iroh o de "local-first", ya no verás magia; sino un tablón de anuncios con un id que es un hash y dos nodos comparando huellas. Y eso es lo bonito de derivar algo desde cero.

Fuentes

• Range-Based Set Reconciliation, de Aljoscha Meyer. El trabajo que generaliza y analiza la técnica. Denso, pero es la fuente.
• 3d Range-Based Set Reconciliation en la especificación del protocolo Willow. La versión aplicada, con huellas y partición recursiva.
• Range-Based Set Reconciliation en Log Periodic, una explicación más digerible de la misma idea.
• Iroh e Iroh-Docs, la implementación en Rust que lleva la reconciliación por rangos a dispositivos reales.
• NIP-77: Negentropy Syncing, la reconciliación por rangos tal como la usa Nostr, con el relay strfry de Doug Hoyte como implementación de referencia.
• Earthstar, base de datos descentralizada sin cuentas al uso que sincroniza por rangos, hoy sobre Willow.
• FTS-0004 EchoMail Specification del FTSC, donde viven el MSGID y el SEEN-BY de FidoNet.
• FidoNet en Wikipedia, para la historia de la red de BBS de Tom Jennings y su modelo de sincronización nocturna.
• ActivityPub, la recomendación del W3C. El modelo de entrega a buzones que reparte en vez de reconciliar.
• Merkle tree y el anti-entropy de Apache Cassandra, para el paso previo a la reconciliación por rangos.
• Composable Moderation en el blog de Bluesky, el modelo de etiquetadores a los que te suscribes.
• The EigenTrust Algorithm for Reputation Management in P2P Networks, la reputación transitiva que aísla al ataque Sybil.
• NoCeM, los avisos firmados de spam en Usenet de los noventa, antepasado de las etiquetas componibles.
• Prolly Trees y los Merkle Search Trees, variantes del árbol de Merkle cuya forma se deduce del contenido y no del orden de inserción.
• Mastodon 4.5 for Developers, que activa por defecto la búsqueda de las respuestas que faltan en un hilo.