Chapter 12 Hashes and the XID Time-Ordered Identifier

Chapter Orientation

Volume 2's closing chapter puts two "identity" topics together: hashing folds arbitrary bytes into a fixed-width fingerprint, and XID generates a time-ordered unique identifier for every record. They share one keyword — determinism: a hash's determinism makes verification and bucketing reproducible; XID's determinism makes "lexicographic order = generation-time order". The chapter also draws the security boundary: keyless hashes resist no collision attack, and the keyed SipHash is the right choice for externally visible keys (like hash-table keys); "storing user passwords" is answered by neither — that is the territory of Volume 8's crypto module. After this chapter you will pick the right tool for three frequent problems: data-consistency verification, external hash-table keys, and distributed primary keys.

12.1引入

Three scenarios. One: syncing gigabytes of index files daily, synchronously, and wanting to know "did anything change" — shipping the whole file over for comparison is too expensive; compute a fingerprint and send 8 bytes. Two: a server uses request-header fields as hash-table keys, and an attacker crafts colliding inputs, degrading the hash map into a linked list — that is hash-collision DoS, and the answer is giving the hash a key only you know. Three: choosing a primary key for a distributed system — auto-increment integers need a coordination center, fully random UUID v4 fragments database indexes, while a "time-first" identifier naturally clusters by creation order.

The three scenarios map to xrtHash32/64 (deterministic fingerprints), xrtSipHash (keyed, collision-resistant), and XID (the time-ordered unique identifier). None is a cryptographic primitive — the usage boundary is pinned in the contracts. This chapter also closes Volume 2: Chapter 10's deterministic numbers, Chapter 11's deterministic random sequences, and this chapter's deterministic fingerprints together form the three cornerstones of "engineering determinism" — everything written into test assertions must be reproducible across platforms and across time.

12.2概念

Deterministic hashing: same input, always the same output

xrtHash32(pData, iSize) and xrtHash64 use a fixed default seed — the same bytes produce the same value at any time, in any process. That is the precondition for checksums, bucketing, and cache keys. When you need cross-process consistency but "don't let an adversary precompute", use the explicit-seed versions xrtHash32Seed / xrtHash64Seed: multi-process sharding keeps one seed for consistency; external scenarios switch seeds to scramble precomputation tables. Note the other face of "determinism": a keyless hash is computable by anyone — it proves "the data is this", not "the data came from whom".

Keyed hashing: SipHash-2-4

xrtSipHash(pData, iSize, Key) uses an xsipkey (a 128-bit key, constructed via xrtSipKey(低64, 高64)). Without the key, collisions cannot be constructed — hash-map keys over untrusted input must use it. The streaming interface xrtSipHashInit / Update / Final handles chunk-arriving data (network streams, large files) and is result-equivalent to the one-shot version — the same key and data give the same 64-bit value either way. The key's lifecycle follows Chapter 5's sensitive-data discipline: xrtSecureZero when done.

XID: the 192-bit identifier with time in front

XID resolves the trilemma of "distributed primary keys": no coordination center needed (time + random + sequence generated locally), no fragmentation (the time prefix clusters), readable (32-character text). xrtXidMake generates, xrtXidWrite writes into the caller's buffer (capacity XID_TEXT_CAPACITY, canonical length XID_TEXT_SIZE without the trailing zero), xrtXidParse strictly parses back to binary (any deviation of length or character set fails whole and reports the first illegal byte's position — xrtXidErrorOffset), and xrtXidTime extracts the generation moment with O(1) bit operations. Batch generation uses xrtXidMakeMany (drawing a whole batch of random bytes at once, cutting syscall overhead); xrtXidCompare provides a stable total order — the base primitive for sorting and deduplication. Compare the division of labor with Chapter 11's four randomness layers: XID internally uses the secure randomness source for uniqueness, but the XID itself is not a "secret" — it may appear in URLs, logs, and databases without harm; when you need an unpredictable identifier (a capability token, say), use Chapter 11's SecureText.

A selection table

A prior reminder: a fingerprint is not encryption

Before running the examples, pin down a frequent misunderstanding: hashing is a fingerprint, not encryption. Encryption is reversible (with the key you can restore); a fingerprint is not (you cannot restore an 8-GB file from 8 bytes); encryption keeps content secret, a fingerprint publicizes the content's existence. "Hash the file then delete the original" is an unrecoverable mistake — a fingerprint serves comparison, never storage. With this boundary clear, the three example groups' outputs get their correct reading.

12.3示例

Complete program: deterministic hashing and the explicit seed

From the repository example 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;
}

What just happened. (1) sizeof(sKey)-1 explicitly excludes the trailing zero — a hash's input is a binary-safe byte string, and zero termination is merely the C-string convention; one extra zero is different data and a different fingerprint. (2) The default seed outputs 9590B597 — stable across platforms and versions; what you compute today matches yesterday's CI. (3) The same data with a different seed gives a completely different fingerprint — the seed participates in the same deterministic function, and "precomputation defense" is precisely that the adversary does not know your function variant.

Complete program: SipHash one-shot versus streaming

From examples/hash/variants/main.c, verifying the two postures' result equivalence:

 */

#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;
}

What just happened. (1) The xsipkey is built from two 64-bit words — a 128-bit key space, the key coming from secure randomness (Chapter 11), not hard-coded. (2) One-shot xrtSipHash over the eighteen-byte input gives 21D9F0C356D09D0A. (3) The streaming version feeds the same data in two chunks (Update twice), and Final's result is identical to the one-shot — the third line stream-equal=yes is this chapter's most important assertion: chunking does not affect the fingerprint, so network streaming and whole-block computation can cross-verify each other. (4) The Hash64Seed line shows the typical use of the seeded deterministic hash: the fingerprint of "user:42" with seed 0x1234 is stable — multi-process sharding routes by this value modulo, and as long as the seed doesn't change, routing doesn't change through scale-up or scale-down.

Complete program: XID generation, textualization, parsing, time extraction

From 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;
}

What just happened. (1) The full chain: Make generates → Write textualizes → Parse parses back to binary → Time extracts the moment — four functions forming XID's read/write loop. (2) Parse's input view length is XID_TEXT_SIZE (no trailing zero): any length or character deviation fails whole, and xrtXidErrorOffset extracts the first illegal byte's position from the error — errors carry their own location, no error-message parsing needed. (3) The output timestamp varies with the run's moment, but the prefix-increasing order property never changes: the earlier-printed XID is lexicographically smaller than the later-printed one.

12.4契约

• Determinism: Hash32/64 and SipHash with the same input and key always give the same output, stable across platforms and versions (chunking does not affect it).
• Security boundary: keyless hashes resist no collision attack; external hash-map keys use SipHash with the key kept secret; password storage does not belong to this chapter (Volume 8's password hashing).
• Key discipline: the xsipkey is sensitive data — generated from secure randomness, xrtSecureZero when done.
• XID ordering: lexicographic order = generation-time order; Compare provides a stable total order; the single-comparison direction of rapidly consecutive generations is not a promise (the millisecond clock decides).
• Parsing strictness: Parse accepts only the fixed-length legal text; on failure nothing is written, and the error offset is readable from the thread error.
• Batch generation: MakeMany generates a contiguously stored batch at once, cutting syscall counts.

Common Mistakes

uint64 iKey = xrtHash64(Header.Value, Header.Size);  /* public function */
Bucket = TableFind(iKey);                             /* collisions craftable */

uint64 iKey = xrtSipHash(Header.Value, Header.Size, gTableKey);  /* key kept secret */
Bucket = TableFind(iKey);

char arrText[XID_TEXT_CAPACITY];
load(arrText);
if ( !xrtXidParse((xstrview){ arrText, XID_TEXT_CAPACITY }, &Value) ) {
	/* length 33: certain failure — the trailing zero is not part of the text */
}

char arrText[XID_TEXT_CAPACITY];
load(arrText);
if ( !xrtXidParse((xstrview){ arrText, XID_TEXT_SIZE }, &Value) ) {
	size_t iOffset = 0;
	xrtXidErrorOffset(xrtGetError(), &iOffset);   /* first illegal byte's position */
}

Programming Exercises

Summary