Two functions, and one number that has to be zero
Session 1 left an address column that passes every test for a key and is not one party per value. Session 2 listed holders after co-spend clustering as one of four defensible definitions and deferred the algorithm. Tonight is the algorithm, in code, running on the same generated world every session uses. Nothing here is heavier than an undergraduate data structure, and the interesting part is not the structure. It is what the output can and cannot support once you have it.
★ What you walk out with tonight. Union-find written out and understood line by line: find with path halving, union by rank, and why both exist. The clustering rule in its entirety, which is one for loop. A reproduction of Bench A with the seed convention stated, so anybody can get 982, 304, 696 and 0 on their own machine. And the derivation of the asymmetry: why a missed link is ordinary and a wrong merge would require something the data cannot express.
LiveWhat the evidence actually is4 min▶
A transaction can draw on more than one input address. Building one that does requires the ability to authorise every input it names, so a transaction with two inputs is a statement that one party could authorise both. That statement is made by the structure of the record rather than inferred from behaviour, timing, amount or anything else, and it is the only statement of its kind that the rows contain.
That is the whole of the evidence. There are no attributes to compare, no names to match, no addresses of the postal kind to standardise and no scores to threshold. The family of technique built for that situation, probabilistic linkage with agreement weights and blocking, belongs to learn-entity-resolution-with-phoebe and has nothing to work on here. What is left is deterministic: either two addresses were spent together or they were not.
Larkfield's team spent a week looking for a second signal before accepting that there is not one. Timing correlation between addresses turned out to be a property of when the product issues rewards rather than of who holds them. Amount patterns were a property of the reward schedule. Both produced clusters that looked plausible and scored badly against the generated truth, which is the reason a generated world exists: a plausible method and a correct method are indistinguishable on data where nobody knows the answer.
Self-studyThe words that keep coming back4 min▶
- Co-spend. A single transaction naming two or more input addresses. The only evidence of common control in the rows.
- Union-find. A structure holding a partition of a set, supporting two operations: which group is this in, and merge these two groups.
- Find. Walk from a node to the root of its tree. The root is the group's name.
- Path halving. While walking, point each node at its grandparent. The next walk is shorter, and nothing about the partition changes.
- Union by rank. Attach the shorter tree under the taller one, so the result does not get deeper than it has to.
- Cluster. One group in the final partition. The count of distinct roots.
- Still split. Clusters beyond the true entity count: links the method failed to make.
- Wrongly merged. A cluster holding addresses from more than one party. Tonight derives why this is 0.
- Probabilistic linkage. Fellegi-Sunter weights, blocking, string comparison. A different craft for a different evidence base, and it lives in learn-entity-resolution-with-phoebe.
Union-find, and the one loop that uses it
15 min liveStart with the structure, because once it is clear the clustering is trivial. Union-find holds a partition of the addresses. Every address begins in a group of its own. Each group is a tree, and the root of the tree is the group's name. Two operations: find, which walks to the root, and union, which joins two trees. Both have one optimisation each and both optimisations exist for the same reason, which is that these functions get called millions of times.
function UF(n) {
var parent = new Array(n);
var rank = new Array(n).fill(0);
for (var i = 0; i < n; i++) parent[i] = i; // everyone starts alone
function find(x) {
while (parent[x] !== x) {
parent[x] = parent[parent[x]]; // path halving
x = parent[x];
}
return x; // the root names the group
}
function union(a, b) {
a = find(a); b = find(b);
if (a === b) return false; // already the same holder
if (rank[a] < rank[b]) { var t = a; a = b; b = t; }
parent[b] = a; // shorter hangs under taller
if (rank[a] === rank[b]) rank[a]++;
return true; // a real merge happened
}
return { find: find, union: union };
}
LiveReading find, line by line4 min▶
The loop condition is the definition of a root: a node whose parent is itself. Walk until you reach one and that is the group's name. If the structure had no optimisation at all, find would still be correct, and it would be correct in a deep chain that takes as many steps as the chain is long.
The one line inside the loop is the optimisation, and it is worth being exact about what it does. parent[x] = parent[parent[x]] reassigns the current node to point at its grandparent, then the walk continues from there. Two things follow. The tree gets shallower every time anybody looks at it, so the cost is paid down by use rather than by maintenance. And the assignment cannot change the answer, because the grandparent is in the same tree as the parent by construction, so the root at the end of the walk is the same root it would have been.
That last point is the one to internalise. Every line in this structure either finds a root or shortens a path. Nothing in it decides whether two addresses belong together. That decision happens somewhere else entirely, in the caller, and it is one line long.
LiveReading union, and why rank exists4 min▶
Union starts by finding both roots, because you never merge nodes, you merge groups. If the two roots are the same the addresses are already in one cluster and there is nothing to do, and returning false there is what lets the caller count real merges rather than attempted ones. That count matters later.
Then the swap. If a is the shorter tree the two are exchanged, so that a is always the taller one and b always hangs underneath. Hanging the taller under the shorter would add a level to every node inside the taller tree, which is the specific thing that turns this structure into a linked list and turns an afternoon into a weekend.
The rank only increases when two trees of equal rank are merged, which is the only case where the result is genuinely deeper. Rank is not the height, it is an upper bound on the height, and it stays an upper bound even though path halving keeps making the real height smaller. Nobody recomputes it and nobody needs to.
function clusterByCoSpend(world, txs) {
var uf = UF(world.addresses.length), links = 0;
txs.forEach(function (inputs) {
for (var i = 1; i < inputs.length; i++)
if (uf.union(inputs[0], inputs[i])) links++; // one line of rule
});
var roots = {};
for (var a = 0; a < world.addresses.length; a++) roots[uf.find(a)] = true;
return { uf: uf, entities: Object.keys(roots).length, links: links };
}
LiveThe rule is one line, and it is the only line with an opinion3 min▶
Everything interesting in the function is the inner for. Every input after the first gets unioned with the first, which makes all inputs of a transaction one group without needing to compare them pairwise. There is no threshold, no weight, no similarity, no tuning parameter and nothing to configure. Somebody who dislikes the answer has nothing to turn.
That absence is worth naming out loud, because it is unusual and it is valuable. A method with a knob is a method that will be adjusted, quietly, by whoever most wants a different number. This one produces the same output from the same rows for everybody, forever, which is exactly the property you want in a figure that will be read by people who do not work for you.
The counter to links exists for one reason: union returns true only when a real merge happened, so links is the number of times the cluster count went down. Address count minus links is the cluster count, which gives you a free consistency check on any run.
Self-studyWhat this is not, and where that craft lives4 min▶
It is tempting to reach for the record linkage toolbox here, and worth being clear about why it does not fit rather than just declining it. Probabilistic linkage compares records on attributes, assigns agreement and disagreement weights, and produces a score you threshold, with blocking to keep the comparison space tractable. It is a mature craft with a real literature, it handles exactly the situation where two records describe the same party and neither is definitive, and it lives in learn-entity-resolution-with-phoebe.
The reason it has nothing to do tonight is that there are no attributes. Not weak attributes, not noisy attributes: none. An address carries no name, no locality, no contact detail, no demographic, nothing that could agree or disagree with anything on another address. A scoring model needs two records with fields to compare, and here the entire evidence base is a structural fact about transactions rather than a property of the records being linked.
One consequence is worth keeping. Because the evidence is deterministic there is no threshold, so there is no precision-recall trade-off to tune and no operating point to argue about. You get one answer. That makes the method much less flexible and much more defensible, and session 4 makes that trade explicit by measuring exactly what the one answer is worth.
Bench A, reproduced, and why one column has to be zero
12 min liveNow run it on the full world. Bench A is 300 ordinary people holding one to four addresses each plus 4 operators running 60 addresses each on purpose, so the truth is 304 entities, and 4,000 transactions are produced from them. The seed convention is part of the canon and belongs in the code rather than in somebody's memory: world seed s, transaction seed s + 1.
// The seed convention IS part of the canon: world seed s, transaction seed s + 1.
var s = 11;
var world = W3.makeWorld({
people: 300, sybils: 4, sybilAddrs: 60, seed: s
});
var txs = W3.makeTransactions(world, {
transactions: 4000, coSpendRate: 0.25, sybilDiscipline: 0.97, seed: s + 1
});
var cl = W3.clusterByCoSpend(world, txs);
var score = W3.scoreClustering(world, cl);
// score -> { addresses: 982, trueEntities: 304, clustered: 696,
// mixedClusters: 0, stillSplit: 392 }
// cl.links -> 286 and 982 - 286 === 696
...
LiveWatch the descent, and watch the column that never moves4 min▶
Drag the transaction slider from 0 to the end. At 0 the clustering has seen no evidence at all and returns one cluster per address, which is the naive count and also the correct output for a method with nothing to go on. As transactions arrive the count falls, smoothly, and it never once rises.
Stop anywhere on the way and check the identity: addresses minus merges equals clusters. It holds at every position, on every seed, because the only thing that changes the count is a successful union and each one removes exactly one cluster. If you build this yourself, that identity is the cheapest possible test and it will catch almost any implementation error you can make in the structure.
Now the column that does not move. Wrongly merged stays at 0 from the first transaction to the last, at every slider position and on every seed. That is not a property of this generator being gentle. Part 2's second half derives why it could not be otherwise.
LivePositive only, and what that buys4 min▶
Two addresses spent together is strong evidence of one holder, and it is strong for a structural reason rather than a statistical one. Two addresses never spent together is no evidence of anything. It is exactly as consistent with two separate parties as it is with one party who happened never to spend from both at once, and nothing else in the rows distinguishes those cases.
An engineer's instinct at this point is to treat the absence as weak negative evidence and build a model around it. Resist that, and notice what would have to be true for it to work: you would need a rate at which one party fails to co-spend, and that rate is a property of individual behaviour that the data does not contain and cannot be estimated from within. Anything you fit would be fitting your own assumption.
What the asymmetry buys is a bound instead of an estimate. Every error inflates, so the output sits above the truth, always, and you can say so without qualification. That is a smaller claim than an estimate and a much more durable one, and the wrongly merged column is the evidence that you are entitled to make it.
LiveThe implementation errors this property will catch3 min▶
Because the zero is structural rather than empirical, it doubles as a test. If your own implementation ever reports a wrongly merged cluster against a world where the truth is known, you have a bug, and it is usually one of three.
The first is an index error: unioning positions in the transaction array rather than address indices, which merges unrelated addresses that happened to appear in the same slot. The second is unioning inputs with outputs, which is a different and much weaker claim and will absolutely fuse separate parties, because paying somebody is not controlling their address. The third is running the union across a batch boundary rather than within a transaction, which quietly unions every address in a block.
All three produce clusters that look bigger and better. All three are caught in one assertion, and it is worth writing that assertion before writing anything else.
Self-studyWhere serious people disagree5 min▶
One camp says run the clustering and publish the bound. Their argument is practical: the naive address count is wrong by a factor of about three, somebody is going to report a number regardless, and a parameterless method that removes half the error and comes with a known direction is strictly better than the alternative, which is the raw count with a hopeful caveat. Refusing to compute it does not protect anybody, it just means the worse number is the one that gets used.
The other camp says the output is a linkage record about real people that did not exist until you built it. The rows were pseudonymous; your cluster table is a map of which pseudonyms belong together, derived without consent, stored in your warehouse, backed up, discoverable, and available to anyone who later gets access to it or compels it. On this view the accuracy gain is real and small, the liability is real and permanent, and the responsible move is to report the address count, label it plainly as an address count, and not create the asset at all.
Both camps include people who have built this and shipped it. They are not disagreeing about the algorithm, which nobody disputes, and they are not disagreeing about the measurement. They disagree about whether an inference you can make is an inference you should hold. Notice that the second position gets stronger the better the method works, which is an uncomfortable shape for an argument to have, and notice that the first position depends on your organisation actually reporting the bound rather than the point. Whether that second condition holds where you work is something you already know.
Write it, break it, and prove the zero
15 min hands onSix steps, most of them at a keyboard with the live box open. The aim is not to have used a union-find, it is to have broken one deliberately and watched the wrongly merged column react, because that is the only way the zero stops being something you were told.
Say the rule in one sentence, then say the loop
The rule first, with no hedging. Then describe the inner loop that implements it, out loud, in one more sentence. If the second sentence is longer than the first, you have added something the algorithm does not do.
Trace the six-address example by hand
On paper, run the five transactions and write the parent array after each one. Check your final partition against the diagram. Then check the identity: six addresses, three real merges, three clusters.
Reproduce Bench A on your own machine
Run the code box with the seed convention, world seed s and transaction seed s plus one. You should get 982, 304, 696 and 0 for s equal to 11. If you get a different number, the seed convention is the first place to look, because it is the thing everybody reconstructs wrongly.
Slide the transactions down and back
Move the slider from 4000 to 0 and watch clusters climb back to the address count. Write down two intermediate positions with addresses, merges and clusters, and check the identity at both. Note that wrongly merged did not move.
Break it on purpose
In your own copy, change the union to join the first input with the transaction's output instead of with its other inputs. Run the score. The wrongly merged column will stop being zero immediately, and the clustered count will look better. Sit with that for a moment.
Write the assertion you will ship
One line, in the language you work in, that fails if wrongly merged is ever above zero on a world where the truth is known. That assertion is worth more than the rest of your test suite for this component. Bring it to session 4.
The habit to keep. When a method produces a suspiciously clean result, find the structural reason or stop believing it. A zero that holds because of what a transaction requires is a fact you can build on. A zero that holds because five seeds happened to be quiet is a coincidence waiting to be reported as a property, and the two look identical in a results table.
Three questions
Inside find, the line parent[x] = parent[parent[x]] runs on every step of the walk. What does it change?
Path halving is purely a performance optimisation. Reassigning a node to its grandparent keeps it in the same tree, so the root at the end of the walk is unchanged and the cluster count is untouched. Only a successful union changes the partition.
A run on month A reports 982 addresses, 286 successful merges and 700 clusters. What do you know?
Union returns true only when two distinct groups are joined, and joining two groups reduces the count by one. The identity addresses minus merges equals clusters holds on every run of any size, which makes it the cheapest possible test on an implementation.
Why is the wrongly merged column 0 across every seed, rather than merely small?
The zero is structural, not empirical and not a configuration artefact. The case that would produce it cannot be constructed, so every error is a link the method failed to make, every one of those inflates the count, and the output is therefore a ceiling. Operator discipline changes how many links are missed, never whether a wrong one is made.
Homework
Twenty minutes, on your own implementation and on the assertion you wrote in step 6.
Run all five seeds and tabulate
Addresses, merges, clusters, still split and wrongly merged for s equal to 11, 101, 2024, 7 and 55555. Check the identity on every row and check that the last column is zero on every row.
Bring one sentence about the bound
Write how you would report the clustered figure to somebody who will repeat it without you in the room. Session 4 measures what the ceiling is worth, where it is tight and where it is nearly useless.