Four lists find a collision sooner

Twenty-three people probably include two who share a birthday, because 23 people make 253 pairs and each pair matches with chance $1/365$. The same arithmetic governs any search for two equal things among random ones. If strings of $n$ random bits are drawn into two lists, each list needs about $2^{n/2}$ entries before some string is likely to appear in both: the lists then make $2^n$ cross pairs, each equal with chance $2^{-n}$. That square root — $2^{n/2}$ work to find a match among $2^n$ possibilities — is the birthday bound, and it is the reason a hash function with $n$-bit outputs offers only $n/2$ bits of protection against anyone looking for two inputs with the same hash.

In 2002 David Wagner asked what happens with more lists. Take four lists of random $n$-bit strings and ask for one string from each whose bitwise exclusive-or is zero: $x_1 \oplus x_2 \oplus x_3 \oplus x_4 = 0$. With two lists that equation is just $x_1 = x_2$, the ordinary birthday problem. With four, the number of candidate quadruples is the fourth power of the list size rather than the square, so smaller lists contain solutions. The question is whether a solution can be found without looking at all of them — and Wagner’s answer is yes, with lists of size about $2^{n/3}$.

Merging in pairs #

The algorithm is two rounds of the birthday problem, each on a third of the bits. Take lists $L_1$ and $L_2$, each of $2^{n/3}$ strings. Form every pair $(x_1, x_2)$ whose exclusive-or has its lowest $n/3$ bits equal to zero. There are $2^{2n/3}$ pairs in all, each with chance $2^{-n/3}$ of qualifying, so about $2^{n/3}$ qualify — the merged list is the same size as the originals. Finding them is cheap: sort $L_2$ by its low bits, and for each $x_1$ look up the entries that agree with it there. Do the same with $L_3$ and $L_4$.

Now the two merged lists hold strings $x_1 \oplus x_2$ and $x_3 \oplus x_4$, each ending in $n/3$ zeros, so each is effectively a random string of $2n/3$ bits. A match between them on those remaining bits is an ordinary birthday problem on $2n/3$ bits, which needs lists of $2^{n/3}$ — exactly what the merges produced. Any match gives $x_1 \oplus x_2 = x_3 \oplus x_4$, and so $x_1 \oplus x_2 \oplus x_3 \oplus x_4 = 0$.

The hero figure follows one run at 24 bits. Four lists of 256 merge on the low eight bits into lists of 272 and 239 pairs, close to the predicted 256, and the final merge on all 24 bits finds one quadruple. The whole run handled about 1,300 strings and pairs. Two lists would have needed 4,096 strings each — over 8,000 — to expect a single match.

One solution, bit by bit #

It is worth looking at a solution itself, because it makes the mechanism concrete.

Exclusive-or compares two strings bit by bit and writes a $1$ wherever they differ. The first two strings were chosen by the first merge because they agree in their last eight bits; nothing else about them is related, and their first sixteen bits look as random as any. The same is true of the last two. What the final merge found is that the two partial results — each a random-looking sixteen bits followed by eight zeros — happen to agree in their first sixteen bits too, which is a one-in-sixty-five-thousand event for any given pair and about a one-in-one event across the 272 × 239 pairs available.

So the solution is assembled in two stages of luck, each tuned to be likely. The first stage asks four strings to pair up on eight bits, which a list of 256 does about 256 times. The second asks two of the results to agree on sixteen more bits, which lists of about 256 do about once. Neither stage asks for anything improbable relative to the number of attempts it gets, and that is the whole design principle: split an improbable event into a sequence of probable ones, and pay for each with the square root of its improbability.

Success, measured #

The claim is a statement about probabilities, so the figure below measures it.

The two curves are the same shape displaced along the axis. Two lists climb from three per cent at 512 strings to near-certainty at 8,192, crossing the middle a little below 4,096 — the birthday bound, $2^{12}$. Four lists climb from nothing at 64 strings through sixty per cent at 256 to certainty at 512 — a crossing near $2^8 = 256$, the cube-root scale. At 512 strings per list, four lists succeed every time and two lists almost never.

The success curve for four lists is steeper than the two-list curve, and that has a reason. When the lists are too small, the first merges keep fewer pairs than they started with, the final merge has less to work with, and the deficit compounds; when the lists are large enough, the merged lists are larger than the originals and solutions multiply. The algorithm works at the scale where each merge preserves the list size, and it fails sharply below it.

The exponent #

At larger sizes the two approaches separate by more than a constant.

On a logarithmic scale the work is a straight line in the number of bits, with slope one half for two lists and one third for four. At 30 bits, two lists need 65,536 strings; four lists need about ten thousand items handled. At 120 bits — a size used in real hash functions — the difference is between $2^{60}$ and $2^{40}$, a factor of a million.

And the pattern continues. With eight lists, a third round of merging splits the bits into quarters, and the work becomes $2^{n/4}$; with $2^t$ lists it is $2^{n/(t + 1)}$. Doubling the number of lists buys one more level of the tree and a smaller exponent, as the eight-list run above shows on a small scale. With as many lists as there are bits, the work becomes polynomial — Avrim Blum, Adam Kalai and Hal Wasserman had used essentially this idea two years earlier, in 2000, to learn parity functions from noisy examples faster than anyone had thought possible.

Eight lists, three merges #

The tree extends by doubling the number of lists, and the figure below runs the next case.

With eight lists the bits are split into four quarters. The first merge pairs the lists on the lowest quarter, the second pairs the results on the second quarter, and the last on everything that remains. The figure’s averages show the design working: at every level the lists hold about 64 entries, because each merge is a birthday problem on six bits between lists of 64, which produces $64 \cdot 64 / 2^6 = 64$ matches. The size never grows and never shrinks, and at the bottom the last merge, on twelve bits between lists of 64, expects $64 \cdot 64 / 2^{12} = 1$ solution. In 125 of 200 runs one was found — close to the $1 - 1/e \approx 63\%$ that a single expected success predicts.

Lists of 64 are a quarter-power of the $2^{24}$ possible strings, where two lists needed a square root and four a cube root. The cost of the extra power is the number of lists: eight lists of 64 is 512 strings, against 1,024 for four lists of 256 and 8,192 for two lists of 4,096. The total keeps falling as the lists multiply, until the tree is so deep that each merge works on a single bit and the method becomes something else — the Blum–Kalai–Wasserman algorithm for noisy parities.

The surprising thing: the solutions are not found by luck #

The count below is what makes the algorithm surprising rather than merely clever.

The four lists of 256 contain about four billion quadruples, of which about 256 cancel. A solution is therefore one in sixteen million of the candidates. A search that tried quadruples at random would need millions of tries to find one; a search that tried them all would take four billion steps. The merges look at fifteen hundred things and find a solution, because they never form a quadruple that has not already passed a test: every pair in a merged list agrees on its low bits, so every quadruple the final merge forms is already a third of the way to cancelling.

That is the birthday phenomenon used against itself. The first merge is a birthday problem that is meant to succeed many times over — it is tuned so that about $2^{n/3}$ of its $2^{2n/3}$ pairs collide on the low bits — and each of those collisions is a step towards a solution of the harder problem. The square-root saving that makes collisions cheap is applied twice, and the two savings compound into a cube root.

The algorithm needs one property of the operation that combines the strings: exclusive-or is associative and commutative, and every string is its own inverse, so $x_1 \oplus x_2 \oplus x_3 \oplus x_4 = 0$ can be split into $x_1 \oplus x_2 = x_3 \oplus x_4$, and a partial agreement on the low bits survives into the final sum. Exclusive-or is addition in the field with two elements, bit by bit, and the same algorithm works for addition modulo $2^n$ and for any other group operation that lets a sum be split into halves. For operations that do not — where a partial match tells nothing about the whole — there is no tree to build, and the birthday bound stands.

Counting pairs, not people #

The birthday bound itself is easiest to understand by the count that the original essay made central: not how many people, but how many pairs. Two lists of $L$ strings make $L^2$ cross pairs, each equal with chance $2^{-n}$, so the expected number of matches is $L^2 / 2^n$, and a match becomes likely when that reaches about one. Everything in Wagner’s algorithm is the same count applied to different objects. The first merge counts cross pairs between $L_1$ and $L_2$ that agree on $n/3$ bits: $L^2 / 2^{n/3}$, which equals $L$ when $L = 2^{n/3}$. The final merge counts cross pairs between two merged lists that agree on $2n/3$ bits: $L^2 / 2^{2n/3} = 1$ at the same $L$. Choosing $L$ so that both counts come out right is the entire analysis.

That way of counting also shows what happens when the strings are not uniform. If some strings are more likely than others — a biased hash, a population with uneven shares — then collisions come sooner, because the chance that two random draws agree is $\sum p_i^2$, which is smallest when the probabilities are equal. Any unevenness brings the match sooner for birthdays, and the same is true at every level of Wagner’s tree: a biased source makes each merge keep more pairs than predicted, and the algorithm succeeds with smaller lists. For an attacker, non-uniformity is a gift; for a designer, it is the first thing to remove. The uniform case drawn in every figure here is the hardest case for the search, which is why it is the one cryptography assumes.

The counting view also explains the steepness of the success curve. Below the right size the expected number of pairs kept at each level falls short of the list size, so the next level starts smaller still, and the shortfall compounds through the tree: a list ten per cent too small at the top ends with far more than ten per cent fewer solutions at the bottom: with four lists, about a third fewer, since the shortfall is squared at the first merge and squared again at the second. Above the right size the same compounding works in the algorithm’s favour. A deep tree is a sharp threshold, and the deeper the tree the sharper it becomes, which is why the eight-list run needs its lists close to exactly a quarter-power.

Why it matters #

Wagner’s paper was about cryptography, and the algorithm broke things. Several proposed constructions combined hash values by exclusive-or or by addition — hashing each block of a message separately and adding the results, for instance — on the assumption that finding a collision would cost the birthday bound. With four or more terms to choose, the cost falls to a cube root or less, and constructions that seemed to offer security at the birthday bound turned out to offer far less — a design with 120-bit outputs, meant to resist $2^{60}$ work, falls to about $2^{40}$. The same idea now underlies attacks on certain signature schemes and on pseudorandom generators built from sums of simpler pieces.

The algorithm has also been put to a constructive use. Equihash, designed by Alex Biryukov and Dmitry Khovratovich in 2016, is a puzzle for verifying computational work, and it asks for exactly this: a set of hash values whose exclusive-or is zero. Its point is that Wagner’s algorithm is the fastest known method and needs a lot of memory — the merged lists must be stored — so the puzzle cannot be solved much more cheaply on special hardware than on an ordinary computer.

Collisions, from factoring to here #

The birthday bound has appeared in this subject in several disguises. Pollard’s rho method finds a factor of a number by waiting for a collision modulo an unknown prime, at the birthday rate. The middle-square generator collapses at a fraction of the birthday rate. A random function’s cycles hold about the square root of its points. In each case the square root is a fact about how fast random choices repeat, and it was natural to treat it as a law.

Wagner’s algorithm shows the square root is a fact about one collision between two lists. Given more freedom — more lists, and an operation that lets partial agreements accumulate — the problem changes and the root deepens. The birthday bound is not wrong; it is the answer to a narrower question than it is often taken to be.

Random strings, and hash functions that are not #

Every run uses random strings. The analysis assumes the lists are independent and their entries uniformly random. Real hash values are deterministic, and if the function has structure — as the polynomials Pollard used sometimes do — the merges can keep more or fewer pairs than predicted. The figures show the random case, which is the case cryptography assumes and, for well-designed hash functions, the case that holds.

The exponents are measured on small sizes. From 18 to 30 bits the measured slopes are one half and one third, as the analysis predicts. At cryptographic sizes nothing can be simulated; the claim that the work is $2^{n/3}$ there is the analysis, which the small cases support and do not prove.

Memory is not drawn. The four-list algorithm must store the merged lists, $2^{n/3}$ entries each, and memory is often the binding constraint in practice. Trading time for memory in generalised birthday problems is a subject of its own, and the figures count only operations.

Still open: how low the exponent can go #

For $2^t$ lists the exponent $n/(t + 1)$ is what Wagner’s tree achieves, and it is the best known for most list counts. For three lists, which do not fit the tree, the best known algorithms are only slightly better than the birthday bound, and whether a three-list version can reach a cube root is a well-known open question. More generally, lower bounds — proofs that no algorithm can do better than a given exponent — are known only in restricted models of computation, and whether Wagner’s exponents are optimal for real algorithms is not known. The problem sits where combinatorics, probability and the theory of algorithms meet, and its simplest-looking case, three lists, is the one least understood.