HRCC C — Hierarchical Radix-Chain Commitment

A production-oriented C17 library for deterministic ordering of fixed-width events and tamper-evident hierarchical commitments over the resulting ordered stream.

HRCC combines stable radix sorting by (key, sequence) with independent local SHA-256 hash chains and a short ordered boundary chain across immutable segments. The design preserves strict global ordering, detects changes, removals, and reordering relative to a trusted root, and avoids a record-by-record global chain dependency across segments.

The repository follows a professional C-library layout: a compact public API, strict CMake builds, deterministic regression tests, sanitizer profiles, a libFuzzer harness, a basic API example, a benchmark harness, raw CSV outputs, and rendered performance charts.

Repository layout

Path	Purpose
include/hrcc.h	Stable public API, types, configuration, and status codes
src/hrcc.c	Optimized core: radix sorting, chains, manifest construction, and verification
tests/	Deterministic regression and mutation tests
examples/	Minimal public API example
bench/	C benchmark, Parquet converter, and plot generators
fuzz/	Optional libFuzzer target for binary inputs
docs/	Architecture, build, and benchmark documentation
results/	Reproducible release results and charts

Data model

The hot path uses contiguous 24-byte records:

typedef struct hrcc_record {
    uint64_t key;
    uint64_t sequence;
    uint64_t payload;
} hrcc_record_t;

key is the primary order key and sequence is the stable deterministic tie-breaker. payload may represent an application identifier, an offset into a payload arena, or a digest of a larger payload. Integrations using variable-length payloads must include the payload bytes or a trusted payload digest in their canonical record commitment.

Commitment scheme

Each local chain starts from a zero digest. For a record r_i:

p[i+1] = H("hrcc/record/v1", p[i], canonical(key, sequence, payload))
local_root = H("hrcc/segment/v1", count, first_hash, last_hash)

After local chains are built in parallel, segments are linked in range order:

boundary[j] = H("hrcc/boundary/v1", boundary[j-1], first_key,
                last_key, count, local_root)
root = H("hrcc/root/v1", segment_count, boundary[last])

Every component is length-prefixed and domain-separated. SHA-256 is specified by the NIST Secure Hash Standard 1.

Quick start

HRCC requires CMake 3.20 or newer, a C17 compiler, OpenSSL Crypto development headers, and optionally OpenMP.

cmake -S . -B build -G Ninja -DCMAKE_BUILD_TYPE=Release \
  -DHRCC_ENABLE_NATIVE_OPTIMIZATION=ON \
  -DHRCC_ENABLE_LTO=ON
cmake --build build --parallel
ctest --test-dir build --output-on-failure
./build/hrcc_basic

Run memory and undefined-behavior checks:

cmake -S . -B build-sanitize -G Ninja \
  -DHRCC_ENABLE_SANITIZERS=ON \
  -DHRCC_ENABLE_NATIVE_OPTIMIZATION=OFF
cmake --build build-sanitize --parallel
ctest --test-dir build-sanitize --output-on-failure

CMake option	Default	Purpose
HRCC_BUILD_TESTS	ON	Build the CTest regression suite
HRCC_BUILD_EXAMPLES	ON	Build the basic API example
HRCC_BUILD_BENCH	ON	Build the benchmark harness
HRCC_BUILD_FUZZ	OFF	Build the libFuzzer target with Clang
HRCC_ENABLE_OPENMP	ON	Enable parallel local chains
HRCC_ENABLE_LTO	OFF	Enable LTO where supported
HRCC_ENABLE_NATIVE_OPTIMIZATION	OFF	Enable local -march=native -mtune=native flags
HRCC_ENABLE_SANITIZERS	OFF	Enable AddressSanitizer and UndefinedBehaviorSanitizer

HRCC_ENABLE_NATIVE_OPTIMIZATION=ON is intended for local benchmark builds. Do not enable it for portable binary packages intended for different CPUs.

API example

hrcc_config_t config;
hrcc_manifest_t manifest;
hrcc_config_init(&config);
hrcc_manifest_init(&manifest);

hrcc_status_t status = hrcc_build(records, scratch, count, &config, &manifest);
if (status == HRCC_OK) {
    status = hrcc_verify(records, count, &manifest);
}
hrcc_manifest_destroy(&manifest);

See examples/basic.c for a complete executable example.

Release benchmark

The primary benchmark uses 2,000,000 real NYC TLC Yellow Taxi records. Values are medians of five runs. Each HRCC build is followed by full verification; verification failure aborts the benchmark, while verification time is excluded from the build-path measurement. The fixture derives its key from pickup timestamp and PULocationID, and uses trip distance as payload. The official NYC TLC catalog documents the yellow-taxi fields and publishes the monthly Parquet files 2.

Method	Workers	Median, ms	Throughput, million records/s	Relative to qsort + chain
libc qsort	1	353.292	5.661	1.91×
radix_only	1	269.136	7.431	2.50×
qsort + sequential SHA-256 chain	1	673.140	2.971	1.00×
HRCC	1	647.848	3.087	1.04×
HRCC	3	408.905	4.891	1.65×

These results apply to the measured CPU, compiler, OpenSSL version, and workload. They demonstrate useful segment-level parallelism for the auditable build path; they are not a performance guarantee for other keys, payloads, machines, or hash backends. See docs/BUILDING.md for reproduction commands and docs/BENCHMARKS.md for raw CSV, worker/segment tuning sweeps, and a second chart.

Security boundary

HRCC provides integrity and ordering relative to a trusted root digest. It is not an authentication protocol or a digital signature. If an attacker can replace both the data and the root or manifest, the integration must sign the root, publish it in an append-only log, or bind it through another trusted mechanism.

This version does not provide a persistent manifest format, signatures, WAL/crash recovery, external-memory sorting, or O(log N) inclusion proofs. Integrations that require individual inclusion proofs should add an authenticated Merkle tree inside each local segment.

License

MIT; see LICENSE.

References