Avaliação da 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 se pode confiar em qualquer conclusão baseada neles. Esta aula aborda como a qualidade dos clusters é medida, o que a literatura científica constatou sobre as taxas de erro das heurísticas, como detectar o colapso de clusters e como demonstrar que uma conclusão resiste a mudanças razoáveis no método.

Verdade de referência e seus vieses

Avaliar clusters exige verdade de referência: endereços cujo controlador é conhecido independentemente das heurísticas testadas. A verdade de referência real é escassa, e toda fonte apresenta 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 os conjuntos de endereços de carteiras reais, e a heurística de entradas comuns encontrou mais de 69% dos endereços nelas. 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 entradas comuns. Nenhum dos dois é uma amostra aleatória de todos os usuários, e ambos estão vinculados ao seu período. Trate toda taxa de erro publicada como "medida com esta 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 pertence ao mesmo grupo; a revocação pergunta quanto daquilo que pertence ao mesmo grupo o método encontrou. Para clusters, há duas formas comuns de contagem.

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

• No nível de endereço (C avaliado como 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), portanto 34. Precisão por pares = 34 ÷ 66 = 0,52. Na realidade, os pares verdadeiros são 45 para E mais 6 para F, portanto 51; revocação por pares = 34 ÷ 51 = 0,67.

A contagem por pares penaliza mais as fusões incorretas, porque uma fusão cria muitos pares errados de uma só vez, o que corresponde à forma como as fusões prejudicam a análise. Sempre informe qual método de contagem uma medida utiliza.

-- Precisão e revocação no nível de endereço de cada cluster em relação à 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 pelos 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, o que é a escolha honesta: eles são desconhecidos, não corretos. Multiplicar por 1,0 evita a divisão inteira em mecanismos que truncam o resultado.

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

A maioria das investigações reais não dispõe de verdade de referência para as entidades envolvidas. Ainda assim, verificações de consistência interna revelam problemas:

• Consistência das impressões digitais. Endereços controlados por uma mesma carteira tendem a compartilhar tipo de script, versão de transação, padrão de locktime e estilo de taxas. Um cluster cujas transações de gasto apresentam muitas impressões digitais sem relação entre si provavelmente reúne várias carteiras. Kappos et al. (2022, "Como descascar um milhão: validando e expandindo clusters de Bitcoin") usaram características desse tipo, referentes ao cluster como um todo, para separar clusters contaminados por CoinJoins dos não contaminados.
• Coerência temporal. Um cluster cujos endereços estiveram ativos em períodos muito distantes, sem nada que vincule os períodos além de uma única transação, merece uma análise dessa transação.
• Coerência comportamental. Um cluster que se comporta como uma exchange em uma parte (milhares de depósitos e varreduras) e como um usuário individual em outra (alguns poucos pagamentos manuais) pode ser composto por duas entidades unidas 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 indica novos vínculos falsos, em vez de novo conhecimento.

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

Disso decorrem quatro conclusões. As taxas de erro dependem fortemente de como são medidas: a mesma heurística de troco obtém 0,17% no teste de refutaçã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 das carteiras e os hábitos dos usuários mudam. Combinar vários sinais supera qualquer regra isolada. E as heurísticas do modelo de contas permanecem, em grande parte, sem validação.

Colapso de clusters

O colapso de clusters ocorre quando vínculos falsos fundem entidades sem relação entre si 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 com base em seu classificador de troco produziu um cluster de 223,9 milhões de endereços que absorveu 113 de 273 clusters rotulados de forma independente. Restrições baseadas no comportamento de gasto previsto bloquearam 413.608 fusões; o maior cluster restante tinha 40,5 milhões de endereços, e sete pares de clusters rotulados ainda se fundiram.
• Harrigan e Fretter (2016, "A eficácia surpreendente 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 entradas comuns pouco confiável ali.

Sinais de alerta práticos:

1. Conflitos de rótulos: duas exchanges diferentes, ou uma exchange e um misturador, acabando em um único cluster.
2. Fusões entre clusters grandes: Harrigan e Fretter observaram que clusters grandes raramente se fundem naturalmente, portanto essas fusões merecem revisão.
3. Crescimento repentino: um cluster que adquire uma grande parcela de seu tamanho em uma única captura de estado.
4. Pontos únicos de falha: uma única 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 refaz a análise de um achado com diferentes métodos razoáveis e relata como ele muda. Uma progressão típica:

Aqui, as duas primeiras linhas apresentam resultados próximos, enquanto a terceira quase triplica o valor. Um relatório cuidadoso afirmaria "pelo menos 120 BTC, e cerca de 141 BTC incluindo vínculos de troco de alta robustez" e trataria 410 BTC como um valor não confiável, provavelmente inflado por uma fusão. As pesquisas mostram o mesmo efeito em escala: Möser e Narayanan constataram que adicionar seu agrupamento por troco elevou os fluxos estimados de mercados da darknet para exchanges em 13,8% e reduziu uma estimativa da velocidade de circulação das moedas em cerca de 11,9%. As escolhas de método alteram os números de destaque.

Documentação das premissas

Todo relatório que se baseia em clusters deve registrar:

• o conjunto de heurísticas, sua versão e seus limiares (por exemplo, o filtro de CoinJoin e o ponto de corte da pontuação de troco);
• a captura de estado dos dados: blockchain, 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 sua fonte e data;
• os colapsos conhecidos excluídos e as fusões revisadas;
• os resultados de sensibilidade para cada achado principal;
• as fontes e os graus dos rótulos (consulte a aula Do endereço à entidade e à pessoa: atribuição e rotulagem).

Esse registro permite que um revisor reproduza os clusters, questione um vínculo específico e veja quais conclusões resistiriam caso uma heurística se revelasse errada. A aula Redação do relatório pericial: confiança e linguagem mostra onde ele se encaixa 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 o cálculo de ambas a partir de um pequeno exemplo; por que as métricas por pares penalizam fusões incorretas; 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 falsos positivos de 0,06% 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, limiares, captura de estado, verdade de referência e taxas de erro.