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}$puede elegirse para tener 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.

La huella digital de Rabin es otro hash que también interpreta la entrada como un polinomio, pero sobre el campo de Galois GF(2) . En lugar de ver la entrada como un polinomio de bytes, se ve como un polinomio de bits, y toda la aritmética se realiza en GF(2) (de forma similar a CRC-32 ). El hash es el resto de la división de ese polinomio por un polinomio irreducible sobre GF(2). Es posible actualizar una huella digital de Rabin utilizando solo el byte de entrada y el de salida, lo que la convierte efectivamente en un hash rodante. ^{[ 2 ]}

Debido a que comparte el mismo autor que el algoritmo de búsqueda de cadenas de Rabin-Karp, que a menudo se explica con otro hash rodante más simple, y debido a que este hash rodante más simple también es un polinomio, ambos hashes rodantes a menudo se confunden entre sí. ^{[ 3 ]}

El hashing mediante polinomio cíclico ^{[ 4 ]} —a veces llamado Buzhash ^{[ 5 ]} — también es sencillo y tiene la ventaja de evitar multiplicaciones, utilizando en su lugar un desplazamiento circular . Es una forma de hashing por tabulación : presupone que existe alguna función de sustitución.${\displaystyle s}$de caracteres a enteros en el intervalo${\displaystyle [0,2^{L})}$, esencialmente una tabla de búsqueda (cada una de las 32 posiciones de bits de los valores de s debe estar equilibrada, es decir, tener tantos 1 como 0). Sea la función${\displaystyle \operatorname {rol} }$ser rotación bit a bit . Por ejemplo,${\displaystyle \operatorname {rol} (101)=011}$. Dejar${\displaystyle \oplus }$sea ​​el OR exclusivo a nivel de bits.${\displaystyle c_{i}}$sea ​​el i-ésimo byte en un flujo, y${\displaystyle w}$sea ​​el tamaño de ventana en uso.

Precalculamos${\displaystyle s'}$para eliminar la contribución de un byte que está fuera de la ventana: ^{[ 4 ] : Tabla III}

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

Los valores hash se definen como la siguiente relación de recurrencia: ^{[ 4 ] : Tabla 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}}}$

Todos los valores de H están dentro del intervalo${\displaystyle [0,2^{L})}$Esta relación de recurrencia describe la forma de calcular el hash de manera continua: ^{[ 4 ] : Tabla III}

• El hash se inicializa en 0.
• Cuando se está llenando la ventana, agregar un carácter implica rotar a la izquierda el hash antiguo una posición y aplicar la operación XOR al nuevo.${\displaystyle s[c_{i}]}$.
• Cuando la ventana está llena, se utiliza el mismo procedimiento para agregar un carácter, seguido de la eliminación de la contribución del carácter fuera de la ventana mediante XOR.${\displaystyle s'[c_{iw}]}$.

El valor de H no es formalmente uniforme ni 2-universal, a pesar de su uniformidad empírica. Sin embargo, puede hacerse formalmente uniforme e independiente por pares si solo se cumple una condición consecutiva.${\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