💻 computer science

The Consensus Number of Untraceable Cryptocurrencies

Este artigo analisa os custos de sincronização da não rastreabilidade do remetente em criptomoedas ao formalizar dois designs — objetos de transferência de ativos não rastreáveis lineares (LUAT) e de estado constante (CUAT) — e determinar que, enquanto o LUAT alcança um número de consenso baixo de 2 à custa de um armazenamento crescente, o CUAT oferece estado constante, mas incorre em números de consenso ilimitados ou quadráticos e carece de ausência de inanição dependendo da força da garantia de não rastreabilidade.

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

Publicado 2026-07-24

📖 7 min de leitura🧠 Leitura aprofundada

CC BY 4.0

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

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

O Grande Assalto Digital: Escondendo-se à Vista de Todos

Imagine que você está em uma sala lotada onde todos estão sussurrando segredos. No mundo digital das criptomoedas, esta sala é o "livro-razão" (ledger), um enorme caderno público que registra quem enviou dinheiro para quem. Normalmente, este caderno é como uma parede de vidro: você pode ver exatamente quem pagou a quem, mesmo que não saiba seus nomes reais. Mas e se você quisesse fazer um pagamento sem que ninguém soubesse qual pessoa na multidão realmente entregou o dinheiro? Este é o desafio da "não rastreabilidade do remetente".

Para resolver isso, os criptógrafos usam um truque chamado "conjunto de mascaramento" (masking set). Imagine que você é quem está pagando, mas você está em um grupo de dez amigos. Todos vocês seguram envelopes de aparência idêntica. Para um observador externo, parece que qualquer um dos dez amigos pode ter pago, mas eles não conseguem dizer qual deles. O artigo que estamos explorando mergulha fundo na mecânica desses grupos. Ele faz uma pergunta muito específica, quase filosófica: Se quisermos esconder o remetente dentro de um grupo, esse ato de esconder altera a forma como o grupo funciona? Especificamente, isso torna mais difícil para o grupo entrar em consenso sobre o que aconteceu a seguir? Os autores estão analisando o "número de consenso", uma forma sofisticada de medir quanta coordenação é necessária para realizar as coisas. Pense nisso como um "medidor de congestionamento": um número baixo significa que os carros podem passar uns pelos outros facilmente; um número alto significa que eles têm que parar, esperar e discutir sobre quem vai primeiro.

As Duas Formas de se Esconder: O "Guardar Tudo" vs. O "Trocar Tudo"

O artigo compara duas estratégias diferentes para gerenciar esses grupos de amigos (conjuntos de mascaramento) para esconder o remetente. Vamos chamá-las de Estratégia Linear e Estratégia Constante.

A Estratégia Linear (LUAT): A Lista de Convidados que Não Para de Crescer
Imagine uma festa onde, toda vez que alguém paga, essa pessoa não apenas se esconde em um grupo; ela também deixa uma nota permanente na parede dizendo: "Alguém deste grupo pagou!". A festa nunca apaga essas notas. A lista de "potenciais pagadores" (allow-set) continua crescendo, e a lista de "pessoas que já pagaram" (deny-set) também continua crescendo.

A Boa Notícia: Este método é surpreendentemente tranquilo. Mesmo que a lista fique enorme, o "medidor de congestionamento" permanece muito baixo. Os autores provam que, não importa o tamanho do grupo de amigos, o sistema só precisa coordenar 2 pessoas por vez. É como uma pista de dança onde todos podem se mover livremente; mesmo que você esbarre em alguém, não precisa parar toda a festa para descobrir quem se moveu primeiro.
O Problema: A parede da festa fica coberta de post-its para sempre. O espaço de armazenamento necessário para lembrar de todos que podem ter pago cresce linearmente com cada transação. É como tentar lembrar de cada pessoa que já passou por uma porta, mesmo que elas tenham saído anos atrás.

A Estratégia Constante (CUAT): A Re-randomização Mágica
Agora, imagine uma festa diferente. Quando alguém paga, a pessoa não apenas deixa uma nota. Em vez disso, o inteiro grupo de amigos muda instantaneamente de roupas, nomes e identidades. O grupo antigo desaparece e um grupo brandamente novo aparece. Isso mantém o número total de pessoas na sala constante, para que a "parede" nunca fique bagunçada. Este é o método usado por sistemas como o Quisquis.

O Problema: É aqui que as coisas ficam caóticas. Como o inteiro grupo muda, se duas pessoas tentarem pagar ao mesmo tempo e seus grupos se sobreporem (mesmo que por apenas uma pessoa em comum), elas colidem. Elas não podem ambas ter sucesso.
O Resultado: O "medidor de congestionamento" explode. Os autores descobriram que a coordenação necessária aqui cresce quadraticamente com o tamanho do grupo. Se o seu grupo tem 10 pessoas, a coordenação necessária é de aproximadamente 100. Se você tem 100 pessoas, precisa de coordenação para 10.000! É como um jogo de dança das cadeiras onde, se dois grupos compartilham até mesmo uma única cadeira, o jogo inteiro tem que parar e recomeçar para descobrir onde cada um se senta.

O Trade-off entre Privacidade e Progresso

A maior descoberta do artigo é um trade-off rigoroso. Você pode ter privacidade, mas tem que pagar por ela em uma de duas moedas: Armazenamento ou Sincronização.

Pagar em Armazenamento (Estratégia Linear): Você mantém o histórico para sempre. O sistema permanece rápido e fácil de coordenar (número de consenso de 2), mas seu disco rígido fica cheio.
Pagar em Sincronização (Estratégia Constante): Você mantém o histórico pequeno e limpo. Mas, para fazer isso, você força o sistema a se coordenar massivamente. Quanto mais pessoas você tenta esconder, mais difícil fica para que todos entrem em acordo sobre a ordem dos eventos.

Os autores também analisaram um modo de "super-privacidade" chamado Não Rastreabilidade Forte (Strong Untraceability). Isso é como ter um detetive que observa o histórico inteiro da festa, não apenas um momento. Eles notaram que, se você quiser esconder o remetente perfeitamente ao longo de um longo histórico, os grupos de amigos devem ser organizados em um padrão matemático muito específico (como uma grade perfeita ou um plano projetivo). Se você não os organizar perfeitamente, o detetive pode adivinhar quem pagou ao ver quem aparece em muitos grupos. Quando você força esse arranjo perfeito, o "medidor de congestionamento" atinge um teto específico e elevado baseado no tamanho do grupo.

O Problema da Inanição: O Agendador Malvado

Finalmente, o artigo aborda um lado sombrio da Estratégia Constante: a Inanição (Starvation).
Imagine um valentão na festa (um "agendador adversário") que controla a música. Na Estratégia Linear, se você estiver pronto para pagar, poderá sempre pagar eventualmente, mesmo que o valentão tente impedi-lo. Na Estratégia Constante, como o grupo inteiro muda, o valentão pode ficar apertando o botão de "reset" no seu grupo específico.
Os autores provaram que, na Estratégia Constante, um valentão pode fazer uma pessoa pagar para sempre enquanto faz outra pessoa esperar para sempre, mesmo que a pessoa que espera tenha dinheiro e esteja pronta para ir. A pessoa que espera continua tentando, mas toda vez que tenta, o valentão reseta o grupo pouco antes de ela conseguir terminar. Isso é um "ataque de negação de serviço" que é matematicamente impossível de prevenir se o sistema for projetado para manter o estado pequeno.

A Conclusão

Este artigo não diz apenas "um é melhor que o outro". Ele mapeia o custo exato das suas escolhas.

Se você quer um sistema que nunca fique sem espaço e seja justo para todos, deve aceitar que a lista de transações passadas crescerá para sempre (Linear).
Se você quer um sistema que permaneça pequeno e organizado, deve aceitar que ele se tornará incrivelmente lento e complicado de coordenar conforme você adiciona mais pessoas, e que pode permitir que um valentão deixe alguns usuários em estado de inanição (Constante).

Os autores provaram esses limites com certeza matemática. Eles mostraram que você não pode ter o melhor dos dois mundos: você não pode ter um histórico pequeno e organizado e um sistema rápido, justo e fácil de coordenar ao mesmo tempo. O universo das criptomoedas exige um preço pela privacidade, e este artigo diz exatamente quanto você terá que pagar.

Resumo Técnico: O Número de Consenso de Criptomoedas Intrac traceáveis

Enunciado do Problema
As criptomoedas visam fornecer a não rastreabilidade do remetente, ocultando a conta específica que financia uma transação dentro de um conjunto de contas candidatas conhecido como "conjunto de mascaramento" (masking set). Embora as definições criptográficas de privacidade sejam bem estabelecidas, os custos de sincronização e as garantias de progresso desses mecanismos permanecem subanalisados. O artigo aborda uma escolha de design fundamental na transferência de ativos não rastreáveis: se deve reter as contas gastas em um livro-razão crescente (estado linear) ou invalidar e substituir todo o conjunto de mascaramento após a transferência (estado constante). Os autores investigam como essa escolha impacta o poder de sincronização do sistema, especificamente seu número de consenso, e sua capacidade de garantir equidade (fairness/starvation-freedom).

Metodologia
Os autores formalizam dois designs distintos como objetos de memória compartilhada parametrizados pelo tamanho do conjunto de mascaramento $\lambda$ :

Transferência de Ativos Não Rastreáveis Linear (LUAT): Modela sistemas como Zcash e Monero. Uma transferência consome uma conta de um conjunto de mascaramento e anexa um nulificador a um conjunto de negação (deny-set), enquanto o conjunto de permissão (allow-set) cresce. O conjunto de mascaramento atua como um conjunto de iscas (decoy set); conjuntos sobrepostos não conflitam.
Transferência de Ativos Não Rastreáveis Constante (CUAT): Modela sistemas como Quisquis. Uma transferência consome e substitui atomicamente cada conta em seu conjunto de mascaramento por novas representações. Consequentemente, quaisquer duas transferências com conjuntos de mascaramento que se interceptam não podem ambas ter sucesso; a sobreposição constitui um conflito.

A análise utiliza a hierarquia de consenso [Her91], determinando o número de consenso (o número máximo de processos para os quais o consenso wait-free pode ser resolvido) para esses objetos. O estudo distingue entre duas noções de não rastreabilidade:

Não Rastreabilidade Fraca: Protege uma transação isoladamente.
Não Rastreabilidade Forte: Protege contra um adversário que observa o histórico completo da transação, exigindo que quaisquer duas contas que compartilham um conjunto de mascaramento apareçam no mesmo número de conjuntos de mascaramento (incidência uniforme).

Os autores utilizam grafos de conflito para modelar restrições de sincronização, onde vértices representam conjuntos de mascaramento e arestas representam conflitos (contas compartilhadas). Eles analisam tanto protocolos de um turno (submissão de transação única) quanto protocolos de múltiplos turnos (adaptação iterativa).

Contribuições Principais e Resultados

1. LUAT: Baixa Sincronização, Alto Armazenamento

Número de Consenso: O número de consenso de um objeto LUAT não compartilhado é exatamente 2, independente do tamanho do conjunto de mascaramento $\lambda$ $λ$ e da noção de não rastreabilidade (fraca ou forte).
- Isso excede o número de consenso da transferência de ativos padrão (1) porque o conjunto de negação revela a ordem de linearização das transferências.
- Se $k$ processos compartilham uma conta, o número de consenso torna-se $\max(k, 2)$ .
Coleta de Lixo (Garbage Collection): O artigo formaliza um objeto de particionamento para coletar conjuntos de mascaramento esgotados. Este objeto tem um número de consenso de 2 (implementável via fetch-and-add), o que significa que a coleta de lixo não adiciona custos de sincronização adicionais.
Equidade (Fairness): O LUAT é livre de inanição (starvation-free). Como uma transferência consome apenas uma conta e nomeia as demais como iscas, um competidor não pode invalidar uma transferência válida ao gastar uma conta diferente no mesmo conjunto de mascaramento.
Troca (Trade-off): O custo do LUAT é o crescimento monotônico do estado (linear no número de transferências).

2. CUAT: Estado Limitado, Alta Sincronização, Sem Equidade

Não Rastreabilidade Fraca: Sob não rastreabilidade fraca, o número de consenso é ilimitado ( $\infty$ ). Uma conta "hub" pode ser incluída em arbitrariamente muitos conjuntos de mascaramento, criando cliques de conflito arbitrariamente grandes.
Não Rastreabilidade Forte: Esta noção impõe uma restrição de incidência uniforme: cada conta em um componente conectado do grafo de conflito deve aparecer no mesmo número de conjuntos de mascaramento.
- Protocolos de Um Turno: O número de consenso é limitado entre $\lfloor \lambda^2/2 \rfloor$ e $\lambda^2 - \lambda + 1$ . O limite superior é alcançado se $\lambda-1$ for uma potência de número primo (usando planos projetivos).
- Protocolos de Múltiplos Turnos: O número de consenso exato é determinado como $4\lfloor \lambda/2 \rfloor \lceil \lambda/2 \rceil$ (ou seja, $\lambda^2$ para $\lambda$ par, $\lambda^2-1$ para $\lambda$ ímpar). Isso é estritamente maior que o limite de um turno para $\lambda \ge 3$ .
Equidade (Fairness): O CUAT não é livre de inanição. Um escalonador adversário pode inaniar indefinidamente um processo ao emitir repetidamente transferências de valor zero em um conjunto de mascaramento sobreposto, invalidando a transferência pendente da vítima antes que ela possa ser confirmada (commit). Isso confirma uma conjectura sobre o Quisquis.
Troca (Trade-off): O custo do CUAT é alto poder de sincronização (quadrático em $\lambda$ ) e a perda de garantias de progresso (starvation-freedom).

Significância e Alegações
O artigo afirma expor uma escolha de design oculta em sistemas de pagamentos privados que é frequentemente obscurecida na camada criptográfica. A hierarquia de consenso revela que a própria não rastreabilidade do remetente não é inerentemente custosa em termos de sincronização. O custo surge especificamente quando o mecanismo usado para esconder o remetente (o conjunto de mascaramento) também é encarregado de limitar o estado do sistema.

O LUAT paga pela privacidade em armazenamento (livro-razão crescente), mas mantém baixa sincronização (número de consenso 2) e equidade.
O CUAT paga pela privacidade em sincronização e garantias de progresso (número de consenso quadrático, sem starvation-freedom) para alcançar estado constante.

Os autores concluem que o "preço" da privacidade depende de se o mecanismo de anonimato está desacoplado da gestão de estado. Quando desacoplado (LUAT), a privacidade é "gratuita" em relação à sincronização. Quando acoplado (CUAT), a privacidade incorre em um custo de sincronização quadrático e renuncia às garantias de equidade. O artigo fornece limites exatos para essas trocas, formalizando as estruturas de conflito (cliques e interseções bipartidas) que ditam os limites de paralelismo e equidade em criptomoedas não rastreáveis.

O Grande Assalto Digital: Escondendo-se à Vista de Todos

As Duas Formas de se Esconder: O "Guardar Tudo" vs. O "Trocar Tudo"

O Trade-off entre Privacidade e Progresso

O Problema da Inanição: O Agendador Malvado

A Conclusão

Mais como este