Unit tests Toeplitz hashing#
TestToeplitzMatrixAlmostSquare#
This is the first relevant unit test to be documented. Previous tests check for correct initialization and use of the correct types for each of the parameters.
The first step is to compute the output length. Given the lower bound on the min-entropy, we compute the largest output length to achieve a distance from uniform lower than the error bound. This is guaranteed by the leftover hash lemma.
\[\text{output_length} = \Big\lfloor \alpha n - 2\log_2\frac{1}{\epsilon}\Big\rfloor =
\Big\lfloor 0.99\times 5 - 2\log_2\frac{1}{0.99} \Big\rfloor = \Big\lfloor 4.921 \Big\rfloor = 4\]
>>> import math
>>> math.floor(0.99*5 - 2*math.log2(1/0.99))
4
Our code does not compute and store the Toeplitz matrix to use the extract() method because we use the
Fast Fourier Transform and work directly with the input and seed
vectors. However, the method to_matrix() allows us to obtain this Toeplitz matrix. The default arrangement of the
seed to form the Toeplitz matrix is the same as described in the theory section, i.e.,
\[\text{seed} =
\begin{bmatrix}
s_0 & \dots & s_{m+n-1}
\end{bmatrix} \equiv
\begin{bmatrix}
y_0 & y_1 & \dots & y_{m-1} & y_{-1} & y_{-2} & \dots & y_{n-1}
\end{bmatrix}\]
In this particular test we have
\begin{align}
\text{seed} &=
\begin{bmatrix}
1_{\color{red}0} & 0_{\color{red}1} & 0_{\color{red}2} & 0_{\color{red}3} & 0_{\color{red}4} & 0_{\color{red}5} &
0_{\color{red}6} & 0_{\color{red}7}
\end{bmatrix}\\
T &= \begin{bmatrix}
1_{\color{red}0} & 0_{\color{red}7} & 0_{\color{red}6} & 0_{\color{red}5} & 0_{\color{red}4} \\
0_{\color{red}1} & 1 & 0 & 0 & 0 \\
0_{\color{red}2} & 0 & 1 & 0 & 0 \\
0_{\color{red}3} & 0 & 0 & 1 & 0
\end{bmatrix}
\end{align}
The seed was chosen to emphasize the differences between the available options for seed_mode and seed_order.
For seed_mode="col-first" we obtain
\begin{align}
\text{seed} &=
\begin{bmatrix}
1_{\color{red}0} & 0_{\color{red}1} & 0_{\color{red}2} & 0_{\color{red}3} & 0_{\color{red}4} & 0_{\color{red}5} &
0_{\color{red}6} & 0_{\color{red}7}
\end{bmatrix}\\
T &= \begin{bmatrix}
0_{\color{red}3} & 0_{\color{red}4} & 0_{\color{red}5} & 0_{\color{red}6} & 0_{\color{red}7} \\
0_{\color{red}2} & 0 & 0 & 0 & 0 \\
0_{\color{red}1} & 0 & 0 & 0 & 0 \\
1_{\color{red}0} & 0 & 0 & 0 & 0
\end{bmatrix}
\end{align}
And for seed_mode="row-first"
\begin{align}
\text{seed} &=
\begin{bmatrix}
1_{\color{red}0} & 0_{\color{red}1} & 0_{\color{red}2} & 0_{\color{red}3} & 0_{\color{red}4} & 0_{\color{red}5} &
0_{\color{red}6} & 0_{\color{red}7}
\end{bmatrix}\\
T &= \begin{bmatrix}
0_{\color{red}4} & 0_{\color{red}3} & 0_{\color{red}2} & 0_{\color{red}1} & 1_{\color{red}0} \\
0_{\color{red}5} & 0 & 0 & 0 & 0 \\
0_{\color{red}6} & 0 & 0 & 0 & 0 \\
0_{\color{red}7} & 0 & 0 & 0 & 0
\end{bmatrix}
\end{align}
With seed_mode="custom", the permutation array seed_order determines how the bits from the seed are used to
construct the matrix. Three permutations are tested, here we show the first one which swaps the first and second
bit.
\begin{align}
\text{seed} &=
\begin{bmatrix}
1_{\color{red}0} & 0_{\color{red}1} & 0_{\color{red}2} & 0_{\color{red}3} & 0_{\color{red}4} & 0_{\color{red}5} &
0_{\color{red}6} & 0_{\color{red}7}
\end{bmatrix}\\
\text{seed_order} &=
\begin{bmatrix}
1 & 0 & 2 & 3 & 4 & 5 & 6 & 7
\end{bmatrix}\\
T &= \begin{bmatrix}
0_{\color{red}3} & 0_{\color{red}4} & 0_{\color{red}5} & 0_{\color{red}6} & 0_{\color{red}7} \\
0_{\color{red}2} & 0 & 0 & 0 & 0 \\
1_{\color{red}0} & 0 & 0 & 0 & 0 \\
0_{\color{red}1} & 1 & 0 & 0 & 0
\end{bmatrix}
\end{align}
Finally, the output of the extract() method matches the matrix-vector multiplication between the Toeplitz matrix
and the input from the weak source. In this particular test we have
\[\begin{split}\text{output} = T \times \text{input} =
\begin{bmatrix}
0 & 1 & 1 & 1 & 1 \\
1 & 0 & 1 & 1 & 1 \\
1 & 1 & 0 & 1 & 1 \\
0 & 1 & 1 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
1 \\ 0 \\ 0 \\ 1 \\ 0
\end{bmatrix} =
\begin{bmatrix}
1 \\ 2 \\ 2 \\ 0
\end{bmatrix} \mod 2=
\begin{bmatrix}
1 \\ 0 \\ 0 \\ 0
\end{bmatrix}\end{split}\]
TestToeplitzMatrixWide#
\[\text{output_length} = \Big\lfloor 0.7\times 8 - 2\log_2\frac{1}{0.5} \Big\rfloor = \Big\lfloor 3.6 \Big\rfloor = 3\]
>>> import math
>>> math.floor(0.7*8 - 2*math.log2(1/0.5))
3
\begin{align}
\text{seed} &=
\begin{bmatrix}
0_{\color{red}0} & 1_{\color{red}1} & 1_{\color{red}2} & 0_{\color{red}3} & 0_{\color{red}4} & 0_{\color{red}5} &
1_{\color{red}6} & 1_{\color{red}7} & 1_{\color{red}8} & 1_{\color{red}9}
\end{bmatrix}\\
T &= \begin{bmatrix}
0_{\color{red}0} & 1_{\color{red}9} & 1_{\color{red}8} & 1_{\color{red}7} & 1_{\color{red}6} & 0_{\color{red}5} &
0_{\color{red}4} & 0_{\color{red}3} \\
1_{\color{red}1} & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\
1_{\color{red}2} & 1 & 0 & 1 & 1 & 1 & 1 & 0
\end{bmatrix}
\end{align}
\[\begin{split}\text{output} = T \times \text{input} =
\begin{bmatrix}
0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\
1 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\
1 & 1 & 0 & 1 & 1 & 1 & 1 & 0
\end{bmatrix}
\begin{bmatrix}
1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 1
\end{bmatrix} =
\begin{bmatrix}
1 \\ 2 \\ 3
\end{bmatrix} \mod 2=
\begin{bmatrix}
1 \\ 0 \\ 1
\end{bmatrix}\end{split}\]
TestToeplitzMatrixOneDimensionalWide#
\[\text{output_length} = \Big\lfloor 0.5\times 10 - 2\log_2\frac{1}{0.25} \Big\rfloor = 1\]
>>> import math
>>> math.floor(0.5*10 - 2*math.log2(1/0.25))
1
This is an extreme scenario where the Toeplitz matrix only has one row, but the “matrix” is still computed in the same way, so it looks reversed except for the first bit.
\begin{align}
\text{seed} &=
\begin{bmatrix}
0_{\color{red}0} & 1_{\color{red}1} & 1_{\color{red}2} & 0_{\color{red}3} & 0_{\color{red}4} & 0_{\color{red}5} &
1_{\color{red}6} & 1_{\color{red}7} & 1_{\color{red}8} & 1_{\color{red}9}
\end{bmatrix}\\
T &= \begin{bmatrix}
0_{\color{red}0} & 1_{\color{red}9} & 1_{\color{red}8} & 1_{\color{red}7} & 1_{\color{red}6} & 0_{\color{red}5} &
0_{\color{red}4} & 0_{\color{red}3} & 1_{\color{red}2} & 1_{\color{red}1}
\end{bmatrix}
\end{align}
\[\begin{split}\text{output} = T \times \text{input} =
\begin{bmatrix}
0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1
\end{bmatrix}
\begin{bmatrix}
0 \\ 1 \\ 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 1 \\ 1 \\ 0
\end{bmatrix} =
4 \mod 2 = 0\end{split}\]
Unit tests Modified Toeplitz hashing#
TestModifiedToeplitzMatrixAlmostSquare#
\[\text{output_length} = \Big\lfloor 0.75\times 9 - 2\log_2\frac{1}{0.5} \Big\rfloor = \Big\lfloor 4.75 \Big\rfloor = 4\]
>>> import math
>>> math.floor(0.75*9 - 2*math.log2(1/0.5))
4
Remember that the modified Toeplitz hashing appends an identity matrix to reduce the
required seed. Because of this, instead of a seed of length \(\text{input_length}+\text{output_length}-1\), we only
need \(\text{input_length}-1\) bits. The order of these bits to form the matrix is exactly the same as in the normal
Toeplitz hashing, and seed_mode and seed_order kwargs can also be used to modify it.
\begin{align}
\text{seed} &=
\begin{bmatrix}
0_{\color{red}0} & 1_{\color{red}1} & 1_{\color{red}2} & 0_{\color{red}3} & 1_{\color{red}4} & 1_{\color{red}5} &
1_{\color{red}6} & 1_{\color{red}7}
\end{bmatrix}\\
T &= \begin{bmatrix}
0_{\color{red}0} & 1_{\color{red}7} & 1_{\color{red}6} & 1_{\color{red}5} & 1_{\color{red}4} & 1 \\
1_{\color{red}1} & 0 & 1 & 1 & 1 & & 1 \\
1_{\color{red}2} & 1 & 0 & 1 & 1 & & & 1 \\
0_{\color{red}3} & 1 & 1 & 0 & 1 & & & & 1
\end{bmatrix}
\end{align}
\[\begin{split}\text{output} = T \times \text{input }= \begin{bmatrix}
0 & 1 & 1 & 1 & 1 & 1 \\
1 & 0 & 1 & 1 & 1 & & 1 \\
1 & 1 & 0 & 1 & 1 & & & 1 \\
0 & 1 & 1 & 0 & 1 & & & & 1
\end{bmatrix}
\begin{bmatrix}
1 \\ 0 \\ 0 \\ 1 \\ 0 \\ 1 \\ 1 \\ 1 \\ 0
\end{bmatrix} =
\begin{bmatrix}
2 \\ 3 \\ 3 \\ 0
\end{bmatrix} \mod 2 =
\begin{bmatrix}
0 \\ 1 \\ 1 \\ 0
\end{bmatrix}\end{split}\]
TestModifiedToeplitzMatrixNarrow#
\[\text{output_length} = \Big\lfloor 0.99\times 11 - 2\log_2\frac{1}{0.5} \Big\rfloor = \Big\lfloor 8.89 \Big\rfloor = 8\]
>>> import math
>>> math.floor(0.99*11 - 2*math.log2(1/0.5))
8
\begin{align}
\text{seed} &=
\begin{bmatrix}
0_{\color{red}0} & 1_{\color{red}1} & 1_{\color{red}2} & 0_{\color{red}3} & 0_{\color{red}4} & 0_{\color{red}5} &
1_{\color{red}6} & 1_{\color{red}7} & 1_{\color{red}8} & 1_{\color{red}9}
\end{bmatrix}\\
T &= \begin{bmatrix}
0_{\color{red}0} & 1_{\color{red}8} & 1_{\color{red}9} & 1\\
1_{\color{red}1} & 0 & 1 & & 1 \\
1_{\color{red}2} & 1 & 0 & & & 1 \\
0_{\color{red}3} & 1 & 1 & & & & 1 \\
0_{\color{red}4} & 0 & 1 & & & & & 1 \\
0_{\color{red}5} & 0 & 0 & & & & & & 1\\
1_{\color{red}6} & 0 & 0 & & & & & & & 1\\
1_{\color{red}7} & 1 & 0 & & & & & & & & 1\\
\end{bmatrix}
\end{align}
\[\begin{split}T \times \text{input }&= \begin{bmatrix}
0 & 1 & 1 & 1\\
1 & 0 & 1 & & 1 \\
1 & 1 & 0 & & & 1 \\
0 & 1 & 1 & & & & 1 \\
0 & 0 & 1 & & & & & 1 \\
0 & 0 & 0 & & & & & & 1\\
1 & 0 & 0 & & & & & & & 1\\
1 & 1 & 0 & & & & & & & & 1\\
\end{bmatrix}
\begin{bmatrix}
1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 1 \\ 1 \\ 0 \\ 1
\end{bmatrix} =
\begin{bmatrix}
1 \\ 1 \\ 3 \\ 1 \\ 1 \\ 1 \\ 1 \\ 3
\end{bmatrix} \mod 2 =
\begin{bmatrix}
1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1
\end{bmatrix}\end{split}\]
TestModifiedToeplitzMatrixWide#
\[\text{output_length} = \Big\lfloor 0.5\times 11 - 2\log_2\frac{1}{0.5} \Big\rfloor = \Big\lfloor 3.5 \Big\rfloor = 3\]
>>> import math
>>> math.floor(0.5*11 - 2*math.log2(1/0.5))
3
\begin{align}
\text{seed} &=
\begin{bmatrix}
0_{\color{red}0} & 1_{\color{red}1} & 1_{\color{red}2} & 0_{\color{red}3} & 0_{\color{red}4} & 0_{\color{red}5} &
1_{\color{red}6} & 1_{\color{red}7} & 1_{\color{red}8} & 1_{\color{red}9}
\end{bmatrix}\\
T &= \begin{bmatrix}
0_{\color{red}0} & 1_{\color{red}9} & 1_{\color{red}8} & 1_{\color{red}7} & 1_{\color{red}6} & 0_{\color{red}5} &
0_{\color{red}4} & 0_{\color{red}3} & 1 \\
1_{\color{red}1} & 0 & 1 & 1 & 1 & 1 & 0 & 0 & & 1 \\
1_{\color{red}2} & 1 & 0 & 1 & 1 & 1 & 1 & 0 & & & 1 \\
\end{bmatrix}
\end{align}
\[\begin{split}T \times \text{input} = \begin{bmatrix}
0 & 1 & 1 & 1 & 1 & 0 &
0 & 0 & 1 \\
1 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & & 1 \\
1 & 1 & 0 & 1 & 1 & 1 & 1 & 0 & & & 1 \\
\end{bmatrix}
\begin{bmatrix}
1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 1 \\ 1 \\ 1 \\ 1
\end{bmatrix} =
\begin{bmatrix}
2 \\ 3 \\ 4
\end{bmatrix} \mod 2 =
\begin{bmatrix}
0 \\ 1 \\ 0
\end{bmatrix}\end{split}\]
TestModifiedToeplitzMatrixOneDimensionalNarrow#
\[\text{output_length} = \Big\lfloor 0.99\times 11 - 2\log_2\frac{1}{0.99} \Big\rfloor = \Big\lfloor 10.861 \Big\rfloor = 10\]
>>> import math
>>> math.floor(0.99*11 - 2*math.log2(1/0.99))
10
\begin{align}
\text{seed} &=
\begin{bmatrix}
0_{\color{red}0} & 1_{\color{red}1} & 1_{\color{red}2} & 0_{\color{red}3} & 0_{\color{red}4} & 0_{\color{red}5} &
1_{\color{red}6} & 1_{\color{red}7} & 1_{\color{red}8} & 1_{\color{red}9}
\end{bmatrix}\\
T &= \begin{bmatrix}
0_{\color{red}0} & 1 \\
1_{\color{red}1} & & 1 \\
1_{\color{red}2} & & & 1\\
0_{\color{red}3} & & & & 1\\
0_{\color{red}4} & & & & & 1\\
0_{\color{red}5} & & & & & & 1\\
1_{\color{red}6} & & & & & & & 1\\
1_{\color{red}7} & & & & & & & & 1\\
1_{\color{red}8} & & & & & & & & & 1\\
1_{\color{red}9} & & & & & & & & & & 1
\end{bmatrix}
\end{align}
\[\begin{split}T \times \text{input} &= \begin{bmatrix}
0 & 1 \\
1 & & 1 \\
1 & & & 1\\
0 & & & & 1\\
0 & & & & & 1\\
0 & & & & & & 1\\
1 & & & & & & & 1\\
1 & & & & & & & & 1\\
1 & & & & & & & & & 1\\
1 & & & & & & & & & & 1
\end{bmatrix}
\begin{bmatrix}
1 \\ 1 \\ 0 \\ 1 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0
\end{bmatrix} =
\begin{bmatrix}
1 \\ 1 \\ 2 \\ 1 \\ 1 \\ 0 \\ 1 \\ 2 \\ 1 \\ 1
\end{bmatrix} \mod 2 =
\begin{bmatrix}
1 \\ 1 \\ 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 1
\end{bmatrix}\end{split}\]
TestModifiedToeplitzMatrixOneDimensionalWide#
\[\text{output_length} = \Big\lfloor 0.5\times 11 - 2\log_2\frac{1}{0.25} \Big\rfloor = \Big\lfloor 1.5 \Big\rfloor = 1\]
>>> import math
>>> math.floor(0.5*11 - 2*math.log2(1/0.25))
1
\begin{align}
\text{seed} &=
\begin{bmatrix}
0_{\color{red}0} & 1_{\color{red}1} & 1_{\color{red}2} & 0_{\color{red}3} & 0_{\color{red}4} & 0_{\color{red}5} &
1_{\color{red}6} & 1_{\color{red}7} & 1_{\color{red}8} & 1_{\color{red}9}
\end{bmatrix}\\
T &=
\begin{bmatrix}
0_{\color{red}0} & 1_{\color{red}9} & 1_{\color{red}8} & 1_{\color{red}7} & 1_{\color{red}6} & 0_{\color{red}5} &
0_{\color{red}4} & 0_{\color{red}3} & 1_{\color{red}2} & 1_{\color{red}1} & 1
\end{bmatrix}
\end{align}
\[\begin{split}T \times \text{input} =
\begin{bmatrix}
0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1
\end{bmatrix}
\begin{bmatrix}
0 \\ 1 \\ 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 1 \\ 1 \\ 0 \\ 0
\end{bmatrix} =
4 \mod 2 = 0\end{split}\]