Hash rodante

Una función hash rodante (también conocida como hash recursivo o suma de verificación rodante) es una función hash en la que la entrada se procesa mediante una ventana que se desplaza a través de la entrada.

Algunas funciones hash permiten calcular un hash rodante muy rápidamente: el nuevo valor hash se calcula rápidamente a partir únicamente del valor hash anterior, se elimina el valor anterior de la ventana y se agrega el nuevo valor a la ventana, de forma similar a como se puede calcular una función de promedio móvil mucho más rápido que otros filtros de paso bajo; y de forma similar a como se puede actualizar rápidamente un hash Zobrist a partir del valor hash anterior.

Una de las principales aplicaciones es el algoritmo de búsqueda de cadenas Rabin-Karp , que utiliza el hash rodante descrito a continuación. Otra aplicación popular es el programa rsync , que utiliza una suma de verificación basada en adler-32 de Mark Adler como hash rodante. El sistema de archivos de red de bajo ancho de banda (LBFS) utiliza una huella digital Rabin como hash rodante. FastCDC (Fast Content-Defined Chunking) utiliza una huella digital Gear de alta eficiencia computacional como hash rodante.

En el mejor de los casos, los valores hash rodantes son independientes por pares ^{[ 1 ]} o fuertemente universales . No pueden ser independientes por tres , por ejemplo.

El algoritmo de búsqueda de cadenas de Rabin-Karp se suele explicar utilizando una función hash rodante que solo emplea multiplicaciones y sumas:

${\displaystyle H=c_{1}a^{k-1}+c_{2}a^{k-2}+c_{3}a^{k-3}+...+c_{k}a^{0}}$,

dónde${\displaystyle a}$es una constante, y${\displaystyle c_{1},...,c_{k}}$son los caracteres de entrada (pero esta función no es una huella digital de Rabin , véase más abajo).

Para evitar manipular grandes cantidades${\displaystyle H}$valores, todas las operaciones matemáticas se realizan módulo${\displaystyle n}$. La elección de${\displaystyle a}$y${\displaystyle n}$es fundamental para obtener un buen hashing; en particular, el módulo${\displaystyle n}$es típicamente un número primo . Consulte el generador congruencial lineal para obtener más información.

Eliminar y añadir caracteres simplemente implica sumar o restar el primer o último término. Desplazar todos los caracteres una posición a la izquierda requiere multiplicar la suma completa.${\displaystyle H}$por${\displaystyle a}$Desplazar todos los caracteres una posición a la derecha requiere dividir la suma total.${\displaystyle H}$por${\displaystyle a}$. Tenga en cuenta que en aritmética modular,${\displaystyle a}$se puede elegir para que tenga un inverso multiplicativo${\displaystyle a^{-1}}$por cual${\displaystyle H}$Se puede multiplicar para obtener el resultado de la división sin realizar realmente una división.

The Rabin fingerprint is another hash, which also interprets the input as a polynomial, but over the Galois fieldGF(2). Instead of seeing the input as a polynomial of bytes, it is seen as a polynomial of bits, and all arithmetic is done in GF(2) (similarly to CRC-32). The hash is the remainder after the division of that polynomial by an irreducible polynomial over GF(2). It is possible to update a Rabin fingerprint using only the entering and the leaving byte, making it effectively a rolling hash.^[2]

Because it shares the same author as the Rabin–Karp string search algorithm, which is often explained with another, simpler rolling hash, and because this simpler rolling hash is also a polynomial, both rolling hashes are often mistaken for each other.^[3]

Hashing by cyclic polynomial^[4]—sometimes called Buzhash^[5]—is also simple and it has the benefit of avoiding multiplications, using circular shift instead. It is a form of tabulation hashing: it presumes that there is some substitution function${\displaystyle s}$ from characters to integers in the interval ${\displaystyle [0,2^{L})}$, essentially a lookup table (each of the 32 bit-positions of the values of s should be balanced, i.e. have as many 1s as there are 0s). Let the function ${\displaystyle \operatorname {rol} }$ be bitwise rotation. E.g., ${\displaystyle \operatorname {rol} (101)=011}$. Let ${\displaystyle \oplus }$ be the bitwise exclusive or. Let ${\displaystyle c_{i}}$ be the i-th byte in a stream, and ${\displaystyle w}$ be the window size in use.

We precalculate ${\displaystyle s'}$ for removing the contribution of a byte that is out of the window:^{[4]:Table III}

${\displaystyle s'[i]=\operatorname {rol} (s[i],w)}$

The hash values is defined as the following recurrence relation:^{[4]:Table III}

${\displaystyle H_{i}={\begin{cases}0&{\text{si }}i=0\\\operatorname {rol} (H_{i-1},1)\oplus s[c_{i}]&{\text{si }}i\leq w\\\operatorname {rol} (H_{i-1},1)\oplus s[c_{i}]\oplus s'[c_{iw}]&{\text{si }}i>w\end{cases}}}$

All values of H are within the interval ${\displaystyle [0,2^{L})}$. This recurrence relation describes the way to compute the hash in a rolling fashion:^{[4]:Table III}

• Hash is initialized at 0.
• When the window is being filled, adding a character involves left-rotating the old hash by one position and XORing the new ${\displaystyle s[c_{i}]}$.
• When the window is full, the same procedure is used to add a character, followed by removal of the contribution of the out-of-window character by XORing ${\displaystyle s'[c_{iw}]}$.

The value of H is neither formally uniform nor 2-universal, despite its empirical uniformity. However, it can be made formally uniform and pairwise independent if only a consecutive ${\displaystyle L-w+1}$Se toman bits del hash. En la práctica, esto puede ser una operación AND (enmascaramiento) a nivel de bits:${\displaystyle H'_{i}=H_{i}\mathbin {\&} (1\ll (w-1)-1)}$, dónde${\displaystyle \mathbin {\&} }$es una operación AND bit a bit y${\displaystyle \ll }$es un desplazamiento a la izquierda. ^{[ 1 ]}

Además, los autores de borg señalan que w no debería ser un múltiplo de 2 L si se utiliza una semilla para modificar s[] mediante la operación XOR de cada valor con la semilla. ^{[ 6 ]}

El agrupamiento de engranajes es otro tipo de hash tabulado. Sea s una tabla inmutable de 256 enteros aleatorios sin signo de 32 bits, H el acumulador hash (entero sin signo, de al menos 32 bits) y f el archivo representado como una matriz de bytes (enteros de 8 bits, subíndice basado en 1).${\displaystyle \ll }$sea ​​el operador de desplazamiento a la izquierda. La relación de recurrencia es: ^{[ 7 ]}

${\displaystyle H_{0}=0}$

${\displaystyle H_{i}=(H_{i-1}\ll 1)+s[f[i]]}$

En comparación con el hash polinomial cíclico, la operación de rotación a la izquierda se reemplaza por un desplazamiento a la izquierda, lo que elimina la necesidad de eliminar la contribución de un byte fuera de la ventana. La operación XOR también se reemplaza por una suma. La segmentación se realiza en función de los bits superiores de H. Este tipo de segmentación genera resultados comparables con la huella digital de Rabin en un tercio del tiempo. ^{[ 7 ]} Sin embargo, en la práctica, la distribución de tamaños de división fue más amplia que la de Rabin, lo que hizo que los resultados de deduplicación fueran aproximadamente un 1 % peores para los casos típicos y un 6 % peores para el peor caso. ^{[ 8 ]}

^{El uso de los bits inferiores también es aceptable ,} pero reduce el tamaño efectivo de la ventana deslizante. El mayor tamaño efectivo aparece cuando la máscara muestrea una serie de bits no consecutivos de un "intervalo" relativamente amplio de H. ^{[ 8} ]

Una de las aplicaciones interesantes de la función hash rodante es que puede crear fragmentos dinámicos basados ​​en el contenido de un flujo o archivo. Esto resulta especialmente útil cuando se requiere enviar solo los fragmentos modificados de un archivo grande a través de una red: una simple adición de bytes al principio del archivo normalmente provocaría que todas las ventanas de tamaño fijo se actualizaran, cuando en realidad, solo se ha modificado el primer "fragmento". ^{[ 9 ]}

Un enfoque simple para hacer fragmentos dinámicos es calcular un hash rodante, y si el valor hash coincide con un patrón arbitrario (por ejemplo, todos ceros) en los N bits inferiores (con una probabilidad de${\textstyle {1 \over 2^{n}}}$Dado que el hash tiene una distribución de probabilidad uniforme, se elige como límite de un fragmento. Cada fragmento tendrá, por lo tanto, un tamaño promedio de${\textstyle 2^{n}}$bytes. Este enfoque garantiza que los datos no modificados (a más de un tamaño de ventana de distancia de los cambios) tendrán los mismos límites. Una vez que se conocen los límites, los fragmentos deben compararse mediante un valor hash criptográfico para detectar cambios. ^{[ 10 ]}

Este tipo de segmentación definida por contenido (CDC) o segmentación basada en contenido (CBC) se utiliza a menudo para la deduplicación de datos . ^{[ 9 ] [ 11 ]} La función hash utilizada puede ser cualquier algoritmo de hash rodante. Algunos ejemplos son:

• Agrupación en los fragmentos menos significativos
  • Una suma no ponderada (rsyncrypto) ^{[ 12 ]}
  • Hash rodante polinomial de Rabin-Karp ^{[ 10 ]}
• Huella digital de Rabin, tal como se utiliza en el software de copia de seguridad restic (con un tamaño de blob que varía entre 512 KiB y 8 MiB y una ventana de 64 bytes). ^{[ 9 ]}
• Agrupación en cualquier bit consecutivo
  • Polinomio cíclico (buzhash), como el que se usa en el software de copia de seguridad Borg . Borg proporciona un rango de tamaño de fragmento personalizable para dividir flujos de archivos, basado en la variación de N , por defecto entre 512 KiB y 8 MiB ). ^{[ 11 ]} Utiliza una ventana de 4095 bytes ^{[ 11 ]} y una función de sustitución no balanceada. ^{[ 13 ]}
• Fragmentación en cualquier colección de bits
  • Un hash de engranaje. ^{[ 7 ]} El CDC basado en engranajes se ha optimizado sucesivamente, dando como resultado FastCDC, RapidCDC y QuickCDC. ^{[ 14 ]}

La segmentación basada en contenido tiene la ventaja de que, en la mayoría de los casos, los cambios locales en un archivo solo afectan al fragmento en el que se encuentra y posiblemente al siguiente, pero no a ningún otro. La elección de distintos algoritmos y funciones hash ofrece diferentes niveles de garantía.

entrada del algoritmo FastCDC : búfer de datos src , longitud de datos n , salida: punto de corte iMinSize ← 2KB // tamaño mínimo de fragmento dividido es 2 KB MaxSize ← 64KB // tamaño máximo de fragmento dividido es 64 KB Mask ← 0x0000d93003530000 // 13 bits activados -> tamaño promedio deseado es 2^13 bytes = 8 KB fp ← 0 // uint64 i ← 0 // El tamaño del búfer es menor que el tamaño mínimo del fragmento. Si n ≤ MinSize , entonces devuelve n. Si n ≥ MaxSize , entonces n ← MaxSize. // Saltar los primeros MinSize bytes y arrancar el hash     mientras i < MinSize hacer fp ← ( fp << 1 ) + Gear [ src [ i ]] i ← i + 1     mientras i < n hacer fp ← ( fp << 1 ) + Gear [ src [ i ]] si !( fp & Mask ) entonces devolver i i ← i + 1     regreso i

Todas las funciones hash rodantes se pueden calcular en tiempo lineal para el número de caracteres y actualizar en tiempo constante cuando los caracteres se desplazan una posición. En particular, el cálculo del hash rodante de Rabin-Karp de una cadena de longitud${\displaystyle k}$requiere${\displaystyle O(k)}$operaciones aritméticas modulares y el hash mediante polinomios cíclicos requiere${\displaystyle O(k)}$OR exclusivos a nivel de bits y desplazamientos circulares . ^{[ 1 ]}

• MinHash – Técnica de minería de datos 
• tejas w

• MIT 6.006: Introducción a los algoritmos 2011 - Sesión 9 - Hash rotatorio