💻 computer science

The Consensus Number of Untraceable Cryptocurrencies

Este artículo analiza los costos de sincronización de la irrastreabilidad del emisor en las criptomonedas mediante la formalización de dos diseños —objetos de transferencia de activos irrastreables lineales (LUAT) y de estado constante (CUAT)— y determinando que mientras el LUAT logra un número de consenso bajo de 2 a expensas de un almacenamiento creciente, el CUAT ofrece un estado constante pero incurre en números de consenso ilimitados o cuadráticos y carece de ausencia de inanición dependiendo de la fuerza de la garantía de irrastreabilidad.

Autores originales: Christian Cachin, David Lehnherr, Juan Villacis, François-Xavier Wicht

Publicado 2026-07-24

📖 7 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Christian Cachin, David Lehnherr, Juan Villacis, François-Xavier Wicht

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

El Gran Atraco Digital: Escondiéndose a plena vista

Imagina que estás en una habitación llena de gente donde todos susurran secretos. En el mundo digital de las criptomonedas, esta habitación es el "libro de contabilidad" (ledger), un cuaderno público gigante que registra quién envió dinero a quién. Normalmente, este cuaderno es como una pared de cristal: puedes ver exactamente quién pagó a quién, incluso si no conoces sus nombres reales. Pero, ¿qué pasaría si quisieras realizar un pago sin que nadie sepa qué persona de la multitud entregó realmente el efectivo? Este es el desafío de la "no trazabilidad del emisor".

Para resolver esto, los criptógrafos utilizan un truco llamado "conjunto de enmascaramiento" (masking set). Imagina que tú eres quien paga, pero te sitúas en un grupo de diez amigos. Todos sostenéis sobres de apariencia idéntica. Para un observador externo, parece que cualquiera de los diez amigos podría haber pagado, pero no pueden saber cuál de ellos fue. El artículo que estamos explorando profundiza en la mecánica de estos grupos. Plantea una pregunta muy específica, casi filosófica: Si queremos esconder al emisor dentro de un grupo, ¿cambia ese acto de ocultación la forma en que funciona el grupo? Específicamente, ¿hace que sea más difícil para el grupo ponerse de acuerdo sobre qué sucede después? Los autores analizan el "número de consenso", una forma elegante de medir cuánta coordinación se necesita para que las cosas funcionen. Piensa en ello como un "medidor de atascos": un número bajo significa que los coches pueden pasar unos junto a otros fácilmente; un número alto significa que tienen que detenerse, esperar y discutir sobre quién va primero.

Las dos formas de esconderse: El "Guardar-todo" frente al "Cambiar-todo"

El artículo compara dos estrategias diferentes para gestionar estos grupos de amigos (conjuntos de enmascaramiento) para ocultar al emisor. Llamémoslas la Estrategia Lineal y la Estrategia Constante.

La Estrategia Lineal (LUAT): La lista de invitados que crece sin cesar
Imagina una fiesta donde, cada vez que alguien paga, no solo se esconde en un grupo, sino que también deja una nota permanente en la pared diciendo: "¡Alguien de este grupo ha pagado!". La fiesta nunca borra estas notas. La lista de "posibles pagadores" (el conjunto de permiso o allow-set) sigue creciendo, y la lista de "personas que ya han pagado" (el conjunto de denegación o deny-set) también sigue creciendo.

La buena noticia: Este método es sorprendentemente tranquilo. Aunque la lista se vuelve enorme, el "medidor de atascos" se mantiene muy bajo. Los autores demuestran que, sin importar cuán grande sea el grupo de amigos, el sistema solo necesita coordinar a 2 personas a la vez. Es como una pista de baile donde todos pueden moverse libremente; incluso si chocas con alguien, no necesitas detener toda la fiesta para averiguar quién se movió primero.
El inconveniente: La pared de la fiesta se cubre de notas adhesivas para siempre. El espacio de almacenamiento necesario para recordar a cada persona que podría haber pagado crece linealmente con cada transacción. Es como intentar recordar a cada una de las personas que alguna vez pasó por una puerta, incluso si se fueron hace años.

La Estrategia Constante (CUAT): La re-randomización mágica
Ahora, imagina una fiesta diferente. Cuando alguien paga, no solo deja una nota. En su lugar, todo el grupo de amigos cambia instantáneamente de ropa, de nombre y de identidad. El viejo grupo desaparece y aparece un grupo completamente nuevo. Esto mantiene constante el número total de personas en la sala, de modo que la "pared" nunca se ensucia. Este es el método utilizado por sistemas como Quisquis.

El inconveniente: Aquí es donde las cosas se vuelven caóticas. Debido a que el grupo entero cambia, si dos personas intentan pagar al mismo tiempo y sus grupos se solapan (aunque sea por una sola persona en común), chocan entre sí. No pueden tener éxito ambos.
El resultado: El "medidor de atascos" explota. Los autores descubrieron que la coordinación necesaria aquí crece de forma cuadrática con el tamaño del grupo. Si tu grupo tiene 10 personas, la coordinación necesaria es aproximadamente 100. Si tienes 100 personas, ¡necesitas coordinación para 10.000! Es como un juego de sillas musicales donde, si dos grupos comparten incluso una silla, todo el juego tiene que detenerse y reiniciarse para decidir quién se sienta dónde.

El equilibrio entre Privacidad y Progreso

El mayor descubrimiento del artículo es un compromiso estricto. Puedes tener privacidad, pero tienes que pagar por ella con una de estas dos monedas: Almacenamiento o Sincronización.

Pagar en Almacenamiento (Estrategia Lineal): Mantienes el historial para siempre. El sistema se mantiene rápido y fácil de coordinar (número de consenso de 2), pero tu disco duro se llena.
Pagar en Sincronización (Estrategia Constante): Mantienes el historial pequeño y limpio. Pero para hacer eso, obligas al sistema a coordinarse masivamente. Cuanta más gente intentes esconder entre, más difícil será lograr que todos se pongan de acuerdo sobre el orden de los eventos.

Los autores también analizaron un modo de "super-privacidad" llamado No trazabilidad fuerte (Strong Untraceability). Esto es como tener un detective que observa el historial completo de la fiesta, no solo un momento dado. Observaron que si quieres ocultar al emisor perfectamente a lo largo de un historial largo, los grupos de amigos deben estar dispuestos en un patrón matemático muy específico (como una cuadrícula perfecta o un plano proyectivo). Si no los dispones perfectamente, el detective puede adivinar quién pagó al ver quién aparece en demasiados grupos. Cuando fuerzas esta disposición perfecta, el "medidor de atascos" alcanza un techo específico y elevado basado en el tamaño del grupo.

El problema de la inanición: El programador malvado

Finalmente, el artículo aborda un lado oscuro de la Estrategia Constante: la Inanición (Starvation).
Imagina a un matón en la fiesta (un "programador adversarial") que controla la música. En la Estrategia Lineal, si estás listo para pagar, siempre podrás pagar eventualmente, incluso si el matón intenta detenerte. Pero en la Estrategia Constante, debido a que todo el grupo cambia, el matón puede pulsar el botón de "reset" en tu grupo específico una y otra vez.
Los autores demostraron que en la Estrategia Constante, un matón puede hacer que una persona pague para siempre mientras hace que otra persona espere eternamente, incluso si la persona que espera tiene dinero y está lista para proceder. La persona que espera sigue intentándolo, pero cada vez que lo intenta, el matón reinicia el grupo justo antes de que pueda terminar. Esto es un "denegación de servicio" que es matemáticamente imposible de prevenir si el sistema está diseñado para mantener el estado pequeño.

Conclusión

Este artículo no se limita a decir "una es mejor que la otra". Mapea el coste exacto de tus elecciones.

Si quieres un sistema que nunca se quede sin espacio y sea justo con todos, debes aceptar que la lista de transacciones pasadas crecerá para siempre (Lineal).
Si quieres un sistema que se mantenga pequeño y ordenado, debes aceptar que se volverá increíblemente lento y complicado de coordinar a medida que añadas más personas, y que podría permitir que un matón deje a algunos usuarios en la inanición (Constante).

Los autores han demostrado estos límites con certeza matemática. Mostraron que no puedes tener lo mejor de ambos mundos: no puedes tener un historial pequeño y ordenado y al mismo tiempo un sistema rápido, justo y fácil de coordinar. El universo de las criptomonedas exige un precio por la privacidad, y este artículo te dice exactamente cuánto tienes que pagar.

Resumen Técnico: El Número de Consenso de las Criptomonedas Intrazables

Planteamiento del Problema
Las criptomonedas pretenden proporcionar la intratabilidad del remitente, ocultando la cuenta específica que financia una transacción dentro de un conjunto de cuentas candidatas conocido como "conjunto de enmascaramiento" (masking set). Si bien las definiciones criptográficas de privacidad están bien establecidas, los costos de sincronización y las garantías de progreso de estos mecanismos permanecen subanalizados. El artículo aborda una elección de diseño fundamental en la transferencia de activos intratables: si se retienen las cuentas gastadas en un libro mayor creciente (estado lineal) o si se invalidan y reemplazan la totalidad del conjunto de enmascaramiento tras la transferencia (estado constante). Los autores investigan cómo esta elección impacta el poder de sincronización del sistema, específicamente su número de consenso, y su capacidad para garantizar la equidad (ausencia de inanición o starvation-freedom).

Metodología
Los autores formalizan dos diseños distintos como objetos de memoria compartida parametrizados por el tamaño del conjunto de enmascaramiento $\lambda$ :

Transferencia de Activos Intratables Lineal (LUAT): Modela sistemas como Zcash y Monero. Una transferencia consume una cuenta de un conjunto de enmascaramiento y añade un nulo (nullifier) a un conjunto de denegación, mientras que el conjunto de permiso crece. El conjunto de enmascaramiento actúa como un conjunto de señuelos; los conjuntos superpuestos no entran en conflicto.
Transferencia de Activos Intratables Constante (CUAT): Modela sistemas como Quisquis. Una transferencia consume y reemplaza atómicamente cada cuenta en su conjunto de enmascaramiento por nuevas representaciones. En consecuencia, cualquier par de transferencias con conjuntos de enmascaramiento que se intersecten no pueden tener éxito simultáneamente; la superposición constituye un conflicto.

El análisis emplea la jerarquía de consenso [Her91], determinando el número de consenso (el número máximo de procesos para los cuales se puede resolver el consenso sin espera o wait-free) para estos objetos. El estudio distingue entre dos nociones de intratabilidad:

Intratabilidad Débil: Protege una transacción de forma aislada.
Intratabilidad Fuerte: Protege contra un adversario que observa el historial completo de transacciones, requiriendo que cualquier par de cuentas que compartan un conjunto de enmascaramiento aparezcan en el mismo número de conjuntos de enmascaramiento (incidencia uniforme).

Los autores utilizan grafos de conflicto para modelar las restricciones de sincronización, donde los vértices representan conjuntos de enmascaramiento y las aristas representan conflictos (cuentas compartidas). Analizan tanto protocolos de una sola ronda (submisión de una única transacción) como protocolos de múltiples rondas (adaptación iterativa).

Contribuciones Clave y Resultados

1. LUAT: Baja Sincronización, Alto Almacenamiento

Número de Consenso: El número de consenso de un objeto LUAT no compartido es exactamente 2, independiente del tamaño del conjunto de enmascaramiento $\lambda$ $λ$ y de la noción de intratabilidad (débil o fuerte).
- Esto supera el número de consenso de la transferencia de activos estándar (1) porque el conjunto de denegación revela el orden de linealización de las transferencias.
- Si $k$ procesos comparten una cuenta, el número de consenso se convierte en $\max(k, 2)$ .
Recolección de Basura (Garbage Collection): El artículo formaliza un objeto de particionamiento para recolectar los conjuntos de enmascaramiento agotados. Este objeto tiene un número de consenso de 2 (implementable mediante fetch-and-add), lo que significa que la recolección de basura no añade costos de sincronización adicionales.
Equidad (Fairness): LUAT es libre de inanición (starvation-free). Dado que una transferencia solo consume una cuenta y nombra al resto como señuelos, un competidor no puede invalidar una transferencia válida gastando una cuenta diferente en el mismo conjunto de enmascaramiento.
Compromiso (Trade-off): El costo de LUAT es el crecimiento monotónico del estado (lineal en el número de transferencias).

2. CUAT: Estado Acotado, Alta Sincronización, Sin Equidad

Intratabilidad Débil: Bajo intratabilidad débil, el número de consenso es no acotado ( $\infty$ ). Una cuenta "núcleo" (hub) puede ser incluida en arbitrariamente muchos conjuntos de enmascaramiento, creando clics de conflicto arbitrariamente grandes.
Intratabilidad Fuerte: Esta noción impone una restricción de incidencia uniforme: cada cuenta en un componente conectado del grafo de conflicto debe aparecer en el mismo número de conjuntos de enmascaramiento.
- Protocolos de una Sola Ronda: El número de consenso está acotado entre $\lfloor \lambda^2/2 \rfloor$ y $\lambda^2 - \lambda + 1$ . El límite superior se alcanza si $\lambda-1$ es una potencia de un número primo (usando planos proyectivos).
- Protocolos de Múltiples Rondas: El número de consenso exacto se determina como $4\lfloor \lambda/2 \rfloor \lceil \lambda/2 \rceil$ (es decir, $\lambda^2$ para $\lambda$ par, $\lambda^2-1$ para $\lambda$ impar). Esto es estrictamente mayor que el límite de una sola ronda para $\lambda \ge 3$ .
Equidad (Fairness): CUAT no es libre de inanición (not starvation-free). Un programador (scheduler) adversarial puede privar de recursos indefinidamente a un proceso mediante la emisión repetida de transferencias de valor cero en un conjunto de enmascaramiento superpuesto, invalidando la transferencia pendiente de la víctima antes de que pueda completarse. Esto confirma una conjetura relativa a Quisquis.
Compromiso (Trade-off): El costo de CUAT es una alta potencia de sincronización (cuadrática en $\lambda$ ) y la pérdida de la garantía de ausencia de inanición.

Significancia y Reivindicaciones
El artículo afirma exponer una elección de diseño oculta en los sistemas de pagos privados que a menudo queda oscurecida en la capa criptográfica. La jerarquía de consenso revela que la intratabilidad del remitente por sí misma no es inherentemente costosa en términos de sincronización. El costo surge específicamente cuando el mecanismo utilizado para ocultar al remitente (el conjunto de enmascaramiento) también tiene la tarea de acotar el estado del sistema.

LUAT paga por la privacidad en almacenamiento (libro mayor creciente) pero mantiene una baja sincronización (número de consenso 2) y equidad.
CUAT paga por la privacidad en sincronización y garantías de progreso (número de consenso cuadrático, sin garantía de ausencia de inanición) para lograr un estado constante.

Los autores concluyen que el "precio" de la privacidad depende de si el mecanismo de anonimato está desacoplado de la gestión del estado. Cuando están desacoplados (LUAT), la privacidad es "gratuita" respecto a la sincronización. Cuando están acoplados (CUAT), la privacidad incurre en un costo de sincronización cuadrático y renuncia a las garantías de equidad. El artículo proporciona límites exactos para estos compromisos, formalizando las estructuras de conflicto (cliques e intersecciones bipartitas) que dictan los límites de paralelismo y equidad en las criptomonedas intratables.

El Gran Atraco Digital: Escondiéndose a plena vista

Las dos formas de esconderse: El "Guardar-todo" frente al "Cambiar-todo"

El equilibrio entre Privacidad y Progreso

El problema de la inanición: El programador malvado

Conclusión

Más como este