java-topology/defects/sparrow-0002/test/sparrow-0002-test.java

import java.util.*;

/**
 * sparrow-0002: UtxoEntry.recountMixesDone stream().anyMatch() O(M*I*T)
 *
 * In Whirlpool postmix, recountMixesDone walks the mix chain backwards.
 * For each mix iteration, for each input, it streams all wallet TXOs to
 * find a matching (hash, index) pair. With a HashMap index, the inner
 * lookup is O(1) instead of O(T).
 *
 * Severity: MEDIUM-HIGH. Whirlpool users with 100+ mix rounds and 500+
 * receive TXOs hit O(M * I * T) = O(100 * 5 * 500) = 250,000 comparisons
 * vs O(M * I) = O(500) with the fix.
 */
public class sparrow_0002_test {

    // Simulates a TXO with hash and index
    static class FakeTxo {
        final int hash;
        final long index;

        FakeTxo(int hash, long index) {
            this.hash = hash;
            this.index = index;
        }
    }

    // Defective: stream().anyMatch() over all TXOs per input per mix
    static long defectiveRecountMixesDone(List<FakeTxo> walletTxos, int mixDepth, int inputsPerMix) {
        long ops = 0;
        for (int mix = 0; mix < mixDepth; mix++) {
            int targetHash = mix; // Each mix looks for a specific tx
            long targetIndex = 0;
            for (int inp = 0; inp < inputsPerMix; inp++) {
                // stream().anyMatch: scans all wallet TXOs
                for (FakeTxo txo : walletTxos) {
                    ops++;
                    if (txo.hash == targetHash && txo.index == targetIndex) {
                        break;
                    }
                }
            }
        }
        return ops;
    }

    // Fixed: HashMap index for O(1) lookup
    static long fixedRecountMixesDone(List<FakeTxo> walletTxos, int mixDepth, int inputsPerMix) {
        // Build index once: O(T)
        Map<Integer, Set<Long>> txoIndex = new HashMap<>();
        long ops = 0;
        for (FakeTxo txo : walletTxos) {
            ops++;
            txoIndex.computeIfAbsent(txo.hash, k -> new HashSet<>()).add(txo.index);
        }

        for (int mix = 0; mix < mixDepth; mix++) {
            int targetHash = mix;
            long targetIndex = 0;
            for (int inp = 0; inp < inputsPerMix; inp++) {
                ops++;
                Set<Long> indices = txoIndex.get(targetHash);
                if (indices != null && indices.contains(targetIndex)) {
                    // found
                }
            }
        }
        return ops;
    }

    public static void main(String[] args) {
        System.out.println("sparrow-0002: UtxoEntry.recountMixesDone stream().anyMatch O(M*I*T)");
        System.out.println("=".repeat(72));
        System.out.printf("%-8s %-8s %-8s %-12s %-12s %-10s %-6s%n",
                "Mixes", "Inputs", "TXOs", "Defect ops", "Fixed ops", "Ratio", "Pass");
        System.out.println("-".repeat(72));

        boolean allPassed = true;

        int[][] configs = {
            {10, 5, 100},
            {50, 5, 300},
            {100, 5, 500},
            {200, 5, 1000}
        };

        for (int[] cfg : configs) {
            int mixDepth = cfg[0];
            int inputsPerMix = cfg[1];
            int numTxos = cfg[2];

            List<FakeTxo> walletTxos = new ArrayList<>();
            for (int i = 0; i < numTxos; i++) {
                walletTxos.add(new FakeTxo(i, 0));
            }

            long defectOps = defectiveRecountMixesDone(walletTxos, mixDepth, inputsPerMix);
            long fixedOps = fixedRecountMixesDone(walletTxos, mixDepth, inputsPerMix);
            double ratio = (double) defectOps / fixedOps;
            boolean pass = ratio > 1.5;
            if (!pass) allPassed = false;

            System.out.printf("%-8d %-8d %-8d %-12d %-12d %-10.1fx %-6s%n",
                    mixDepth, inputsPerMix, numTxos, defectOps, fixedOps, ratio, pass ? "PASS" : "FAIL");
        }

        System.out.println("-".repeat(72));
        System.out.println("Result: " + (allPassed ? "ALL PASS" : "FAIL"));
        System.exit(allPassed ? 0 : 1);
    }
}