Глава 12 Хеши и временно-упорядоченный идентификатор XID

Ориентация главы

Завершающая глава тома 2 ставит рядом две темы «идентичности»: хеширование сворачивает произвольные байты в отпечаток фиксированной ширины, а XID генерирует для каждой записи временно-упорядоченный уникальный идентификатор. Их объединяет одно слово — детерминированность: детерминированность хеша делает проверку и распределение по корзинам воспроизводимыми; детерминированность XID даёт «словарный порядок = порядок времени генерации». Глава одновременно проводит границу безопасности: хеш без ключа не стойкое к атаке коллизий; ключевой SipHash — правильный выбор для внешне видимых ключей (вроде ключей хеш-таблиц); «хранение пользовательских паролей» не ответ ни тем ни другим — это территория криптомодуля тома 8. Прочитав главу, вы выберете верный инструмент для трёх частых задач: проверка целостности данных, внешние ключи хеш-таблиц, распределённые первичные ключи.

12.1引入

Три сценария. Первый: ежедневная синхронизация гигабайт индексных файлов — нужно знать «изменилось ли» — пересылать весь файл для сравнения слишком дорого; посчитайте отпечаток и отправьте 8 байт. Второй: сервер делает ключи хеш-таблицы из полей заголовков запроса, и атакующий конструирует коллизионные входы, вырождая хеш-таблицу в связный список — это hash-collision DoS, и ответ — дать хешу ключ, известный только вам. Третий: выбор первичного ключа для распределённой системы — автоприращаемые целые требуют координационного центра, полностью случайный UUID v4 фрагментирует индексы базы, а идентификатор со «временем впереди» естественно кластеризуется по порядку создания.

Три сценария соответствуют xrtHash32/64 (детерминированные отпечатки), xrtSipHash (ключевой, стойкий к коллизиям) и XID (временно-упорядоченный уникальный идентификатор). Никто из них — не криптографический примитив; граница применения пришпилена в контрактах. Глава также закрывает том 2: детерминированные числа главы 10, детерминированные случайные последовательности главы 11 и детерминированные отпечатки этой главы вместе — три краеугольных камня «инженерной определённости»: всё, что записано в ассерты тестов, обязано быть воспроизводимо кроссплатформенно и сквозь время.

12.2概念

Детерминированное хеширование: один вход — всегда один выход

xrtHash32(pData, iSize) и xrtHash64 используют фиксированное семя по умолчанию — одни и те же байты дают одно и то же значение когда угодно и в любом процессе. Это предпосылка контрольных сумм, распределения по корзинам и ключей кэша. Когда нужна межпроцессная согласованность, но «не дать противнику предвычислить», берите версии с явным семенем xrtHash32Seed / xrtHash64Seed: многомашинное шардирование держит одно семя ради согласованности; внешние сценарии меняют семя, перемешивая таблицы предвычислений. Заметьте другую сторону «детерминированности»: бесплючевой хеш вычислим кем угодно — он доказывает «данные таковы», но не «от кого данные».

Ключевое хеширование: SipHash-2-4

xrtSipHash(pData, iSize, Key) использует xsipkey (128-битный ключ, конструируется xrtSipKey(低64, 高64) — дословные токены). Не зная ключа, коллизии не построить — ключи хеш-таблиц над недоверенным входом обязаны идти через него. Потоковый интерфейс xrtSipHashInit / Update / Final обрабатывает данные, приходящие кусками (сетевые потоки, большие файлы), и равнозначен по результату одноразовой версии — тот же ключ и те же данные дают то же 64-битное значение в обеих позах. Жизненный цикл ключа следует дисциплине чувствительных данных главы 5: по завершении xrtSecureZero.

XID: 192-битный идентификатор со временем впереди

XID разрешает трилемму «распределённого первичного ключа»: координационный центр не нужен (время + случайность + последовательность генерируются локально), фрагментации нет (временной префикс кластеризуется), читаемо (32-символьный текст). xrtXidMake генерирует, xrtXidWrite пишет в буфер вызывающего (ёмкость XID_TEXT_CAPACITY, каноническая длина XID_TEXT_SIZE без хвостового нуля), xrtXidParse строго разбирает обратно в двоичное (любое отклонение длины или набора символов отказывает целиком и сообщает позицию первого нелегального байта — xrtXidErrorOffset), а xrtXidTime извлекает момент генерации за O(1) битовых операций. Пакетная генерация — xrtXidMakeMany (берёт сразу партию случайных байт, снижая накладные расходы системных вызовов); xrtXidCompare даёт стабильный полный порядок — базовый примитив сортировки и дедупликации. Сверьте разделение труда с четырьмя слоями главы 11: XID внутри использует безопасный источник случайности ради уникальности, но сам XID — не «секрет»: его появление в URL, журналах и базах безвредно; когда нужен непредсказуемый идентификатор (скажем capability-токен), берите SecureText главы 11.

Таблица выбора

Предварительное напоминание: отпечаток — не шифрование

Перед прогоном примеров пришпилим частое заблуждение: хеширование — это отпечаток, не шифрование. Шифрование обратимо (с ключом можно восстановить); отпечаток нет (из 8 байт не восстановить файл в 8 ГБ); шифрование прячет содержимое, отпечаток публикует существование содержимого. «Посчитать отпечаток файла и удалить оригинал» — неисправимая ошибка: отпечаток служит только сравнению, не хранению. С этой границей в голове три группы примеров получают правильное прочтение.

12.3示例

Полная программа: детерминированное хеширование и явное семя

Из примера репозитория examples/hash/hash32/main.c:

 */

#include <stdio.h>

#include <xrt.h>



int main(void)
{
	/* 长度用 sizeof-1 显式排除结尾零——键是二进制安全的。 */
	static const char sKey[] = "user:42";

	printf("default: %08X\n", (unsigned int)xrtHash32(sKey, sizeof(sKey) - 1u));
	printf("seeded : %08X\n", (unsigned int)xrtHash32Seed(sKey,
		sizeof(sKey) - 1u, UINT32_C(0x12345678)));
	return 0;
}

Что только что произошло. (1) sizeof(sKey)-1 явно исключает хвостовой ноль — вход хеша бинарно-безопасная байтовая строка, нулевое завершение — лишь конвенция C-строк; один лишний ноль — другие данные и другой отпечаток. (2) Семя по умолчанию выводит 9590B597 — стабильно кроссплатформенно и межверсионно: что вы посчитали сегодня, совпадает со вчерашним CI. (3) Те же данные с другим семенем дают совершенно иной отпечаток — семя участвует в той же детерминированной функции, и суть «защиты от предвычислений» в том, что противник не знает вашего варианта функции.

Полная программа: сведение одноразового и потокового SipHash

Из examples/hash/variants/main.c — проверка равнозначности двух поз:

 */

#include <stdio.h>
#include <xrt.h>

int main(void)
{
	xsipkey Key = xrtSipKey(UINT64_C(0x0123456789ABCDEF),
		UINT64_C(0xFEDCBA9876543210));
	uint64 iStreamed = 0;

	/* 显式种子：跨进程一致分片、防预计算。 */
	printf("seed64: %016llX\n",
		(unsigned long long)xrtHash64Seed("user:42", 7u, UINT64_C(0x1234)));

	/* 一次性 SipHash；与 keyed 范例的 Init/Update/Final 对拍。 */
	printf("sip:    %016llX\n",
		(unsigned long long)xrtSipHash("request:user-input", 18u, Key));

	/* 对拍：流式喂同样数据（分两块）结果一致。 */
	{
		xsiphash State;

		xrtSipHashInit(&State, Key);
		(void)xrtSipHashUpdate(&State, "request:", 8u);
		(void)xrtSipHashUpdate(&State, "user-input", 10u);
		iStreamed = xrtSipHashFinal(&State);
	}
	printf("stream-equal=%s\n",
		iStreamed == xrtSipHash("request:user-input", 18u, Key) ? "yes" : "no");
	return 0;
}

Что только что произошло. (1) xsipkey строится из двух 64-битных слов — 128-битное пространство ключей, ключ из безопасной случайности (глава 11), не зашит в код. (2) Одноразовый xrtSipHash на восемнадцатибайтовом входе даёт 21D9F0C356D09D0A. (3) Потоковая версия скармливает те же данные двумя кусками (Update дважды), и результат Final полностью совпадает с одноразовым — третья строка stream-equal=yes есть важнейший ассерт главы: нарезка на куски не влияет на отпечаток, сетевая потоковая обработка и цельноблочное вычисление взаимно сверяемы. (4) Строка Hash64Seed показывает типовое употребление сеяного детерминированного хеша: отпечаток "user:42" с семенем 0x1234 стабилен — многомашинное шардирование маршрутизирует по этому значению по модулю, и пока семя неизменно, маршрутизация не меняется при масштабировании.

Полная программа: генерация XID, текстовизация, разбор, извлечение времени

Из examples/id/xid/main.c:

 */

#include <xrt.h>

#include <stdio.h>



int main(void)
{
	xid Value;
	xid Parsed;
	char arrText[XID_TEXT_CAPACITY];   /* 定长文本缓冲（含结尾零） */
	xtime iTime;

	



	 */
	if ( !xrtXidMake(&Value) ||
		 !xrtXidWrite(&Value, arrText, sizeof(arrText)) ||
		 !xrtXidParse((xstrview){ arrText, XID_TEXT_SIZE }, &Parsed) ||
		 !xrtXidTime(&Parsed, &iTime) ) {
		return 1;
	}

	/* 文本恒定 32 字符（base62 风格），可直接进 URL/日志/主键。 */
	printf("XID: %s\n", arrText);

	/* 时间提取：不需要查表或解码整个标识，O(1) 位运算。 */
	printf("civil UTC milliseconds: %lld\n", (long long)iTime);
	return 0;
}

Что только что произошло. (1) Одна линия: Make генерирует → Write текстовизирует → Parse разбирает обратно в двоичное → Time извлекает момент — четыре функции образуют цикл чтения-записи XID. (2) Длина входного представления Parse — XID_TEXT_SIZE (без хвостового нуля): любое отклонение длины или символа отказывает целиком, а xrtXidErrorOffset извлекает из ошибки позицию первого нелегального байта — ошибка несёт собственную локацию, разбирать сообщения не нужно. (3) Временная метка вывода меняется с моментом запуска, но свойство префиксного возрастания неизменно: напечатанный раньше XID словарно меньше напечатанного позже.

12.4契约

• Детерминированность: Hash32/64 и SipHash с одним входом и ключом всегда дают один вывод, стабильно кроссплатформенно и межверсионно (нарезка на куски не влияет).
• Граница безопасности: беспключевые хеши не стойки к атаке коллизий; внешние ключи таблиц — SipHash с ключом в секрете; хранение паролей не входит в главу (хеширование паролей тома 8).
• Дисциплина ключа: xsipkey — чувствительные данные; генерация из безопасной случайности, по завершении xrtSecureZero.
• Упорядоченность XID: словарный порядок = порядок времени генерации; Compare даёт стабильный полный порядок; направление единичного сравнения при быстрых подряд идущих генерациях не является обещанием (миллисекундные часы решают очерёдность).
• Строгость разбора: Parse принимает только канонический текст фиксированной длины; при неудаче вывод не пишется, смещение ошибки читается из ошибки потока.
• Пакетная генерация: MakeMany генерирует сразу партию в непрерывном хранилище, снижая число системных вызовов.

Типичные ошибки

uint64 iKey = xrtHash64(Header.Value, Header.Size);  /* публичная функция */
Bucket = TableFind(iKey);                             /* коллизии конструируемы */

uint64 iKey = xrtSipHash(Header.Value, Header.Size, gTableKey);  /* ключ в секрете */
Bucket = TableFind(iKey);

char arrText[XID_TEXT_CAPACITY];
load(arrText);
if ( !xrtXidParse((xstrview){ arrText, XID_TEXT_CAPACITY }, &Value) ) {
	/* длина 33: верный отказ — хвостовой ноль не часть текста */
}

char arrText[XID_TEXT_CAPACITY];
load(arrText);
if ( !xrtXidParse((xstrview){ arrText, XID_TEXT_SIZE }, &Value) ) {
	size_t iOffset = 0;
	xrtXidErrorOffset(xrtGetError(), &iOffset);   /* позиция первого нелегального байта */
}

Практические задания

Итоги