Shedding Light on Complex Bitcoin Mixer Transactions: 67-Fold Reduction in Unclassified Cases

1 Introduction

• Bitcoin’s public transaction history enables fund-flow analysis, but Shared Send Mixers combine payments to obscure those flows.The protocol’s pseudonymity and the continuing effectiveness of SSMs are part of the motivation for the analysis.Source: §1 · p. 2
• The existing practical untangling algorithm leaves 1.4% of SSM transactions unresolved because of computational time limits.Earlier work found that 15% of transactions were SSMs and 90% of those were uniquely untanglable.Source: §1 · p. 2
• The paper introduces preemptive grouping, connectable singleton, ambiguous pairing, and knapsack fallback, each with a theoretical correctness proof.An optimized pipeline orders the heuristics to maximize classification efficiency.Source: §1 · p. 2
• 1.4% to 0.021% of all SSM transactions: the optimized heuristic pipeline reduces the unclassified rate, a 98.5% improvement.The pipeline targets timeout transactions left unresolved by the practical untangling algorithm.Source: §1 · p. 2
• The paper reports an open-source implementation and an empirical evaluation on historical Bitcoin data through block 882,421.The evaluation provides statistics on heuristic effectiveness and resulting transaction-type distributions.Source: §1 · p. 2

2 Related Work

• Address-clustering heuristics infer ownership from spending, change, and coinbase patterns, but are probabilistic and can misclassify.Shared Send Mixers are one source of errors because they combine payments from different users.Source: §2 · p. 3
• The practical untangling algorithm left approximately 1.4% of mixer transactions unclassified after a one-second time limit.Manual inspection found recurrent structural patterns that could help resolve these cases or reduce the search space.Source: §2 · p. 4
• Related approaches include off-chain labels, network-level attacks and countermeasures, and machine-learning models for clustering, classification, and risk scoring.These techniques complement rather than replace transaction untangling.Source: §2 · p. 5
• KeyLinker links addresses derived from a reused public key across formats, while later work examines key reuse across cryptocurrencies.These links are described as cryptographically grounded rather than based on probabilistic heuristics.Source: §2 · p. 5
• SSM untangling differs from address clustering because it seeks to recover internal fund flows within transactions combining multiple payments.The related-work discussion identifies timeout-limited SSM analysis as a remaining gap in transaction analysis.Source: §2 · pp. 5–6
• 98.5% of previously timed-out SSM transactions are resolved, reducing the overall unclassified rate from 1.4% to 0.021%.The approach targets timeout cases left by the practical algorithm.Source: §2 · p. 6

3 Transactions untangling

• The formulation represents a transaction with input and output multisets of amount-address pairs and consolidates repeated addresses before untangling.The simplification groups by address, sums values, matches the smaller input and output amounts, then discards zero amounts.Source: §3 · pp. 6–7
• The analysis assumes intended expenditure from any input subset does not exceed its actual expenditure, and favors minimal partitions over non-minimal ones.The paper motivates the minimality restriction by saying divisible flows would require additional deliberate measures.Source: §3 · pp. 7–8
• A minimal untangling is a partition into connectable input/output pairs that cannot be subdivided further into an acceptable partition.The problem asks for every minimal partition of the transaction graph.Source: §3 · p. 8
• Transactions are simple when they have no non-trivial acceptable partition, separable when they have a unique minimal partition, and ambiguous when they have multiple minimal partitions.These classes are determined from the minimal untangling solution.Source: §3 · p. 8

3.1 Transaction examples

• The examples contrast a simple transaction with no proper connectable input subset and a separable transaction whose inputs and outputs form two connectable pairs.The separable example shows one input paired with one output, while the other input pairs with the remaining two outputs.Source: §3.1 · p. 9, Figure 1 · p. 9

4 Untangling Heuristics

• The four heuristics target recurring structural patterns in timeout transactions, each with a correctness proof.The paper frames the patterns as ways to resolve cases or prune the search space for the NP-complete untangling problem.Source: §4 · p. 10

4.1 Heuristic 1: Preemptive Grouping

• Heuristic 1 locks a sufficiently dominant input and output together, then replaces them with their value difference while preserving valid untanglings and reducing transaction size.The reduction can be repeated until no qualifying pair remains.Source: §4.1 · p. 10

4.2 Heuristic 2: Connectable Singleton Reduction

• For transactions with exactly two inputs or outputs, Heuristic 2 need only enumerate candidate pairs containing the smaller side’s element, halving the search space.It prunes once the cumulative sum exceeds min(B) + c; the procedure is symmetric for two outputs.Source: §4.2 · pp. 10–11

4.3 Heuristic 3: Ambiguity via Identical Values

• Heuristic 3 classifies a transaction as ambiguous when equal-valued inputs or outputs can each form a connectable singleton pair with the opposite side.The duplicate values yield distinct minimal partitions; the heuristic checks value collisions among elements participating in singleton pairs.Source: §4.3 · pp. 11–12

4.4 Heuristic 4: Knapsack Fallback and Ambiguity Propagation

• Heuristic 4 uses bounded-knapsack search to find candidate connectable pairs, then infers transaction type from solver-result symmetries or their absence rather than treating a candidate as definitive.A second distinct pair for the same output, equal-valued elements across a pair and its complement, or no non-trivial pair supports ambiguity or simplicity under the stated rules.Source: §4.4 · pp. 12–13

Experimental pipeline

• Heuristic 1 runs first because it is computationally efficient and composable with the base solver and later heuristics; the solver then classifies transactions.Figure 5 visualizes the execution order.Source: §5 · p. 13
• Heuristic 2 precedes Heuristic 3 because both enumerate subsets iteratively, and Heuristic 3 requires multiple cycles that add computational cost.Both exclude trivially small or excessively large subsets, but remain computationally intensive.Source: §5 · p. 13
• Heuristic 4 runs last because its knapsack-solving subroutine dominates runtime, avoiding that cost for cases resolved earlier.Table 1 reports execution timing measurements.Source: §5 · p. 13

Numerical results

• On the full dataset, separable transactions generally decreased over time, though their share recently rose alongside ambiguous and time-limit transactions.Figure 6 marks the point at which prior research reported results.Source: Figure 6 · p. 14, §6 · p. 14
• The evaluation used a random sample of 50,000 transactions from 5,023,471 transactions exceeding the one-second timeout threshold.Experiments covered the blockchain through block 882,421 and used the untangling algorithm with a one-second per-transaction limit.Source: §6 · p. 14
• Heuristic 1 resolved 84% of initially ambiguous cases; Heuristics 2, 3, and 4 resolved 40%, 20%, and 80% of their respective remaining cases.Only 7.7% of transactions reached the expensive knapsack stage.Source: §6 · pp. 14, 16, Figure 7 · p. 15
• Among timeout transactions, 62% were ambiguous, 26% simple, and 11% separable, unlike the full-dataset distribution of 70% simple, 19% separable, and 9% ambiguous.The authors interpret this contrast as evidence that timeout-exceeding cases are disproportionately structurally complex.Source: §6 · p. 15
• Table 1’s timing measurements show strictly increasing computational complexity across the heuristic sequence, supporting placement of resource-intensive operations later.The pipeline’s design aims to maximize early-stage pruning efficiency.Source: Table 1 · p. 15, §6 · p. 15
• 98.5% of timeout transactions were resolved by the heuristic pipeline, versus 25% with a 300-second base-solver budget; the pipeline averaged 11.4 seconds per transaction.The reported unclassified rate fell 50-fold compared with the brute-force approach.Source: §6 · p. 15
• The sampled unresolved rate was 1.53%, with a 95% confidence interval of [1.42%, 1.64%]; sample and full-set medians closely agreed on the reported transaction measures.The authors describe the narrow interval and median agreement as evidence that the sample estimates the full timeout population reliably.Source: §6 · p. 16

• 98.5% of timeout transactions are resolved, reducing the global unclassified SSM rate from 1.4% to 0.021%—a 67-fold reduction.Source: §7 · p. 16
• Timeout cases are 62% ambiguous and 26% simple, unlike non-timeout cases at 9% ambiguous and 70% simple.Source: §7 · p. 16
• Heuristic 1 averages 0.01 s and can be integrated into transaction-processing pipelines for complexity reduction without significant overhead.Source: §7 · p. 16
• The remaining 1.5% of timeout transactions resist all four heuristics; manual inspection points to interacting conditions or near-equality constraints.Source: §7 · p. 17
• Bitcoin Cash and Litecoin can use the implementation unchanged, while Cardano’s multi-asset EUTXO setting would require adaptation.Source: §7 · p. 17
• Untangling more timeouts yields a larger separable corpus for studying address clustering and downstream forensic applications.Source: §7 · p. 17
• Ambiguous transactions may still support probabilistic flow analysis by distinguishing pairings shared across valid partitions from those that vary.Source: §7 · p. 17