Heurísticas de detecção de troco

A maioria dos pagamentos em Bitcoin devolve parte do valor gasto ao remetente como troco. Identificar a saída de troco permite ao analista acompanhar os fundos restantes do remetente, reconstruir cadeias de descascamento e adicionar o endereço de troco ao cluster do remetente. Diferentemente da regra de entradas comuns, porém, a detecção de troco é sempre uma estimativa probabilística, e o histórico de pesquisas mostra que heurísticas de troco mal escolhidas são a principal causa de clusters que crescem descontroladamente.

Por que o troco existe

Um UTXO deve ser gasto integralmente. Uma carteira que possui uma moeda de 0,09 BTC e quer pagar 0,05 BTC gasta a moeda inteira, envia 0,05 BTC ao destinatário e envia o restante, descontada a taxa, para um endereço que ela controla. Veja uma transação desse tipo, decodificada e simplificada:

{
  "txid": "b52d…0e7a", "version": 2, "locktime": 861203,
  "vin": [
    {"address": "bc1q…h8e2", "type": "p2wpkh", "value_btc": 0.09000000,
     "sequence": "0xfffffffd"}
  ],
  "vout": [
    {"n": 0, "address": "1Kx3…9vQe", "type": "p2pkh", "value_btc": 0.05000000},
    {"n": 1, "address": "bc1q…7k3f", "type": "p2wpkh", "value_btc": 0.03985860}
  ]
}

A taxa é 0,09000000 − 0,08985860 = 0,00014140 BTC (14.140 satoshis). Nada nos dados indica qual saída é o pagamento. O analista precisa inferir isso, e várias pistas independentes apontam para a mesma conclusão neste caso.

As heurísticas clássicas

A ideia do endereço novo vem de Androulaki et al. (2013, "Avaliando a privacidade dos usuários no Bitcoin"), que chamaram as saídas de troco de "endereços-sombra", e de Meiklejohn et al. (2013, "Por um punhado de bitcoins"), cuja Heurística 2 classifica uma saída como troco se ela for o único endereço de saída a aparecer pela primeira vez, a transação não for uma coinbase e nenhuma saída enviar fundos de volta para um endereço de entrada (sem troco para o próprio endereço de entrada). Trabalhos posteriores acrescentaram condições: Goldfeder et al. (2018, um estudo sobre riscos à privacidade em pagamentos na web) excluíram CoinJoins, e Ermilov et al. (2017, "Agrupamento automático de endereços Bitcoin") exigiram exatamente duas saídas e um valor significativo até pelo menos a quarta casa decimal.

No exemplo: a saída 1 é um endereço novo, corresponde ao tipo P2WPKH da entrada e seu valor não é redondo, enquanto a saída 0 tem um valor redondo de 0,05 BTC destinado a um endereço legado que já recebeu fundos antes. Todos os sinais concordam que a saída 1 é troco.

Transações posteriores podem confirmar ou refutar a estimativa. Se bc1q…7k3f acabar sendo gasto junto com outras moedas já presentes no cluster do remetente, a regra de entradas comuns passa a vinculá-lo de forma independente, e a classificação como troco se torna uma evidência forte, em vez de uma inferência. Se, em vez disso, ele for gasto junto com moedas de um cluster conhecido de uma exchange, a saída 1 provavelmente era o pagamento, e a classificação deve ser revertida junto com todos os vínculos construídos a partir dela. Essa confirmação posterior é exatamente como Möser e Narayanan (2022) construíram sua base de referência validada, descrita abaixo, e é por isso que as classificações de troco devem ser reavaliadas à medida que a cadeia cresce, em vez de serem fixadas no momento em que foram atribuídas.

Impressões digitais de carteiras

O software de carteira deixa rastros consistentes em campos que o consenso não determina:

• Versão. Transações que usam bloqueios temporais relativos (BIP 68) devem definir a versão como 2; muitas carteiras ainda usam a versão 1. Nos dados analisados por Möser e Narayanan (2022), cerca de 80% das transações usavam a versão 1, portanto a versão 2, por si só, restringe as possibilidades apenas parcialmente.
• Locktime. Alguns clientes, especialmente o Bitcoin Core, definem nLockTime como a altura atual do bloco por padrão para desestimular a captura oportunista de taxas. Um locktime próximo da altura de confirmação é uma impressão digital.
• Sinalização de substituição por taxa. Uma transação sinaliza a possibilidade de substituição segundo a BIP 125 quando uma entrada tem nSequence abaixo de 0xfffffffe, como no exemplo (0xfffffffd).
• Ordenação. A BIP 69 define uma ordenação lexicográfica opcional de entradas e saídas; carteiras que a seguem produzem um padrão reconhecível.
• Comportamento de scripts e taxas. Tipos de endereço, arredondamento da taxa por unidade de tamanho e estruturas de múltiplas assinaturas também diferem entre carteiras.

A heurística de impressão digital compara a transação que gasta cada saída candidata com a original. Se a original tinha versão 2, um locktime definido como a altura do bloco e sinalização RBF, e a saída 1 é posteriormente gasta por uma transação com as mesmas três características, enquanto a saída 0 é gasta por uma transação de versão 1 com locktime 0, a saída 1 provavelmente é troco. Impressões digitais são evidências vinculadas a um período: as configurações padrão mudam entre versões, portanto registre o período que suas regras de impressão digital descrevem.

O que as pesquisas dizem sobre a precisão

A mesma heurística pode parecer excelente ou ruim dependendo de quando e como é medida.

• Meiklejohn et al. (2013) trataram um endereço reutilizado posteriormente como um sinal de falso positivo. Sua Heurística 2 ingênua produziu 13% de falsos positivos e um supercluster de 1,6 milhão de chaves; após refinamentos (esperar uma semana antes de classificar, isentar transações de jogos de dados, excluir alguns padrões de endereços, revisão manual), estimaram 0,17%.
• Kappos et al. (2022, "Como descascar um milhão") testaram a mesma família de heurísticas em clusters verificados manualmente. Mediram uma taxa de falsas descobertas de 51,64% para a heurística de Meiklejohn, 64,19% para a heurística de Androulaki e 12,7% para a heurística mais rigorosa de Ermilov, atribuindo a diferença ao quanto o uso do Bitcoin mudou desde 2013. Seu próprio método, que usa o comportamento anterior de troco e os padrões de gasto do cluster, atingiu 0,62% e 0,02% em duas variantes.
• Möser e Narayanan (2022, "Ressuscitando o agrupamento de endereços no Bitcoin") construíram uma base de referência validada a partir de trocos revelados posteriormente pela reutilização de endereços. Heurísticas individuais apresentaram baixas taxas de falsos positivos, mas encontraram apenas uma minoria das saídas de troco: a de troco ideal identificou 30,6% com uma taxa de falsos positivos de 2,6%, e a de tipo de endereço, 23,7% com 3,1%. Um classificador de floresta aleatória que combinava heurísticas e impressões digitais encontrou cerca de 82% dos trocos com uma taxa de falsos positivos próxima de 0,06%.

Disso decorrem dois aprendizados. Primeiro, as taxas de erro estão vinculadas ao seu conjunto de dados e período; cite-as com sua fonte, nunca como constantes. Segundo, mesmo uma taxa de falsos positivos de 0,06% é grande quando aplicada a centenas de milhões de transações: Möser e Narayanan descobriram que unir clusters ingenuamente com base na saída de seu classificador produziu um supercluster de 223,9 milhões de endereços, e tiveram de adicionar restrições para impedir isso (consulte a aula Avaliando a qualidade dos clusters).

Pontuação e força

Uma abordagem transparente atribui uma pontuação a cada saída candidata e aceita uma classificação como troco apenas quando uma saída está claramente à frente:

-- Pontue cada saída de transações com duas saídas como candidata a troco
SELECT o.transaction_hash, o.output_index, o.address,
       (CASE WHEN o.script_type = s.input_script_type THEN 1 ELSE 0 END)
     + (CASE WHEN MOD(o.value, 100000) <> 0 THEN 1 ELSE 0 END)
     + (CASE WHEN f.first_seen_block = o.block_number THEN 1 ELSE 0 END)
       AS change_score
FROM outputs o
JOIN tx_summary s          ON s.transaction_hash = o.transaction_hash
JOIN address_first_seen f  ON f.address = o.address
WHERE s.output_count = 2
  AND s.single_input_type = TRUE;  -- ignore entradas de tipos mistos

Cada saída ganha um ponto por corresponder ao tipo de script da entrada, um por ter um valor não redondo (não ser múltiplo de 100.000 satoshis, ou 0,001 BTC) e um por ser vista pela primeira vez neste bloco. Alguns mecanismos escrevem MOD(a, b) como a % b. A consulta pontua as duas saídas; uma etapa posterior aceita a saída 1 como troco apenas se, por exemplo, ela obtiver 3 pontos e a saída 0 obtiver 0 ou 1. Empates significam "desconhecido", não uma escolha ao acaso. A aula Consultando dados UTXO e logs e rastros EVM deriva o teste de tipo único de entrada das tabelas inputs e outputs; as tabelas auxiliares aqui são construídas a partir delas da mesma forma.

Modos de falha a lembrar

• Nenhum troco. Métodos de seleção de moedas como o Branch and Bound do Bitcoin Core procuram conjuntos de entradas que correspondam exatamente ao pagamento, produzindo transações sem troco. Uma heurística forçada a escolher uma saída classificará, então, o pagamento como troco.
• Transferências para si próprio e consolidações, nas quais todas as saídas pertencem ao remetente.
• Pagamentos em lote com muitas saídas, nas quais várias parecem novas.
• PayJoin e CoinJoin, que são projetados para frustrar essas regras.
• Tipos de endereço uniformes, que eliminam o sinal do tipo de script.

Os vínculos de troco devem levar para a tabela de evidências sua força e a classificação A–D que ela sustenta na escala do curso (Aula 3.2), e os relatórios devem declarar se uma constatação depende deles.

Foco no exame: por que existem saídas de troco; as heurísticas de endereço novo, tipo de script, valor redondo e troco ideal e o modo de falha de cada uma; as condições da Heurística 2 de Meiklejohn et al. e seu supercluster ingênuo; impressões digitais de carteiras (versão e BIP 68, locktime e prevenção da captura oportunista de taxas, sinalização RBF da BIP 125, ordenação da BIP 69) e por que são evidências vinculadas a um período; o contraste entre 0,17% (Meiklejohn, 2013) e 51,64% (Kappos et al., 2022) para a mesma heurística; por que baixas taxas de falsos positivos ainda causam colapso em grande escala; pontuar saídas e tratar empates como desconhecidos; transações sem troco.