Hash Functions (continued)

The Verdict

MixingFunction mf = new Jenkins32();
double[,] am = mf.AvalancheMatrix(1000000, 1);

Now we're ready to find out how well Bob Jenkins did with this mixing function with regards to achieving avalanche. Figure 1 shows the two lines of code we need to create an instance of the Jenkins32 mixing function and call the AvalanceMatrix method.

Here are the results, shown as percentages from 0 to 100, rounded to 1%:

Each row represents an input bit and each column represents an output bit. So to determine the probability that bit 6 affects bit 1, look at the row numbered "6" (the 7th row) and the column numbered "1" and you'll see that the result is 51%.

The technical term for these results is sweet. We can be pretty confident that this mixing function will do a good job at collision-avoidance with 32-bit integers for the purposes of hash table lookup.

But if we examine the data very closely, we do find that this function doesn't behave quite the same as a function that satisfies the strict avalanche criterion (SAC) would. This does not suggest that this is a bad mixing function. It's very good. I'm just using it as an example to show how to analyze the avalanche behavior.

The numbers in red show the places where the probability differs by at least 4% from the expected value. For example, the 0th bit affects the 31st bit 54% of the time. To tell whether this is significant or whether it's just a random variation due to the fact that we didn't actually check every combination of input bits and instead just did a sample, we need to compare this to a mixing function that satisfies SAC exactly.

Such a function would have exactly a 50% probability in every position, but because we're sampling there would be variations. Since we did one million samples it would behave like flipping a coin one million times, and we would see a binomial distribution. This would look essentially the same as a normal distribution with a mean of 50 and a standard deviation of 0.05. But some positions would be worse than others. With 1024 elements (32 × 32), we can expect that the worst positive deviation is going to be about 3.5 standard deviations above the mean, or about 0.175. Because this is well under 0.5, we shouldn't see any non-50's in the table if we round to the nearest 1%.

public class Artificial32 : MixingFunction
{
    RandomNumberGenerator rng = 
        new RNGCryptoServiceProvider();
    byte[] b = new byte[4];

    public override int Size 
    { get { return 32; } }

    public override void Mix()
    {
        rng.GetBytes(b);
        state = BitConverter.ToUInt32(b, 0);
    }
}

Since we don't (yet) know of a mixing function that obeys SAC exactly, we can instead create one that actually does a 50% coin flip (simulated). This isn't a real mixing function because the outputs don't depend on the inputs, but it will fool the avalanche calculator into thinking it's real. Figure 2 shows this mixing function.

I won't show the results of this function here because it would be a complete waste of bandwidth, but you can run it yourself and see that it shows 50's in every position, and the raw data shows that the worst positions probably deviate from this by about 0.175 percentage points (it varies each time you run it, of course, so your results may differ).

How Bad Can It Get?

public class KnuthMultiplicative : MixingFunction
{
    public override int Size 
    { get { return 32; } }

    public override void Mix()
    {
        state *= 2654435761U;
    }
}

      0   1   2   3   4   5   6   7 

 0  100   0   0   0 100  50  75  63
 1    0 100   0   0   0 100  50  75
 2    0   0 100   0   0   0 100  50
 3    0   0   0 100   0   0   0 100
 4    0   0   0   0 100  50  25  13
 5    0   0   0   0   0 100  50  25
 6    0   0   0   0   0   0 100  50
 7    0   0   0   0   0   0   0 100

If you compare the Jenkins32 function to a more primitive multiplicative mixer that people have used in real hash functions, you'll see that we could do much, much worse. Figure 3 shows such a function and a sub-section of the results matrix. It clearly shows that this hash function is bad at propagating high-order bits into low-order bit positions. Whether that's acceptible or not depends on the application. And it's not really as bad as it seems, because the intended use of this function requires taking a prime modulus of the final value, which does scramble the lower bits somewhat.

Can We Do Better?

Is it possible to do better than Jenkins32? The answer is yes. To illustrate this, let's just run Jenkins32 twice. The first step already does a great job at mixing, so if we do it twice it should be even better, right? We can easily do this by calling the AvalancheMatrix method with a repetitions parameter of 2. And we find that, in fact, the results are near-perfect. They are practically indistinguishable from a SAC-perfect mixing function.

Note that this isn't true of every mixing function. With KnuthMultiplicative, those 0's and 100's never go away because of where they're positioned.

You might wonder if a mixing function that exactly satisfies SAC even exists. Once again the answer is yes. Figure 4 shows a 4-bit mixing function with this property. The truth table of this function is shown so you can confirm that SAC is actually satisfied.

public void Mix()
{
    uint[] tab = 
        {8, 7, 0, 10, 1, 3, 5, 12, 
         11, 13, 15, 14, 2, 6, 9, 4};
    
    state = tab[state];
}

Input         Output
0   0 0 0 0   8   1 0 0 0
1   0 0 0 1   7   0 1 1 1
2   0 0 1 0   0   0 0 0 0
3   0 0 1 1   10  1 0 1 0
4   0 1 0 0   1   0 0 0 1
5   0 1 0 1   3   0 0 1 1
6   0 1 1 0   5   0 1 0 1
7   0 1 1 1   12  1 1 0 0
8   1 0 0 0   11  1 0 1 0
9   1 0 0 1   13  1 1 0 1
10  1 0 1 0   15  1 1 1 1
11  1 0 1 1   14  1 1 1 0
12  1 1 0 0   2   0 0 1 0
13  1 1 0 1   6   0 1 1 0
14  1 1 1 0   9   1 0 0 1
15  1 1 1 1   4   0 1 0 0

We know that we can get arbitrarily close just by concatenating a good-enough function two or more times. The challenge is to get closer without adding additional computation time.

Mixing Function Search

Warning! I can think of no practical reason why you would need "perfect" avalanche instead of the excellent avalanche achieved by the Jenkins32 integer hash. The rest of this page is motivated purely by intellectual curiosity.

To create the mixing function of Figure 4 I did a random search of different permutation tables until I came across one that satisfied the SAC. That works for a 4-bit function, but a lookup table isn't going to be feasible for a 32-bit or larger function. So we can choose to limit our search to functions that are a combination of the reversible operations from the previous page. That's where those "magic numbers" come in. We choose them at random! Some values will be good, some will be bad, but we have a way to measure to see which are the best.

But a completely random search will be too slow. Even if we restrict our search to functions of the same form as Jenkins32, that's still 31⁸ combinations, or almost a million million. And most of those will be complete rubbish.

Error   Vector

0.0257  12 22 4 9 10 2 7 12
0.0185  12 22 4 9 10 2 7 16
0.0116  12 18 4 9 10 2 7 16
0.0112  12 18 4 9 10 2 7 15
0.0105  12 18 4 9 10 2 8 15
0.0088  12 18 5 9 10 2 8 15
0.0085  12 18 5 9 10 3 8 15
0.0083  16 18 5 9 10 3 8 15
0.0080  16 17 5 9 10 3 8 15
0.0052  16 17 5 9 10 3 6 15
0.0052  16 13 5 9 10 3 6 15
0.0048  16 13 5 9 10 3 6 17
0.0047  16 13 5 7 10 3 6 17
0.0044  16 13 5 7 10 2 6 17
0.0039  16 13 5 7 10 2 6 16
0.0039  16 13 4 7 10 2 6 16
0.0038  16 13 4 7 10 2 8 16
0.0024  16 13 4 7 10 5 8 16

Instead what we'll do is start with a known-good function and try modifying each of the constants one at a time to see if we can improve on the previous avalanche matrix. In order to compare two functions to determine which is better, we'll need a single number that summarizes the avalance matrix results. I chose to use the "sum of squared errors", which just means I take the difference between each matrix entry and the expected value of 0.5, square it, and then sum all 1024 values together.

I used 100 thousand trials for the matrix calculation. If you use too few trials there is too much "noise" in the results and you can't reliably compare values. The minimum result we can expect to get this way is 0.00256, which is what you would get if the each matrix value were distributed binomially, which is what you'd expect from a function that satisfies SAC. Jenkins32 gets about 0.0257, about 10 times the expected squared error.

Figure 5 shows the trajectory of the best "search path" that I've been able to find using Jenkins32 as the starting point. It shows that we're able to reduce the squared error essentially equal to the theoretical minimum, minus some sampling noise.

First page, Next page