Універсальне гешування

У математиці та обчислювальній техніці універсальне гешування (у рандомізованому алгоритмі чи структурі даних) означає випадковий вибір геш-функції з сімейства геш-функцій із певною математичною властивістю (див. визначення нижче). Це гарантує низьку кількість колізій в очікуванні, навіть якщо дані вибирає противник. Відомо багато універсальних сімейств (для гешування цілих чисел, векторів, рядків), і їх оцінка часто дуже ефективна. Універсальне гешування має численні застосування в інформатиці, наприклад у реалізації геш-таблиць, рандомізованих алгоритмів і криптографії.

Вступ

Припустимо, ми хочемо відобразити ключі з якогось універсуму $U$ в $m$ кошиків (позначених $[m]=\{0,\dots ,m-1\}$). Алгоритм повинен буде обробляти певний набір даних $S\subseteq U$ з $|S|=n$ ключів, про які заздалегідь не відомо. Зазвичай метою гешування є отримання невеликої кількості колізій (ключів з $S$ які потрапляють в один кошик). Детермінована геш-функція не може запропонувати жодних гарантій у ситуації змагання, якщо $|U|>m\cdot n$, оскільки противник може вибрати $S$, яке є саме прообразом кошика. Це означає, що всі ключі даних потрапляють в один кошик, що робить гешування марним. Крім того, детермінована геш-функція не допускає повторного гешування: іноді вхідні дані виявляються поганими для геш-функції (наприклад, забагато колізій), тому можна змінити геш-функцію.

Рішення цих проблем полягає у випадковому виборі геш-функції з сімейства геш-функцій. Сімейство геш-функцій $H=\{h:U\to [m]\}$ називається універсальним, якщо

$\forall x,y\in U,~x\neq y:~~|\{h\in H:h(x)=h(y)\}|\leq {\frac {|H|}{m}}$

Іншими словами, будь-які два різні ключі універсуму утворюють колізію з максимальною ймовірністю $1/m$ коли геш-функція $h$ обирається рівноімовірно випадковим чином із $H$. Це саме та ймовірність колізії, яку ми очікували б, якби геш-функція призначала справді випадкові геш-коди кожному ключу.

Іноді визначення пом'якшується постійним множником, коли вимагається лише ймовірність колізії $O(1/m)$ а не $\leq 1/m$ . Ця концепція була введена Картером і Вегманом у 1977 році та знайшла численні застосування в інформатиці (див., приклад) .

Якщо верхня межа ймовірності колізії $\epsilon <1$, говорять про $\epsilon$-майже універсальність. Так, наприклад, універсальне сімейство є $1/m$-майже універсальним.

Багато, але не всі універсальні родини мають наступну сильнішу властивість рівномірної різниці:

$\forall x,y\in U,~x\neq y$, коли $h$ вибирається випадковим чином із сімейства $H$, різниця $h(x)-h(y)~{\bmod {~}}m$ рівномірно розподілена в $[m]$.

Слід зауважити, що визначення універсальності стосується лише випадку $h(x)-h(y)=0$, по якому підраховуються колізії. Властивість рівномірної різниці сильніша.

Аналогічно універсальне сімейство може бути XOR-універсальним, якщо для $\forall x,y\in U,~x\neq y$ значення $h(x)\oplus h(y)~{\bmod {~}}m$ рівномірно розподілене в $[m]$, де $\oplus$ — операція побітового виключного АБО. Це можливо тільки якщо $m$ є степенем двійки.

Ще сильнішою умовою є попарна незалежність: коли $\forall x,y\in U,~x\neq y$, то ймовірність, що гешування відобразить $x,y$ у будь-яку пару геш-значень $z_{1},z_{2}$ ніби вони абсолютно випадкові: $P(h(x)=z_{1}\land h(y)=z_{2})=1/m^{2}$. Попарну незалежність іноді називають сильною універсальністю.

Ще одна властивість — однорідність. Кажуть, що сімейство однорідне, якщо всі геш-значення однаково імовірні: $P(h(x)=z)=1/m$ для будь-якого геш-значення $z$. Універсальність не означає однорідності. Однак сильна універсальність передбачає однорідність.

Маючи сімейство з властивістю рівномірної відстані, можна створити попарно незалежне або сильно універсальне геш-сімейство шляхом додавання рівномірно розподіленої випадкової константи зі значеннями з $[m]$ до геш-функцій. (Так само, якщо $m$ є степенем двійки, ми можемо досягти попарної незалежності від XOR-універсального геш-сімейства за допомогою операції XOR з рівномірно розподіленою випадковою константою.) Оскільки зсув на константу іноді нерелевантний у програмах (наприклад, геш-таблиці), ретельне розрізнення між властивістю рівномірної відстані та попарною незалежністю іноді не робиться.

Для деяких застосувань (таких як геш-таблиці) важливо, щоб молодші біти геш-значень також були універсальними. Коли сімейство сильно універсальне, це гарантовано: якщо $H$ є сильно універсальним сімейством з $m=2^{L}$, то сімейство, що складається з функцій $h{\bmod {2^{L'}}}$ для усіх $h\in H$, також є універсальним для $L'\leq L$ . На жаль, це не стосується (просто) універсальних сімейств. Наприклад, сімейство з функції ідентичності $h(x)=x$ є однозначно універсальним, але сімейство, яке складається з функції $h(x)=x{\bmod {2^{L'}}}$, не може бути універсальним.

UMAC і Poly1305-AES, а також кілька інших алгоритмів кодів автентифікації повідомлень базуються на універсальному гешуванні. У таких застосуваннях програмне забезпечення вибирає нову геш-функцію для кожного повідомлення на основі унікального довільного числа для цього повідомлення.

Кілька реалізацій геш-таблиць засновані на універсальному гешуванні. У таких застосуваннях зазвичай програмне забезпечення вибирає нову геш-функцію лише після того, як помічає, що «забагато» ключів утворюють колізії; до того часу та сама геш-функція продовжує використовуватися знову і знову. (Деякі схеми вирішення колізій, такі як динамічне ідеальне гешування, вибирають нову геш-функцію кожного разу, коли виникає колізія. Інші схеми вирішення колізій, такі як зозулине гешування та гешування з двома варіантами, допускають кілька колізій перед вибором нової геш-функції). Огляд найшвидших відомих універсальних і сильно універсальних геш-функцій для цілих чисел, векторів і рядків можна знайти в джерелі.

Математичні гарантії

Для будь-якого фіксованого набору $S$ з $n$ ключів, використання універсального сімейства гарантує такі властивості.

1. Для будь-якого фіксованого $x$ у $S$ очікуване число ключів у кошику $h(x)$ дорівнює $n/m$. При реалізації геш-таблиць методом ланцюжків це число пропорційне очікуваному часу роботи по ключу $x$ (наприклад запиту, вставляння чи видалення).
2. Очікуване число пар ключів $x,y$ у $S$ з $x\neq y$, які утворюють колізію ($h(x)=h(y)$) обмежене зверху $n(n-1)/2m$, що є порядком $O(n^{2}/m)$. Коли число кошиків $m$ обране лінійно в $n$ (тобто визначене функцією у $\Omega (n)$), очікуване число колізій становить $O(n)$. При гешуванні у $n^{2}$ кошиків з імовірністю не менше 0.5 не існує колізій взагалі.
3. Очікуване число ключів $x\in S$, які утворюють щонайменше $t$ колізій, обмежене зверху як $2n/(t-2(n/m)+1)$. Таким чином, якщо ємність кожного кошика обмежена потрійним середнім розміром ($t=3n/m$), загальна кількість ключів у переповнених кошиках не більше $O(m)$. Це справедливо лише для геш-сімейства, ймовірність колізії якого обмежена згори $1/m$. Якщо використовується слабше визначення з обмеженням імовірності колізій $O(1/m)$, результат перестає бути істинним.

Оскільки наведені вище гарантії справедливі для будь-якого фіксованого набору $S$, вони зберігаються, якщо набір даних вибрано противником. Однак противник повинен зробити цей вибір до (або незалежно від) випадкового вибору алгоритму геш-функції. Якщо зловмисник може спостерігати за випадковим вибором алгоритму, випадковість не має сенсу, і ситуація така ж, як і з детермінованим гешуванням.

Друга і третя гарантія зазвичай використовуються в поєднанні з перегешуванням. Наприклад, може бути підготовлений рандомізований алгоритм для обробки деякої кількості $O(n)$ колізій. Якщо він спостерігає занадто багато колізій, він вибирає іншу випадкову $h$ з родини і повторює гешування. Універсальність гарантує, що кількість повторень є геометричною випадковою величиною.

Конструкції

Оскільки будь-які комп'ютерні дані можуть бути представлені як одне або більше машинних слів, зазвичай потрібні геш-функції для трьох типів доменів: машинні слова («цілі числа»); вектори машинних слів фіксованої довжини; і вектори змінної довжини («рядки»).

Гешування цілих чисел

У цьому розділі розглядається випадок гешування цілих чисел, які вписуються в машинні слова; таким чином, такі операції, як множення, додавання, ділення тощо, є дешевими машинними інструкціями. Нехай універсум, що гешується $\{0,\dots ,|U|-1\}$.

Початкова пропозиція Картера і Вегмана полягала у виборі простого числа $p\geq |U|$ і визначенні

$h_{a,b}(x)=((ax+b)~{\bmod {~}}p)~{\bmod {~}}m$

де $a,b$ випадково вибрані цілі числа за модулем $p$ з $a\neq 0$ . (Це одна ітерація лінійного конгруентного генератора.)

Щоб побачити, що $H=\{h_{a,b}\}$ є універсальним сімейством, слід зауважити, що $h(x)=h(y)$ виконується лише коли

$ax+b\equiv ay+b+i\cdot m{\pmod {p}}$

для деякого цілого числа $i$ між $0$ і $(p-1)/m$ . Оскільки $p\geq |U|$, якщо $x\neq y$ їх різниця $x-y$ не дорівнює нулю і має оберенене за модулем $p$ число. Розв'язання для $a$

$a\equiv i\cdot m\cdot (x-y)^{-1}{\pmod {p}}$ .

Існує $p-1$ можливих варіантів для $a$ (оскільки $a=0$ виключається) і, варіюючи $i$ в допустимому діапазоні, можливо отримати $\lfloor (p-1)/m\rfloor$ ненульових значень для правої частини. Таким чином, ймовірність колізії дорівнює

$\lfloor (p-1)/m\rfloor /(p-1)\leq ((p-1)/m)/(p-1)=1/m$ .

Інший спосіб побачити, що $H$ є універсальним сімейством використовує поняття статистичної відстані. Різницю $h(x)-h(y)$ можна переписати як

$h(x)-h(y)\equiv (a(x-y)~{\bmod {~}}p){\pmod {m}}$ .

Оскільки $x-y$ не дорівнює нулю і $a$ рівномірно розподіляється в $\{1,\dots ,p-1\}$, з цього випливає, що $a(x-y)$ по модулю $p$ також рівномірно розподіляється в $\{1,\dots ,p-1\}$. Розподіл $(h(x)-h(y))~{\bmod {~}}m$ таким чином є майже рівномірним, аж до різниці в ймовірності $\pm 1/p$ між зразками. У результаті статистична відстань до однорідної родини становить $O(m/p)$, яка стає незначною, коли $p\gg m$.

Сімейство простіших геш-функцій

$h_{a}(x)=(ax~{\bmod {~}}p)~{\bmod {~}}m$

є лише приблизно універсальним: $\Pr\{h_{a}(x)=h_{a}(y)\}\leq 2/m$ для усіх $x\neq y$. Крім того, цей аналіз є майже строгим; Картер і Вегман показують що $\Pr\{h_{a}(1)=h_{a}(m+1)\}\geq 2/(m-1)$ будь-коли $(p-1)~{\bmod {~}}m=1$ .

Уникнення модульної арифметики

Найсучаснішим для гешування цілих чисел є схема множення-зсуву, описана Діцфельбінгером та ін. у 1997 р. Завдяки уникненню модульної арифметики цей метод набагато легше реалізувати, а також він працює значно швидше на практиці (зазвичай щонайменше в чотири рази). Схема припускає, що кількість кошиків є ступенем двійки, $m=2^{M}$. Нехай $w$ буде кількістю бітів у машинному слові. Потім геш-функції параметризуються над непарними додатними цілими числами $a<2^{w}$ (що вписується в одне $w$-бітове слово). Щоб оцінити $h_{a}(x)$, слід помножити $x$ на $a$ по модулю $2^{w}$ а потім зберегти старші $M$ бітів як геш-код. У математичній нотації це

$h_{a}(x)=(a\cdot x\,\,{\bmod {\,}}2^{w})\,\,\mathrm {div} \,\,2^{w-M}.$

Ця схема не задовольняє властивості рівномірної різниці і є єдиною $2/m$ -майже універсальною; для будь-якого $x\neq y$, $\Pr\{h_{a}(x)=h_{a}(y)\}\leq 2/m$.

Щоб зрозуміти поведінку геш-функції, зауважимо, що якщо $ax{\bmod {2}}^{w}$ і $ay{\bmod {2}}^{w}$ мають однакові старші M бітів, тоді $a(x-y){\bmod {2}}^{w}$ має всі одиниці або всі нулі у старших M бітах (залежно від того, що більше: $ax{\bmod {2}}^{w}$ чи $ay{\bmod {2}}^{w}$). Припустимо, що набір молодших бітів $x-y$ з'являється на позиції $w-c$. Через те, що $a$ є випадковим непарним цілим числом, а непарні цілі числа мають обернені значення у кільці $Z_{2^{w}}$, слідує, що $a(x-y){\bmod {2}}^{w}$ буде рівномірно розподілено серед $w$-бітових цілих чисел з молодшим установленим бітом на позиції $w-c$. Таким чином, імовірність того, що всі ці біти складаються з 0 або 1, не перевищує $2/2^{M}=2/m$.

З іншого боку, якщо $c<M$, тоді старші M бітів $a(x-y){\bmod {2}}^{w}$ містять і 0, і 1, тому $h(x)\neq h(y)$. Насамкінець, якщо $c=M$ то біт $w-M$ значення $a(x-y){\bmod {2}}^{w}$ є 1, і $h_{a}(x)=h_{a}(y)$ тоді і тільки тоді, коли біти $w-1,\ldots ,w-M+1$ також є 1, що відбувається з імовірністю $1/2^{M-1}=2/m$.

Цей аналіз є строгим, як можна показати на прикладі $x=2^{w-M-2}$ і $y=3x$. Щоб отримати дійсно «універсальну» геш-функцію, можна використати схему множення-додавання-зсуву, яка вибирає старші біти

$h_{a,b}(x)=((ax+b){\bmod {2}}^{w+M})\,\mathrm {div} \,2^{w},$

де $a$ є випадковим натуральним числом з $a<2^{2w}$ і $b$ є випадковим невід'ємним цілим числом з $b<2^{2w}$. Для цього потрібно виконувати арифметику $2w$ -розрядних беззнакових цілих чисел. Ця версія множинного зсуву належить Діцфельбінгеру, а пізніше була більш точно проаналізована Вельфелем.

Гешування векторів

Цей розділ стосується гешування вектора машинних слів фіксованої довжини. Вхідні дані інтерпретуються як вектор ${\bar {x}}=(x_{0},\dots ,x_{k-1})$ з $k$ машинних слів (цілі числа по $w$ бітів кожне). Якщо $H$ є універсальним сімейством з властивістю рівномірної різниці, наступне сімейство (походить від Картера і Вегмана) також має властивість рівномірної різниці (і, отже, є універсальним):

$h_{\bar {a}}({\bar {x}})=\left({\big (}\sum _{i=0}^{k-1}x_{i}\cdot a_{i}{\big )}~{\bmod {~}}2^{2w}\right)\,\,\mathrm {div} \,\,2^{2w-M}$ .

Якщо $m$ є степенем двійки, підсумовування можна замінити виключним або.

На практиці, якщо доступна арифметика подвійної точності, вона створюється за допомогою сімейства геш-функцій із множним зсувом. Якщо ніціалізувати геш-функцію вектором ${\bar {a}}=(a_{0},\dots ,a_{k-1})$ випадкових непарних цілих чисел по $2w$ бітів кожне, тоді, якщо кількість кошиків дорівнює $m=2^{M}$ для $M\leq w$ :

$h_{\bar {a}}({\bar {x}})=\left({\Big (}\sum _{i=0}^{\lceil k/2\rceil }(x_{2i}+a_{2i})\cdot (x_{2i+1}+a_{2i+1}){\Big )}{\bmod {~}}2^{2w}\right)\,\,\mathrm {div} \,\,2^{2w-M}$ .

Можна вдвічі зменшити кількість множень, що на практиці приблизно означає подвійне прискорення. Якщо ніціалізувати геш-функцію вектором ${\bar {a}}=(a_{0},\dots ,a_{k-1})$ випадкових непарних цілих чисел на $2w$ біти кожне, то наступне сімейство геш-функцій є універсальним:

$h_{\bar {a}}({\bar {x}})^{\mathrm {strong} }=(a_{0}+\sum _{i=0}^{k-1}a_{i+1}x_{i}{\bmod {~}}2^{2w})\,\,\mathrm {div} \,\,2^{w}$ .

Якщо операції подвійної точності недоступні, можна інтерпретувати вхідні дані як вектор півслів ($w/2$ -розрядні цілі числа). Далі буде використовуватися алгоритм $\lceil k/2\rceil$ множення, де $k$ — кількість півслів у векторі. Таким чином, алгоритм працює зі швидкістю одного множення на вхідне слово.

Цю ж схему також можна використовувати для гешування цілих чисел, інтерпретуючи їхні біти як вектори байтів. У цьому варіанті векторна техніка відома як табуляційне гешування та забезпечує практичну альтернативу універсальним схемам гешування на основі множення.

Також можлива сильна універсальність на високій швидкості. Потрібно ініціалізувати геш-функцію вектором ${\bar {a}}=(a_{0},\dots ,a_{k})$ випадкових цілих чисел на $2w$ бітів. Обчислити

$h_{\bar {a}}({\bar {x}})^{\mathrm {strong} }=(a_{0}+\sum _{i=0}^{k-1}a_{i+1}x_{i}{\bmod {~}}2^{2w})\,\,\mathrm {div} \,\,2^{w}$ .

Результат сильно універсальний на $w$ бітах. Експериментально було встановлено, що він працює на швидкості на 0,2 цикла процесора на байт на останніх процесорах Intel для $w=32$.

Гешування рядків

Це стосується гешування вектора машинних слів змінного розміру. Якщо довжину рядка можна обмежити невеликим числом, найкраще використовувати векторне рішення зверху (концептуально доповнюючи вектор нулями до верхньої межі). Потрібний простір — це максимальна довжина рядка, але час для оцінки $h(s)$ це просто довжина $s$. Поки нулі заборонені в рядку, доповнення нулями можна ігнорувати під час оцінювання геш-функції без впливу на універсальність. Слід зауважити, що якщо в рядку дозволені нулі, тоді, можливо, найкраще буде додати фіктивний ненульовий символ (наприклад, 1) до всіх рядків перед доповненням: це гарантує, що це не вплине на універсальність.

Тепер припустимо, що ми хочемо гешувати ${\bar {x}}=(x_{0},\dots ,x_{\ell })$, де гарна межа $\ell$ апріорі невідома. Універсальне сімейство, запропоноване, розглядає рядок $x$ як коефіцієнти полінома за модулем великого простого числа. Якщо $x_{i}\in [u]$, прийняти просте число $p\geq \max\{u,m\}$ і визначити:

$h_{a}({\bar {x}})=h_{\mathrm {int} }\left({\big (}\sum _{i=0}^{\ell }x_{i}\cdot a^{\ell -i}{\big )}{\bmod {~}}p\right)$, де $a\in [p]$ є рівномірно випадковим і $h_{\mathrm {int} }$ вибирається випадковим чином із універсального сімейства, що відображає: цілі числа $[p]\mapsto [m]$ .

Використовуючи властивості модульної арифметики, наведене вище можна обчислити без отримання великих чисел для великих рядків, як показано нижче:

uint hash(String x, int a, int p)
	uint h = INITIAL_VALUE
	for (uint i=0 ; i < x.length ; ++i)
		h = ((h*a) + x[i]) mod p
	return h

Цей коткий геш Рабіна-Карпа базується на лінійному конгруентному генераторі. Наведений вище алгоритм також відомий як мультиплікативна геш-функція. На практиці оператора mod і параметра p можна взагалі уникнути, просто дозволивши цілочисельне переповнення, оскільки це еквівалентно mod (Max-Int-Value + 1) у багатьох мовах програмування. У таблиці нижче показано значення, вибрані для ініціалізації h і a для деяких популярних реалізацій.

Реалізація	Початкове значення	a
геш-функція Бернштайна djb2	5381	33
STLPort 4.6.2	0	5
геш-функція Кернігана та Річі	0	31
java.lang.String.hashCode()	0	31

Розглянемо два рядки ${\bar {x}},{\bar {y}}$ і нехай $\ell$ бути довжиною довшого; для аналізу коротший рядок концептуально доповнюється нулями до довжини $\ell$ . Колізія при застосуванні $h_{\mathrm {int} }$ означає, що $a$ є коренем многочлена з коефіцієнтами ${\bar {x}}-{\bar {y}}$. Цей многочлен має не більше $\ell$ коренів по модулю $p$, тому ймовірність колізії не більше $\ell /p$. Імовірність колізії через випадковість $h_{\mathrm {int} }$ доводить загальну ймовірність колізії до ${\frac {1}{m}}+{\frac {\ell }{p}}$. Таким чином, якщо просте $p$ є достатньо великим порівняно з довжиною гешованих рядків, сімейство дуже близько до універсального (за статистичною відстанню).

Інші універсальні сімейства геш-функцій, які використовуються для гешування рядків невідомої довжини до геш-значень фіксованої довжини, включають відбиток Рабіна та Бужаш.

Уникнення модульної арифметики

Щоб пом'якшити обчислювальні витрати від модульної арифметики, на практиці використовуються три прийоми:

1. Обирається просте $p$, близьке до степеня двійки, наприклад просте число Мерсенна. Це дозволяє арифметику по модулю $p$ реалізувати без ділення (з використанням швидших операцій, таких як додавання та зсув). Наприклад, на сучасних архітектурах можна працювати з $p=2^{61}-1$, поки $x_{i}$ є 32-розрядними значеннями.
2. До блоків можна застосувати векторне гешування. Наприклад, можна застосувати гешування векторів до кожного блоку з 16 слів рядка, а також застосувати гешування рядка до $\lceil k/16\rceil$ результатів. Оскільки повільніше гешування рядків застосовується до значно меншого вектора, загальна швидкість, по суті, буде така ж, як і швидкість гешування векторів.
3. Дільником вибирається ступінь двійки, що дозволяє виконувати арифметичні дії за модулем $2^{w}$ без ділення (з використанням швидших операцій маскування бітів). Сімейство геш-функцій NH використовує цей підхід.

Див. також

• K-independent hashing
• Коткий геш
• Tabulation hashing
• Min-wise independence
• Universal one-way hash function
• Послідовність із низькою розбіжністю
• Perfect hashing

Подальше читання

• Knuth, Donald Ervin (1998). The Art of Computer Programming, Vol. III: Sorting and Searching (вид. 3rd). Reading, Mass; London: Addison-Wesley. ISBN 0-201-89685-0.

Посилання

• Відкриті структури даних — Розділ 5.1.1 — Мультиплікативне гешування, Пет Морін