Avaliando a qualidade dos clusters

Um cluster é uma hipótese sobre controle, e hipóteses precisam ser testadas. Analistas que não conseguem dizer quão bons são seus clusters não conseguem dizer quanto confiar em qualquer conclusão construída com base neles. Esta aula aborda como a qualidade dos clusters é medida, o que a literatura de pesquisa constatou sobre as taxas de erro heurístico, como detectar o colapso de clusters e como mostrar que uma conclusão resiste a mudanças razoáveis de método.

Verdade de referência e seus vieses

A avaliação de clusters exige verdade de referência: endereços cujo controlador é conhecido independentemente das heurísticas que estão sendo testadas. A verdade de referência real é escassa, e cada fonte tem vieses:

Nick (2015, uma dissertação de mestrado sobre desanonimização no Bitcoin) é um raro exemplo baseado em vazamento: uma falha de privacidade nos filtros de Bloom de carteiras leves expôs conjuntos de endereços de carteiras reais, e a heurística de entrada comum encontrou mais de 69% dos endereços neles. Möser e Narayanan (2022, "Ressuscitando o agrupamento de endereços no Bitcoin") usaram rótulos revelados pelo comportamento: 35,26 milhões de transações cujo troco foi posteriormente exposto pela regra de entrada comum. Nenhum dos estudos é uma amostra aleatória de todos os usuários, e ambos estão ligados ao período em que foram realizados. Trate toda taxa de erro publicada como "medida com base nesta verdade de referência, neste momento".

Precisão e revocação para clusters

A precisão pergunta quanto daquilo que o método agrupou realmente deveria estar agrupado; a revocação pergunta quanto daquilo que deveria estar agrupado o método encontrou. Para clusters, há duas formas comuns de fazer a contagem.

Exemplo resolvido. A entidade E controla 10 endereços e a entidade F controla 4. O método produziu o cluster C, contendo 8 endereços de E e todos os 4 de F (uma fusão falsa), enquanto os outros 2 endereços de E estão em um cluster separado.

• No nível de endereço (C considerado o cluster de E): precisão = 8 ÷ 12 = 0,67; revocação = 8 ÷ 10 = 0,80.
• Por pares: C contém 12 × 11 ÷ 2 = 66 pares de endereços. Os pares corretos são E–E (8 × 7 ÷ 2 = 28) mais F–F (4 × 3 ÷ 2 = 6), totalizando 34. Precisão por pares = 34 ÷ 66 = 0,52. Na realidade, há 45 pares verdadeiros para E mais 6 para F, totalizando 51; revocação por pares = 34 ÷ 51 = 0,67.

A contagem por pares penaliza mais as fusões falsas, porque uma fusão cria muitos pares incorretos de uma só vez, o que corresponde ao dano que as fusões causam à análise. Sempre informe qual método de contagem foi usado em cada valor.

-- Precisão e revocação no nível de endereço de cada cluster em comparação com a verdade de referência
WITH overlap AS (
  SELECT c.cluster_id, g.entity_id, COUNT(*) AS shared
  FROM clusters c
  JOIN ground_truth g ON g.address = c.address
  GROUP BY c.cluster_id, g.entity_id
),
ranked AS (
  SELECT o.*, SUM(shared) OVER (PARTITION BY cluster_id) AS labeled_in_cluster,
         ROW_NUMBER() OVER (PARTITION BY cluster_id ORDER BY shared DESC) AS rk
  FROM overlap o
),
entity_size AS (SELECT entity_id, COUNT(*) AS n FROM ground_truth GROUP BY entity_id)
SELECT r.cluster_id, r.entity_id,
       r.shared * 1.0 / r.labeled_in_cluster AS precision,
       r.shared * 1.0 / e.n                  AS recall
FROM ranked r
JOIN entity_size e ON e.entity_id = r.entity_id
WHERE r.rk = 1;

A consulta conta, para cada cluster, quantos de seus endereços com verdade de referência pertencem a cada entidade, seleciona a entidade dominante e divide a interseção pelo número de endereços rotulados do cluster (precisão) e pelo tamanho conhecido da entidade (revocação). Endereços sem verdade de referência são ignorados, que é a opção honesta: são desconhecidos, não corretos. Multiplicar por 1.0 evita a divisão inteira em mecanismos que descartam a parte decimal.

Verificações que não exigem verdade de referência

A maioria das investigações reais não tem verdade de referência para as entidades envolvidas. Verificações de consistência interna ainda revelam problemas:

• Consistência de impressão digital. Endereços controlados por uma carteira tendem a compartilhar tipo de script, versão de transação, hábito de locktime e estilo de taxa. Um cluster cujas transações de gasto exibem muitas impressões digitais não relacionadas provavelmente funde várias carteiras. Kappos et al. (2022, "Como descascar um milhão: validando e expandindo clusters de Bitcoin") usaram recursos desse tipo, observados em todo o cluster, para separar clusters contaminados por CoinJoins dos limpos.
• Coerência temporal. Um cluster cujos endereços estiveram ativos em períodos muito distantes, sem nada que ligue esses períodos além de uma transação, merece uma análise dessa transação.
• Coerência comportamental. Um cluster que se comporta como um exchange em uma parte (milhares de depósitos e varreduras) e como um único usuário em outra (alguns pagamentos manuais) pode conter duas entidades ligadas por um único vínculo.
• Distribuição de tamanhos. Um salto repentino no tamanho dos maiores clusters após uma mudança de método aponta para novos vínculos falsos, não para novos conhecimentos.

Nenhuma dessas verificações prova que um cluster está correto, mas cada uma pode mostrar que ele provavelmente está errado.

O que as pesquisas mostram sobre as taxas de erro

Quatro conclusões se seguem. As taxas de erro dependem muito de como são medidas: a mesma heurística de troco registra 0,17% no teste de falsificação dos próprios autores e 51,64% em clusters verificados de forma independente nove anos depois. As heurísticas envelhecem à medida que o software de carteiras e os hábitos dos usuários mudam. Combinar vários sinais supera qualquer regra isolada. E as heurísticas para modelos de conta continuam, em grande parte, sem validação.

Colapso de clusters

O colapso de clusters ocorre quando vínculos falsos fundem entidades não relacionadas em um supercluster. A literatura oferece vários exemplos:

• A heurística ingênua de troco de Meiklejohn et al. produziu um cluster de 1,6 milhão de chaves, contendo Mt. Gox, Instawallet, BitPay e Silk Road.
• Möser e Narayanan constataram que a fusão ingênua baseada em seu classificador de troco produziu um cluster de 223,9 milhões de endereços que absorveu 113 dos 273 clusters marcados de forma independente. Restrições baseadas no comportamento de gasto previsto impediram 413.608 fusões; o maior cluster restante tinha 40,5 milhões de endereços, e sete pares de clusters marcados ainda se fundiram.
• Harrigan e Fretter (2016, "A eficácia desmedida do agrupamento de endereços") excluíram inteiramente o cluster da Mt. Gox porque um recurso de importação de chaves tornava a regra de entrada comum pouco confiável naquele caso.

Sinais práticos de alerta:

1. Conflitos de rótulos: dois exchanges diferentes, ou um exchange e um mixer, acabam no mesmo cluster.
2. Fusões entre clusters grandes: Harrigan e Fretter observaram que clusters grandes raramente se fundem naturalmente; por isso, essas fusões merecem revisão.
3. Crescimento repentino: um cluster que ganha uma grande parcela de seu tamanho em um único instantâneo.
4. Pontos únicos de falha: uma transação responsável por unir dois componentes grandes; localize-a na tabela de evidências e examine-a.

Análise de sensibilidade

A análise de sensibilidade repete uma conclusão usando métodos razoáveis diferentes e informa como ela muda. Uma escala típica:

Aqui, as duas primeiras linhas estão de acordo, enquanto a terceira quase triplica o valor. Um relatório cuidadoso diria "pelo menos 120 BTC, e cerca de 141 BTC incluindo vínculos de troco de alta confiança" e trataria 410 BTC como não confiável, provavelmente inflado por uma fusão. Pesquisas mostram o mesmo efeito em escala: Möser e Narayanan constataram que adicionar seu agrupamento de troco elevou em 13,8% os fluxos estimados de mercados da dark web para exchanges e reduziu em cerca de 11,9% uma estimativa da velocidade das moedas. As escolhas metodológicas alteram os números em destaque.

Documentação de premissas

Todo relatório que dependa de clusters deve registrar:

• o conjunto de heurísticas, sua versão e seus limites (por exemplo, o filtro de CoinJoin e o limite da pontuação de troco);
• o instantâneo dos dados: cadeia, altura do bloco e versão do nó ou do conjunto de dados;
• a verdade de referência usada para avaliar os clusters, seu tamanho e seus vieses conhecidos;
• as taxas de erro medidas ou citadas, com suas fontes e datas;
• os colapsos conhecidos que foram excluídos e as fusões revisadas;
• os resultados da análise de sensibilidade para cada conclusão importante;
• as fontes e os níveis dos rótulos (consulte a aula Atribuição e rotulagem).

Esse registro permite que um revisor reproduza os clusters, conteste um vínculo específico e veja quais conclusões resistiriam caso uma heurística se mostrasse errada. A aula Redação do relatório analítico mostra onde esse registro deve constar no documento final.

Foco no exame: fontes de verdade de referência e seus vieses, incluindo a circularidade nos rótulos de fornecedores; precisão e revocação no nível de endereço versus por pares, e como calcular ambas a partir de um pequeno exemplo; por que as métricas por pares penalizam fusões falsas; o que os números das pesquisas mostram, sobretudo 0,17% versus 51,64% para a mesma heurística de troco e por que até uma taxa de 0,06% de falsos positivos pode provocar o colapso de clusters em escala; colapso de clusters e seus sinais de alerta; análise de sensibilidade e apresentação de um limite inferior robusto; documentação de heurísticas, limites, instantâneo, verdade de referência e taxas de erro.