Euristiche di rilevamento del resto

La maggior parte dei pagamenti Bitcoin restituisce al mittente una parte del valore speso sotto forma di resto. Identificare l'output di resto consente all'analista di seguire i fondi rimanenti del mittente, ricostruire le catene di peeling e aggiungere l'indirizzo di resto al cluster del mittente. A differenza della regola degli input comuni, tuttavia, il rilevamento del resto è sempre un'ipotesi probabilistica e la letteratura scientifica mostra che euristiche del resto scelte in modo inadeguato sono la causa principale dell'espansione incontrollata dei cluster.

Perché esiste il resto

Un UTXO deve essere speso interamente. Un wallet che detiene una moneta da 0,09 BTC e vuole pagare 0,05 BTC spende l'intera moneta, invia 0,05 BTC al destinatario e invia la parte rimanente, al netto della commissione, a un indirizzo sotto il proprio controllo. Ecco una transazione di questo tipo, decodificata e semplificata:

{
  "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}
  ]
}

La commissione è pari a 0,09000000 − 0,08985860 = 0,00014140 BTC (14.140 satoshi). Nessun elemento nei dati indica quale output rappresenti il pagamento. L'analista deve dedurlo e, in questo caso, diversi indizi indipendenti conducono alla stessa conclusione.

Le euristiche classiche

L'idea dell'indirizzo nuovo deriva da Androulaki et al. (2013, "Evaluating User Privacy in Bitcoin"), che chiamavano gli output di resto "indirizzi ombra", e da Meiklejohn et al. (2013, "A Fistful of Bitcoins"), la cui Euristica 2 classifica un output come resto se è l'unico indirizzo di output che compare per la prima volta, la transazione non è una coinbase e nessun output rinvia fondi a un indirizzo di input (nessun resto allo stesso indirizzo). Studi successivi hanno aggiunto condizioni: Goldfeder et al. (2018, uno studio sui rischi per la riservatezza nei pagamenti web) hanno escluso i CoinJoin, mentre Ermilov et al. (2017, "Automatic Bitcoin Address Clustering") hanno richiesto esattamente due output e un valore significativo almeno fino alla quarta cifra decimale.

Nell'esempio, l'output 1 è un indirizzo nuovo, corrisponde al tipo P2WPKH dell'input e il suo importo non è tondo, mentre l'output 0 è un importo tondo di 0,05 BTC verso un indirizzo legacy che ha già ricevuto fondi. Tutti i segnali concordano sul fatto che l'output 1 sia il resto.

Le transazioni successive possono confermare o smentire l'ipotesi. Se bc1q…7k3f viene infine speso insieme ad altre monete già presenti nel cluster del mittente, la regola degli input comuni lo collega ora in modo indipendente e la classificazione come resto diventa un elemento probatorio solido anziché un'inferenza. Se invece viene speso insieme a monete appartenenti al cluster di un exchange noto, l'output 1 era probabilmente il pagamento e la classificazione deve essere revocata insieme a ogni collegamento costruito su di essa. Questa conferma differita è esattamente il metodo con cui Möser e Narayanan (2022) hanno costruito i loro dati di riferimento verificati, descritti di seguito, ed è il motivo per cui le classificazioni del resto dovrebbero essere rivalutate man mano che la catena cresce, anziché rimanere fissate al momento della loro assegnazione.

Impronte caratteristiche dei wallet

Il software wallet lascia tracce coerenti nei campi che il consenso non vincola:

• Versione. Le transazioni che utilizzano blocchi temporali relativi (BIP 68) devono impostare la versione 2; molti wallet utilizzano ancora la versione 1. Nei dati analizzati da Möser e Narayanan (2022), circa l'80% delle transazioni utilizzava la versione 1, quindi la sola versione 2 restringe il campo soltanto in parte.
• Locktime. Alcuni client, in particolare Bitcoin Core, impostano per impostazione predefinita nLockTime all'altezza corrente del blocco per scoraggiare il fee sniping. Un locktime vicino all'altezza di conferma costituisce un'impronta caratteristica.
• Segnalazione replace-by-fee. Una transazione segnala la sostituibilità prevista da BIP 125 quando un input ha un valore nSequence inferiore a 0xfffffffe, come nell'esempio (0xfffffffd).
• Ordinamento. BIP 69 definisce un ordinamento lessicografico facoltativo degli input e degli output; i wallet che lo seguono producono uno schema riconoscibile.
• Comportamento relativo a script e commissioni. Anche i tipi di indirizzo, l'arrotondamento del tasso di commissione e le strutture multisig differiscono tra i wallet.

L'euristica delle impronte caratteristiche confronta la transazione che spende ciascun output candidato con quella originale. Se quella originale aveva versione 2, un locktime impostato all'altezza del blocco e la segnalazione RBF, e l'output 1 viene successivamente speso da una transazione con le stesse tre caratteristiche mentre l'output 0 viene speso da una transazione di versione 1 con locktime 0, l'output 1 è probabilmente il resto. Le impronte caratteristiche sono elementi probatori legati a un periodo specifico: le impostazioni predefinite cambiano tra le versioni, quindi occorre registrare il periodo descritto dalle regole di riconoscimento delle impronte caratteristiche.

Che cosa dice la ricerca sull'accuratezza

La stessa euristica può apparire eccellente o scadente a seconda di quando e come viene misurata.

• Meiklejohn et al. (2013) consideravano il successivo riutilizzo di un indirizzo come un segnale di falso positivo. La loro Euristica 2 non raffinata produceva il 13% di falsi positivi e un supercluster di 1,6 milioni di chiavi; dopo alcuni perfezionamenti (attendere una settimana prima della classificazione, esentare le transazioni dei giochi di dadi, escludere alcuni schemi di indirizzi, effettuare una revisione manuale) hanno stimato lo 0,17%.
• Kappos et al. (2022, "How to Peel a Million") hanno verificato la stessa famiglia di euristiche su cluster verificati manualmente. Hanno misurato un tasso di false scoperte del 51,64% per l'euristica di Meiklejohn, del 64,19% per quella di Androulaki e del 12,7% per la più restrittiva euristica di Ermilov, attribuendo la differenza ai cambiamenti nell'utilizzo di Bitcoin dal 2013. Il loro metodo, che utilizza il comportamento passato del cluster relativo al resto e gli schemi di spesa, ha raggiunto lo 0,62% e lo 0,02% in due varianti.
• Möser e Narayanan (2022, "Resurrecting Address Clustering in Bitcoin") hanno costruito dati di riferimento verificati a partire dal resto successivamente rivelato dal riutilizzo degli indirizzi. Le singole euristiche presentavano bassi tassi di falsi positivi, ma individuavano soltanto una minoranza degli output di resto: il resto ottimale ne identificava il 30,6% con un tasso di falsi positivi del 2,6%, il tipo di indirizzo il 23,7% con il 3,1%. Un classificatore a foresta casuale che combinava euristiche e impronte caratteristiche individuava circa l'82% del resto con un tasso di falsi positivi vicino allo 0,06%.

Ne derivano due insegnamenti. In primo luogo, i tassi di errore sono legati al relativo insieme di dati e al periodo; vanno citati con la loro fonte, mai come costanti. In secondo luogo, anche un tasso di falsi positivi dello 0,06% è elevato quando viene applicato a centinaia di milioni di transazioni: Möser e Narayanan hanno riscontrato che unire i cluster in modo ingenuo sulla base dei risultati del loro classificatore produceva un supercluster di 223,9 milioni di indirizzi e hanno dovuto aggiungere vincoli per impedirlo (si veda la lezione Valutazione della qualità dei cluster).

Assegnazione dei punteggi e solidità

Un approccio trasparente assegna un punteggio a ciascun output candidato e accetta una classificazione come resto soltanto quando un output è nettamente in vantaggio:

-- Assegna a ogni output delle transazioni con due output un punteggio come candidato resto
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;  -- esclude gli input di tipi diversi

Ogni output ottiene un punto per la corrispondenza con il tipo di script degli input, uno per un valore non tondo (non multiplo di 100.000 satoshi, ovvero 0,001 BTC) e uno per essere comparso per la prima volta in questo blocco. Alcuni motori scrivono MOD(a, b) come a % b. La query assegna un punteggio a entrambi gli output; un passaggio successivo accetta l'output 1 come resto soltanto se, ad esempio, ottiene 3 punti e l'output 0 ne ottiene 0 o 1. La parità significa "sconosciuto", non una scelta casuale. La lezione Interrogazione dei dati UTXO e dei log e delle tracce EVM ricava il controllo sull'unicità del tipo di input dalle tabelle inputs e outputs; le tabelle ausiliarie qui utilizzate sono costruite a partire da esse nello stesso modo.

Modalità di errore da ricordare

• Totale assenza di resto. Metodi di selezione delle monete come Branch and Bound di Bitcoin Core cercano insiemi di input che corrispondano esattamente al pagamento, producendo transazioni senza resto. Un'euristica obbligata a scegliere un output classificherà quindi il pagamento come resto.
• Trasferimenti a sé stessi e consolidamenti, in cui ogni output appartiene al mittente.
• Pagamenti in blocco con molti output, diversi dei quali appaiono nuovi.
• PayJoin e CoinJoin, progettati per vanificare queste regole.
• Tipi di indirizzo uniformi, che eliminano il segnale del tipo di script.

I collegamenti basati sul resto dovrebbero riportare nella tabella degli elementi probatori la propria solidità e il grado A–D che essa giustifica sulla scala del corso (Lezione 3.2), e i rapporti dovrebbero dichiarare se un risultato dipende da tali collegamenti.

Focus sull'esame: perché esistono gli output di resto; le euristiche dell'indirizzo nuovo, del tipo di script, dell'importo tondo e del resto ottimale e la modalità di errore di ciascuna; le condizioni dell'Euristica 2 di Meiklejohn et al. e il supercluster prodotto dalla sua applicazione ingenua; le impronte caratteristiche dei wallet (versione e BIP 68, locktime e prevenzione del fee sniping, segnalazione RBF secondo BIP 125, ordinamento secondo BIP 69) e perché sono elementi probatori legati a un periodo specifico; il contrasto tra lo 0,17% (Meiklejohn, 2013) e il 51,64% (Kappos et al., 2022) per la stessa euristica; perché bassi tassi di falsi positivi causano comunque il collasso su larga scala; assegnare punteggi agli output e considerare le parità come esiti sconosciuti; le transazioni senza resto.